CSC/ECE 506 Spring 2011/ch8 cl - Revision history

Laddaga: Undo revision 60323 by Laddaga (talk)

2012-03-21T20:36:43Z

Undo revision 60323 by Laddaga (talk)

← Older revision		Revision as of 20:36, 21 March 2012
Line 53:		Line 53:
	<center>[[Image:MSI.jpg]]</center>		<center>[[Image:MSI.jpg]]</center>

			===Implementation complexities===
			In the MSI system, an explicit upgrade message is required for a read followed by a write, even if there are no other sharers. When a processor reads in and modifies a data item, two bus transactions are generated in this protocol even in the absence of sharers. The first is a BusRd that gets the memory block in S state, and the second is a BusRdX(or BusUpgr) that converts the blcok from S to M state. In this protocol, the complexity of the mechanism that determines the exclusiveness of the block is an aspect that needs attention. Also, in snoop-based cache-coherence protocols, the overall set of actions for memory operations is not atomic. This could lead to race conditions, and the issues of deadlock, serialization, etc. make it harder to implement.

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

Laddaga: Undo revision 60321 by Laddaga (talk)

2012-03-21T07:59:10Z

Undo revision 60321 by Laddaga (talk)

← Older revision		Revision as of 07:59, 21 March 2012
Line 53:		Line 53:
	<center>[[Image:MSI.jpg]]</center>		<center>[[Image:MSI.jpg]]</center>

	~~===Implementation complexities===~~
	In the MSI system, an explicit upgrade message is required for a read followed by a write, even if there are no other sharers. When a processor reads in and modifies a data item, two bus transactions are generated in this protocol even in the absence of sharers. The first is a BusRd that gets the memory block in S state, and the second is a BusRdX(or BusUpgr) that converts the blcok from S to M state. In this protocol, the complexity of the mechanism that determines the exclusiveness of the block is an aspect that needs attention. Also, in snoop-based cache-coherence protocols, the overall set of actions for memory operations is not atomic. This could lead to race conditions, and the issues of deadlock, serialization, etc. make it harder to implement.

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

Laddaga: /* MSI Protocol */

2012-03-21T07:56:36Z

MSI Protocol

← Older revision		Revision as of 07:56, 21 March 2012
Line 53:		Line 53:
	<center>[[Image:MSI.jpg]]</center>		<center>[[Image:MSI.jpg]]</center>

			===Implementation complexities===
			In the MSI system, an explicit upgrade message is required for a read followed by a write, even if there are no other sharers. When a processor reads in and modifies a data item, two bus transactions are generated in this protocol even in the absence of sharers. The first is a BusRd that gets the memory block in S state, and the second is a BusRdX(or BusUpgr) that converts the blcok from S to M state. In this protocol, the complexity of the mechanism that determines the exclusiveness of the block is an aspect that needs attention. Also, in snoop-based cache-coherence protocols, the overall set of actions for memory operations is not atomic. This could lead to race conditions, and the issues of deadlock, serialization, etc. make it harder to implement.

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

Admin: /* Prefetching */

2012-03-13T01:45:43Z

Prefetching

← Older revision		Revision as of 01:45, 13 March 2012
Line 264:		Line 264:
	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 />
	An example of this type of a situation is a page-table update followed by accesses to the physical pages referenced by the updated page tables. The physical-memory references for the page tables are different than the physical-memory references for the data. Because of prefetching there ~~maybe problem~~ with correctness. The following sequence of events shows such a situation when software changes the translation of virtual-page A from physical-page M to physical-page N:		An example of this type of a situation is a page-table update followed by accesses to the physical pages referenced by the updated page tables. The physical-memory references for the page tables are different than the physical-memory references for the data. Because of prefetching there may be problems with correctness. The following sequence of events shows such a situation when software changes the translation of virtual-page A from physical-page M to physical-page N:
	# The tables that translate virtual-page A to physical-page M are now held only in main memory. The copies in the cache ae invalidated.		# The tables that translate virtual-page A to physical-page M are now held only in main memory. The copies in the cache ae invalidated.
	# 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.		# 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.
	# Data in virtual-page A is accessed.		# Data in virtual-page A is accessed.

	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 physical-memory references are different, the processor does not recognize them as requiring coherence checking and believes it is safe to prefetch the data from virtual-page A, which is translated into a read from physical page M. Similar behavior can occur when instructions are prefetched from beyond the page table update instruction.		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 physical-memory references are different, the processor does not recognize them as requiring coherence checking and believes it is safe to prefetch the data from virtual-page A, which is translated into a read from physical page M. Similar behavior can occur when instructions are prefetched from beyond the page-table update instruction.

	In order to prevent errors from occurring, there are special instructions provided by prefetching software which is 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 TLB invalidation operation preceding the table update.		In order to prevent errors from occurring, there are special instructions provided by prefetching software which is 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 TLB invalidation operation preceding the table update.

	More information can be found about this in [http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/24593.pdf AMD64 Architecture Programmer's manual]		More information can be found about this in [http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/24593.pdf AMD64 Architecture Programmer's manual]




	= CMP Implementation in Intel Architecture =		= CMP Implementation in Intel Architecture =

Admin at 01:40, 13 March 2012

2012-03-13T01:40:00Z

