CSC/ECE 506 Spring 2011/ch10 sb - Revision history

Admin: /* '''Comparison Between different models''' */

2011-05-02T04:19:30Z

'''Comparison Between different models'''

← Older revision		Revision as of 04:19, 2 May 2011
Line 240:		Line 240:


	='''Comparison Between ~~different models~~'''=		='''Comparison Between Different Models'''=
	In this section we will consider the comparison made between different consistency models in Performance Evaluation of Memory Consistency Models for Shared-Memory Multiprocessors by Kourosh Gharachorloo, Anoop Gupta, and John Hennessy.		In this section we will consider the comparison made between different consistency models in Performance Evaluation of Memory Consistency Models for Shared-Memory Multiprocessors by Kourosh Gharachorloo, Anoop Gupta, and John Hennessy.
	Architecture used		Architecture used

Admin: /* '''Eager Release Consistency Model''' */

2011-05-02T04:17:15Z

'''Eager Release Consistency Model'''

← Older revision		Revision as of 04:17, 2 May 2011
Line 197:		Line 197:
	==='''Release Consistency Models'''===		==='''Release Consistency Models'''===
	===='''Eager Release Consistency Model'''====		===='''Eager Release Consistency Model'''====
	In Eager Release Consistency Model , the invalidations (or write notices) are propagated at release points. '''Munin's write shared protocol''' proposed by '''John K. Bennett, John B. Carter, and ~~WiUy~~ Zwaenepoel''' of Rice University implemented this Eager Release Consistency Model. It is a software implementation of Release consistency Model which buffers writes until a release, instead of pipelining them as in the DASH implementation. At the release all writes going to the same destination are merged into a single message. This is illustrated in the following diagram:		In Eager Release Consistency Model , the invalidations (or write notices) are propagated at release points. '''Munin's write shared protocol''' proposed by '''John K. Bennett, John B. Carter, and Willy Zwaenepoel''' of Rice University implemented this Eager Release Consistency Model. It is a software implementation of Release consistency Model which buffers writes until a release, instead of pipelining them as in the DASH implementation. At the release all writes going to the same destination are merged into a single message. This is illustrated in the following diagram:
	<center> [[Image:munin.jpg]] </center>		<center> [[Image:munin.jpg]] </center>

Admin: /* '''Relax Read to Read and Read to Write program orders''' */

2011-05-02T04:15:23Z

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

← Older revision		Revision as of 04:15, 2 May 2011
Line 157:		Line 157:
	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).		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).

	==='''Relax Read to Read and Read to Write program orders'''===		==='''Relax Read-to-Read and Read-to-Write program orders'''===
	This model sheds the restriction on program order between all operations, including read to read and read followed by write to different locations . This flexibility provides the possibility of hiding the latency of read operations by implementing true non-blocking reads in the context of either static (in-order) or dynamic (out-of-order) scheduling processors, supported by techniques such as non-blocking (lockup-free) caches and speculative execution. The compiler also has full flexibility to reorder operations.<br />		This model sheds the restriction on program order between all operations, including read to read and read followed by write to different locations . This flexibility provides the possibility of hiding the latency of read operations by implementing true non-blocking reads in the context of either static (in-order) or dynamic (out-of-order) scheduling processors, supported by techniques such as non-blocking (lockup-free) caches and speculative execution. The compiler also has full flexibility to reorder operations.<br />
	'''Weak ordering (WO)''', '''Release consistency (RC)''', '''DEC Alpha''', '''Relaxed Memory Order (RMO)''', and '''PowerPC''' are examples of this model, with the last three models for commercial architectures. Except for Alpha,all the other models allow reordering of two reads to the same location. <br />		'''Weak ordering (WO)''', '''Release consistency (RC)''', '''DEC Alpha''', '''Relaxed Memory Order (RMO)''', and '''PowerPC''' are examples of this model, with the last three models for commercial architectures. Except for Alpha,all the other models allow reordering of two reads to the same location. <br />
