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

Jdhartle: /* Special Coherence Considerations in AMD64 architectures */

2012-03-29T14:52:35Z

Special Coherence Considerations in AMD64 architectures

← Older revision		Revision as of 14:52, 29 March 2012
Line 286:		Line 286:
	<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 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:
	# 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 are 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.

Jdhartle: /* Introduction to bus-based cache coherence in real machines */

2012-03-29T14:41:57Z

Introduction to bus-based cache coherence in real machines

Cjkirkpa: /* Summary of Cache Coherence Protocols */

2012-03-28T17:06:16Z

Summary of Cache Coherence Protocols

← Older revision		Revision as of 17:06, 28 March 2012
Line 46:		Line 46:
	* '''Bus Read-Exclusive (BusRdX)''' The cache controller asks for a copy of the data it intends to modify and all other caches need to be invalidated		* '''Bus Read-Exclusive (BusRdX)''' The cache controller asks for a copy of the data it intends to modify and all other caches need to be invalidated
	* '''Writeback (BusWB)''' Main memory updates its contents		* '''Writeback (BusWB)''' Main memory updates its contents
	* '''Bus upgrade BusUpgr''' Bus upgrade obtains exclusive ownership and invalidates other copies bus does not return data to the requestor		* '''Bus upgrade (BusUpgr)''' Bus upgrade obtains exclusive ownership and invalidates other copies bus does not return data to the requestor

	==MSI==		==MSI==

Cjkirkpa: /* Summary of Cache Coherence Protocols */

2012-03-28T17:05:52Z

Summary of Cache Coherence Protocols

← Older revision		Revision as of 17:05, 28 March 2012
Line 43:		Line 43:
	The first widely adopted approach to cache coherence is snooping on a bus. Snooping entails each processor seeing or "snooping" all bus transactions. Common bus transactions are		The first widely adopted approach to cache coherence is snooping on a bus. Snooping entails each processor seeing or "snooping" all bus transactions. Common bus transactions are

	'''BusRd''' The cache controller asks for a copy of the data it does not intend to modify		* '''BusRd''' The cache controller asks for a copy of the data it does not intend to modify
	'''Bus Read-Exclusive (BusRdX)''' The cache controller asks for a copy of the data it intends to modify and all other caches need to be invalidated		* '''Bus Read-Exclusive (BusRdX)''' The cache controller asks for a copy of the data it intends to modify and all other caches need to be invalidated
	'''Writeback (BusWB)''' Main memory updates its contents		* '''Writeback (BusWB)''' Main memory updates its contents
	'''Bus upgrade BusUpgr''' Bus upgrade obtains exclusive ownership and invalidates other copies bus does not return data to the requestor		* '''Bus upgrade BusUpgr''' Bus upgrade obtains exclusive ownership and invalidates other copies bus does not return data to the requestor

	==MSI==		==MSI==

Cjkirkpa: /* Summary of Cache Coherence Protocols */

2012-03-28T17:05:07Z

Summary of Cache Coherence Protocols

← Older revision		Revision as of 17:05, 28 March 2012
Line 41:		Line 41:
	<br />		<br />
	<br />		<br />
	The first widely adopted approach to cache coherence is snooping on a bus. ~~We will now discuss them in details in~~ the ~~following sections.~~		The first widely adopted approach to cache coherence is snooping on a bus. Snooping entails each processor seeing or "snooping" all bus transactions. Common bus transactions are

			'''BusRd''' The cache controller asks for a copy of the data it does not intend to modify
			'''Bus Read-Exclusive (BusRdX)''' The cache controller asks for a copy of the data it intends to modify and all other caches need to be invalidated
			'''Writeback (BusWB)''' Main memory updates its contents
			'''Bus upgrade BusUpgr''' Bus upgrade obtains exclusive ownership and invalidates other copies bus does not return data to the requestor

	==MSI==		==MSI==

Cjkirkpa at 16:27, 28 March 2012

2012-03-28T16:27:27Z

Show changes

Cjkirkpa at 16:13, 28 March 2012

2012-03-28T16:13:12Z

Cjkirkpa: /* MESI */

2012-03-28T16:11:30Z

MESI

