CSC/ECE 506 Spring 2012/ch10 sj - Revision history

Jjaube: /* Lazy Release Consistency Model */

2012-04-14T01:37:53Z

Lazy Release Consistency Model

← Older revision		Revision as of 01:37, 14 April 2012
Line 304:		Line 304:

	===='''Lazy Release Consistency Model'''====		===='''Lazy Release Consistency Model'''====
	Lazy release consistency (LRC) is consistency model most frequently used in Software Distributed Shared Memory. It is used for implementing release consistency that lazily pulls modifications across the interconnect only when necessary. The basic concept behind the protocol is to allow processors to continue referencing cache blocks that have been written by other processors. Although write notices are sent as soon as a processor writes a shared block, invalidations occur only at acquire operations. This is sufficient to ensure that true sharing dependencies are observed. Lazy algorithms such as LRC do not make modifications globally visible at the time of a release. Instead, LRC guarantees only that a processor that acquires a lock will see all modifications that precede the lock acquire.<ref>http://delivery.acm.org.www.lib.ncsu.edu:2048/10.1145/230000/224398/a61-kontothanassis.html?key1=224398&key2=6529911721&coll=ACM&dl=ACM&CFID=140829&CFTOKEN=60032635</ref><ref name="Keleher">http://infoscience.epfl.ch/record/55789/files/isca92.ps.pdf</ref>		Lazy release consistency (LRC) is consistency model most frequently used in Software Distributed Shared Memory. It is used for implementing release consistency that lazily pulls modifications across the interconnect only when necessary. The basic concept behind the protocol is to allow processors to continue referencing cache blocks that have been written by other processors. Although write notices are sent as soon as a processor writes a shared block, invalidations occur only at acquire operations. This is sufficient to ensure that true sharing dependencies are observed. Lazy algorithms such as LRC do not make modifications globally visible at the time of a release. Instead, LRC guarantees only that a processor that acquires a lock will see all modifications that precede the lock acquire.<ref name="Kontothanassis">http://delivery.acm.org.www.lib.ncsu.edu:2048/10.1145/230000/224398/a61-kontothanassis.html?key1=224398&key2=6529911721&coll=ACM&dl=ACM&CFID=140829&CFTOKEN=60032635</ref><ref name="Keleher">http://infoscience.epfl.ch/record/55789/files/isca92.ps.pdf</ref>

	<center> [[Image: LRC.jpg]] </center>		<center> [[Image: LRC.jpg]] </center>

Jjaube: /* Performance Analysis of Lazy and Eager Consistency Models */

2012-04-14T01:37:23Z

Performance Analysis of Lazy and Eager Consistency Models

← Older revision		Revision as of 01:37, 14 April 2012
Line 327:		Line 327:
	support for coherence should use protocols based on lazy release consistency, but in a less ''aggressively lazy'' form than is appropriate for DSM.		support for coherence should use protocols based on lazy release consistency, but in a less ''aggressively lazy'' form than is appropriate for DSM.

	These are the results they show from their experiments to compare Lazy and Eager Consistency Models:<ref~~>http://delivery.acm.org.www.lib.ncsu.edu:2048/10.1145/230000/224398/a61-kontothanassis.html?key1=224398&key2=6529911721&coll=ACM&dl=ACM&CFID=140829&CFTOKEN~~=~~60032635<~~/~~ref~~>		These are the results they show from their experiments to compare Lazy and Eager Consistency Models:<ref name="Kontothanassis" />
	<br>		<br>
	<center>[[Image:Perf.jpg]]</center>		<center>[[Image:Perf.jpg]]</center>

Jjaube: /* Comparison between Lazy and Eager Release Consistency Models */

2012-04-14T01:35:19Z

Comparison between Lazy and Eager Release Consistency Models

