CSC/ECE 506 Spring 2011/ch9 ms - Revision history

Admin: /* Avoiding Locks */

2011-05-02T03:53:32Z

Avoiding Locks

← Older revision		Revision as of 03:53, 2 May 2011
Line 61:		Line 61:
	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. There are many problems that can arise with the use of locks.<sup><span id="4body">[[#4foot\|[4]]]</span></sup>

	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.		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 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.<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>

Mdsakalu: /* References */

2011-04-25T02:11:18Z

References

← Older revision		Revision as of 02:11, 25 April 2011
Line 151:		Line 151:
	<span id="4foot">[[#4body\|4.]]</span> http://www.statemaster.com/encyclopedia/Lock-(computer-science)<br>		<span id="4foot">[[#4body\|4.]]</span> http://www.statemaster.com/encyclopedia/Lock-(computer-science)<br>
	<span id="5foot">[[#5body\|5.]]</span> http://faydoc.tripod.com/cpu/cmpxchg.htm<br>		<span id="5foot">[[#5body\|5.]]</span> http://faydoc.tripod.com/cpu/cmpxchg.htm<br>
	<span id="6foot">[[#6body\|6.]]</span> http://www.cs.duke.edu/~~~chase~~/cps110/slides/threads3.ppt<br>		<span id="6foot">[[#6body\|6.]]</span> http://www.cs.duke.edu/courses/fall09/cps110/slides/threads3.ppt<br>
	<span id="7foot">[[#7body\|7.]]</span> Scalability evaluation of barrier algorithms for OpenMP. http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf<br>		<span id="7foot">[[#7body\|7.]]</span> Scalability evaluation of barrier algorithms for OpenMP. http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf<br>
	<span id="8foot">[[#8body\|8.]]</span> Carwyn Ball and Mark Bull. Barrier Synchronization in Java. http://www.ukhec.ac.uk/publications/reports/synch_java.pdf<br>		<span id="8foot">[[#8body\|8.]]</span> Carwyn Ball and Mark Bull. Barrier Synchronization in Java. http://www.ukhec.ac.uk/publications/reports/synch_java.pdf<br>
	<span id="9foot">[[#9body\|9.]]</span> http://www.cs.brown.edu/courses/cs176/barrier.ppt<br>		<span id="9foot">[[#9body\|9.]]</span> http://www.cs.brown.edu/courses/cs176/barrier.ppt<br>

Mdsakalu: /* Improving performance */

2011-04-04T16:58:45Z

Improving performance

← Older revision		Revision as of 16:58, 4 April 2011
Line 39:		Line 39:

	=== Improving performance ===		=== Improving performance ===
	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.[[#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>

	Another 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.[[#3foot\|[3]]]</span></sup>]]		Another 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>

	One way to guarantee fairness is to queue lock attempts in shared memory so that they happen in order.[[#3foot\|[3]]]</span></sup>]]		One way to guarantee fairness is to queue lock attempts in shared memory so that they happen in order.<sup><span>[[#3foot\|[3]]]</span></sup>

	== Atomic Instructions ==		== Atomic Instructions ==

Mdsakalu at 16:57, 4 April 2011

2011-04-04T16:57:58Z

← Older revision		Revision as of 16:57, 4 April 2011
Line 37:		Line 37:

	[[Image:lockperf.png\|frame\|none\|Performance comparison of test&set and test-and-test&set (spin on read)<sup><span id="3body">[[#3foot\|[3]]]</span></sup>]]		[[Image:lockperf.png\|frame\|none\|Performance comparison of test&set and test-and-test&set (spin on read)<sup><span id="3body">[[#3foot\|[3]]]</span></sup>]]

			=== Improving performance ===
			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.[[#3foot\|[3]]]</span></sup>]]

			Another 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.[[#3foot\|[3]]]</span></sup>]]

			One way to guarantee fairness is to queue lock attempts in shared memory so that they happen in order.[[#3foot\|[3]]]</span></sup>]]

	== Atomic Instructions ==		== Atomic Instructions ==

Mdsakalu: /* References */

2011-04-02T04:48:07Z

References

← Older revision		Revision as of 04:48, 2 April 2011
Line 139:		Line 139:

	= References =		= References =
	<span id="1foot">[[#1body\|1.]]</span>David Culler, J.P. Singh and Anoop Gupta. Parallel Computer Architecture: A Hardware/Software Approach. Morgan Kaufmann. August 1998.<br>		<span id="1foot">[[#1body\|1.]]</span> David Culler, J.P. Singh and Anoop Gupta. Parallel Computer Architecture: A Hardware/Software Approach. Morgan Kaufmann. August 1998.<br>
	<span id="2foot">[[#2body\|2.]]</span>Yan Solihin. Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems. Solihin Books. August 2009.<br>		<span id="2foot">[[#2body\|2.]]</span> Yan Solihin. Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems. Solihin Books. August 2009.<br>
	<span id="3foot">[[#3body\|3.]]</span>Thomas E. Anderson. The Performance of Spin Lock Alternatives for Shared-memory Multiprocessors. http://www.cc.gatech.edu/classes/AY2010/cs4210_fall/papers/anderson-spinlock.pdf<br>		<span id="3foot">[[#3body\|3.]]</span> Thomas E. Anderson. The Performance of Spin Lock Alternatives for Shared-memory Multiprocessors. http://www.cc.gatech.edu/classes/AY2010/cs4210_fall/papers/anderson-spinlock.pdf<br>
	<span id="4foot">[[#4body\|4.]]</span>http://www.statemaster.com/encyclopedia/Lock-(computer-science)<br>		<span id="4foot">[[#4body\|4.]]</span> http://www.statemaster.com/encyclopedia/Lock-(computer-science)<br>
	<span id="5foot">[[#5body\|5.]]</span>http://faydoc.tripod.com/cpu/cmpxchg.htm<br>		<span id="5foot">[[#5body\|5.]]</span> http://faydoc.tripod.com/cpu/cmpxchg.htm<br>
	<span id="6foot">[[#6body\|6.]]</span>www.cs.duke.edu/~chase/cps110/slides/threads3.ppt<br>		<span id="6foot">[[#6body\|6.]]</span> http://www.cs.duke.edu/~chase/cps110/slides/threads3.ppt<br>
	<span id="7foot">[[#7body\|7.]]</span>Scalability evaluation of barrier algorithms for OpenMP. http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf<br>		<span id="7foot">[[#7body\|7.]]</span> Scalability evaluation of barrier algorithms for OpenMP. http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf<br>
	<span id="8foot">[[#8body\|8.]]</span>Carwyn Ball and Mark Bull. Barrier Synchronization in Java. http://www.ukhec.ac.uk/publications/reports/synch_java.pdf<br>		<span id="8foot">[[#8body\|8.]]</span> Carwyn Ball and Mark Bull. Barrier Synchronization in Java. http://www.ukhec.ac.uk/publications/reports/synch_java.pdf<br>
	<span id="9foot">[[#9body\|9.]]</span>http://www.cs.brown.edu/courses/cs176/barrier.ppt<br>		<span id="9foot">[[#9body\|9.]]</span> http://www.cs.brown.edu/courses/cs176/barrier.ppt<br>

Mdsakalu: /* References */

2011-04-02T04:47:14Z

References

← Older revision		Revision as of 04:47, 2 April 2011
Line 148:		Line 148:
	<span id="8foot">[[#8body\|8.]]</span>Carwyn Ball and Mark Bull. Barrier Synchronization in Java. http://www.ukhec.ac.uk/publications/reports/synch_java.pdf<br>		<span id="8foot">[[#8body\|8.]]</span>Carwyn Ball and Mark Bull. Barrier Synchronization in Java. http://www.ukhec.ac.uk/publications/reports/synch_java.pdf<br>
	<span id="9foot">[[#9body\|9.]]</span>http://www.cs.brown.edu/courses/cs176/barrier.ppt<br>		<span id="9foot">[[#9body\|9.]]</span>http://www.cs.brown.edu/courses/cs176/barrier.ppt<br>
	~~<span id="10foot">[[#10body\|10.]]</span>~~
	~~<span id="11foot">[[#11body\|11.]]</span>~~
	~~<span id="12foot">[[#12body\|12.]]</span>~~


	* Deadlock [http://www.statemaster.com/encyclopedia/Deadlock]

Mdsakalu at 04:46, 2 April 2011

2011-04-02T04:46:43Z

Show changes

Mdsakalu: /* References */

2011-04-02T04:33:05Z

References

← Older revision		Revision as of 04:33, 2 April 2011
Line 147:		Line 147:

	= References =		= References =
	<span id="1foot">[[#1body\|1.]]</span>David Culler, J.P. Singh and Anoop Gupta, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann, August 1998.<br>		<span id="1foot">[[#1body\|1.]]</span>David Culler, J.P. Singh and Anoop Gupta. Parallel Computer Architecture: A Hardware/Software Approach. Morgan Kaufmann. August 1998.<br>
	<span id="2foot">[[#2body\|2.]]</span>Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.<br>		<span id="2foot">[[#2body\|2.]]</span>Yan Solihin. Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems. Solihin Books. August 2009.<br>
	<span id="3foot">[[#3body\|3.]]</span>		<span id="3foot">[[#3body\|3.]]</span>Thomas E. Anderson. The Performance of Spin Lock Alternatives for Shared-memory Multiprocessors. http://www.cc.gatech.edu/classes/AY2010/cs4210_fall/papers/anderson-spinlock.pdf<br>
	<span id="4foot">[[#4body\|4.]]</span>		<span id="4foot">[[#4body\|4.]]</span>
	<span id="5foot">[[#5body\|5.]]</span>		<span id="5foot">[[#5body\|5.]]</span>

Mdsakalu: /* References */

2011-04-02T04:30:14Z

References

← Older revision		Revision as of 04:30, 2 April 2011
Line 147:		Line 147:

	= References =		= References =
			<span id="1foot">[[#1body\|1.]]</span>David Culler, J.P. Singh and Anoop Gupta, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann, August 1998.<br>
	* Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.		<span id="2foot">[[#2body\|2.]]</span>Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.<br>
			<span id="3foot">[[#3body\|3.]]</span>
			<span id="4foot">[[#4body\|4.]]</span>
			<span id="5foot">[[#5body\|5.]]</span>
			<span id="6foot">[[#6body\|6.]]</span>
			*
	* 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)]

Mdsakalu: /* Performance Comparison */

2011-04-02T04:25:04Z

Performance Comparison

← Older revision		Revision as of 04:25, 2 April 2011
Line 101:		Line 101:
	\| 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. [http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf]]]		[[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. [http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf]]]



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

← Older revision		Revision as of 02:11, 25 April 2011
Line 151:		Line 151:
	<span id="4foot">[[#4body\|4.]]</span> http://www.statemaster.com/encyclopedia/Lock-(computer-science)<br>		<span id="4foot">[[#4body\|4.]]</span> http://www.statemaster.com/encyclopedia/Lock-(computer-science)<br>
	<span id="5foot">[[#5body\|5.]]</span> http://faydoc.tripod.com/cpu/cmpxchg.htm<br>		<span id="5foot">[[#5body\|5.]]</span> http://faydoc.tripod.com/cpu/cmpxchg.htm<br>
	<span id="6foot">[[#6body\|6.]]</span> http://www.cs.duke.edu/~~~chase~~/cps110/slides/threads3.ppt<br>		<span id="6foot">[[#6body\|6.]]</span> http://www.cs.duke.edu/courses/fall09/cps110/slides/threads3.ppt<br>
	<span id="7foot">[[#7body\|7.]]</span> Scalability evaluation of barrier algorithms for OpenMP. http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf<br>		<span id="7foot">[[#7body\|7.]]</span> Scalability evaluation of barrier algorithms for OpenMP. http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf<br>
	<span id="8foot">[[#8body\|8.]]</span> Carwyn Ball and Mark Bull. Barrier Synchronization in Java. http://www.ukhec.ac.uk/publications/reports/synch_java.pdf<br>		<span id="8foot">[[#8body\|8.]]</span> Carwyn Ball and Mark Bull. Barrier Synchronization in Java. http://www.ukhec.ac.uk/publications/reports/synch_java.pdf<br>
	<span id="9foot">[[#9body\|9.]]</span> http://www.cs.brown.edu/courses/cs176/barrier.ppt<br>		<span id="9foot">[[#9body\|9.]]</span> http://www.cs.brown.edu/courses/cs176/barrier.ppt<br>

← Older revision		Revision as of 04:48, 2 April 2011
Line 139:		Line 139:

	= References =		= References =
	<span id="1foot">[[#1body\|1.]]</span>David Culler, J.P. Singh and Anoop Gupta. Parallel Computer Architecture: A Hardware/Software Approach. Morgan Kaufmann. August 1998.<br>		<span id="1foot">[[#1body\|1.]]</span> David Culler, J.P. Singh and Anoop Gupta. Parallel Computer Architecture: A Hardware/Software Approach. Morgan Kaufmann. August 1998.<br>
	<span id="2foot">[[#2body\|2.]]</span>Yan Solihin. Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems. Solihin Books. August 2009.<br>		<span id="2foot">[[#2body\|2.]]</span> Yan Solihin. Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems. Solihin Books. August 2009.<br>
	<span id="3foot">[[#3body\|3.]]</span>Thomas E. Anderson. The Performance of Spin Lock Alternatives for Shared-memory Multiprocessors. http://www.cc.gatech.edu/classes/AY2010/cs4210_fall/papers/anderson-spinlock.pdf<br>		<span id="3foot">[[#3body\|3.]]</span> Thomas E. Anderson. The Performance of Spin Lock Alternatives for Shared-memory Multiprocessors. http://www.cc.gatech.edu/classes/AY2010/cs4210_fall/papers/anderson-spinlock.pdf<br>
	<span id="4foot">[[#4body\|4.]]</span>http://www.statemaster.com/encyclopedia/Lock-(computer-science)<br>		<span id="4foot">[[#4body\|4.]]</span> http://www.statemaster.com/encyclopedia/Lock-(computer-science)<br>
	<span id="5foot">[[#5body\|5.]]</span>http://faydoc.tripod.com/cpu/cmpxchg.htm<br>		<span id="5foot">[[#5body\|5.]]</span> http://faydoc.tripod.com/cpu/cmpxchg.htm<br>
	<span id="6foot">[[#6body\|6.]]</span>www.cs.duke.edu/~chase/cps110/slides/threads3.ppt<br>		<span id="6foot">[[#6body\|6.]]</span> http://www.cs.duke.edu/~chase/cps110/slides/threads3.ppt<br>
	<span id="7foot">[[#7body\|7.]]</span>Scalability evaluation of barrier algorithms for OpenMP. http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf<br>		<span id="7foot">[[#7body\|7.]]</span> Scalability evaluation of barrier algorithms for OpenMP. http://www2.cs.uh.edu/~hpctools/pub/iwomp-barrier.pdf<br>
	<span id="8foot">[[#8body\|8.]]</span>Carwyn Ball and Mark Bull. Barrier Synchronization in Java. http://www.ukhec.ac.uk/publications/reports/synch_java.pdf<br>		<span id="8foot">[[#8body\|8.]]</span> Carwyn Ball and Mark Bull. Barrier Synchronization in Java. http://www.ukhec.ac.uk/publications/reports/synch_java.pdf<br>
	<span id="9foot">[[#9body\|9.]]</span>http://www.cs.brown.edu/courses/cs176/barrier.ppt<br>		<span id="9foot">[[#9body\|9.]]</span> http://www.cs.brown.edu/courses/cs176/barrier.ppt<br>

← Older revision		Revision as of 04:47, 2 April 2011
Line 148:		Line 148:
	<span id="8foot">[[#8body\|8.]]</span>Carwyn Ball and Mark Bull. Barrier Synchronization in Java. http://www.ukhec.ac.uk/publications/reports/synch_java.pdf<br>		<span id="8foot">[[#8body\|8.]]</span>Carwyn Ball and Mark Bull. Barrier Synchronization in Java. http://www.ukhec.ac.uk/publications/reports/synch_java.pdf<br>
	<span id="9foot">[[#9body\|9.]]</span>http://www.cs.brown.edu/courses/cs176/barrier.ppt<br>		<span id="9foot">[[#9body\|9.]]</span>http://www.cs.brown.edu/courses/cs176/barrier.ppt<br>
	~~<span id="10foot">[[#10body\|10.]]</span>~~
	~~<span id="11foot">[[#11body\|11.]]</span>~~
	~~<span id="12foot">[[#12body\|12.]]</span>~~


	* Deadlock [http://www.statemaster.com/encyclopedia/Deadlock]

← Older revision		Revision as of 04:33, 2 April 2011
Line 147:		Line 147:

	= References =		= References =
	<span id="1foot">[[#1body\|1.]]</span>David Culler, J.P. Singh and Anoop Gupta, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann, August 1998.<br>		<span id="1foot">[[#1body\|1.]]</span>David Culler, J.P. Singh and Anoop Gupta. Parallel Computer Architecture: A Hardware/Software Approach. Morgan Kaufmann. August 1998.<br>
	<span id="2foot">[[#2body\|2.]]</span>Yan Solihin, Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems, Solihin Books, August 2009.<br>		<span id="2foot">[[#2body\|2.]]</span>Yan Solihin. Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems. Solihin Books. August 2009.<br>
	<span id="3foot">[[#3body\|3.]]</span>		<span id="3foot">[[#3body\|3.]]</span>Thomas E. Anderson. The Performance of Spin Lock Alternatives for Shared-memory Multiprocessors. http://www.cc.gatech.edu/classes/AY2010/cs4210_fall/papers/anderson-spinlock.pdf<br>
	<span id="4foot">[[#4body\|4.]]</span>		<span id="4foot">[[#4body\|4.]]</span>
	<span id="5foot">[[#5body\|5.]]</span>		<span id="5foot">[[#5body\|5.]]</span>