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

Pxu: /* MSI Protocol */

2012-03-19T01:28:35Z

MSI Protocol

← Older revision		Revision as of 01:28, 19 March 2012
Line 45:		Line 45:

	The state diagram of the MSI protocol is shown below. Note that the left part shows the response to processor-side requests, and the right part shows the response to snopper-side requests.		The state diagram of the MSI protocol is shown below. Note that the left part shows the response to processor-side requests, and the right part shows the response to snopper-side requests.
	~~<center>~~[[~~Image~~:MSInew.jpg]]~~</center>~~		[[File:MSInew.jpg\|600px\|thumb\|center\|MSI state transition diagram]]]

	==Synapse protocol==		==Synapse protocol==

Pxu: /* MOESI */

2012-03-19T01:27:34Z

MOESI

← Older revision		Revision as of 01:27, 19 March 2012
Line 257:		Line 257:


	<center>[[File:MOESI.jpg\|~~300px~~\|thumb\|center\|~~alt text~~]]</center>		<center>[[File:MOESI.jpg\|500px\|thumb\|center\|MOESI state transition diagram]]</center>

	~~<center>MOESI State Transition Diagram</center>~~
	<br />		<br />
	<br />		<br />

Pxu: /* MOESI */

2012-03-19T01:26:56Z

MOESI

← Older revision		Revision as of 01:26, 19 March 2012
Line 257:		Line 257:


	<center>[[~~Image~~:MOESI.jpg]]</center>		<center>[[File:MOESI.jpg\|300px\|thumb\|center\|alt text]]</center>

	<center>MOESI State Transition Diagram</center>		<center>MOESI State Transition Diagram</center>

Pxu: /* MOESI */

2012-03-19T01:26:05Z

MOESI

← Older revision		Revision as of 01:26, 19 March 2012
Line 257:		Line 257:


	<center>[[Image:~~MOESI_State_Transition_Diagram~~.jpg]]</center>		<center>[[Image:MOESI.jpg]]</center>

	<center> MOESI State ~~transition~~ Diagram</center>		<center>MOESI State Transition Diagram</center>
	<br />		<br />
	<br />		<br />
Line 274:		Line 274:

	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]




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

Pxu: /* MSI Protocol */

2012-03-19T01:23:51Z

MSI Protocol

← Older revision		Revision as of 01:23, 19 March 2012
Line 44:		Line 44:
	'''[http://en.wikipedia.org/wiki/MSI_protocol MSI]''' is a three-state write-back '''invalidation protocol''' which is one of the earliest snooping-based cache coherence-protocols. It marks the cache line in '''Modified (M) ,Shared (S)''' and '''Invalid (I)''' state. '''Invalid''' means the cache line is either not present or is invalid state. If the cache line is clean and is shared by more than one processor , it is marked '''shared'''. If cache line is dirty and the processor has exclusive ownership of the cache line, it is present in '''Modified''' state. BusRdx causes others to invalidate (demote) to '''I''' state. If it is present in '''M''' state in another cache, it will flush. A BusRdx, even if it causes a cache hit in '''S''' state, is promoted to '''M''' (upgrade) state.		'''[http://en.wikipedia.org/wiki/MSI_protocol MSI]''' is a three-state write-back '''invalidation protocol''' which is one of the earliest snooping-based cache coherence-protocols. It marks the cache line in '''Modified (M) ,Shared (S)''' and '''Invalid (I)''' state. '''Invalid''' means the cache line is either not present or is invalid state. If the cache line is clean and is shared by more than one processor , it is marked '''shared'''. If cache line is dirty and the processor has exclusive ownership of the cache line, it is present in '''Modified''' state. BusRdx causes others to invalidate (demote) to '''I''' state. If it is present in '''M''' state in another cache, it will flush. A BusRdx, even if it causes a cache hit in '''S''' state, is promoted to '''M''' (upgrade) state.

	The ~~following~~ state ~~transition~~ diagram ~~for~~ MSI protocol ~~explains~~ the ~~working of~~ the ~~protocol:~~		The state diagram of the MSI protocol is shown below. Note that the left part shows the response to processor-side requests, and the right part shows the response to snopper-side requests.

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

Pxu: /* MSI Protocol */

2012-03-19T01:21:22Z

MSI Protocol

← Older revision		Revision as of 01:21, 19 March 2012
Line 46:		Line 46:
	The following state transition diagram for MSI protocol explains the working of the protocol:		The following state transition diagram for MSI protocol explains the working of the protocol:

	<center>[[Image:~~MSI~~.jpg]]</center>		<center>[[Image:MSInew.jpg]]</center>



	==Synapse protocol==		==Synapse protocol==

Jcledfo3: /* MESI */

2012-03-18T20:50:01Z

MESI