← Older revision		Revision as of 01:35, 14 April 2012
Line 318:		Line 318:
	If an update policy is used in conjunction with Munin's write shared protocol and x is present in all caches, then all of these cached copies are updated at every release. Logically, however it suffices to update each processor's copy only when it acquires l. This results in a single message exchange per acquire as in a message passing implementation.		If an update policy is used in conjunction with Munin's write shared protocol and x is present in all caches, then all of these cached copies are updated at every release. Logically, however it suffices to update each processor's copy only when it acquires l. This results in a single message exchange per acquire as in a message passing implementation.

	Unlike eager algorithms such as Munin's write shared protocol, lazy algorithms such as LRC (Lazy Release Consistency) do not make modifications globally visible at the time of a release. Instead LRC guarantees only that a processor that acquires a lock will see all modifications that precede the lock acquire. As indicated in the above figure , all modifications that occur in program order before any of the releases in p1 through p4 precede the lock acquisition in p4. With LRC, modifications are propagated at the time of an acquire. Only the modifications that precede the acquire are sent to the acquiring processor. The modifications can be piggybacked on the message that grants the lock, further reducing message traffic. The following figure shows the message traffic in LRC for the same shared data accesses as in Figure under lazy consistency model section. l and x are sent in a single message at each acquire.<ref>http://www.cs.rochester.edu/research/cashmere/SC95/lazeag.html</ref><ref~~>http:~~/~~/infoscience.epfl.ch/record/55789/files/isca92.ps.pdf</ref~~>		Unlike eager algorithms such as Munin's write shared protocol, lazy algorithms such as LRC (Lazy Release Consistency) do not make modifications globally visible at the time of a release. Instead LRC guarantees only that a processor that acquires a lock will see all modifications that precede the lock acquire. As indicated in the above figure , all modifications that occur in program order before any of the releases in p1 through p4 precede the lock acquisition in p4. With LRC, modifications are propagated at the time of an acquire. Only the modifications that precede the acquire are sent to the acquiring processor. The modifications can be piggybacked on the message that grants the lock, further reducing message traffic. The following figure shows the message traffic in LRC for the same shared data accesses as in Figure under lazy consistency model section. l and x are sent in a single message at each acquire.<ref>http://www.cs.rochester.edu/research/cashmere/SC95/lazeag.html</ref><ref name="Keleher" />
	<center> [[Image:lazy2.jpg]] </center>		<center> [[Image:lazy2.jpg]] </center>

Jjaube: /* Lazy Release Consistency Model */

2012-04-14T01:34:41Z

Lazy Release Consistency Model

← Older revision		Revision as of 01:34, 14 April 2012
Line 304:		Line 304:

	===='''Lazy Release Consistency Model'''====		===='''Lazy Release Consistency Model'''====
	Lazy release consistency (LRC) is consistency model most frequently used in Software Distributed Shared Memory. It is used for implementing release consistency that lazily pulls modifications across the interconnect only when necessary. The basic concept behind the protocol is to allow processors to continue referencing cache blocks that have been written by other processors. Although write notices are sent as soon as a processor writes a shared block, invalidations occur only at acquire operations. This is sufficient to ensure that true sharing dependencies are observed. Lazy algorithms such as LRC do not make modifications globally visible at the time of a release. Instead, LRC guarantees only that a processor that acquires a lock will see all modifications that precede the lock acquire.<ref>http://delivery.acm.org.www.lib.ncsu.edu:2048/10.1145/230000/224398/a61-kontothanassis.html?key1=224398&key2=6529911721&coll=ACM&dl=ACM&CFID=140829&CFTOKEN=60032635</ref><ref>http://infoscience.epfl.ch/record/55789/files/isca92.ps.pdf</ref>		Lazy release consistency (LRC) is consistency model most frequently used in Software Distributed Shared Memory. It is used for implementing release consistency that lazily pulls modifications across the interconnect only when necessary. The basic concept behind the protocol is to allow processors to continue referencing cache blocks that have been written by other processors. Although write notices are sent as soon as a processor writes a shared block, invalidations occur only at acquire operations. This is sufficient to ensure that true sharing dependencies are observed. Lazy algorithms such as LRC do not make modifications globally visible at the time of a release. Instead, LRC guarantees only that a processor that acquires a lock will see all modifications that precede the lock acquire.<ref>http://delivery.acm.org.www.lib.ncsu.edu:2048/10.1145/230000/224398/a61-kontothanassis.html?key1=224398&key2=6529911721&coll=ACM&dl=ACM&CFID=140829&CFTOKEN=60032635</ref><ref name="Keleher">http://infoscience.epfl.ch/record/55789/files/isca92.ps.pdf</ref>

	<center> [[Image: LRC.jpg]] </center>		<center> [[Image: LRC.jpg]] </center>

