CSC/ECE 506 Spring 2012/8a fu - Revision history

Jcledfo3: /* Performance: MOESI vs MEI/MESI */

2012-03-25T22:21:55Z

Performance: MOESI vs MEI/MESI

← Older revision		Revision as of 22:21, 25 March 2012
Line 407:		Line 407:

	Source: [http://www.lexisnexis.com.www.lib.ncsu.edu:2048/hottopics/lnacademic/?shr=t&csi=155278&sr=HLEAD%28Architects+wrestle+with+multiprocessor+options%29+and+date+is+August%2C%202001 Edwards, Chris (08/06/2001). "Architects wrestle with multiprocessor options". Electronic engineering times (0192-1541), (1178), p. 48.]		Source: [http://www.lexisnexis.com.www.lib.ncsu.edu:2048/hottopics/lnacademic/?shr=t&csi=155278&sr=HLEAD%28Architects+wrestle+with+multiprocessor+options%29+and+date+is+August%2C%202001 Edwards, Chris (08/06/2001). "Architects wrestle with multiprocessor options". Electronic engineering times (0192-1541), (1178), p. 48.]
			<br/>
			<br/>

	=References=		=References=

Jcledfo3: /* Word Invalidation */

2012-03-25T22:21:38Z

Word Invalidation

← Older revision		Revision as of 22:21, 25 March 2012
Line 398:		Line 398:

	In essence, the solution proposed here is to advance the MOESI protocol with word invalidation and specific treatment of temporal and spatial data, so that the block is not invalidated.		In essence, the solution proposed here is to advance the MOESI protocol with word invalidation and specific treatment of temporal and spatial data, so that the block is not invalidated.
			<br/>
			<br/>

	=Performance: MOESI vs MEI/MESI=		=Performance: MOESI vs MEI/MESI=

Jcledfo3: /* Instruction Prefetching */

2012-03-25T22:21:22Z

Instruction Prefetching

← Older revision		Revision as of 22:21, 25 March 2012
Line 389:		Line 389:
	<br/>		<br/>
	Another optimization considered for bus-based multiprocessors is cache-injection. In cache-injection, a cache uses prefetching to predict it's future needs by placing the address of the data expected in a injection table to initiate the read bus transaction. Once the data is produced, a write-back bus transaction is initiated, and all other caches snoop the bus for an injection table hit to determine if they should store the data.[[#References\|<sup>[29]</sup>]] Cache-injection can be implemented on any bus-based cache coherency protocol, supplying support for cache prefetching, [http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1160&context=ecetr data forwarding]. Section 4.2 of [[#References\|[29]]] walks through an in-depth example of using cache-injection on a MESI write-back invalidation cache.		Another optimization considered for bus-based multiprocessors is cache-injection. In cache-injection, a cache uses prefetching to predict it's future needs by placing the address of the data expected in a injection table to initiate the read bus transaction. Once the data is produced, a write-back bus transaction is initiated, and all other caches snoop the bus for an injection table hit to determine if they should store the data.[[#References\|<sup>[29]</sup>]] Cache-injection can be implemented on any bus-based cache coherency protocol, supplying support for cache prefetching, [http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1160&context=ecetr data forwarding]. Section 4.2 of [[#References\|[29]]] walks through an in-depth example of using cache-injection on a MESI write-back invalidation cache.
			<br/>
			<br/>

	=Word Invalidation=		=Word Invalidation=

Jcledfo3: /* Instruction Prefetching */

2012-03-25T22:16:37Z

Instruction Prefetching

← Older revision		Revision as of 22:16, 25 March 2012
Line 380:		Line 380:
	<br/>		<br/>
	Prefetching's optimization is that it brings additional blocks into cache that are surrounding blocks currently being hit by the processor. [[#References\|[28]]] states that simply increasing the hit ratio does not automatically improve overall performance in multiprocessor computation. Prefetching can actually produce stalls on individual CPUs of multiprocessor systems, as the hit ratio benefit will only apply to the thread currently benefiting from the prefetch, and it will have to wait for other threads to catch up. [[#References\|[28]]] suggests that overlapping prefetching decision-making time with user process time as much as possible to minimize the impact of the overall execution sequence as one attempt to implement prefetching within multiprocessor systems.		Prefetching's optimization is that it brings additional blocks into cache that are surrounding blocks currently being hit by the processor. [[#References\|[28]]] states that simply increasing the hit ratio does not automatically improve overall performance in multiprocessor computation. Prefetching can actually produce stalls on individual CPUs of multiprocessor systems, as the hit ratio benefit will only apply to the thread currently benefiting from the prefetch, and it will have to wait for other threads to catch up. [[#References\|[28]]] suggests that overlapping prefetching decision-making time with user process time as much as possible to minimize the impact of the overall execution sequence as one attempt to implement prefetching within multiprocessor systems.
			<br/>
			<br/>
			Due to prefetching in multiprocessor systems, the data can be modified in such a way that the memory coherence protocol will not be able to handle the effects, and software must use serializing or cache-invalidation instructions to guarantee subsequent data accesses are coherent. Take for example a [http://en.wikipedia.org/wiki/Page_table page-table] update followed by accesses to the physical pages referenced by the updated page tables. The following is a sequence in which software changes the translation of virtual-page A from physical-page M to physical-page N, which can lead to prefetching of incorrect data: 1) The tables that translate virtual-page A to physical-page M are now held only in main memory and the copies in the cache are invalidated. 2) Page-table entry is changed by the software for virtual-page A in main memory to point to physical page N rather than physical-page M. 3) Data in virtual-page A is accessed.
			<br/>
			<br/>
			Software expects the processor to access the data from physical-page N after the update. However, it is possible for the processor to prefetch the data from physical-page M before the page table for virtual page A is updated because the processor is unable to recognize that coherence checking is needed. Without coherence checking, it will be assumed that it is safe to prefetch the data. Similar behavior can occur when instructions are prefetched from beyond the page-table update instruction. Special instructions are provided by prefetching software (executed immediately after the page-table update) to ensure that subsequent instruction fetches and data accesses use the correct virtual-page-to-physical-page translation. It is not necessary to perform a [http://en.wikipedia.org/wiki/Translation_lookaside_buffer TLB] invalidation operation preceding the table update.
	<br/>		<br/>
	<br/>		<br/>

Jcledfo3: /* References */

2012-03-25T22:05:37Z

References

← Older revision		Revision as of 22:05, 25 March 2012
Line 427:		Line 427:
	# Yan Solihin, "Fundamentals of Parallel Computer Architecture," Solihin Publishing & Consulting LLC, 2008, pp. 168-173.		# Yan Solihin, "Fundamentals of Parallel Computer Architecture," Solihin Publishing & Consulting LLC, 2008, pp. 168-173.
	# David F. Kotz and Carla Schlatter Ellis, "Prefetching in File Systems for MIMD Multiprocessors," in IEEE Transactions on Parallel and Distributed Systems, Vol. 1, No. 2, April 1990, pp. 218-230.		# David F. Kotz and Carla Schlatter Ellis, "Prefetching in File Systems for MIMD Multiprocessors," in IEEE Transactions on Parallel and Distributed Systems, Vol. 1, No. 2, April 1990, pp. 218-230.
	# [http://www.ece.uah.edu/~milenka/docs/apads98.pdf cache-injection		# [http://www.ece.uah.edu/~milenka/docs/apads98.pdf cache-injection 1998]

Jcledfo3: /* Dragon Protocol */

2012-03-25T22:03:07Z

Dragon Protocol

← Older revision		Revision as of 22:03, 25 March 2012
Line 368:		Line 368:

	The Dragon protocol implements snoopy caches that provided the appearance of a uniform memory space to multiple processors. Here, each cache listens to 2 buses: the processor bus and the memory bus. The caches are also responsible for address translation, so the processor bus carries virtual addresses and the memory bus carries physical addresses. The Dragon system was designed to support 4 to 8 Dragon processors.		The Dragon protocol implements snoopy caches that provided the appearance of a uniform memory space to multiple processors. Here, each cache listens to 2 buses: the processor bus and the memory bus. The caches are also responsible for address translation, so the processor bus carries virtual addresses and the memory bus carries physical addresses. The Dragon system was designed to support 4 to 8 Dragon processors.
			<br/>
			<br/>

	=[http://en.wikipedia.org/wiki/Instruction_prefetch Instruction Prefetching]=		=[http://en.wikipedia.org/wiki/Instruction_prefetch Instruction Prefetching]=

Jcledfo3: /* Implementation Complexities */

2012-03-25T22:02:43Z

Implementation Complexities

← Older revision		Revision as of 22:02, 25 March 2012
Line 355:		Line 355:

	You can find more information on how this is implemented and various other ways of optimizations in this manual [http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/40546.pdf Software Optimization guide for AMD 10h Processors]		You can find more information on how this is implemented and various other ways of optimizations in this manual [http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/40546.pdf Software Optimization guide for AMD 10h Processors]
			<br/>
			<br/>

	==Dragon Protocol==		==Dragon Protocol==

Jcledfo3: /* Implementation Complexities */

2012-03-25T22:02:17Z

Implementation Complexities

← Older revision		Revision as of 22:02, 25 March 2012
Line 171:		Line 171:

	===Implementation Complexities===		===Implementation Complexities===
	One implementation complexity already mentioned is the inefficiency of task migration in MESI that the ARM MPCore addresses.[[#References\|<sup>[19]</sup>]] Another possible implementation complexity is found during the replacement of a cache line: one possible MESI implementation requires a message to be sent to main memory when a cache line is flushed (i.e. an E to I transition), as the line was exclusively in one cache before it was removed. It is possible to avoid this replacement message if the system is designed so that the flush of a modified (exclusive) line requires an acknowledgment from main memory. However, this requires the flush to be stored in a 'write-back' buffer until the reply arrives (to ensure the change is successfully propagated to memory).[[#References\|<sup>[23]</sup>]]<br/>		One implementation complexity already mentioned is the inefficiency of task migration in MESI that the ARM MPCore addresses.[[#References\|<sup>[19]</sup>]] Another possible implementation complexity is found during the replacement of a cache line: one possible MESI implementation requires a message to be sent to main memory when a cache line is flushed (i.e. an E to I transition), as the line was exclusively in one cache before it was removed. It is possible to avoid this replacement message if the system is designed so that the flush of a modified (exclusive) line requires an acknowledgment from main memory. However, this requires the flush to be stored in a 'write-back' buffer until the reply arrives (to ensure the change is successfully propagated to memory).[[#References\|<sup>[23]</sup>]]
			<br/>
			<br/>

	==MESIF==		==MESIF==

Jcledfo3: /* Implementation Complexities */

2012-03-25T22:01:59Z

Implementation Complexities

← Older revision		Revision as of 22:01, 25 March 2012
Line 74:		Line 74:
	===Implementation Complexities===		===Implementation Complexities===
	In the Synapse system, memory contention is reduced by designing a processor cache employing a non-write-through algorithm to minimized bandwidth between cache and shared memory. The Synapse Expansion Bus includes an ownership level protocol between processor caches.[[#References\|<sup>[24]</sup>]]		In the Synapse system, memory contention is reduced by designing a processor cache employing a non-write-through algorithm to minimized bandwidth between cache and shared memory. The Synapse Expansion Bus includes an ownership level protocol between processor caches.[[#References\|<sup>[24]</sup>]]
			<br/>
			<br/>

	==[http://en.wikipedia.org/wiki/MESI_protocol MESI]==		==[http://en.wikipedia.org/wiki/MESI_protocol MESI]==

Jcledfo3: /* Real Architectures using MSI */

2012-03-25T22:01:48Z

Real Architectures using MSI

← Older revision		Revision as of 22:01, 25 March 2012
Line 54:		Line 54:

	With the simple rules of '''[http://en.wikipedia.org/wiki/MSI_protocol MSI]'''protocol enforced by hardware, efficient synchronization and efficient data sharing are achieved in a simple shared memory model of parallel processing in the 4D-MP graphics superworkstation.		With the simple rules of '''[http://en.wikipedia.org/wiki/MSI_protocol MSI]'''protocol enforced by hardware, efficient synchronization and efficient data sharing are achieved in a simple shared memory model of parallel processing in the 4D-MP graphics superworkstation.


	===Implementation Complexities===		===Implementation Complexities===