CSC/ECE 506 Spring 2010/ch 7 pl/ - Revision history

Admin: /* Open MP */

2010-04-08T21:25:47Z

Open MP

← Older revision		Revision as of 21:25, 8 April 2010
Line 50:		Line 50:
	The Solihin text uses the "#pragma omp" critical directive in the code given in the cache-coherence section above. In order to use this directive the hardware must have some provision to ensure that only this one thread is going to be accessing the critical section at a given time. According to the text, the problem not only exists on multiprocessor systems but on uniprocessors as well. The problem discussed in the text is based on the implementation of a lock function.		The Solihin text uses the "#pragma omp" critical directive in the code given in the cache-coherence section above. In order to use this directive the hardware must have some provision to ensure that only this one thread is going to be accessing the critical section at a given time. According to the text, the problem not only exists on multiprocessor systems but on uniprocessors as well. The problem discussed in the text is based on the implementation of a lock function.

	The problem is that ~~with out~~ special directives, there is no way to ensure that only 1 processor obtains that lock, and in turn that there is only one processing element inside the critical section. The text suggests that the one good way to remedy this problem is to use an atomic instruction for the locking function. With an atomic function, all commands must execute successfully or else it will appear that none of the commands were executed. This allows for one processor to obtain the lock and enter the critical section, while the other processor(s) wait until the lock is released before entering the critical section.		The problem is that without special directives, there is no way to ensure that only 1 processor obtains that lock, and in turn that there is only one processing element inside the critical section. The text suggests that the one good way to remedy this problem is to use an atomic instruction for the locking function. With an atomic function, all commands must execute successfully or else it will appear that none of the commands were executed. This allows for one processor to obtain the lock and enter the critical section, while the other processor(s) wait until the lock is released before entering the critical section.

	== Fence Insertion ==		== Fence Insertion ==

Admin: /* Ordering on a Uniprocessor */

2010-04-08T21:25:26Z

Ordering on a Uniprocessor

← Older revision		Revision as of 21:25, 8 April 2010
Line 25:		Line 25:
	== Ordering on a Uniprocessor ==		== Ordering on a Uniprocessor ==

	On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf] goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:		On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf] goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of permissible changes to ordering are:

	<pre>		<pre>

Admin: /* Cache Coherence */

2010-04-08T21:24:57Z

Cache Coherence

← Older revision		Revision as of 21:24, 8 April 2010
Line 5:		Line 5:
	This problem arises when each chip in the system has its own separate and discrete cache. The Solihin text gives a good example on how a problem can arise in a multiprocessor when there is no method to ensure cache coherence. In the example given in the text, the code below is executed.		This problem arises when each chip in the system has its own separate and discrete cache. The Solihin text gives a good example on how a problem can arise in a multiprocessor when there is no method to ensure cache coherence. In the example given in the text, the code below is executed.

	~~{{{~~		<pre>
	sum = 0;		sum = 0;
	#pragma omp parallel for		#pragma omp parallel for
Line 14:		Line 14:
	}		}
	print sum;		print sum;
	~~}}}~~		</pre>

Admin: /* Ordering on a Multiprocessor */

2010-04-08T21:24:16Z

Ordering on a Multiprocessor

← Older revision		Revision as of 21:24, 8 April 2010
Line 40:		Line 40:
	On a multiprocessor much more care must be taken to ensure that all of the loads and stores are committed to memory in a valid order. According to the blog referred to above the following must take place on a multiprocessor system:		On a multiprocessor much more care must be taken to ensure that all of the loads and stores are committed to memory in a valid order. According to the blog referred to above the following must take place on a multiprocessor system:

	(store A, store B): maintained in order.		(store A, store B): maintained in order.<br/>
	(load A, store B): load must be done first, ignoring a younger store in the queue.		(load A, store B): load must be done first, ignoring a younger store in the queue.<br/>
	(store A, load B): load must be not go ahead of the store, even though the store is to a different address.		(store A, load B): load must be not go ahead of the store, even though the store is to a different address.<br/>
	(load A, load B): even if the addresses are different, the older load must go first.		(load A, load B): even if the addresses are different, the older load must go first.

Admin: /* Ordering on a Uniprocessor */

2010-04-08T21:23:34Z

Ordering on a Uniprocessor

← Older revision		Revision as of 21:23, 8 April 2010
Line 34:		Line 34:
	These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"		These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"

	Although it appears that we can freely change the order of memory operations on a uniprocessor, even on a uniprocessor we cannot change the order of operations to the ''same'' address. For example (load A, store A) --> (store A, load A) would not be OK.		Although it appears that we can freely change the order of memory operations on a uniprocessor, even on a uniprocessor we cannot change the order of operations to the ''same'' address. For example <nowiki>(load A, store A) --> (store A, load A)</nowiki> would not be OK.

	== Ordering on a Multiprocessor ==		== Ordering on a Multiprocessor ==