Jjaube: /* High design and implementation cost */

2012-04-14T01:33:18Z

High design and implementation cost

← Older revision		Revision as of 01:33, 14 April 2012
Line 55:		Line 55:
	Protocols are complex and getting them right in hardware take substantial design time. A simple directory-based protocol can be developed under various assumptions, namely that the directory state and sharing vector are always aware of current cache state and that there is no overlap between requests. These assumptions, however, do not generally hold true in real systems, and various means have been devised to handle these types of situations.		Protocols are complex and getting them right in hardware take substantial design time. A simple directory-based protocol can be developed under various assumptions, namely that the directory state and sharing vector are always aware of current cache state and that there is no overlap between requests. These assumptions, however, do not generally hold true in real systems, and various means have been devised to handle these types of situations.

	The first situation can be handled by splitting up one of the states based on which node is believed to be the owner at the time. While the second situation can be handle by serializing requests, this tends to be very expensive from a performance standpoint. Additional complexity, therefore, must be built into the protocol design in order to allow for non-atomic request processing.<ref name="Solihin />		The first situation can be handled by splitting up one of the states based on which node is believed to be the owner at the time. While the second situation can be handle by serializing requests, this tends to be very expensive from a performance standpoint. Additional complexity, therefore, must be built into the protocol design in order to allow for non-atomic request processing.<ref name="Solihin" />

	All of the above schemes mentioned to improve performance of SC allow a processor to overlap or reorder its memory accesses without software support, however, either require complex or restricted hardware (e.g., hardware prefetching and rollback) or the gains are expected to be small. Further, the optimizations of these schemes can be exploited by hardware (or the runtime		All of the above schemes mentioned to improve performance of SC allow a processor to overlap or reorder its memory accesses without software support, however, either require complex or restricted hardware (e.g., hardware prefetching and rollback) or the gains are expected to be small. Further, the optimizations of these schemes can be exploited by hardware (or the runtime

Jjaube: /* High design and implementation cost */

2012-04-14T01:32:21Z

High design and implementation cost

← Older revision		Revision as of 01:32, 14 April 2012
Line 55:		Line 55:
	Protocols are complex and getting them right in hardware take substantial design time. A simple directory-based protocol can be developed under various assumptions, namely that the directory state and sharing vector are always aware of current cache state and that there is no overlap between requests. These assumptions, however, do not generally hold true in real systems, and various means have been devised to handle these types of situations.		Protocols are complex and getting them right in hardware take substantial design time. A simple directory-based protocol can be developed under various assumptions, namely that the directory state and sharing vector are always aware of current cache state and that there is no overlap between requests. These assumptions, however, do not generally hold true in real systems, and various means have been devised to handle these types of situations.

	The first situation can be handled by splitting up one of the states based on which node is believed to be the owner at the time. While the second situation can be handle by serializing requests, this tends to be very expensive from a performance standpoint. Additional complexity, therefore, must be built into the protocol design in order to allow for non-atomic request processing.<ref~~>http:~~/~~/www.cesr.ncsu.edu/solihin/Main.html</ref~~>		The first situation can be handled by splitting up one of the states based on which node is believed to be the owner at the time. While the second situation can be handle by serializing requests, this tends to be very expensive from a performance standpoint. Additional complexity, therefore, must be built into the protocol design in order to allow for non-atomic request processing.<ref name="Solihin />

	All of the above schemes mentioned to improve performance of SC allow a processor to overlap or reorder its memory accesses without software support, however, either require complex or restricted hardware (e.g., hardware prefetching and rollback) or the gains are expected to be small. Further, the optimizations of these schemes can be exploited by hardware (or the runtime		All of the above schemes mentioned to improve performance of SC allow a processor to overlap or reorder its memory accesses without software support, however, either require complex or restricted hardware (e.g., hardware prefetching and rollback) or the gains are expected to be small. Further, the optimizations of these schemes can be exploited by hardware (or the runtime

Jjaube: /* Introduction to Sequential Consistency Model */

2012-04-14T01:31:46Z

Introduction to Sequential Consistency Model

← Older revision		Revision as of 01:31, 14 April 2012
Line 15:		Line 15:
	[[Image:SeqC.jpg]] <br />		[[Image:SeqC.jpg]] <br />
	The figure above shows the basic representation for sequential consistency. This conceptual system for SC consists of n processors sharing a single logical memory. Though the figure does not show caches, an SC implementation may still cache data as long as the memory system appears as a single copy memory(i.e the writes should appear atomic). As SC requires program order to be maintained among all operation types, the pictorial representation of the program order shows all combinations of reads and writes, the line between them telling that the operations are required to complete in program order.		The figure above shows the basic representation for sequential consistency. This conceptual system for SC consists of n processors sharing a single logical memory. Though the figure does not show caches, an SC implementation may still cache data as long as the memory system appears as a single copy memory(i.e the writes should appear atomic). As SC requires program order to be maintained among all operation types, the pictorial representation of the program order shows all combinations of reads and writes, the line between them telling that the operations are required to complete in program order.
	This model ensures that the reads of a variable, will return the new values written to it by a processor. Sequential consistency provides a simple, intuitive programming model. Because of its strict consistency requirements, sequential consistency, many of the architecture and compiler optimizations used in uniprocessors are not safely applicable to sequentially consistent multiprocessors.<ref>http://www.cesr.ncsu.edu/solihin/Main.html</ref> For this reason, many [http://en.wikipedia.org/wiki/Consistency_model Relaxed consistency models] have been proposed, most of which		This model ensures that the reads of a variable, will return the new values written to it by a processor. Sequential consistency provides a simple, intuitive programming model. Because of its strict consistency requirements, sequential consistency, many of the architecture and compiler optimizations used in uniprocessors are not safely applicable to sequentially consistent multiprocessors.<ref name="Solihin">http://www.cesr.ncsu.edu/solihin/Main.html</ref> For this reason, many [http://en.wikipedia.org/wiki/Consistency_model Relaxed consistency models] have been proposed, most of which
	are supported by commercial architectures.		are supported by commercial architectures.

Jjaube: /* SPARC V8 Partial Store Ordering */

2012-04-14T01:30:22Z

SPARC V8 Partial Store Ordering

← Older revision		Revision as of 01:30, 14 April 2012
Line 152:		Line 152:
	Let us consider an example to demonstrate the working of PSO.<br />		Let us consider an example to demonstrate the working of PSO.<br />
	[[Image:code2.jpg]]<br />		[[Image:code2.jpg]]<br />
	With relaxed Write to Read models, the only value for (u,v) is (1,1). With PSO, since it allows writes to different locations to complete out of program order, it also allows the outcomes (0,0) or (0,1) or (1,0) for (u,v). In this example, STBAR instruction needs to be placed immediately before ''c1'' on P1 in order to disallow all outcomes except (1,1).<ref~~>http:~~/~~/infolab.stanford.edu/pub/cstr/reports/csl/tr/95/685/CSL-TR-95-685.pdf</ref~~>		With relaxed Write to Read models, the only value for (u,v) is (1,1). With PSO, since it allows writes to different locations to complete out of program order, it also allows the outcomes (0,0) or (0,1) or (1,0) for (u,v). In this example, STBAR instruction needs to be placed immediately before ''c1'' on P1 in order to disallow all outcomes except (1,1).<ref name="Gharachorloo" />

	==='''Relax Read to Read and Read to Write program orders'''===		==='''Relax Read to Read and Read to Write program orders'''===

Jjaube: /* SPARC V8 Total Store Ordering (TSO) */

2012-04-14T01:29:34Z

SPARC V8 Total Store Ordering (TSO)

← Older revision		Revision as of 01:29, 14 April 2012
Line 139:		Line 139:

	First consider the program segment in (a). Under the SC or IBM-370 model, the outcome (u,v,w,x)=(1,1,0,0) is disallowed. However, this outcome is possible under TSO because reads are allowed to bypass all previous writes, even if they are to the same location; therefore the sequence (b1,b2,c1,c2,a1,a2) is a valid total order for TSO. Of course, consistency value requirement still requires b1 and b2 to return the values of a1 and a2, respectively, even though the reads occur earlier in the sequence than the		First consider the program segment in (a). Under the SC or IBM-370 model, the outcome (u,v,w,x)=(1,1,0,0) is disallowed. However, this outcome is possible under TSO because reads are allowed to bypass all previous writes, even if they are to the same location; therefore the sequence (b1,b2,c1,c2,a1,a2) is a valid total order for TSO. Of course, consistency value requirement still requires b1 and b2 to return the values of a1 and a2, respectively, even though the reads occur earlier in the sequence than the
	writes. This maintains the intuition that a read observes all the writes issued from the same processor as the read. Consider the program segment in (b). In this case, the outcome (u,v,w,x)=(1,2,0,0)is not allowed under SC or IBM-370, but is possible under TSO.<ref~~>http:~~/~~/infolab.stanford.edu/pub/cstr/reports/csl/tr/95/685/CSL-TR-95-685.pdf</ref~~>		writes. This maintains the intuition that a read observes all the writes issued from the same processor as the read. Consider the program segment in (b). In this case, the outcome (u,v,w,x)=(1,2,0,0)is not allowed under SC or IBM-370, but is possible under TSO.<ref name="Gharachorloo" />

	==='''Relax Write to Write program order'''===		==='''Relax Write to Write program order'''===

Jjaube: /* IBM-370 */

2012-04-14T01:29:02Z

IBM-370

← Older revision		Revision as of 01:29, 14 April 2012
Line 123:		Line 123:

	The conceptual system shown in the above figure is similar to that used for representing SC. The main difference is the presence of a buffer between each processor and the memory. Since we assume that each processor issues its operations in program order, we use the buffer to model the fact that the operations are not necessarily issued in the same order to memory. The cancelled reply path from the buffer to the processor implies that a read is not allowed to return the value of a writeto the same location from the buffer. <br />		The conceptual system shown in the above figure is similar to that used for representing SC. The main difference is the presence of a buffer between each processor and the memory. Since we assume that each processor issues its operations in program order, we use the buffer to model the fact that the operations are not necessarily issued in the same order to memory. The cancelled reply path from the buffer to the processor implies that a read is not allowed to return the value of a writeto the same location from the buffer. <br />
	The IBM-370 model has two types of serialization instructions: special instructions that generate memory operations (e.g., compare-and-swap) and special non-memory instructions (e.g., a special branch)<ref>http://infolab.stanford.edu/pub/cstr/reports/csl/tr/95/685/CSL-TR-95-685.pdf</ref>		The IBM-370 model has two types of serialization instructions: special instructions that generate memory operations (e.g., compare-and-swap) and special non-memory instructions (e.g., a special branch)<ref name="Gharachorloo">http://infolab.stanford.edu/pub/cstr/reports/csl/tr/95/685/CSL-TR-95-685.pdf</ref>

	====''SPARC V8 Total Store Ordering (TSO)''====		====''SPARC V8 Total Store Ordering (TSO)''====