← Older revision		Revision as of 16:11, 28 March 2012
Line 54:		Line 54:
	MSI is the most basic cache coherence protocols, and also the easiest to implement. However, the MSI protocol requires that all state changes occur atomically to ensure cache coherency, and is therefore not recommended for real-world, complex systems.[http://books.google.com/books?id=eqSYY7CRWhoC&pg=PA107&lpg=PA107&dq=msi+cache++implementation&source=bl&ots=V3sO0fSt5a&sig=HmK3ntQ3daI7uTaowAgi7crVgcU&hl=en&sa=X&ei=2CRpT7rkMcWrsQKB8fmvCQ&ved=0CFoQ6AEwBg#v=onepage&q=msi%20cache%20%20implementation&f=true] Adding an exclusive, owner, or forwarding state to the architecture increases the cache coherence design complexity, but greatly improves performance. For this reason, most modern multiprocessors use a variant of MSI (MESI, MOSI, or MOESI). [http://en.wikipedia.org/wiki/MSI_protocol]		MSI is the most basic cache coherence protocols, and also the easiest to implement. However, the MSI protocol requires that all state changes occur atomically to ensure cache coherency, and is therefore not recommended for real-world, complex systems.[http://books.google.com/books?id=eqSYY7CRWhoC&pg=PA107&lpg=PA107&dq=msi+cache++implementation&source=bl&ots=V3sO0fSt5a&sig=HmK3ntQ3daI7uTaowAgi7crVgcU&hl=en&sa=X&ei=2CRpT7rkMcWrsQKB8fmvCQ&ved=0CFoQ6AEwBg#v=onepage&q=msi%20cache%20%20implementation&f=true] Adding an exclusive, owner, or forwarding state to the architecture increases the cache coherence design complexity, but greatly improves performance. For this reason, most modern multiprocessors use a variant of MSI (MESI, MOSI, or MOESI). [http://en.wikipedia.org/wiki/MSI_protocol]

	===MESI===		==MESI==
	'''[http://en.wikipedia.org/wiki/MSI_protocol MSI protocol]''' has a major drawback in that each read-write sequence incurs two bus transactions irrespective of whether the cache line is stored in only one cache or not. This is a huge setback for highly parallel programs that have little data sharing. '''[http://en.wikipedia.org/wiki/MESI_protocol MESI'''] protocol solves this problem by introducing the E ('''Exclusive''') state to distinguish between a cache line stored in multiple caches and a line stored in a single cache.		'''[http://en.wikipedia.org/wiki/MSI_protocol MSI protocol]''' has a major drawback in that each read-write sequence incurs two bus transactions irrespective of whether the cache line is stored in only one cache or not. This is a huge setback for highly parallel programs that have little data sharing. '''[http://en.wikipedia.org/wiki/MESI_protocol MESI'''] protocol solves this problem by introducing the E ('''Exclusive''') state to distinguish between a cache line stored in multiple caches and a line stored in a single cache.
	Let us briefly look at how the MESI protocol works. (For a more detailed version readers are referred to Solihin textbook pg. 215)		Let us briefly look at how the MESI protocol works. (For a more detailed version readers are referred to Solihin textbook pg. 215)
Line 104:		Line 104:

	[[Image:MESIFig.jpg\|thumb\|400px\|center\|<b>Figure 3:</b> MESI State Diagram]]		[[Image:MESIFig.jpg\|thumb\|400px\|center\|<b>Figure 3:</b> MESI State Diagram]]
			==MESI Implementation Complexities==
	~~===~~==MESI Implementation Complexities~~===~~==
	----		----
	n 1984, researchers at the University of Illinois developed and published a new, improved cache coherence protocol. This protocol added an "exclusive" state to the MSI protocol. The new state improves performance by reducing bus traffic when data is being used by a single processor. For more information on MESI, here is an excerpt of the original article:		n 1984, researchers at the University of Illinois developed and published a new, improved cache coherence protocol. This protocol added an "exclusive" state to the MSI protocol. The new state improves performance by reducing bus traffic when data is being used by a single processor. For more information on MESI, here is an excerpt of the original article:

Cjkirkpa: /* MSI */

2012-03-28T16:11:03Z

MSI