← Older revision		Revision as of 20:50, 18 March 2012
Line 65:		Line 65:
	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>]]

	==MESI==		==[http://en.wikipedia.org/wiki/MESI_protocol MESI]==
	The main drawback of MSI is that each read-write sequence incurs two bus transactions irrespective of whether the cache line is stored in only one cache or not. Highly parallel programs that have little data sharing suffer the most from this. ~~'''[http://en.wikipedia.org/wiki/MESI_protocol~~ MESI~~''']~~ protocol solves this problem by introducing the '''Exclusive''' state to distinguish between a cache line stored in multiple caches and a line stored in a single cache.		The main drawback of MSI is that each read-write sequence incurs two bus transactions irrespective of whether the cache line is stored in only one cache or not. Highly parallel programs that have little data sharing suffer the most from this. MESI protocol solves this problem by introducing the '''Exclusive''' state to distinguish between a cache line stored in multiple caches and a line stored in a single cache.
	Let us briefly see how the MESI protocol works. For a more detailed version refer Solihin textbook pg. 215.		Let us briefly see how the MESI protocol works. For a more detailed version refer Solihin textbook pg. 215.

Jcledfo3: /* Prefetching */

2012-03-18T20:49:15Z

Prefetching

← Older revision		Revision as of 20:49, 18 March 2012
Line 296:		Line 296:


	=Prefetching=		=[http://en.wikipedia.org/wiki/Instruction_prefetch Instruction Prefetching]=
	~~<br />~~



	Instruction prefetching is a technique used to speedup the execution of the program. But in multiprocessors, prefetching comes at the cost of performance. Due to prefetching, the data can be modified in such a way that the memory coherence protocol will not be able to handle the effects. In such situations software must use serializing instructions or cache-invalidation instructions to guarantee subsequent data accesses are coherent.		Instruction prefetching is a technique used to speedup the execution of the program. But in multiprocessors, prefetching comes at the cost of performance. Due to prefetching, the data can be modified in such a way that the memory coherence protocol will not be able to handle the effects. In such situations software must use serializing instructions or cache-invalidation instructions to guarantee subsequent data accesses are coherent.
	<br />		<br />

Jcledfo3: /* Implementation Complexities */

2012-03-18T20:47:05Z

Implementation Complexities

← Older revision		Revision as of 20:47, 18 March 2012
Line 353:		Line 353:


	~~=Implementation Complexities=~~		=Word Invalidation=
	==Word Invalidation==
	One complexity problem applying to a number of the protocols deals with invalidation. In newer protocols, individual words may be modified in a cache line, as opposed to the entirety of the line. The other processors will thus have a mostly correct cache line, with only a word difference. This leads to potential complexity, because to 'correct' the error the other processors must transition from shared to invalid, where they then can read the correct word from the bus and place it back into the line, transitioning back into shared. This transition is potentially unnecessary, as the second processor may never access the specific word changed, but it may access other words in the cache line. One potential solution to this is being researched at the present time, advancing the protocols so that a cache line is "not invalidated on the first dirty word, but after the number of dirty words crosses some predetermined value, which is data type and application dependent." In other words, if the application can possibly have multiple words 'incorrect,' several transitions to and from the invalid state may be avoided.		One complexity problem applying to a number of the protocols deals with invalidation. In newer protocols, individual words may be modified in a cache line, as opposed to the entirety of the line. The other processors will thus have a mostly correct cache line, with only a word difference. This leads to potential complexity, because to 'correct' the error the other processors must transition from shared to invalid, where they then can read the correct word from the bus and place it back into the line, transitioning back into shared. This transition is potentially unnecessary, as the second processor may never access the specific word changed, but it may access other words in the cache line. One potential solution to this is being researched at the present time, advancing the protocols so that a cache line is "not invalidated on the first dirty word, but after the number of dirty words crosses some predetermined value, which is data type and application dependent." In other words, if the application can possibly have multiple words 'incorrect,' several transitions to and from the invalid state may be avoided.
	<br/>Source: http://tab.computer.org/tcca/NEWS/sept96/dsmideas.ps		<br/>Source: http://tab.computer.org/tcca/NEWS/sept96/dsmideas.ps

Jcledfo3: /* Real Architectures using Synapse */

2012-03-18T20:42:02Z

Real Architectures using Synapse

← Older revision		Revision as of 20:42, 18 March 2012
Line 59:		Line 59:
	Nothing can be found on an any actual architecture using the Synapse cache-coherence protocol. From the abstract of the paper written by Steve Frank and Armond Inselberg in 1984, "[http://dl.acm.org/citation.cfm?id=1499317 Synapse Tightly Coupled Multiprocessors: A New Approach to Solve Old Problems]", Synapse was theoretical.		Nothing can be found on an any actual architecture using the Synapse cache-coherence protocol. From the abstract of the paper written by Steve Frank and Armond Inselberg in 1984, "[http://dl.acm.org/citation.cfm?id=1499317 Synapse Tightly Coupled Multiprocessors: A New Approach to Solve Old Problems]", Synapse was theoretical.
	<br/>		<br/>

			The [http://www.disi.unige.it/person/DelzannoG/CacheProtocol/synapse.hy The BABYLON Project] did one example of a Synapse cache coherence protocol with atomic synchronization actions.

	===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>]]