CSC/ECE 506 Spring 2010/ch 9 - Revision history

Admin: /* Performance Comparison */

2010-05-04T21:38:50Z

Performance Comparison

← Older revision		Revision as of 21:38, 4 May 2010
Line 86:		Line 86:
	== Performance Comparison ==		== Performance Comparison ==

	Additive Schwarz Preconditioned Conjugate Gradient (ASPCG) ~~kernal~~ on Altix System		Additive Schwarz Preconditioned Conjugate Gradient (ASPCG) kernel on Altix System

	[[Image:Ch9wiki05.png]]		[[Image:Ch9wiki05.png]]
Line 97:		Line 97:

	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. [http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf]		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. [http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf]



	= References =		= References =

Admin: /* Tournament Barrier */

2010-05-04T19:10:22Z

Tournament Barrier

← Older revision		Revision as of 19:10, 4 May 2010
Line 72:		Line 72:
	== Tournament Barrier ==		== Tournament Barrier ==

	In tournament barrier the threads are considered to be leaves at the end of a binary tree and each node represents a flag. Two threads compete with each other and the ~~looser~~ thread is allowed to set the flag and move to higher level and compete to ~~loose~~ with the ~~looser~~ thread from other section of binary tree. Thus the thread which completes last is able to set the highest flag in the binary tree. On setting the flag it indicates to all the threads that barrier has been completed and thus synchronization is achieved.		In tournament barrier the threads are considered to be leaves at the end of a binary tree and each node represents a flag. Two threads compete with each other and the loser thread is allowed to set the flag and move to higher level and compete to lose with the loser thread from other section of binary tree. Thus the thread which completes last is able to set the highest flag in the binary tree. On setting the flag it indicates to all the threads that barrier has been completed and thus synchronization is achieved.

	[[Image:Ch9wiki03.png]]		[[Image:Ch9wiki03.png]]

Pwlane at 23:02, 28 April 2010

2010-04-28T23:02:27Z

← Older revision		Revision as of 23:02, 28 April 2010
Line 39:		Line 39:

	= Barrier Implementations =		= Barrier Implementations =

			In many ways, barriers are simpler than locks. A barrier simply is 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.

			== Performance Evaluation ==

			The Solihin text gives 2 metrics for which the performance of a barrier implementation should be evaluated.

			*Latency - The time required to enter and exit a barrier.

			*Traffic - Communications overhead required by the barrier.

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

Pwlane at 22:57, 28 April 2010

2010-04-28T22:57:19Z

← Older revision		Revision as of 22:57, 28 April 2010
Line 5:		Line 5:
	Locks are an important concept when programming for multi core systems. The basic concept of a lock is to protect the code inside the lock. That is to be sure that while a certain thread X has entered the critical section, another thread Y is not also inside of the critical section and possibly modifying critical values. When a lock is being used, while thread X has entered into the critical section, thread Y must wait until X has exited before entering. This can be accomplished in a variety of ways of varying complexity and performance.		Locks are an important concept when programming for multi core systems. The basic concept of a lock is to protect the code inside the lock. That is to be sure that while a certain thread X has entered the critical section, another thread Y is not also inside of the critical section and possibly modifying critical values. When a lock is being used, while thread X has entered into the critical section, thread Y must wait until X has exited before entering. This can be accomplished in a variety of ways of varying complexity and performance.

	== Performance Evaluation		== Performance Evaluation ==

	The Solihin text gives 4 methods to determine the performance of a lock implementation.		The Solihin text gives 4 methods to determine the performance of a lock implementation.

Pwlane at 21:49, 26 April 2010

2010-04-26T21:49:33Z

@@ Line 5: / Line 5: @@
 Locks are an important concept when programming for multi core systems.  The basic concept of a lock is to protect the code inside the lock.  That is to be sure that while a certain thread X has entered the critical section, another thread Y is not also inside of the critical section and possibly modifying critical values.  When a lock is being used, while thread X has entered into the critical section, thread Y must wait until X has exited before entering.  This can be accomplished in a variety of ways of varying complexity and performance.