← Older revision		Revision as of 16:11, 28 March 2012
Line 43:		Line 43:
	The first widely adopted approach to cache coherence is snooping on a bus. We will now discuss them in details in the following sections.		The first widely adopted approach to cache coherence is snooping on a bus. We will now discuss them in details in the following sections.

	===MSI===		==MSI==
	'''[http://en.wikipedia.org/wiki/MSI_protocol MSI protocol]''', one of the earliest snooping-based cache coherence-protocols, is a three-state write-back '''invalidation protocol'''. It marks the cache line with one of three possible states: '''Modified (M), Shared (S)''', and '''Invalid (I)'''. If a cache line is dirty and the processor has exclusive ownership of it, it is in '''Modified''' state. If the cache line is clean and is shared by more than one processor , it is marked as '''Shared'''. '''Invalid''' means the cache line is either not present or is in invalid state. '''BusRdx''' causes all other processors to invalidate (demote) their copy of the cache line to the '''I''' state. If the cache line is present in the '''M''' state in another cache, it will flush.		'''[http://en.wikipedia.org/wiki/MSI_protocol MSI protocol]''', one of the earliest snooping-based cache coherence-protocols, is a three-state write-back '''invalidation protocol'''. It marks the cache line with one of three possible states: '''Modified (M), Shared (S)''', and '''Invalid (I)'''. If a cache line is dirty and the processor has exclusive ownership of it, it is in '''Modified''' state. If the cache line is clean and is shared by more than one processor , it is marked as '''Shared'''. '''Invalid''' means the cache line is either not present or is in invalid state. '''BusRdx''' causes all other processors to invalidate (demote) their copy of the cache line to the '''I''' state. If the cache line is present in the '''M''' state in another cache, it will flush.

