CSC/ECE 506 Spring 2015/10a dr - Revision history

Rrmercer at 02:54, 6 April 2015

2015-04-06T02:54:50Z

← Older revision		Revision as of 02:54, 6 April 2015
Line 30:		Line 30:

	= Sequential Consistency Examples =		= Sequential Consistency Examples =
	In Example 1 below we provide a run through of a typical program where several reads and writes of several variables occur in a sequentially consistent manner. This diagram of processor execution is motivated by Lamport ~~[1]~~. In Example 1 below the example begins with processor 1 doing a write of 1 to variable x. Then processor 2 then performs two back-to-back reads of variable x. Note that the second read performed by P2 occurs at the same time as P3 reads the 1st value of x as well. Finally, P3 writes value 2 to y which is then read by P1.		In Example 1 below we provide a run through of a typical program where several reads and writes of several variables occur in a sequentially consistent manner. This diagram of processor execution is motivated by Lamport <ref>Leslie Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE Trans. Comput. C-28,9 (Sept. 1979), 690-691.</ref>. In Example 1 below the example begins with processor 1 doing a write of 1 to variable x. Then processor 2 then performs two back-to-back reads of variable x. Note that the second read performed by P2 occurs at the same time as P3 reads the 1st value of x as well. Finally, P3 writes value 2 to y which is then read by P1.

	Example 1: Sequential Consistency[4]		Example 1: Sequential Consistency[4]
Line 197:		Line 197:

	Speculating is store is however more difficult as stores are much harder to cancel if speculated wrongly than loads. The reason is that after accessing the cache, store already deposits the new value in the cache and it propagates to the main memory and other processors and as a result cancelling a store becomes a much harder problem.		Speculating is store is however more difficult as stores are much harder to cancel if speculated wrongly than loads. The reason is that after accessing the cache, store already deposits the new value in the cache and it propagates to the main memory and other processors and as a result cancelling a store becomes a much harder problem.
	Even with these improvements SC is still slower than other relaxed consistency models ~~[HP]~~. The primary problem with Sequential Consistency (SC) is that it does not allow program instruction reordering ([[Instruction Level Parallelism]]) by the processor or by the compiler to occur to improve performance and as a result the SC is not implemented by any major hardware platforms ~~[HP~~, ~~figure 9]~~.		Even with these improvements SC is still slower than other relaxed consistency models <ref>Memory Consistency Models: A Tutorial, http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf</ref>. The primary problem with Sequential Consistency (SC) is that it does not allow program instruction reordering ([[Instruction Level Parallelism]]) by the processor or by the compiler to occur to improve performance and as a result the SC is not implemented by any major hardware platforms <ref>Memory Consistency Models: A Tutorial, http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf</ref>.

	= Current work on Sequential Consistency =		= Current work on Sequential Consistency =

	There are two main areas of active research in SC. One area of research in SC is in finding new ways to optimize SC. One such implementation called BulkSC improves on SC, and provides an implementation comparable to Release Consistency by dynamically grouping sets of consecutive instructions into chunks that appear to execute atomically and in isolation. Then the hardware enforces SC at the coarse grain of chunks rather than at the conventional fine grain of memory accesses. It can be realized via simple hardware ~~[5]~~.		There are two main areas of active research in SC. One area of research in SC is in finding new ways to optimize SC. One such implementation called BulkSC improves on SC, and provides an implementation comparable to Release Consistency by dynamically grouping sets of consecutive instructions into chunks that appear to execute atomically and in isolation. Then the hardware enforces SC at the coarse grain of chunks rather than at the conventional fine grain of memory accesses. It can be realized via simple hardware <ref>Bulk SC: Bulk Enforcement of Sequential Consistency, https://homes.cs.washington.edu/~luisceze/publications/isca07_bulksc.pdf</ref>.
	Another area of work is in verifying sequential consistency in implementations of compilers and hardware. This turns out to be a difficult problem ~~[icpp90_seqcon]~~. One area of research is to find ways to quickly and easily confirm an implementation will confirm to SC.		Another area of work is in verifying sequential consistency in implementations of compilers and hardware. This turns out to be a difficult problem <ref>Implementing Sequential Consistency In Cache-Based Systems, Sarita Adve Mark Hill, Proceedings of the 1990 Internation Conference on Parallel Processing</ref>. One area of research is to find ways to quickly and easily confirm an implementation will confirm to SC.

	= 10 Question Quiz =		= 10 Question Quiz =

Rrmercer: /* Implementing Sequential Consistency */

2015-04-06T02:47:58Z

Implementing Sequential Consistency