Line 187:		Line 187:

	The IBM PowerPC model exposes multiple-copy semantics of memory to the programmer as shown in the conceptual system above. Safety net fence instruction is called SYNC which is similar to the MB fence instruction of the Alpha systems. However, SYNC between two reads allows to occur out of program order. Also PowerPC allows a write to be seen early by another processor’s read. Hence a read-modify-write operation may be needed to enforce program order between two reads to the same location as well as to make writes appear atomic.		The IBM PowerPC model exposes multiple-copy semantics of memory to the programmer as shown in the conceptual system above. Safety net fence instruction is called SYNC which is similar to the MB fence instruction of the Alpha systems. However, SYNC between two reads allows to occur out of program order. Also PowerPC allows a write to be seen early by another processor’s read. Hence a read-modify-write operation may be needed to enforce program order between two reads to the same location as well as to make writes appear atomic.



	=='''The Big Picture - Relationship Between Different Models'''==		=='''The Big Picture - Relationship Between Different Models'''==

Admin: /* '''Relax Write to Write program order''' */

2011-05-02T04:13:55Z

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

← Older revision		Revision as of 04:13, 2 May 2011
Line 145:		Line 145:
	# Before any write operation is allowed to perform with respect to any other processor, all previous reads and writes must have been performed. The two conditions above imply one important fact: only the read-after-write program order requirement is relaxed.		# Before any write operation is allowed to perform with respect to any other processor, all previous reads and writes must have been performed. The two conditions above imply one important fact: only the read-after-write program order requirement is relaxed.

	==='''Relax Write to Write program order'''===		==='''Relax Write-to-Write program order'''===
	The second category of relaxed models that we consider allow two writes to execute out of program order in addition to allowing the reordering of a write followed by a read. This relaxation enables a number of hardware optimizations, including write merging in a write buffer and overlapping multiple write misses, all of which can lead to a reodering of write operations. Therefore, write operations can be serviced at a much faster rate.		The second category of relaxed models that we consider allow two writes to execute out of program order in addition to allowing the reordering of a write followed by a read. This relaxation enables a number of hardware optimizations, including write merging in a write buffer and overlapping multiple write misses, all of which can lead to a reodering of write operations. Therefore, write operations can be serviced at a much faster rate.