Line 50:		Line 50:
	[[Image:MSIfig.jpg\|thumb\|400px\|center\|<b>Figure 3:</b> MSI State Diagram]]		[[Image:MSIfig.jpg\|thumb\|400px\|center\|<b>Figure 3:</b> MSI State Diagram]]

	=====MSI Implementation Complexities=====		===MSI Implementation Complexities===
	----		----
	MSI is the most basic cache coherence protocols, and also the easiest to implement. However, the MSI protocol requires that all state changes occur atomically to ensure cache coherency, and is therefore not recommended for real-world, complex systems.[http://books.google.com/books?id=eqSYY7CRWhoC&pg=PA107&lpg=PA107&dq=msi+cache++implementation&source=bl&ots=V3sO0fSt5a&sig=HmK3ntQ3daI7uTaowAgi7crVgcU&hl=en&sa=X&ei=2CRpT7rkMcWrsQKB8fmvCQ&ved=0CFoQ6AEwBg#v=onepage&q=msi%20cache%20%20implementation&f=true] Adding an exclusive, owner, or forwarding state to the architecture increases the cache coherence design complexity, but greatly improves performance. For this reason, most modern multiprocessors use a variant of MSI (MESI, MOSI, or MOESI). [http://en.wikipedia.org/wiki/MSI_protocol]		MSI is the most basic cache coherence protocols, and also the easiest to implement. However, the MSI protocol requires that all state changes occur atomically to ensure cache coherency, and is therefore not recommended for real-world, complex systems.[http://books.google.com/books?id=eqSYY7CRWhoC&pg=PA107&lpg=PA107&dq=msi+cache++implementation&source=bl&ots=V3sO0fSt5a&sig=HmK3ntQ3daI7uTaowAgi7crVgcU&hl=en&sa=X&ei=2CRpT7rkMcWrsQKB8fmvCQ&ved=0CFoQ6AEwBg#v=onepage&q=msi%20cache%20%20implementation&f=true] Adding an exclusive, owner, or forwarding state to the architecture increases the cache coherence design complexity, but greatly improves performance. For this reason, most modern multiprocessors use a variant of MSI (MESI, MOSI, or MOESI). [http://en.wikipedia.org/wiki/MSI_protocol]

Cjkirkpa: /* References */

2012-03-28T15:59:39Z

References

← Older revision		Revision as of 14:41, 29 March 2012
Line 2:		Line 2:

	Most parallel software in the commercial market relies on the shared-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. 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 [http://en.wikipedia.org/wiki/Multi-core_(computing) CMP]) the [http://en.wikipedia.org/wiki/Symmetric_multiprocessing 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 '''''[http://en.wikipedia.org/wiki/Cache_coherence 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.		programming model in which all processors access the same physical address space. 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 [http://en.wikipedia.org/wiki/Multi-core_(computing) CMP]) the [http://en.wikipedia.org/wiki/Symmetric_multiprocessing 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 the '''''[http://en.wikipedia.org/wiki/Cache_coherence 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.

	[[Image:Busbased SMP.jpg\|frame\|center\|<b>Figure 1:</b> Typical Bus-Based Processor Model]]		[[Image:Busbased SMP.jpg\|frame\|center\|<b>Figure 1:</b> Typical Bus-Based Processor Model]]

	==Summary of Cache Coherence Protocols==		==Summary of Cache Coherence Protocols==
	At any point in logical time, the permissions for a cache block can allow either a single writer or multiple readers. The '''''[http://en.wikipedia.org/wiki/Cache_coherence#Coherency_protocol coherence protocol]''''' ensures the ~~invariants~~ of the states are maintained. The different coherent states used by most of the cache coherent protocols are 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 '''''[http://en.wikipedia.org/wiki/Cache_coherence#Coherency_protocol coherence protocol]''''' ensures the invariance of the states are maintained. The different coherent states used by most of the cache coherent protocols are shown in ''Table 1'':

	<center>		<center>
Line 41:		Line 41:
	<br />		<br />
	<br />		<br />
	The first widely adopted approach to cache coherence is snooping on a bus. Snooping entails each processor seeing or "snooping" all bus transactions. Common bus transactions are		The first widely adopted approach to cache coherence uses snooping on a bus. Snooping entails each processor seeing or "snooping" all bus transactions. Common bus transactions are

	* '''BusRd''' The cache controller asks for a copy of the data it does not intend to modify		* '''BusRd''' The cache controller asks for a copy of the data it does not intend to modify
	* '''Bus Read-Exclusive (BusRdX)''' The cache controller asks for a copy of the data it intends to modify ~~and~~ all other caches need to be invalidated		* '''Bus Read-Exclusive (BusRdX)''' The cache controller asks for a copy of the data it intends to modify (all other caches need to be invalidated)
	* '''Writeback (BusWB)''' Main memory updates its contents		* '''Writeback (BusWB)''' Main memory updates its contents
	* '''Bus upgrade (BusUpgr)''' Bus upgrade obtains exclusive ownership and invalidates other copies bus does not return data to the requestor		* '''Bus upgrade (BusUpgr)''' Bus upgrade obtains exclusive ownership and invalidates other copies - bus does not return data to the requestor

	==MSI==		==MSI==
Line 63:		Line 63:
	Let us briefly look at how the MESI protocol works. (For a more detailed version readers are referred to Solihin textbook pg. 215)		Let us briefly look at how the MESI protocol works. (For a more detailed version readers are referred to Solihin textbook pg. 215)

	'''[http://en.wikipedia.org/wiki/MESI_protocol MESI]''' coherence protocol marks each cache line in one of the Modified, Exclusive, Shared or Invalid ~~state~~.		'''[http://en.wikipedia.org/wiki/MESI_protocol MESI]''' coherence protocol marks each cache line as being in one of the Modified, Exclusive, Shared or Invalid states.
	* '''Invalid''' : The cache line is either not present or is invalid		* '''Invalid''' : The cache line is either not present or is invalid
	* '''Exclusive''' : The cache line is clean and is owned by this core/processor only		* '''Exclusive''' : The cache line is clean and is owned by this core/processor only
Line 69:		Line 69:
	* '''Shared''' : The cache line is clean and is shared by more than one core/processor		* '''Shared''' : The cache line is clean and is shared by more than one core/processor

	The '''[http://en.wikipedia.org/wiki/MESI_protocol MESI'''] protocol works as ~~the following~~:		The '''[http://en.wikipedia.org/wiki/MESI_protocol MESI'''] protocol works as follows:
	A line that is just fetched receives E or S state depending on whether it exists in other processors in the system or not. Similarly, a cache line gets the M state when a processor writes to it. If the line is not in E or M state prior to being written to, the cache sends a Bus Upgrade (BusUpgr) signal or as the Intel manuals call it, a “Read-For-Ownership (RFO) request” ~~that~~ ensures that the line exists in the cache and is in the I state in all other processors on the bus (if any). The table shown below will summarize '''[http://en.wikipedia.org/wiki/MESI_protocol MESI]''' protocol.		A line that is just fetched receives E or S state depending on whether it exists in other processors in the system or not. Similarly, a cache line gets the M state when a processor writes to it. If the line is not in E or M state prior to being written to, the cache sends a Bus Upgrade (BusUpgr) signal or, as the Intel manuals call it, a “Read-For-Ownership (RFO) request” which ensures that the line exists in the cache and is in the I state in all other processors on the bus (if any). The table shown below will summarize the '''[http://en.wikipedia.org/wiki/MESI_protocol MESI]''' protocol.

	<center>		<center>