← Older revision		Revision as of 02:47, 6 April 2015
Line 140:		Line 140:
	The programmer’s intuition is that the write by processor P0 should be propagated to both P1 and P2 instantaneously. Therefore c should be printed as 1. However it may happen that a is propagated to P1 before P2 and then P1 writes b=1 and datum1ready1=1. As a result P2 will print c = 0 as a is still not propagated to P2 yet.		The programmer’s intuition is that the write by processor P0 should be propagated to both P1 and P2 instantaneously. Therefore c should be printed as 1. However it may happen that a is propagated to P1 before P2 and then P1 writes b=1 and datum1ready1=1. As a result P2 will print c = 0 as a is still not propagated to P2 yet.

	[[Image:Figure5_write_buffer.png]]		[[Image:Figure5_write_buffer.png\|frame\|center\|Write Buffer reordering]]

	Given all of the problems above with different optimizations how does one guarantee both program order and write atomicity. We begin with examining how to ensure program order in a bus-based SMP system. In order to guarantee program order, typically requires the system to receive an acknowledgement that the previous operation has completed before moving on to the next operation.		Given all of the problems above with different optimizations how does one guarantee both program order and write atomicity. We begin with examining how to ensure program order in a bus-based SMP system. In order to guarantee program order, typically requires the system to receive an acknowledgement that the previous operation has completed before moving on to the next operation.

Rrmercer: /* Implementing Sequential Consistency */

2015-04-06T02:46:21Z

Implementing Sequential Consistency

← Older revision		Revision as of 02:46, 6 April 2015
Line 139:		Line 139:

	The programmer’s intuition is that the write by processor P0 should be propagated to both P1 and P2 instantaneously. Therefore c should be printed as 1. However it may happen that a is propagated to P1 before P2 and then P1 writes b=1 and datum1ready1=1. As a result P2 will print c = 0 as a is still not propagated to P2 yet.		The programmer’s intuition is that the write by processor P0 should be propagated to both P1 and P2 instantaneously. Therefore c should be printed as 1. However it may happen that a is propagated to P1 before P2 and then P1 writes b=1 and datum1ready1=1. As a result P2 will print c = 0 as a is still not propagated to P2 yet.

			[[Image:Figure5_write_buffer.png]]

	Given all of the problems above with different optimizations how does one guarantee both program order and write atomicity. We begin with examining how to ensure program order in a bus-based SMP system. In order to guarantee program order, typically requires the system to receive an acknowledgement that the previous operation has completed before moving on to the next operation.		Given all of the problems above with different optimizations how does one guarantee both program order and write atomicity. We begin with examining how to ensure program order in a bus-based SMP system. In order to guarantee program order, typically requires the system to receive an acknowledgement that the previous operation has completed before moving on to the next operation.

Rrmercer: /* Implementing Sequential Consistency */

2015-04-06T02:42:52Z

Implementing Sequential Consistency

← Older revision		Revision as of 02:42, 6 April 2015
Line 125:		Line 125:

	This example demonstrates a violation of the write-atomicity property of SC.		This example demonstrates a violation of the write-atomicity property of SC.

	Example 5.		Example 5.
	{\|		{\|

Rrmercer: /* Implementing Sequential Consistency */

2015-04-06T02:42:28Z

Implementing Sequential Consistency

← Older revision		Revision as of 02:42, 6 April 2015
Line 94:		Line 94:
	How could something like Example 2 from the above section occur? We will present several examples of when Sequential Consistency can be violated in a two different types of multiprocessor machines. First we will start with a shared-memory bus-based SMP example with no cache. We will also assume in the following examples that no form of synchronization has been added to the code.		How could something like Example 2 from the above section occur? We will present several examples of when Sequential Consistency can be violated in a two different types of multiprocessor machines. First we will start with a shared-memory bus-based SMP example with no cache. We will also assume in the following examples that no form of synchronization has been added to the code.

	In the first example we will look at we will assume that both values start out as zero.		In the first example we will look at we will assume that both values start out as zero.

	Example 3. Instruction Reorder between Processors		Example 3. Instruction Reorder between Processors
	{\|		{\|
Line 171:		Line 172:
	\|}		\|}

	This causes a huge restriction on performance as many techniques which exploit out-of-order execution of instructions are disabled. Hence SC cannot exploit [[instruction level parallelism (ILP)]] to increase performance.		This causes a huge restriction on performance as many techniques which exploit out-of-order execution of instructions are disabled. Hence SC cannot exploit [[instruction level parallelism (ILP)]] to increase performance.

	= Improving the performance of Sequential Consistency =		= Improving the performance of Sequential Consistency =

Rrmercer: /* Programmer’s Intuition vs Sequential Consistency */

2015-04-06T02:41:46Z

Programmer’s Intuition vs Sequential Consistency

← Older revision		Revision as of 02:41, 6 April 2015
Line 25:		Line 25:

	These two expectations lead us to the following conceptual model of a programmer’s intuition. The basic idea is that there is one large main memory which switches between processors in a global order committing operations as it goes.		These two expectations lead us to the following conceptual model of a programmer’s intuition. The basic idea is that there is one large main memory which switches between processors in a global order committing operations as it goes.
	[Image:Programmers_intuition_diagram.png\|frame\|center\|Programmers Intuition about Multiprocessor consistency]]		[[Image:Programmers_intuition_diagram.png\|frame\|center\|Programmers Intuition about Multiprocessor consistency]]

	These 'programmer’s intuitive' expectations closely match [[Sequential Consistency]].		These 'programmer’s intuitive' expectations closely match [[Sequential Consistency]].

Rrmercer: /* Programmer’s Intuition vs Sequential Consistency */

2015-04-06T02:40:55Z

Programmer’s Intuition vs Sequential Consistency

← Older revision		Revision as of 02:40, 6 April 2015
Line 25:		Line 25:

	These two expectations lead us to the following conceptual model of a programmer’s intuition. The basic idea is that there is one large main memory which switches between processors in a global order committing operations as it goes.		These two expectations lead us to the following conceptual model of a programmer’s intuition. The basic idea is that there is one large main memory which switches between processors in a global order committing operations as it goes.
	[~~[File~~:Programmers_intuition_diagram.png \| ~~Programmers Intuition about Multiprocessor consistency]]~~		[Image:Programmers_intuition_diagram.png\|frame\|center\|Programmers Intuition about Multiprocessor consistency]]
	~~[[File:Programmers_intuition_diagram.png~~ \| Programmers Intuition about Multiprocessor consistency]]

	~~[[Image:Busbased SMP.jpg\|frame\|center\|<b>Figure 1:</b> Typical Bus-Based Processor Model]]~~
	These 'programmer’s intuitive' expectations closely match [[Sequential Consistency]].		These 'programmer’s intuitive' expectations closely match [[Sequential Consistency]].

