CSC/ECE 506 Spring 2013/9b sc - Revision history

Schakra8: /* Combining Tree Barrier */

2013-04-04T00:14:22Z

Combining Tree Barrier

@@ Line 204: / Line 204: @@
 Since in this case all the threads are updated local variables in form of smaller groups the miss rate is not as high as sense-reversal barrier.
 The diagram below shows the operation of combining tree barrier with threads grouped in two groups. The variables C0 and C1 are local to each group and C2 is the variable that is at higher level of hierarchy in the tree.
 [[Image:Ch9wiki02.png]]<sup><span id="8body">[[#8foot|[8]]]</span></sup>
 == Tournament Barrier ==

Schakra8: /* Tournament Barrier */

2013-04-04T00:08:36Z

Tournament Barrier

← Older revision		Revision as of 00:08, 4 April 2013
Line 214:		Line 214:

	[[Image:Ch9wiki03.png]]<sup><span id="8body">[[#8foot\|[8]]]</span></sup>		[[Image:Ch9wiki03.png]]<sup><span id="8body">[[#8foot\|[8]]]</span></sup>

			An example of tournament barrier is given as follows:

			void await(boolean mySense) {
			if (top) {
			return;
			} else if (parent != null) {
			while (flag != mySense) {};
			parent.await(mySense);
			partner.flag = mySense;
			} else {
			partner.flag = mySense;
			while (flag != mySense) {};
			}}}
			Here, the parent variable stores the value i.e. null if not a winner else a winner, and then waits for a partner (represented by flag) and then performs synchronization. Otherwise a natural loser is chosen and partnered with current thread.

	== Disseminating Barrier ==		== Disseminating Barrier ==

Schakra8: /* Disseminating Barrier */

2013-04-03T23:59:01Z

Disseminating Barrier

← Older revision		Revision as of 23:59, 3 April 2013
Line 217:		Line 217:
	== Disseminating Barrier ==		== Disseminating Barrier ==

	In this barrier each thread maintains a record of the activity of other threads. For every round i with n threads, thread A notifies thread (A + 2i) mod n. Thus after logn rounds all the threads are aware of the status of every other thread running and whether it has reached the barrier.		In this barrier each thread maintains a record of the activity of other threads. For every round i with n threads, thread A notifies thread (A + 2i) mod n. Thus after logn rounds all the threads are aware of the status of every other thread running and whether it has reached the barrier. Overall synchronization is achieved by implication from a carefully chosen sequence of pairwise synchronizations.

	[[Image:Ch9wiki04.png]]<sup><span id="9body">[[#9foot\|[9]]]</span></sup>		[[Image:Ch9wiki04.png]]<sup><span id="9body">[[#9foot\|[9]]]</span></sup>

			An example of this type of barrier can be found below:

			for [s = 0 to stages-1] { ## there will be ceiling(log_2 p) stages
			work out who my out-going partner is at stage s;
			<await (arrive[partner][s] == 0);>
			arrive[partner][s] = 1;
			<await (arrive[myid][s] == 1);>
			arrive[myid][s] = 0;
			}
			Here, each thread xecutes the same code, choosing partners for the pairwise synchs as a function of its own identiﬁer and the internal
			iteration.Our own arrive ﬂag is now set by an “in-coming” partner, who is distinct from our “out-going” partner (except when p=2).

	= References =		= References =

Schakra8: /* References */

2013-04-03T23:56:07Z

References

← Older revision		Revision as of 23:56, 3 April 2013
Line 234:		Line 234:
	<span id="11foot">[[#11body\|11.]]</span>http://www.cs.duke.edu/courses/fall09/cps110/handouts/threads3.pdf<br>		<span id="11foot">[[#11body\|11.]]</span>http://www.cs.duke.edu/courses/fall09/cps110/handouts/threads3.pdf<br>
	<span id="12foot">[[#12body\|12.]]</span>http://preshing.com/20120612/an-introduction-to-lock-free-programming<br>		<span id="12foot">[[#12body\|12.]]</span>http://preshing.com/20120612/an-introduction-to-lock-free-programming<br>
			<span id="13foot">[[#13body\|13.]]</span>http://my.safaribooksonline.com/book/software-engineering-and-development/9780123705914/barriers/ch17lev1sec3#X2ludGVybmFsX0h0bWxWaWV3P3htbGlkPTk3ODAxMjM3MDU5MTQlMkZjaDE3bGV2MXNlYzMmcXVlcnk9<br>

Schakra8: /* Sense-Reversal Barrier */

2013-04-03T23:55:26Z

Sense-Reversal Barrier

@@ Line 169: / Line 169: @@
 == Sense-Reversal Barrier ==
-This barrier is a centralized barrier where a single count variable protected by a lock is shared among all the threads. Each thread on reaching the barrier increments its value and waits till the value of variable has reached the number of threads for which barrier was implemented.
+This barrier is a centralized barrier where a single count variable protected by a lock is shared among all the threads. Each thread on reaching the barrier increments its value and waits till the value of variable has reached the number of threads for which barrier was implemented.Since all the threads are spinning around a single variable the miss rate is scales quadratically with number of processors.
-Since all the threads are spinning around a single variable the miss rate is scales quadratically with number of processors.
+[[Image:Ch9wiki01.png]]<sup><span id="8body">[[#8foot|[8]]]</span></sup>
-[[Image:Ch9wiki01.png]]<sup><span id="8body">[[#8foot|[8]]]</span></sup>
+A sense-reversing barrier is a more elegant and practical solution to the problem of reusing barriers. A phase’s sense is a Boolean value: true for even-numbered phases and false otherwise. Each SenseBarrier object has a Boolean sense field indicating the sense of the currently executing phase. Each thread keeps its current sense as a thread-local object. Initially the barrier’s sense is the complement of the local sense of all the threads. When a thread calls await(), it checks whether it is the last thread to decrement the counter. If so, it reverses the barrier’s sense and continues. Otherwise, it spins waiting for the balancer’s sense field to change to match its own local sense.<sup><span id="13body">[[#13foot|[13]]]</span></sup>
 == Combining Tree Barrier ==

Schakra8: /* Performance Comparison */

2013-04-03T23:35:16Z

Performance Comparison

← Older revision		Revision as of 23:35, 3 April 2013
Line 166:		Line 166:
	\| moved to a separate network		\| moved to a separate network
	\|}		\|}



	[[Image:Ch9wiki05.png\|frame\|none\|Additive Schwarz Preconditioned Conjugate Gradient (ASPCG) kernel on Altix System - This figure shows the timings of the ASPCG kernel using the different barrier implementations. It can be seen that the blocking barrier does not scale with number of threads as with increase in number of threads the contention increases.<sup><span id="7body">[[#7foot\|[7]]]</span></sup>]]



	[[Image:Ch9wiki06.png\|frame\|none\|EPCC Microbenchmark - This figure shows the timings to implement a barrier of the EPCC Microbenchmark using the different barrier implementations. It can be seen that the blocking barrier/centralized blocking barrier does not scale with number of threads as with increase in number of threads the contention increases.<sup><span id="7body">[[#7foot\|[7]]]</span></sup>]]

	== Sense-Reversal Barrier ==		== Sense-Reversal Barrier ==

Schakra8 at 23:32, 3 April 2013

2013-04-03T23:32:09Z

← Older revision		Revision as of 23:32, 3 April 2013
Line 1:		Line 1:
			= Instruction and Previous Work =
			Changes are made as per the instructions given in https://docs.google.com/a/ncsu.edu/document/d/18ap34rWJImZjMAtGbANK9lZMon4NgwqDb5UY9Z8ksLM/edit

			Previous Version can be found here: http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_506_Spring_2011/ch9_ms

	= Synchronization =		= Synchronization =
	In addition to a proper cache coherency model, it is important for a multiprocessor system to provide support for synchronization. This must be provided at the hardware level, and can also be implemented to some degree in software. The most common types of hardware synchronization are locks and barriers, which are discussed in this chapter.		In addition to a proper cache coherency model, it is important for a multiprocessor system to provide support for synchronization. This must be provided at the hardware level, and can also be implemented to some degree in software. The most common types of hardware synchronization are locks and barriers, which are discussed in this chapter.

Schakra8: /* Avoiding Locks */

2013-04-03T23:26:31Z

Avoiding Locks

← Older revision		Revision as of 23:26, 3 April 2013
Line 118:		Line 118:
	}		}
	}		}
			The above code basically follows the Read-Write-Update order and makes sure that each thread has its local copy to work on and gets it updated sequentially so that the next thread has the correct value. If the value is not correct, write fails

	= Barrier Implementations =		= Barrier Implementations =

Schakra8: /* References */

2013-04-03T23:23:51Z

References

← Older revision		Revision as of 23:23, 3 April 2013
Line 211:		Line 211:
	<span id="10foot">[[#10body\|10.]]</span>http://heather.cs.ucdavis.edu/~matloff/50/PLN/lock.pdf<br>		<span id="10foot">[[#10body\|10.]]</span>http://heather.cs.ucdavis.edu/~matloff/50/PLN/lock.pdf<br>
	<span id="11foot">[[#11body\|11.]]</span>http://www.cs.duke.edu/courses/fall09/cps110/handouts/threads3.pdf<br>		<span id="11foot">[[#11body\|11.]]</span>http://www.cs.duke.edu/courses/fall09/cps110/handouts/threads3.pdf<br>
			<span id="12foot">[[#12body\|12.]]</span>http://preshing.com/20120612/an-introduction-to-lock-free-programming<br>

Schakra8: /* Avoiding Locks */

2013-04-03T23:23:01Z

Avoiding Locks

← Older revision		Revision as of 23:23, 3 April 2013
Line 98:		Line 98:

	Another problem with using locks is that the performance is not optimal, as often a lock is used when there is only a chance of conflict. This approach to programming yields slower performance than what might be possible with other methods. This also leads to questions of granularity, that is how much of the code should be protected under the critical section. The programmer must decide between many small (fine grain) locks or fewer, more encompassing locks. This decision can greatly effect the performance of the program.<sup><span id="4body">[[#4foot\|[4]]]</span></sup>		Another problem with using locks is that the performance is not optimal, as often a lock is used when there is only a chance of conflict. This approach to programming yields slower performance than what might be possible with other methods. This also leads to questions of granularity, that is how much of the code should be protected under the critical section. The programmer must decide between many small (fine grain) locks or fewer, more encompassing locks. This decision can greatly effect the performance of the program.<sup><span id="4body">[[#4foot\|[4]]]</span></sup>

			To avoid locks, lock free programming techniques like compare and swap and sequential consistency can be followed. This pattern typically involves copying a shared variable to a local variable, performing some speculative work, and attempting to publish the changes using CAS<sup><span id="12body">[[#12foot\|[12]]]</span></sup>:

			void LockFreeQueue::push(Node* newHead)
			{
			for (;;)
			{
			// Copy a shared variable (m_Head) to a local.
			Node* oldHead = m_Head;

			// Do some speculative work, not yet visible to other threads.
			newHead->next = oldHead;

			// Next, attempt to publish our changes to the shared variable.
			// If the shared variable hasn't changed, the CAS succeeds and we return.
			// Otherwise, repeat.
			if (_InterlockedCompareExchange(&m_Head, newHead, oldHead) == oldHead)
			return;
			}
			}

	= Barrier Implementations =		= Barrier Implementations =

← Older revision		Revision as of 23:56, 3 April 2013
Line 234:		Line 234:
	<span id="11foot">[[#11body\|11.]]</span>http://www.cs.duke.edu/courses/fall09/cps110/handouts/threads3.pdf<br>		<span id="11foot">[[#11body\|11.]]</span>http://www.cs.duke.edu/courses/fall09/cps110/handouts/threads3.pdf<br>
	<span id="12foot">[[#12body\|12.]]</span>http://preshing.com/20120612/an-introduction-to-lock-free-programming<br>		<span id="12foot">[[#12body\|12.]]</span>http://preshing.com/20120612/an-introduction-to-lock-free-programming<br>
			<span id="13foot">[[#13body\|13.]]</span>http://my.safaribooksonline.com/book/software-engineering-and-development/9780123705914/barriers/ch17lev1sec3#X2ludGVybmFsX0h0bWxWaWV3P3htbGlkPTk3ODAxMjM3MDU5MTQlMkZjaDE3bGV2MXNlYzMmcXVlcnk9<br>

← Older revision		Revision as of 23:23, 3 April 2013
Line 211:		Line 211:
	<span id="10foot">[[#10body\|10.]]</span>http://heather.cs.ucdavis.edu/~matloff/50/PLN/lock.pdf<br>		<span id="10foot">[[#10body\|10.]]</span>http://heather.cs.ucdavis.edu/~matloff/50/PLN/lock.pdf<br>
	<span id="11foot">[[#11body\|11.]]</span>http://www.cs.duke.edu/courses/fall09/cps110/handouts/threads3.pdf<br>		<span id="11foot">[[#11body\|11.]]</span>http://www.cs.duke.edu/courses/fall09/cps110/handouts/threads3.pdf<br>
			<span id="12foot">[[#12body\|12.]]</span>http://preshing.com/20120612/an-introduction-to-lock-free-programming<br>