Admin: /* Ordering on a Uniprocessor */

2010-04-08T21:23:00Z

Ordering on a Uniprocessor

← Older revision		Revision as of 21:23, 8 April 2010
Line 27:		Line 27:
	On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf] goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:		On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf] goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:

			<pre>
	(load A, load B) > (load B, load A)		(load A, load B) > (load B, load A)
	(store B, store A) > (store A, store B)		(store B, store A) > (store A, store B)
			</pre>

	These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"		These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"

Admin: /* Ordering on a Uniprocessor */

2010-04-08T21:21:01Z

Ordering on a Uniprocessor

← Older revision		Revision as of 21:21, 8 April 2010
Line 27:		Line 27:
	On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf] goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:		On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf] goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:

	~~{{{~~
	(load A, load B) > (load B, load A)		(load A, load B) > (load B, load A)
	(store B, store A) > (store A, store B)		(store B, store A) > (store A, store B)
	~~}}}~~

	These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"		These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"

Admin: /* Ordering on a Uniprocessor */

2010-04-08T21:20:39Z

Ordering on a Uniprocessor

← Older revision		Revision as of 21:20, 8 April 2010
Line 27:		Line 27:
	On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf] goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:		On a uniprocessor system, memory ordering can be changed by the compiler quite a bit to ensure the best possible performance. The 2008 blog post on flickeringtubelight.net [http://flickeringtubelight.net/blog/wp-content/uploads/2008/06/notesonconsistencyandcoherence.pdf] goes into some details about ordering on a uniprocessor vs. a multiprocessor. For example, reordering memory operations to different addresses is fine, and will cause no harm on a uniprocessor system. Some examples of OK changes to ordering are:

			{{{
	(load A, load B) > (load B, load A)		(load A, load B) > (load B, load A)
	(store B, store A) > (store A, store B)		(store B, store A) > (store A, store B)
			}}}

	These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"		These are OK since we on a uniprocessor system we can be certain that there is not another processor waiting for this information or "could observe this order and infer anything from the order"

Pwlane: /* Other Methods */

2010-04-05T20:05:44Z

Other Methods

← Older revision		Revision as of 20:05, 5 April 2010
Line 65:		Line 65:
	== Other Methods ==		== Other Methods ==

	There are many other ways to implement synchronization directives as well. ~~The~~ ACM article [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf] discusses using a test and set method for synchronization as well as a direct interrupt to another core. As it states, both of these are special hardware solutions that must be implemented in order for the programmer to be able to take advantage of them. The programmer (or complier) is responsible for knowing which synchronization directives are available on a given architecture and implementing them in an efficient manner.		There are many other ways to implement synchronization directives as well. This ACM article [https://wiki.ittc.ku.edu/ittc/images/0/0f/Loghi.pdf] discusses using a test and set method for synchronization as well as a direct interrupt to another core. As it states, both of these are special hardware solutions that must be implemented in order for the programmer to be able to take advantage of them. The programmer (or complier) is responsible for knowing which synchronization directives are available on a given architecture and implementing them in an efficient manner.

	= References =		= References =

Pwlane: /* Fence Insertion */

2010-04-05T20:04:56Z

Fence Insertion

← Older revision		Revision as of 20:04, 5 April 2010
Line 52:		Line 52:
	== Fence Insertion ==		== Fence Insertion ==

	One method that is commonly used on production shared memory systems and microprocessors it the insertion of fences. These fences can be used by the programmer to force the chip to perform a synchronization, or wait until "all previous memory operations of the processor are guaranteed to have completed" [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790] Fence insertion is ~~an important go between for~~ the programmer~~, allowing~~ control over the hardware's default ordering of memory operations. It is important from a performance standpoint that the complier be able to quickly and efficiently insert fences automatically, and the algorithms used for this automatic insertion have a large bearing on performance. [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]		One method that is commonly used on production shared memory systems and microprocessors it the insertion of fences. These fences can be used by the programmer to force the chip to perform a synchronization, or wait until "all previous memory operations of the processor are guaranteed to have completed" [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790] Fence insertion is a method giving the programmer (or compiler) control over the hardware's default ordering of memory operations (such as sequential consistency, processor consistency, weak ordering, etc). It is important from a performance standpoint that the complier be able to quickly and efficiently insert fences automatically, and the algorithms used for this automatic insertion have a large bearing on performance. [http://portal.acm.org/citation.cfm?id=782854&dl=GUIDE&coll=GUIDE&CFID=84866326&CFTOKEN=84791790]

	=== Instructions used for fence operations ===		=== Instructions used for fence operations ===