CSC/ECE 506 Spring 2014/9b vn - Revision history

Vperesa: /* Performance Comparison */

2014-04-24T01:01:39Z

Performance Comparison

← Older revision		Revision as of 01:01, 24 April 2014
Line 247:		Line 247:
	Traffic is the communications overhead required by the barrier. Ideally barrier traffic should be low, as excess traffic limits scalability.<sup><span id="1body">[[#1foot\|[1]]]</span></sup>		Traffic is the communications overhead required by the barrier. Ideally barrier traffic should be low, as excess traffic limits scalability.<sup><span id="1body">[[#1foot\|[1]]]</span></sup>

	=== Performance Comparison ===		== Performance Comparison ==

			The comparison of the performance of some of the barrier implementations have been tabulated below:

	{\| class="wikitable" border="1"		{\| class="wikitable" border="1"
	\|+Performance Comparison of Barrier Implementations<sup><span id="2body">[[#2foot\|[2]]]</span></sup>		\|+Performance Comparison of Barrier Implementations<sup><span id="2body">[[#2foot\|[2]]]</span></sup>

Vperesa: /* Performance Evaluation */

2014-04-24T01:00:17Z

Performance Evaluation

← Older revision		Revision as of 01:00, 24 April 2014
Line 239:		Line 239:
	== Performance Evaluation ==		== Performance Evaluation ==

	To evaluate lock performance, we can use these two criteria:		To evaluate lock performance, we can use these two criteria:<sup><span id="2body">[[#2foot\|[2]]]</span></sup>

	*Latency - The time required to enter and exit a barrier.
	*Traffic - Communications overhead required by the barrier.<sup><span id="2body">[[#2foot\|[2]]]</span></sup>

	=== Latency ===		=== Latency ===
			Latency can be defined as the time taken to enter and exit a barrier. Ideally the latency of a barrier should be small, but for barriers that do not scale well, latency can increase as the number of threads increases.<sup><span id="1body">[[#1foot\|[1]]]</span></sup>
	Ideally the latency of a barrier should be small, but for barriers that ~~don't~~ scale well latency can increase as the number of threads increases.<sup><span id="1body">[[#1foot\|[1]]]</span></sup>

	=== Traffic ===		=== Traffic ===
			Traffic is the communications overhead required by the barrier. Ideally barrier traffic should be low, as excess traffic limits scalability.<sup><span id="1body">[[#1foot\|[1]]]</span></sup>
	~~Low~~ traffic ~~is also good~~, as ~~we do not want~~ excess ~~buss~~ traffic ~~to prevent~~ scalability.<sup><span id="1body">[[#1foot\|[1]]]</span></sup>

	=== Performance Comparison ===		=== Performance Comparison ===

Njkarajg: /* Improving performance */

2014-04-24T00:58:48Z

Improving performance

← Older revision		Revision as of 00:58, 24 April 2014
Line 89:		Line 89:
	Performance of locking mechanisms can be improved in the following ways:		Performance of locking mechanisms can be improved in the following ways:

	*Optimizing software can improve the performance of locks. For instance, inserting a delay between a processor noticing a release and then trying to acquire a lock can reduce contention and bus traffic, and increase the performance of the locks. TCP-like back off algorithms can be used to adjust this delay depending on the number of threads contending for the lock.<sup><span>[[#3foot\|[3]]]</span></sup>		# Optimizing software can improve the performance of locks. For instance, inserting a delay between a processor noticing a release and then trying to acquire a lock can reduce contention and bus traffic, and increase the performance of the locks. TCP-like back off algorithms can be used to adjust this delay depending on the number of threads contending for the lock.<sup><span>[[#3foot\|[3]]]</span></sup>
			#The term "Spinning" or "Spinlock" refers to a processor waiting in a loop while trying to acquire the lock. One way to improve performance is to insert a delay between memory references so as to limit the bandwidth (traffic) each processor can use for spinning.<sup><span>[[#3foot\|[3]]]</span></sup>
	*The term "Spinning" or "Spinlock" refers to a processor waiting in a loop while trying to acquire the lock. One way to improve performance is to insert a delay between memory references so as to limit the bandwidth (traffic) each processor can use for spinning.<sup><span>[[#3foot\|[3]]]</span></sup>		#Additionally, fairness can be guaranteed by queuing the lock attempts in shared memory so that they happen in order.<sup><span>[[#3foot\|[3]]]</span></sup>

	*Additionally, fairness can be guaranteed by queuing the lock attempts in shared memory so that they happen in order.<sup><span>[[#3foot\|[3]]]</span></sup>

	=== Avoiding Locks ===		=== Avoiding Locks ===

Vperesa: /* Disseminating Barrier */

2014-04-24T00:56:55Z

Disseminating Barrier

← Older revision		Revision as of 00:56, 24 April 2014
Line 237:		Line 237:
	}		}

	Here, each thread executes the same code, choosing partners for the pairwise synchronizations 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).		Here, each thread executes the same code, choosing partners for the pairwise synchronizations 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).

	== Performance Evaluation ==		== Performance Evaluation ==

Vperesa: /* Disseminating Barrier */

2014-04-24T00:56:26Z

Disseminating Barrier

← Older revision		Revision as of 00:56, 24 April 2014
Line 222:		Line 222:
	== 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 log(n) 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.		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 log(n) 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>
Line 237:		Line 237:
	}		}

	Here, each thread executes the same code, choosing partners for the pairwise synchronizations as a function of its own identiﬁer and the internal		Here, each thread executes the same code, choosing partners for the pairwise synchronizations 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).
	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).

	== Performance Evaluation ==		== Performance Evaluation ==

Vperesa: /* Sense-Reversal Barrier */

2014-04-24T00:53:39Z

Sense-Reversal Barrier

← Older revision		Revision as of 00:53, 24 April 2014
Line 134:		Line 134:
	== Sense-Reversal Barrier ==		== 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.Since all the threads are spinning around a single variable the miss rate is scales quadratically with number of processors.		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 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>

Vperesa: /* Fuzzy Barrier */

2014-04-24T00:52:06Z

Fuzzy Barrier

← Older revision		Revision as of 00:52, 24 April 2014
Line 128:		Line 128:

	== Fuzzy Barrier ==		== Fuzzy Barrier ==
	Barriers can have a major performance impact because of two properties. Firstly, threads that have reached a barrier are forced to wait for other barriers and as a result are in an idling state. The thread is essentially performing no useful function in this state. Secondly, the execution of the barrier itself may be slow (if implemented in software), due to the fact that they may ~~be consisting~~ of several instructions that need to execute.		Barriers can have a major performance impact because of two properties. Firstly, threads that have reached a barrier are forced to wait for other barriers and as a result are in an idling state. The thread is essentially performing no useful function in this state. Secondly, the execution of the barrier itself may be slow (if implemented in software), due to the fact that they may consist of several instructions that need to execute.

	The fuzzy barrier aims to solve both of these issues. To increase the speed of the barrier implementation, fuzzy barriers are implemented in hardware. The other problem is to keep each thread as busy as possible for a majority of the time. This is done by extending the concept of a barrier to include a set of instructions that can be safely executed by the waiting/idling thread. By making this safe barrier region as large as possible we can ensure that almost none of the threads have to completely stall at any particular time. <sup><span id="14body">[[#14foot\|[14]]]</span></sup>		The fuzzy barrier aims to solve both of these issues. To increase the speed of the barrier implementation, fuzzy barriers are implemented in hardware. The other problem is to keep each thread as busy as possible for a majority of the time. This is done by extending the concept of a barrier to include a set of instructions that can be safely executed by the waiting/idling thread. By making this safe barrier region as large as possible we can ensure that almost none of the threads have to completely stall at any particular time. <sup><span id="14body">[[#14foot\|[14]]]</span></sup>

Vperesa: /* Barrier Implementations */

2014-04-24T00:51:21Z

Barrier Implementations

← Older revision		Revision as of 00:51, 24 April 2014
Line 125:		Line 125:
	= Barrier Implementations =		= Barrier Implementations =

	In many ways, barriers are simpler than locks. A barrier is simply a point in a program where one or more threads must reach before the parallel program is allowed to continue. When using barriers, a programmer does not have to be concerned with advanced topics such as fairness, that are required when programming for locks.		In many ways, barriers are simpler than locks. A barrier is simply a point in a program where one or more threads must reach before the parallel program is allowed to continue. When using barriers, a programmer does not have to be concerned with advanced topics such as fairness, that are required when programming for locks. Some of the popular barrier techniques are listed below

	== Fuzzy Barrier ==		== Fuzzy Barrier ==

Vperesa: /* Avoiding Locks */

2014-04-24T00:49:30Z

Avoiding Locks

← Older revision		Revision as of 00:49, 24 April 2014
Line 121:		Line 121:
	}		}
	}		}
	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. IN case the value is incorrect, the write fails.		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. In case the value is incorrect, the write fails.

	= Barrier Implementations =		= Barrier Implementations =

Vperesa: /* Avoiding Locks */

2014-04-24T00:49:05Z

Avoiding Locks

← Older revision		Revision as of 00:49, 24 April 2014
Line 96:		Line 96:

	=== Avoiding Locks ===		=== Avoiding Locks ===
	There are many reasons why a programmer should attempt to write programs in such a way as to avoid locks if possible~~. There~~ are many problems that can arise with the use of locks.<sup><span id="4body">[[#4foot\|[4]]]</span></sup>		There are many reasons why a programmer should attempt to write programs in such a way as to avoid locks if possible as there are many problems that can arise with the use of locks. Some of them are discussed below<sup><span id="4body">[[#4foot\|[4]]]</span></sup>

	One of the ~~must~~ well known issues is deadlock. This can occur when the threads are waiting to acquire the lock, but the lock ~~will~~ never be ~~unlocked~~. For example, there are two processes A and B and they need two methods (1 and 2) to be grabbed for completion of a task which are shared by both A and B. ~~This can create~~ a deadlock when A grabs 1 and B grabs 2. ~~This reaches~~ to ~~a situation where both A and B cannot~~ change their ~~states~~. The solution to this problem is to set a condition where in A ~~process~~ can lock method 2 only if t has locked method 1.		One of the most well known issues is deadlock. This can occur when the threads are waiting to acquire the lock, but the lock would never be released. For example, there are two processes A and B and they need two methods (1 and 2) to be grabbed for completion of a task which are shared by both A and B. There is a potential deadlock situation when A grabs 1 and B grabs 2. Since both processes need one other method to reach completion, neither of them change their state. The solution to this problem is to set a condition where in process A can lock method 2 only if it has locked method 1.

	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, since a lock is often 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>:		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>:
Line 121:		Line 121:
	}		}
	}		}
	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		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. IN case the value is incorrect, the write fails.

	= Barrier Implementations =		= Barrier Implementations =