Line 151:		Line 151:

	==== ''SPARC V8 Partial Store Ordering'' ====		==== ''SPARC V8 Partial Store Ordering'' ====
	The '''Partial Store Ordering'''('''PSO''') model is very ~~much~~ similar to the TSO model for SPARC V8. The figure below shows an identical conceptual system. There is only a slight difference in the program order, where writes to locations can be overlapped only if they are not to same locations. This is represented by the dashed line between the W's in the program order figure. Safety net for the program order is provided through a fence instruction, called the store barrier or STBAR, that may be used to enforce the program order between writes.<br />		The '''Partial Store Ordering'''('''PSO''') model is very similar to the TSO model for SPARC V8. The figure below shows an identical conceptual system. There is only a slight difference in the program order, where writes to locations can be overlapped only if they are not to same locations. This is represented by the dashed line between the W's in the program order figure. Safety net for the program order is provided through a fence instruction, called the store barrier or STBAR, that may be used to enforce the program order between writes.<br />
	[[Image:PSO.jpg]] <br />		[[Image:PSO.jpg]] <br />
	Let us consider an example from '''[http://infolab.stanford.edu/pub/cstr/reports/csl/tr/95/685/CSL-TR-95-685.pdf Technical Report by Kourosh Gharachorloo on Memory Consistency Models for shared-memory Multiprocessors]''' to demonstrate the working of PSO.<br />		Let us consider an example from '''[http://infolab.stanford.edu/pub/cstr/reports/csl/tr/95/685/CSL-TR-95-685.pdf Technical Report by Kourosh Gharachorloo on Memory Consistency Models for shared-memory Multiprocessors]''' to demonstrate the working of PSO.<br />

Admin: /* '''Relax Write to Read program order''' */

2011-05-02T04:11:49Z

'''Relax Write to Read program order'''

← Older revision		Revision as of 04:11, 2 May 2011
Line 98:		Line 98:
	Let us now see the consistency models in some of the real multiprocessor systems listed above. We will not introduce those topics that are already covered in Solihin's textbook, like Weak ordering and Processor consistency models. '''RCsc''' and '''RCpc'''. RCsc maintains sequential consistency among synchronization operations, while RCpc maintains processor consistency among synchronization operations.		Let us now see the consistency models in some of the real multiprocessor systems listed above. We will not introduce those topics that are already covered in Solihin's textbook, like Weak ordering and Processor consistency models. '''RCsc''' and '''RCpc'''. RCsc maintains sequential consistency among synchronization operations, while RCpc maintains processor consistency among synchronization operations.

	==='''Relax Write to Read program order'''===		==='''Relax Write-to-Read program order'''===
	Generally in all systems writes ~~takes~~ more time than ~~read~~. Based on this, the first category of relaxed models that we consider are those models that allow a write followed by a read to execute out of program order. The typical way hardware exploits this relaxation is through buffering writes and allowing a read to bypass the writes in the buffer. While maintaining sequential consistency typically requires the processor to wait for a previous write to complete before completing the next read operation, this optimization allows the processor to continue with a read without waiting for write operations to complete. As a result, the write latency can be effectively hidden. Furthermore, many applications function correctly(i.e., provide sequentially consistent results) even if the program order from a write to a read is not maintained.		Generally in all systems writes take more time than reads. Based on this, the first category of relaxed models that we consider are those models that allow a write followed by a read to execute out of program order. The typical way hardware exploits this relaxation is through buffering writes and allowing a read to bypass the writes in the buffer. While maintaining sequential consistency typically requires the processor to wait for a previous write to complete before completing the next read operation, this optimization allows the processor to continue with a read without waiting for write operations to complete. As a result, the write latency can be effectively hidden. Furthermore, many applications function correctly (i.e., provide sequentially consistent results) even if the program order from a write to a read is not maintained.

	Therefore, even though systems that exploit this optimization are not sequentially consistent, they appear sequentially consistent to a large class of programs.		Therefore, even though systems that exploit this optimization are not sequentially consistent, they appear sequentially consistent to a large class of programs.

Ssbengal: /* '''References''' */

2011-04-03T22:09:07Z

'''References'''

← Older revision		Revision as of 22:09, 3 April 2011
Line 356:		Line 356:
	# James R. Goodman. Cache consistency and sequential consistency. Technical Report 61, IEEE Scalable Coherent Interface (SCI) Working Group, March 1989.		# James R. Goodman. Cache consistency and sequential consistency. Technical Report 61, IEEE Scalable Coherent Interface (SCI) Working Group, March 1989.
	# Dan Lenoski, James Laudon, Kourosh Gharachorloo,Anoop Gupta, and John Hennessy. The directory-based cache coherence protocol for the DASH multiprocessor. In Proceedings of the 17th Annual International Symposium on Computer Architecture, May 1990.		# Dan Lenoski, James Laudon, Kourosh Gharachorloo,Anoop Gupta, and John Hennessy. The directory-based cache coherence protocol for the DASH multiprocessor. In Proceedings of the 17th Annual International Symposium on Computer Architecture, May 1990.
			#Jenny Mankin. Parallel Computing Memory Consistency Models: A Survey in Past and Present Research

Ssbengal: /* '''Comparison Between different models''' */

2011-04-03T22:05:00Z

'''Comparison Between different models'''

← Older revision		Revision as of 22:05, 3 April 2011
Line 301:		Line 301:

	<div style='width:1900px;'>[[Image:perf2.png\|370px]] [[Image:perf3.png\|370px]] [[Image:perf4.png\|370px]]</div>		<div style='width:1900px;'>[[Image:perf2.png\|370px]] [[Image:perf3.png\|370px]] [[Image:perf4.png\|370px]]</div>


			In another study Ronald Bos et al. investigated the performance benefits of relaxed consistency models on multiprocessors executing a process network application. They used a trace-driven simulator, developed using SystemC, to model the distributed shared memory system of a
			prototype multiprocessor developed at Philips called Philips '''[http://www.es.ele.tue.nl/epicurus/files/report_jvrijnsen.pdf CAKE]''' (a nonuniform, distributed shared memory multiprocessor prototype). The simulator offers two consistency models: Sequential Consistency (SC) and a generalized Relaxed Consistency (RC) model. Input traces were generated by running a process network application in a cycle-accurate simulator of the prototype multiprocessor. The results showed that relaxed consistency has marginal performance benefits over sequential consistency. The advantage of relaxed memory consistency decreases for increasing network latency. More information about this study can be found in this paper '''[http://ce.et.tudelft.nl/publicationfiles/915_463_bos.pdf Performance Benefits of Relaxed Memory Consistency for Process Network Applications]'''

	='''Some Shortcomings of Relaxed Models'''=		='''Some Shortcomings of Relaxed Models'''=

Ssbengal: /* '''Some Shortcomings of Relaxed Models''' */

2011-04-03T22:04:22Z

'''Some Shortcomings of Relaxed Models'''

← Older revision		Revision as of 22:04, 3 April 2011
Line 303:		Line 303:

	='''Some Shortcomings of Relaxed Models'''=		='''Some Shortcomings of Relaxed Models'''=
	~~The advantage of the less strict~~ models is increased ~~performance potential~~. The ~~disadvantage~~ is ~~increased hardware complexity and~~ a ~~more complex programming model~~. ~~To make an informed decision on~~ the ~~above tradeoff requires performance data for the various models.~~		Even though relaxed models enable desirable optimizations, their major drawback is increased programming complexity. Most programmers have implicit assumptions about the memory behavior of a shared-memory multiprocessor and use these assumptions when reasoning about the correctness of their programs. Correctness
	~~There were many experiments conducted to examine systems with non-bus interconnection networks and that use real programs as workloads~~.		problems arise when certain orders that are implicitly assumed by the programmer are not maintained by
			the underlying memory model. The advantage of sequential consistency is that no matter what implicit
			assumptions a programmer makes regarding the program order or atomicity of memory operations, SC
			conservatively maintains all such orders. Therefore, the programmer’s implicit assumptions are never
			violated.

	~~Kourosh Gharachorloo et al. at Stanford University compared the models of~~ sequential consistency, processor consistency, weak ordering, and release consistency for a DASH-like architecture '''([http://ra.ziti.uni-heidelberg.de/pages/lectures/hws06/ra2/script_pdf/dash.pdf Directory Architecture for Shared Memory])'''. The results show that in an environment where processor reads are blocking and ~~writes are buffered, a significant performance increase is achieved from allowing reads to bypass previous writes. Pipelining~~ of ~~writes, which determines the rate at which writes are retired from the write buffer, is of secondary importance~~. ~~As a result, they have showed that the sequential consistency model performs poorly relative to all other models, while the processor consistency model provides most~~ of ~~the benefits of the weak and release consistency models. It showed that~~ the relaxed models ~~can hide most of~~ the ~~write latency and can perform upto 41% better than sequential consistency. It also showed that~~ with ~~blocking reads, processor consistency performed as well as weak ordering~~ and ~~release consistency for most cases. This result is surprising because processor consistency only allows reads~~ to ~~bypass writes, whereas weak ordering and release consistency also allow writes to be pipelined~~. ~~Thus, potentially with processor consistency~~, the ~~write buffer could get full faster and the processor could~~ have ~~to block~~		In contrast to sequential consistency, relaxed memory models require programmers to abandon their
	~~often on writes. However~~, ~~with blocking reads~~, ~~much of~~ the ~~latency of writes is hidden behind~~ the ~~reads, and the write buffer does not block often. In one case, processor consistency even does better than weak ordering because weak ordering requires its synchronization reads~~ to ~~stall for previous write operations, whereas in processor consistency, reads are never stalled for previous writes~~. ~~More information about~~ the ~~experimentation and the evaluation results can be found~~ in ~~this paper : '''[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1~~.~~1.52.9935&rep=rep1&type=pdf Performance Evaluation of Memory Consistency Models for Shared-Memory Multiprocessors]'''~~		implicit and intuitive understanding of how memory behaves. Most of the relaxed models we have described
			require the programmer to reason with low level (and non-intuitive) reordering optimizations to understand
			the behavior of their programs. In addition, many of the models have been defined using complicated
			terminology, and in some cases, the original definitions have ambiguities which leave the semantics open to
			interpretation. These factors further exacerbate the difficulties in programming these models.

	~~Ronald Bos et al~~. ~~investigated~~ the performance ~~benefits~~ of ~~relaxed consistency models on multiprocessors executing~~ a ~~process network application~~. ~~They used a trace-driven simulator, developed using SystemC~~, ~~to model~~ the ~~distributed shared memory system~~ of a		Another difficulty with relaxed models is the lack of compatibility among the numerous models and
	~~prototype multiprocessor developed at Philips called Philips '''[http://www.es.ele.tue.nl/epicurus/files/report_jvrijnsen~~.~~pdf CAKE]''' (a nonuniform~~, ~~distributed shared memory multiprocessor prototype). The simulator offers two consistency~~ models~~: Sequential Consistency (SC) and~~ a ~~generalized Relaxed Consistency (RC) model~~. ~~Input traces were generated by running a process network application~~ in ~~a cycle-accurate simulator of the prototype~~ multiprocessor. The ~~results showed~~ that ~~relaxed consistency has marginal performance benefits over~~ sequential consistency. The advantage of relaxed memory consistency decreases for increasing network latency. More information about this study can be found in this paper '''[http://ce.et.tudelft.nl/publicationfiles/915_463_bos.pdf Performance Benefits of Relaxed Memory Consistency for Process Network Applications]'''		systems in existence. Many of the subtle differences among models make little difference in the actual
			performance of a model. However, such differences make the task of porting programs across different
	~~Most of the above studies evaluate runtime optimizations. These clearly show that there have not been any studies evaluating performance gains~~ for ~~the relaxed models due to compiler optimizations. Many researchers argue that the~~ performance ~~boost from implementing models~~ in the ~~class relaxing all orders is enough~~ to ~~justify the additional intellectual burden~~ the ~~relaxed~~		systems quite cumbersome. Similarly, the variety of models in existence make it difficult for programmers to
	~~models place on the middleware authors of complex commercial systems. The~~ performance ~~gained by using relaxed models does~~		adopt a programming methodology that works across a wide range of systems.
	~~not justify their~~ complexity. ~~More information about this can be found here : '''[http://www.cs.wisc.edu/multifacet/papers/computer98_sccase.pdf Multiprocessors Should Support Simple Memory-Consistency Models]'''~~		With all their shortcomings, relaxed models are widely used in many commercial multiprocessor systems,
			including systems designed by major computer manufacturers such as Digital Equipment, IBM, and Sun
			Microsystems. The wide-spread use of these systems suggests that even though sequential consistency is
			simpler to use for programmers, performance often plays an important role in the ultimate choice made by
			system designers and programmers. Nevertheless, we would ideally like to provide the extra performance
			with as little programming complexity as possible.

	='''References'''=		='''References'''=

Ssbengal: /* '''Some Shortcomings of Relaxed Models''' */

2011-04-03T22:03:06Z

'''Some Shortcomings of Relaxed Models'''

← Older revision		Revision as of 22:03, 3 April 2011
Line 240:		Line 240:
	More information about this experimentation and results can be obtained from their paper : '''[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 Lazy Release Consistency for Hardware-Coherent Multiprocessors]'''		More information about this experimentation and results can be obtained from their paper : '''[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 Lazy Release Consistency for Hardware-Coherent Multiprocessors]'''

	~~==='''Some Shortcomings of Relaxed Models'''===~~
	Even though relaxed models enable desirable optimizations, their major drawback is increased programming complexity. Most programmers have implicit assumptions about the memory behavior of a shared-memory multiprocessor and use these assumptions when reasoning about the correctness of their programs. Correctness
	~~problems arise when certain orders that are implicitly assumed by the programmer are not maintained by~~
	~~the underlying memory model. The advantage of sequential consistency is that no matter what implicit~~
	~~assumptions a programmer makes regarding the program order or atomicity of memory operations, SC~~
	~~conservatively maintains all such orders. Therefore, the programmer’s implicit assumptions are never~~
	~~violated.~~

	~~In contrast to sequential consistency, relaxed memory models require programmers to abandon their~~
	~~implicit and intuitive understanding of how memory behaves. Most of the relaxed models we have described~~
	~~require the programmer to reason with low level (and non-intuitive) reordering optimizations to understand~~
	~~the behavior of their programs. In addition, many of the models have been defined using complicated~~
	~~terminology, and in some cases, the original definitions have ambiguities which leave the semantics open to~~
	~~interpretation. These factors further exacerbate the difficulties in programming these models.~~

	~~Another difficulty with relaxed models is the lack of compatibility among the numerous models and~~
	~~systems in existence. Many of the subtle differences among models make little difference in the actual~~
	~~performance of a model. However, such differences make the task of porting programs across different~~
	~~systems quite cumbersome. Similarly, the variety of models in existence make it difficult for programmers to~~
	~~adopt a programming methodology that works across a wide range of systems.~~
	~~With all their shortcomings, relaxed models are widely used in many commercial multiprocessor systems,~~
	~~including systems designed by major computer manufacturers such as Digital Equipment, IBM, and Sun~~
	~~Microsystems. The wide-spread use of these systems suggests that even though sequential consistency is~~
	~~simpler to use for programmers, performance often plays an important role in the ultimate choice made by~~
	~~system designers and programmers. Nevertheless, we would ideally like to provide the extra performance~~
	~~with as little programming complexity as possible.~~

	='''Comparison Between different models'''=		='''Comparison Between different models'''=

Ssbengal: /* '''Performance of Consistency Models''' */

2011-04-03T22:02:25Z

'''Performance of Consistency Models'''

← Older revision		Revision as of 22:02, 3 April 2011
Line 327:		Line 327:
	<div style='width:1900px;'>[[Image:perf2.png\|370px]] [[Image:perf3.png\|370px]] [[Image:perf4.png\|370px]]</div>		<div style='width:1900px;'>[[Image:perf2.png\|370px]] [[Image:perf3.png\|370px]] [[Image:perf4.png\|370px]]</div>

	='''~~Performance~~ of ~~Consistency~~ Models'''=		='''Some Shortcomings of Relaxed Models'''=
	The advantage of the less strict models is increased performance potential. The disadvantage is increased hardware complexity and a more complex programming model. To make an informed decision on the above tradeoff requires performance data for the various models.		The advantage of the less strict models is increased performance potential. The disadvantage is increased hardware complexity and a more complex programming model. To make an informed decision on the above tradeoff requires performance data for the various models.
	There were many experiments conducted to examine systems with non-bus interconnection networks and that use real programs as workloads.		There were many experiments conducted to examine systems with non-bus interconnection networks and that use real programs as workloads.