← Older revision		Revision as of 01:40, 13 March 2012
Line 8:		Line 8:


	At any point in logical time, the permissions for a cache block can allow either a single writer or multiple readers. The '''''coherence protocol''''' ensures the invariants of the states are maintained. The different coherent states used by most of the cache ~~coherent~~ protocols are as shown in ''Table 1'':		At any point in logical time, the permissions for a cache block can allow either a single writer or multiple readers. The '''''coherence protocol''''' ensures the invariants of the states are maintained. The different coherent states used by most of the cache coherence protocols are as shown in ''Table 1'':

	{\| class="wikitable" border="1"		{\| class="wikitable" border="1"

Cslingaf: added in the performance section (missed it when I was first writing the chapter)

2011-03-27T15:46:09Z

added in the performance section (missed it when I was first writing the chapter)

← Older revision		Revision as of 15:46, 27 March 2011
Line 330:		Line 330:


	In essence, the solution proposed here is to advance		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.
	the MOESI protocol with word invalidation and specific
	treatment of temporal and spatial data, so that the block
	is not ~~invalidated~~		=Performance: MOESI vs MEI/MESI=
			Early multiprocessors (such as the PowerPC processors) were designed to work with three states (Modified, Exclusive, Invalid - this is similar to the MSI protocol discussed earlier, the term MEI is used to remain consistent with the sources used for reference). As time progressed, more multi-processors transitioned to the MESI protocol. This is most likely due to the characteristics of MEI - it is "easy to implement but leads to inefficiencies in the way that memory bus bandwidth is used" [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 source]. As a result, systems with two or more MEI processors (most likely) will not see the 'full' potential of the extra processors, due to the inefficient bus transactions.

			In contrast, the five-state protocol MOESI is more complex to implement than MESI and MEI/MSI. However, advantages arise from using it. As Any Keane (VP of Marketing for PMC-Sierra) put it "this [fifth] state allows shared data that is dirty to remain in the cache. Without this state, any shared line would be written back to memory to change the original state form modified. Since we have a dedicated, fast path from CPU to CPU, this state maximizes the use of this path rather than the path to memory, which is inherently slower" [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 source]. This advantage can be implemented by allowing MOESI to make some processor to processor transfers from level 2 caches.

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

	=References=		=References=

Cslingaf at 19:23, 20 March 2011

2011-03-20T19:23:51Z

← Older revision		Revision as of 19:23, 20 March 2011
Line 2:		Line 2:


	==SMP ~~Protocol~~==		==SMP Architecture==
	Most parallel software in the commercial market relies on the shared-memory programming model in which all processors access the same physical address space. And the most common multiprocessors today use [http://en.wikipedia.org/wiki/Symmetric_multiprocessing SMP] architecture which use a common bus as the interconnect. In the case of multicore processors ("chip multiprocessors," or CMP) the SMP architecture applies to the cores treating them as separate processors. The key problem of shared-memory multiprocessors is providing a consistent view of memory with various cache hierarchies. This is called '''''cache coherence problem'''''. It is critical to achieve correctness and performance-sensitive design point for supporting the shared-memory model. The cache coherence mechanisms not only govern communication in a shared-memory multiprocessor, but also typically determine how the memory system transfers data between processors, caches, and memory.		Most parallel software in the commercial market relies on the shared-memory programming model in which all processors access the same physical address space. And the most common multiprocessors today use [http://en.wikipedia.org/wiki/Symmetric_multiprocessing SMP] architecture which use a common bus as the interconnect. In the case of multicore processors ("chip multiprocessors," or CMP) the SMP architecture applies to the cores treating them as separate processors. The key problem of shared-memory multiprocessors is providing a consistent view of memory with various cache hierarchies. This is called '''''cache coherence problem'''''. It is critical to achieve correctness and performance-sensitive design point for supporting the shared-memory model. The cache coherence mechanisms not only govern communication in a shared-memory multiprocessor, but also typically determine how the memory system transfers data between processors, caches, and memory.

Cslingaf at 19:22, 20 March 2011

2011-03-20T19:22:52Z

← Older revision		Revision as of 19:22, 20 March 2011
Line 325:		Line 325:
	<br/>Source: http://rsim.cs.illinois.edu/rsim/Manual/node109.html		<br/>Source: http://rsim.cs.illinois.edu/rsim/Manual/node109.html

	==~~MOESI~~==		==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.
			<br/>Source: http://tab.computer.org/tcca/NEWS/sept96/dsmideas.ps


			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

	=References=		=References=

Cslingaf at 19:12, 20 March 2011

2011-03-20T19:12:15Z

← Older revision		Revision as of 19:12, 20 March 2011
Line 320:		Line 320:


	=Implementation Complexities of MESI=		=Implementation Complexities=
			==MESI==
	There are two possible causes of complexity with the MESI protocol during replacement of a cache line. Some MESI implementations require a message to be sent to memory when a cache line is flushed - 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 the 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).		There are two possible causes of complexity with the MESI protocol during replacement of a cache line. Some MESI implementations require a message to be sent to memory when a cache line is flushed - 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 the 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).
	<br/>Source: http://rsim.cs.illinois.edu/rsim/Manual/node109.html		<br/>Source: http://rsim.cs.illinois.edu/rsim/Manual/node109.html

			==MOESI==


	=References=		=References=

Cslingaf at 19:08, 20 March 2011

2011-03-20T19:08:02Z

← Older revision		Revision as of 19:08, 20 March 2011
Line 322:		Line 322:
	=Implementation Complexities of MESI=		=Implementation Complexities of MESI=
	There are two possible causes of complexity with the MESI protocol during replacement of a cache line. Some MESI implementations require a message to be sent to memory when a cache line is flushed - 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 the 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).		There are two possible causes of complexity with the MESI protocol during replacement of a cache line. Some MESI implementations require a message to be sent to memory when a cache line is flushed - 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 the 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).
	Source: http://rsim.cs.illinois.edu/rsim/Manual/node109.html		<br/>Source: http://rsim.cs.illinois.edu/rsim/Manual/node109.html

	=References=		=References=