Rrmercer at 02:40, 6 April 2015

2015-04-06T02:40:17Z

← Older revision		Revision as of 02:40, 6 April 2015
Line 26:		Line 26:
	These two expectations lead us to the following conceptual model of a programmer’s intuition. The basic idea is that there is one large main memory which switches between processors in a global order committing operations as it goes.		These two expectations lead us to the following conceptual model of a programmer’s intuition. The basic idea is that there is one large main memory which switches between processors in a global order committing operations as it goes.
	[[File:Programmers_intuition_diagram.png \| Programmers Intuition about Multiprocessor consistency]]		[[File:Programmers_intuition_diagram.png \| Programmers Intuition about Multiprocessor consistency]]
			[[File:Programmers_intuition_diagram.png \| Programmers Intuition about Multiprocessor consistency]]

			[[Image:Busbased SMP.jpg\|frame\|center\|<b>Figure 1:</b> Typical Bus-Based Processor Model]]
	These 'programmer’s intuitive' expectations closely match [[Sequential Consistency]].		These 'programmer’s intuitive' expectations closely match [[Sequential Consistency]].

Rrmercer at 02:38, 6 April 2015

2015-04-06T02:38:33Z

← Older revision		Revision as of 02:38, 6 April 2015
Line 25:		Line 25:

	These two expectations lead us to the following conceptual model of a programmer’s intuition. The basic idea is that there is one large main memory which switches between processors in a global order committing operations as it goes.		These two expectations lead us to the following conceptual model of a programmer’s intuition. The basic idea is that there is one large main memory which switches between processors in a global order committing operations as it goes.
	[[File:Programmers_intuition_diagram.png~~\|thumbnail~~\|Programmers Intuition about Multiprocessor consistency]]		[[File:Programmers_intuition_diagram.png \| Programmers Intuition about Multiprocessor consistency]]
	~~[[File:Programmers_intuition_diagram.png~~]]
	These 'programmer’s intuitive' expectations closely match [[Sequential Consistency]].		These 'programmer’s intuitive' expectations closely match [[Sequential Consistency]].

Rrmercer at 02:37, 6 April 2015

2015-04-06T02:37:36Z

← Older revision		Revision as of 02:37, 6 April 2015
Line 26:		Line 26:
	These two expectations lead us to the following conceptual model of a programmer’s intuition. The basic idea is that there is one large main memory which switches between processors in a global order committing operations as it goes.		These two expectations lead us to the following conceptual model of a programmer’s intuition. The basic idea is that there is one large main memory which switches between processors in a global order committing operations as it goes.
	[[File:Programmers_intuition_diagram.png\|thumbnail\|Programmers Intuition about Multiprocessor consistency]]		[[File:Programmers_intuition_diagram.png\|thumbnail\|Programmers Intuition about Multiprocessor consistency]]
			[[File:Programmers_intuition_diagram.png]]
	These 'programmer’s intuitive' expectations closely match [[Sequential Consistency]].		These 'programmer’s intuitive' expectations closely match [[Sequential Consistency]].