Line 111:		Line 111:
	===MESI Implementation Complexities===		===MESI Implementation Complexities===
	----		----
	n 1984, researchers at the University of Illinois developed and published a new, improved cache coherence protocol. This protocol added an "exclusive" state to the MSI protocol. The new state improves performance by reducing bus traffic when data is being used by a single processor. For more information on MESI, here is an excerpt of the original article:		In 1984, researchers at the University of Illinois developed and published a new, improved cache coherence protocol. This protocol added an "exclusive" state to the MSI protocol. The new state improves performance by reducing bus traffic when data is being used by a single processor. For more information on MESI, here is an excerpt of the original article:
	[http://www.deepdyve.com/lp/association-for-computing-machinery/a-low-overhead-coherence-solution-for-multiprocessors-with-private-AqsgSDo8s0 A low-overhead coherence solution for multiprocessors with private cache memories]		[http://www.deepdyve.com/lp/association-for-computing-machinery/a-low-overhead-coherence-solution-for-multiprocessors-with-private-AqsgSDo8s0 A low-overhead coherence solution for multiprocessors with private cache memories]

Line 118:		Line 118:

	==MOESI==		==MOESI==
	[http://en.wikipedia.org/wiki/Opteron AMD Opteron] was AMD’s first-generation dual core processor which had two distinct [http://en.wikipedia.org/wiki/Athlon_64 K8 cores] together on a single die. Cache coherence produces bigger problems on such multicore processors. It was necessary to use an appropriate coherence protocol to address this problem. The [http://en.wikipedia.org/wiki/Xeon Intel Xeon], which was the competitive counterpart from Intel to AMD dual core Opteron, used the [http://en.wikipedia.org/wiki/MESI_protocol MESI] protocol to handle cache coherence. [http://en.wikipedia.org/wiki/MESI_protocol MESI] came with the drawback of using much time and bandwidth in certain situations.		[http://en.wikipedia.org/wiki/Opteron AMD Opteron] was AMD’s first-generation dual core processor which had two distinct [http://en.wikipedia.org/wiki/Athlon_64 K8 cores] together on a single die. Cache coherence produces bigger problems on such multicore processors. It was necessary to use an appropriate coherence protocol to address this problem. The [http://en.wikipedia.org/wiki/Xeon Intel Xeon], which was the competitive counterpart from Intel to AMD dual core Opteron, used the [http://en.wikipedia.org/wiki/MESI_protocol MESI] protocol to handle cache coherence. [http://en.wikipedia.org/wiki/MESI_protocol MESI] came with the drawback of using too much time and bandwidth in certain situations.

	[http://en.wikipedia.org/wiki/MOESI_protocol MOESI] was AMD’s answer to this problem. [http://en.wikipedia.org/wiki/MOESI_protocol MOESI] added a fifth state to [http://en.wikipedia.org/wiki/MESI_protocol MESI] protocol called the owned state. [http://en.wikipedia.org/wiki/MOESI_protocol MOESI] protocol addresses the bandwidth problem faced by MESI protocol when processor having invalid data in its cache wants to modify the data. The processor seeking the data will have to wait for the processor which modified this data to write back to the main memory, which takes time and bandwidth. This drawback is removed in MOESI by allowing dirty sharing. When the data is held by a processor in the new state owned, it can provide other processors the modified data without writing it to the main memory. This is called dirty sharing. The processor with the data in the owned state stays responsible to update the main memory later when the cache line is evicted.		[http://en.wikipedia.org/wiki/MOESI_protocol MOESI] was AMD’s answer to this problem. [http://en.wikipedia.org/wiki/MOESI_protocol MOESI] added a fifth state to [http://en.wikipedia.org/wiki/MESI_protocol MESI] protocol called the owned state. [http://en.wikipedia.org/wiki/MOESI_protocol MOESI] protocol addresses the bandwidth problem faced by MESI protocol when processor having invalid data in its cache wants to modify the data. The processor seeking the data will have to wait for the processor which modified this data to write back to the main memory, which takes time and bandwidth. This drawback is removed in MOESI by allowing dirty sharing. When the data is held by a processor in the new state owned, it can provide other processors the modified data without writing it to the main memory. This is called dirty sharing. The processor with the data in the owned state stays responsible to update the main memory later when the cache line is evicted.

	[http://en.wikipedia.org/wiki/MOESI_protocol MOESI] has become one of the most popular snoop-based protocols supported in AMD64 architecture. AMD dual-core Opteron can maintain cache coherence in systems up to 8 processors using this protocol.		[http://en.wikipedia.org/wiki/MOESI_protocol MOESI] has become one of the most popular snoop-based protocols supported in AMD64 architecture. AMD dual-core Opteron can maintain cache coherence in systems up to 8 processors using this protocol.

	The five different states of [http://en.wikipedia.org/wiki/MOESI_protocol MOESI] protocol are:		The five different states of [http://en.wikipedia.org/wiki/MOESI_protocol MOESI] protocol are:

← Older revision		Revision as of 16:13, 28 March 2012
Line 104:		Line 104:

	[[Image:MESIFig.jpg\|thumb\|400px\|center\|<b>Figure 3:</b> MESI State Diagram]]		[[Image:MESIFig.jpg\|thumb\|400px\|center\|<b>Figure 3:</b> MESI State Diagram]]
	==MESI Implementation Complexities==		===MESI Implementation Complexities===
	----		----
	n 1984, researchers at the University of Illinois developed and published a new, improved cache coherence protocol. This protocol added an "exclusive" state to the MSI protocol. The new state improves performance by reducing bus traffic when data is being used by a single processor. For more information on MESI, here is an excerpt of the original article:		n 1984, researchers at the University of Illinois developed and published a new, improved cache coherence protocol. This protocol added an "exclusive" state to the MSI protocol. The new state improves performance by reducing bus traffic when data is being used by a single processor. For more information on MESI, here is an excerpt of the original article:
Line 112:		Line 112:
	For more details, see pages 215-220 of the Solihin textbook.		For more details, see pages 215-220 of the Solihin textbook.

	~~==Five State Cache Coherence Protocols==~~		==MOESI==

	===MOESI===
	[http://en.wikipedia.org/wiki/Opteron AMD Opteron] was AMD’s first-generation dual core processor which had two distinct [http://en.wikipedia.org/wiki/Athlon_64 K8 cores] together on a single die. Cache coherence produces bigger problems on such multicore processors. It was necessary to use an appropriate coherence protocol to address this problem. The [http://en.wikipedia.org/wiki/Xeon Intel Xeon], which was the competitive counterpart from Intel to AMD dual core Opteron, used the [http://en.wikipedia.org/wiki/MESI_protocol MESI] protocol to handle cache coherence. [http://en.wikipedia.org/wiki/MESI_protocol MESI] came with the drawback of using much time and bandwidth in certain situations.		[http://en.wikipedia.org/wiki/Opteron AMD Opteron] was AMD’s first-generation dual core processor which had two distinct [http://en.wikipedia.org/wiki/Athlon_64 K8 cores] together on a single die. Cache coherence produces bigger problems on such multicore processors. It was necessary to use an appropriate coherence protocol to address this problem. The [http://en.wikipedia.org/wiki/Xeon Intel Xeon], which was the competitive counterpart from Intel to AMD dual core Opteron, used the [http://en.wikipedia.org/wiki/MESI_protocol MESI] protocol to handle cache coherence. [http://en.wikipedia.org/wiki/MESI_protocol MESI] came with the drawback of using much time and bandwidth in certain situations.

Line 177:		Line 175:
	[[Image:MOESIfig.jpg\|thumb\|upright\|center\|450px\|<b>Figure 3:</b> MOESI State Diagram]]		[[Image:MOESIfig.jpg\|thumb\|upright\|center\|450px\|<b>Figure 3:</b> MOESI State Diagram]]

	=====MOESI Implementation Complexities=====		===MOESI Implementation Complexities===
	----		----
	Allowing '''dirty sharing''' by implementing an owner state reduces bus traffic between the individual caches and main memory, but comes at the cost of higher complexity. MOESI has two more states than MSI, so the underlying state transition logic is more complex. In addition, MOESI has six bus=side request types, compared with three for MSI (or four, if BusUpgr is used). For more information, see p. 222-228 in the Solihin text.		Allowing '''dirty sharing''' by implementing an owner state reduces bus traffic between the individual caches and main memory, but comes at the cost of higher complexity. MOESI has two more states than MSI, so the underlying state transition logic is more complex. In addition, MOESI has six bus=side request types, compared with three for MSI (or four, if BusUpgr is used). For more information, see p. 222-228 in the Solihin text.
Line 187:		Line 185:
	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.

	===MESIF===		==MESIF==
	Intel's solution to the redundant messages sent using the '''MESI''' protocol was the '''[http://en.wikipedia.org/wiki/MESIF_protocol MESIF]''' protocol incorporated in the latest Intel multi-core processors Core i7, and accommodating the point-to-point links used in the [http://en.wikipedia.org/wiki/Intel_QuickPath_Interconnect QuickPath Interconnect]. Using the '''MESI''' protocol in this architecture would send many redundant messages between different processors, often with unnecessarily high latency. For example, when a processor requests a cache line that is stored in multiple locations, every location might respond with the data. As the requesting processor only needs a single copy of the data, the system would be wasting the bandwidth.		Intel's solution to the redundant messages sent using the '''MESI''' protocol was the '''[http://en.wikipedia.org/wiki/MESIF_protocol MESIF]''' protocol incorporated in the latest Intel multi-core processors Core i7, and accommodating the point-to-point links used in the [http://en.wikipedia.org/wiki/Intel_QuickPath_Interconnect QuickPath Interconnect]. Using the '''MESI''' protocol in this architecture would send many redundant messages between different processors, often with unnecessarily high latency. For example, when a processor requests a cache line that is stored in multiple locations, every location might respond with the data. As the requesting processor only needs a single copy of the data, the system would be wasting the bandwidth.
	As a solution to this problem, an additional state, '''Forward state''', was added by slightly changing the role of the Shared state. Whenever there is a read request, only the cache line in the F state will respond to the request, while all the S state caches remain dormant. Hence, by designating a single cache line to respond to requests, coherency traffic is substantially reduced when multiple copies of the data exist. This advantage is diagrammatically depicted in figure 5. Also, on a read request, the F state transitions to the S state. That is, when a cache line in the '''F''' state is copied, the F state migrates to the newer copy, while the older one drops back to the '''S''' state. Moving the new copy to the F state exploits both temporal and spatial locality. Because the newest copy of the cache line is always in the F state, it is very unlikely that the line in the F state will be evicted from the caches. This takes advantage of the temporal locality of the request. The second advantage is that if a particular cache line is in high demand due to spatial locality, the bandwidth used to transmit that data will be spread across several cores.		As a solution to this problem, an additional state, '''Forward state''', was added by slightly changing the role of the Shared state. Whenever there is a read request, only the cache line in the F state will respond to the request, while all the S state caches remain dormant. Hence, by designating a single cache line to respond to requests, coherency traffic is substantially reduced when multiple copies of the data exist. This advantage is diagrammatically depicted in figure 5. Also, on a read request, the F state transitions to the S state. That is, when a cache line in the '''F''' state is copied, the F state migrates to the newer copy, while the older one drops back to the '''S''' state. Moving the new copy to the F state exploits both temporal and spatial locality. Because the newest copy of the cache line is always in the F state, it is very unlikely that the line in the F state will be evicted from the caches. This takes advantage of the temporal locality of the request. The second advantage is that if a particular cache line is in high demand due to spatial locality, the bandwidth used to transmit that data will be spread across several cores.
Line 196:		Line 194:
	[[Image:MESIFVMESI.jpg\|thumb\|upright\|center\|450px\|<b>Figure 5:</b> Reduced Traffic with MESIF Protocol [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4606981&tag=1]]]		[[Image:MESIFVMESI.jpg\|thumb\|upright\|center\|450px\|<b>Figure 5:</b> Reduced Traffic with MESIF Protocol [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4606981&tag=1]]]

	=====MESIF Implementation Complexities=====		===MESIF Implementation Complexities===
	----		----
	Intel has used the MESIF protocol in their recent Nehalem architecture, in an attempt to reduce the amount of snooping traffic between caches. They accomplish this by using a large L3 cache that is shared between all the processor caches to keep track of which cores are using data. If the L3 cache has been modified, each core using that data will need to update its L1/L2 caches with the new value.		Intel has used the MESIF protocol in their recent Nehalem architecture, in an attempt to reduce the amount of snooping traffic between caches. They accomplish this by using a large L3 cache that is shared between all the processor caches to keep track of which cores are using data. If the L3 cache has been modified, each core using that data will need to update its L1/L2 caches with the new value.

← Older revision		Revision as of 15:59, 28 March 2012
Line 312:		Line 312:
	# [http://www.intel.com/technology/itj/2006/volume10issue02/art02_CMP_Implementation/p03_implementation.htm CMP Implementation in Intel Core Duo Processors]		# [http://www.intel.com/technology/itj/2006/volume10issue02/art02_CMP_Implementation/p03_implementation.htm CMP Implementation in Intel Core Duo Processors]
	# [http://en.wikipedia.org/wiki/Symmetric_multiprocessing Common System Interface in Intel Processors]		# [http://en.wikipedia.org/wiki/Symmetric_multiprocessing Common System Interface in Intel Processors]
	~~# []~~
	# [http://techreport.com/articles.x/8236/2 AMD dual core Architecture]		# [http://techreport.com/articles.x/8236/2 AMD dual core Architecture]
	# [http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/24593.pdf AMD64 Architecture Programmer's manual]		# [http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/24593.pdf AMD64 Architecture Programmer's manual]
	# [http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/40546.pdf Software Optimization guide for AMD 10h Processors]		# [http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/40546.pdf Software Optimization guide for AMD 10h Processors]
	# [http://www.chip-architect.com/news/2003_09_21_Detailed_Architecture_of_AMDs_64bit_Core.html Architecture of AMD 64 bit core]		# [http://www.chip-architect.com/news/2003_09_21_Detailed_Architecture_of_AMDs_64bit_Core.html Architecture of AMD 64 bit core]
	~~#[]~~
	# [http://www.freepatentsonline.com/5283886.html Three state invalidation protocols]		# [http://www.freepatentsonline.com/5283886.html Three state invalidation protocols]
	# [http://portal.acm.org/citation.cfm?id=1499317&dl=GUIDE&coll=GUIDE&CFID=83027384&CFTOKEN=95680533 Synapse tightly coupled multiprocessors: a new approach to solve old problems]		# [http://portal.acm.org/citation.cfm?id=1499317&dl=GUIDE&coll=GUIDE&CFID=83027384&CFTOKEN=95680533 Synapse tightly coupled multiprocessors: a new approach to solve old problems]
Line 323:		Line 321:
	# [http://en.wikipedia.org/wiki/Dragon_protocol Dragon Protocol]		# [http://en.wikipedia.org/wiki/Dragon_protocol Dragon Protocol]
	# [http://en.wikipedia.org/wiki/Xerox_Dragon Xerox Dragon]		# [http://en.wikipedia.org/wiki/Xerox_Dragon Xerox Dragon]
	~~# []~~
	# [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=289691 XDBus]		# [http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=289691 XDBus]
	~~# [http://www.ece.wisc.edu/~wddd/2002/final/ekman.pdf Evaluation of Snoop-Energy Reduction Techniques for Chip-Multiprocessors]~~
	# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.7463&rep=rep1&type=pdf Power Efficient Cache Coherence]		# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.7463&rep=rep1&type=pdf Power Efficient Cache Coherence]
	# [http://www.realworldtech.com/page.cfm?ArticleID=RWT082807020032&p=5 The Common System Interface: Intel's Future Interconnect]		# [http://www.realworldtech.com/page.cfm?ArticleID=RWT082807020032&p=5 The Common System Interface: Intel's Future Interconnect]
	# [http://support.amd.com/us/Processor_TechDocs/24593.pdf AMD64 Architecture Programmer's Manual Vol 2 'System Programming']		# [http://support.amd.com/us/Processor_TechDocs/24593.pdf AMD64 Architecture Programmer's Manual Vol 2 'System Programming']
	# [http://ieeexplore.ieee.org/search/srchabstract.jsp?tp=&arnumber=5375423&queryText%3D%28%28mesi%29+AND+moesi%29%26openedRefinements%3D*%26matchBoolean%3Dtrue%26searchField%3DSearch+All+Text 'Comparing cache architectures and coherency protocols on x86-64 multicore SMP systems' by Hackenberg, D., Molka, D. and Nagel, W.E.]		# [http://ieeexplore.ieee.org/search/srchabstract.jsp?tp=&arnumber=5375423&queryText%3D%28%28mesi%29+AND+moesi%29%26openedRefinements%3D*%26matchBoolean%3Dtrue%26searchField%3DSearch+All+Text 'Comparing cache architectures and coherency protocols on x86-64 multicore SMP systems' by Hackenberg, D., Molka, D. and Nagel, W.E.]