-== Performance Evaluation ==
+== Performance Evaluation
 The Solihin text gives 4 methods to determine the performance of a lock implementation.
@@ Line 28: / Line 28: @@
 == Hand-off Lock ==
-Another type of lock that is not discussed in the text is known as the "Hand-off" lock.  In this lock the first thread acquires the lock if no other thread is currently locked (since it is the first thread).  When another thread attempts to gain the lock it will see that the lock is in use and adds itself to the queue.  Once done this thread can sleep until called by the thread with the lock.  Once the thread in the lock is finished, it will pass the lock to the next thread in the queue.  [http://www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]
+Another type of lock that is not discussed in the text is known as the "Hand-off" lock.  In this lock the first thread acquires the lock if no other thread is currently locked (since it is the first thread).  When another thread attempts to gain the lock it will see that the lock is in use and adds itself to the queue.  Once done this thread can sleep until called by the thread with the lock.  Once the thread in the lock is finished, it will pass the lock to the next thread in the queue.  [www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]
 == Avoiding Locks ==
@@ Line 40: / Line 40: @@
 = Barrier Implementations =
-Partners Work Not Received
+== Sense-Reversal Barrier ==
@@ Line 48: / Line 95: @@
 * CMPXCHG - Compare and Exchange [http://faydoc.tripod.com/cpu/cmpxchg.htm]
 * Lock (computer science) [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]
-* www.cs.duke.edu/~chase/cps110/slides/threads3.ppt  [http://www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]
+* www.cs.duke.edu/~chase/cps110/slides/threads3.ppt  [www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]
 * Deadlock [http://www.statemaster.com/encyclopedia/Deadlock]

Pwlane at 18:25, 26 April 2010

2010-04-26T18:25:10Z

← Older revision		Revision as of 18:25, 26 April 2010
Line 28:		Line 28:
	== Hand-off Lock ==		== Hand-off Lock ==

	Another type of lock that is not discussed in the text is known as the "Hand-off" lock. In this lock the first thread acquires the lock if no other thread is currently locked (since it is the first thread). When another thread attempts to gain the lock it will see that the lock is in use and adds itself to the queue. Once done this thread can sleep until called by the thread with the lock. Once the thread in the lock is finished, it will pass the lock to the next thread in the queue. [www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]		Another type of lock that is not discussed in the text is known as the "Hand-off" lock. In this lock the first thread acquires the lock if no other thread is currently locked (since it is the first thread). When another thread attempts to gain the lock it will see that the lock is in use and adds itself to the queue. Once done this thread can sleep until called by the thread with the lock. Once the thread in the lock is finished, it will pass the lock to the next thread in the queue. [http://www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]

	== Avoiding Locks ==		== Avoiding Locks ==
Line 48:		Line 48:
	* CMPXCHG - Compare and Exchange [http://faydoc.tripod.com/cpu/cmpxchg.htm]		* CMPXCHG - Compare and Exchange [http://faydoc.tripod.com/cpu/cmpxchg.htm]
	* Lock (computer science) [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]		* Lock (computer science) [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]
	* www.cs.duke.edu/~chase/cps110/slides/threads3.ppt [www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]		* www.cs.duke.edu/~chase/cps110/slides/threads3.ppt [http://www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]
	* Deadlock [http://www.statemaster.com/encyclopedia/Deadlock]		* Deadlock [http://www.statemaster.com/encyclopedia/Deadlock]

Pwlane at 18:24, 26 April 2010

2010-04-26T18:24:31Z

← Older revision		Revision as of 18:24, 26 April 2010
Line 5:		Line 5:
	Locks are an important concept when programming for multi core systems. The basic concept of a lock is to protect the code inside the lock. That is to be sure that while a certain thread X has entered the critical section, another thread Y is not also inside of the critical section and possibly modifying critical values. When a lock is being used, while thread X has entered into the critical section, thread Y must wait until X has exited before entering. This can be accomplished in a variety of ways of varying complexity and performance.		Locks are an important concept when programming for multi core systems. The basic concept of a lock is to protect the code inside the lock. That is to be sure that while a certain thread X has entered the critical section, another thread Y is not also inside of the critical section and possibly modifying critical values. When a lock is being used, while thread X has entered into the critical section, thread Y must wait until X has exited before entering. This can be accomplished in a variety of ways of varying complexity and performance.

	== Performance Evaluation		== Performance Evaluation ==

	The Solihin text gives 4 methods to determine the performance of a lock implementation.		The Solihin text gives 4 methods to determine the performance of a lock implementation.

Pwlane at 18:24, 26 April 2010

2010-04-26T18:24:15Z

New page

In addition to a proper cache coherency model, it is also important for a multiprocessor system to provide support at the hardware level for synchronization. The most common types of synchronization are locks and barriers, which are discussed in this chapter.

= Lock Implementations =

Locks are an important concept when programming for multi core systems. The basic concept of a lock is to protect the code inside the lock. That is to be sure that while a certain thread X has entered the critical section, another thread Y is not also inside of the critical section and possibly modifying critical values. When a lock is being used, while thread X has entered into the critical section, thread Y must wait until X has exited before entering. This can be accomplished in a variety of ways of varying complexity and performance.

== Performance Evaluation

The Solihin text gives 4 methods to determine the performance of a lock implementation.

*Acquisition Latency - How much time does it take to acquire the lock?

*Traffic - How much bus traffic is generated by threads attempting to acquire the lock?

*Fairness - FIFO vs. Luck

*Storage - How much storage is needed compared to the number of threads?

== Atomic Instructions ==

Since a multiprocessor system cannot disable interupts as an effective method to execute a bit of code atomically, there must be hardware support for atomic operations. [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]

Being able to execute an atomic instruction is a requirement for most lock implementations. It is important that when a processor attempts to set a lock either the lock is fully set and the thread is able to enter into the critical section, or the lock is not set, and it appears that none of the instructions required to set the lock have executed.

In the x86 instruction set the opcode CMPXCHG (meaning compare and exchange) can be used in a lock implementation in order to guarantee atomicity. This function works by sending a destination and a source. The accumulator is compared to the destination and if they are equal loaded with the source. If they are NOT equal the accumulator is loaded with the destination value. In order to assure that this is executed atomically the opcode must be issued with the LOCK prefix. This is useful in implementing some locks, such as ticket locks. [http://faydoc.tripod.com/cpu/cmpxchg.htm]

== Hand-off Lock ==

Another type of lock that is not discussed in the text is known as the "Hand-off" lock. In this lock the first thread acquires the lock if no other thread is currently locked (since it is the first thread). When another thread attempts to gain the lock it will see that the lock is in use and adds itself to the queue. Once done this thread can sleep until called by the thread with the lock. Once the thread in the lock is finished, it will pass the lock to the next thread in the queue. [www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]

== 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. [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]

One of the must well known issue is deadlock. This can occur when the threads are waiting to acquire the lock, but the lock will never be unlocked. For example if 2 threads are both spinning on a lock that is locked, they will continue to spin forever, as each thread 'thinks' that the other is inside the critical section.

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. Lock (computer science) [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]

= Barrier Implementations =

Partners Work Not Received

= References =

* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.
* CMPXCHG - Compare and Exchange [http://faydoc.tripod.com/cpu/cmpxchg.htm]
* Lock (computer science) [http://www.statemaster.com/encyclopedia/Lock-(computer-science)]
* www.cs.duke.edu/~chase/cps110/slides/threads3.ppt [www.cs.duke.edu/~chase/cps110/slides/threads3.ppt]
* Deadlock [http://www.statemaster.com/encyclopedia/Deadlock]