CSC/ECE 506 Spring 2013/8a an - Revision history

Dhupadhy at 19:44, 18 March 2015

2015-03-18T19:44:31Z

← Older revision		Revision as of 19:44, 18 March 2015
Line 8:		Line 8:

	= MSI Protocol =		= MSI Protocol =
	[http://www.scribd.com/doc/50676653/19/MSI-protocol MSI] protocol is a three-state write-back invalidation protocol which is one of the simplest and earliest-used snooping-based cache coherence-protocols. According to this protocol, a cache block can be in one of the Modified (M), Shared (S)~~, and~~ Invalid (I) ~~states~~.		[http://www.scribd.com/doc/50676653/19/MSI-protocol MSI] protocol is a three-state write-back invalidation protocol which is one of the simplest and earliest-used snooping-based cache coherence-protocols. According to this protocol, a cache block can be in one of the following three states: Modified (M), Shared (S) or Invalid (I).
	[[File:MSInew.jpg\|600px\|thumbnail\|State transition diagram for MSI protocol]]		[[File:MSInew.jpg\|600px\|thumbnail\|State transition diagram for MSI protocol]]
	*'''Modified''' state indicates that the variable in the cache has been modified and therefore has a different value from that found in the main memory. A cache line in this state thus needs to be written back ~~to the block~~ to memory during eviction.		*'''Modified''' state indicates that the variable in the cache has been modified and therefore has a different value from that found in the main memory. A cache line in this state thus needs to be written back to memory during eviction.
	*'''Shared''' state indicates that the block exists in one or more caches, and is clean, implying that its value is consistent with the one in main memory. So a cache block in this state can be evicted without having to write it back to the main memory.		*'''Shared''' state indicates that the block exists in one or more caches, and is clean, implying that its value is consistent with the one in main memory. So a cache block in this state can be evicted without having to write it back to the main memory.
	*'''Invalid''' state indicates that the cache block is invalid.		*'''Invalid''' state indicates that the cache block is invalid.

Nartal: /* MESIF in Intel Nehalem Computer */

2013-03-25T18:24:50Z

MESIF in Intel Nehalem Computer

← Older revision		Revision as of 18:24, 25 March 2013
Line 125:		Line 125:

	== MESIF in Intel Nehalem Computer==		== MESIF in Intel Nehalem Computer==
	[http://rolfed.com/nehalem/nehalemPaper.pdf Intel Nehalem Computer] uses the MESIF protocol. In the Nehalem architecture each core has its own L1 and L2 cache. Nehalem does has a shared cache, implemented as L3 cache. This cache is shared among all cores and is relatively large. This cache is inclusive, meaning that		[http://rolfed.com/nehalem/nehalemPaper.pdf Intel Nehalem Computer] uses the MESIF protocol. In the Nehalem architecture each core has its own L1 and L2 cache. Nehalem does has a shared cache, implemented as L3 cache. This cache is shared among all cores and is relatively large. This cache is inclusive, meaning that it duplicates all data stored in each indivitual L1 and L2 cache. This duplication greatly adds to the inter-core communication efficiency because any given core does not have to locate data in another processor’s cache. If the requested data is not found in any level of the core’s cache, it knows the data is also not present in any other core’s cache. To ensure coherency across all caches, the L3 cache has
	it duplicates all data stored in each indivitual L1 and L2 cache. This duplication greatly adds to the inter-core communication efficiency because any given core does not have to locate data in another processor’s cache. If the requested data is not found in any level of the core’s cache, it knows the data is also not present in any other core’s cache. To ensure coherency across all caches, the L3 cache has
	additional flags that keep track of which core the data came from. If the data is modified in L3 cache, then the L3 cache knows if the data came from a different core than last time,and that the data in the first core needs its L1/L2 values updated with the new data. This greatly reduces the amount of traditional “snooping” coherency traffic between cores.<ref>[http://www.cs.uwaterloo.ca/~brecht/courses/856/Possible-Readings/multicore/cache-performance-x86-2009.pdf Comparing Cache Organization and Memory Management of the Intel Nehalem Computer Architecture]</ref>		additional flags that keep track of which core the data came from. If the data is modified in L3 cache, then the L3 cache knows if the data came from a different core than last time,and that the data in the first core needs its L1/L2 values updated with the new data. This greatly reduces the amount of traditional “snooping” coherency traffic between cores.<ref>[http://www.cs.uwaterloo.ca/~brecht/courses/856/Possible-Readings/multicore/cache-performance-x86-2009.pdf Comparing Cache Organization and Memory Management of the Intel Nehalem Computer Architecture]</ref>
	<br><br>		<br><br>

Abhatta4: /* Synapse Protocol */

2013-03-19T20:05:41Z

Synapse Protocol

← Older revision		Revision as of 20:05, 19 March 2013
Line 187:		Line 187:

	= Synapse Protocol =		= Synapse Protocol =
	[[File:Synapse-sk.jpg\|thumbnail\|State Transition Diagram for Synapse Protocol]]		[[File:Synapse-sk.jpg\|500px\|thumbnail\|State Transition Diagram for Synapse Protocol]]
	In Synapse protocol, cache blocks are in one of the following states:		In Synapse protocol, cache blocks are in one of the following states:
	*'''Invalid''': Indicates that the block is invalid		*'''Invalid''': Indicates that the block is invalid

Abhatta4: /* MESIF in Intel® QuickPath Interconnect */

2013-03-19T19:47:01Z

MESIF in Intel® QuickPath Interconnect

← Older revision		Revision as of 19:47, 19 March 2013
Line 133:		Line 133:

	== MESIF in Intel® QuickPath Interconnect ==		== MESIF in Intel® QuickPath Interconnect ==
	The [http://www.intel.com/content/www/us/en/io/quickpath-technology/quick-path-interconnect-introduction-paper.html Intel QuickPath Interconnect] is a high speed packetized point-to-point interconnect used in Intel's next generation of microprocessors introduced in second half of 2008. The narrow high speed links stitch together processors in distributed memory style platform architecture. The Intel QuickPath Interconnect includes the cache coherency protocol, MESIF to keep the distributed memory and shared caching coherent during system operation. It supports both low latency source snooping and direct cache-to-cache transfers for low latency. [[File:QuickPath.jpg\|thumbnail\|Intel® QuickPath Interconnect]]		The [http://www.intel.com/content/www/us/en/io/quickpath-technology/quick-path-interconnect-introduction-paper.html Intel QuickPath Interconnect] is a high speed packetized point-to-point interconnect used in Intel's next generation of microprocessors introduced in second half of 2008. The narrow high speed links stitch together processors in distributed memory style platform architecture. The Intel QuickPath Interconnect includes the cache coherency protocol, MESIF to keep the distributed memory and shared caching coherent during system operation. It supports both low latency source snooping and direct cache-to-cache transfers for low latency. [[File:QuickPath.jpg\|400px\|thumbnail\|Intel® QuickPath Interconnect]]

	The Intel® QuickPath Interconnect coherency protocol consists of two distinct types of agents: caching agents and home agents. A micro-processor will typically have both types of agents and possibly multiple agents of each type. A caching agent represents an entity which may initiate transactions into coherent memory, and which may retain copies in its own cache structure. The caching agent is defined by the messages it may sink and source according to the behaviors defined in the cache coherence protocol. A caching agent can also provide copies of the coherent memory contents to other caching agents.A home agent represents an entity which services coherent transactions, including handshaking as necessary with caching agents. A home agent supervises a portion of the coherent memory. Home agent logic is not specifically the memory controller circuits for main memory, but rather the additional Intel® QuickPath Interconnect logic which maintains the coherency for a given address space. It is responsible for managing the conflicts that might arise among the different caching agents. It provides the appropriate data and ownership responses as required by a given transaction’s flow.		The Intel® QuickPath Interconnect coherency protocol consists of two distinct types of agents: caching agents and home agents. A micro-processor will typically have both types of agents and possibly multiple agents of each type. A caching agent represents an entity which may initiate transactions into coherent memory, and which may retain copies in its own cache structure. The caching agent is defined by the messages it may sink and source according to the behaviors defined in the cache coherence protocol. A caching agent can also provide copies of the coherent memory contents to other caching agents.A home agent represents an entity which services coherent transactions, including handshaking as necessary with caching agents. A home agent supervises a portion of the coherent memory. Home agent logic is not specifically the memory controller circuits for main memory, but rather the additional Intel® QuickPath Interconnect logic which maintains the coherency for a given address space. It is responsible for managing the conflicts that might arise among the different caching agents. It provides the appropriate data and ownership responses as required by a given transaction’s flow.

Abhatta4: /* MOESI Protocol */

2013-03-19T19:44:04Z

MOESI Protocol

← Older revision		Revision as of 19:44, 19 March 2013
Line 146:		Line 146:

	= MOESI Protocol=		= MOESI Protocol=
	MOESI is a five state cache coherence protocol with the following states:[[File:MOESI-s.jpg\|thumbnail\|State Transition Diagram for MOESI protocol]]		MOESI is a five state cache coherence protocol with the following states:[[File:MOESI.jpg\|500px\|thumbnail\|State Transition Diagram for MOESI protocol]]
	*'''Invalid''': A cache line in the invalid state does not hold a valid copy of the data. Valid copies of the data can be either in main memory or another processor cache.		*'''Invalid''': A cache line in the invalid state does not hold a valid copy of the data. Valid copies of the data can be either in main memory or another processor cache.
	*'''Exclusive''': A cache line in the exclusive state holds the most recent, correct copy of the data. The copy in main memory is also the most recent, correct copy of the data. No other processor holds a copy of the data.		*'''Exclusive''': A cache line in the exclusive state holds the most recent, correct copy of the data. The copy in main memory is also the most recent, correct copy of the data. No other processor holds a copy of the data.
Line 159:		Line 159:

	== MOESI in AMD64 architecture ==		== MOESI in AMD64 architecture ==
	The cache-coherency protocol supported by the [http://www.viva64.com/en/a/0029/ AMD64 architecture] is the[http://en.wikipedia.org/wiki/MOESI_protocol MOESI]. The figure ~~above below~~ shows the general MOESI state transitions possible with various types of memory accesses in AMD64 architecture. This is a logical software view, not a hardware view, of how cache-line state transitions. Instruction-execution activity and external-bus transactions can both be used to modify the cache MOESI state in multiprocessing or multi-mastering systems. To maintain memory coherency, external bus masters (typically other processors with their own internal caches) need to acquire the most recent copy of data before caching it internally. That copy can be in main memory or in the internal caches of other bus-mastering devices. When an external master has a cache read-miss or write-miss, it probes the other mastering devices to determine whether the most recent copy of data is held in any of their caches. If one of the other mastering devices holds the most recent copy, it provides it to the requesting device. Otherwise, the most recent copy is provided		The cache-coherency protocol supported by the [http://www.viva64.com/en/a/0029/ AMD64 architecture] is the[http://en.wikipedia.org/wiki/MOESI_protocol MOESI]. The figure beside shows the general MOESI state transitions possible with various types of memory accesses in AMD64 architecture. This is a logical software view, not a hardware view, of how cache-line state transitions. Instruction-execution activity and external-bus transactions can both be used to modify the cache MOESI state in multiprocessing or multi-mastering systems. To maintain memory coherency, external bus masters (typically other processors with their own internal caches) need to acquire the most recent copy of data before caching it internally. That copy can be in main memory or in the internal caches of other bus-mastering devices. When an external master has a cache read-miss or write-miss, it probes the other mastering devices to determine whether the most recent copy of data is held in any of their caches. If one of the other mastering devices holds the most recent copy, it provides it to the requesting device. Otherwise, the most recent copy is provided
	by main memory.<ref>[http://www.cse.wustl.edu/~roger/569M.s09/24593.pdf AMD 64 Technology]</ref><br>		by main memory.<ref>[http://www.cse.wustl.edu/~roger/569M.s09/24593.pdf AMD 64 Technology]</ref><br>
	[[Image:MOESI State Transition Diagram.jpg\|400px]]		[[Image:MOESI State Transition Diagram.jpg\|400px\|right\|thumbnail\|MOESI protocol in AMD64]]
	<br><br>		<br><br>
	There are two general types of bus-master probes:<br>		There are two general types of bus-master probes:<br>

Abhatta4: /* MESI Protocol */

2013-03-19T19:34:10Z

MESI Protocol

← Older revision		Revision as of 19:34, 19 March 2013
Line 36:		Line 36:

	= MESI Protocol=		= MESI Protocol=
	[http://eecourses.technion.ac.il/044800/lectures/MESI.pdf MESI] protocol is a 4-state protocol, in which a cache block can have an 'Exclusive' state apart from the Modified, Shared and Invalid state as in MSI protocol. [[File:~~MESI-sk~~.jpg\|thumbnail\|State Transition Diagram for MESI protocol]]		[http://eecourses.technion.ac.il/044800/lectures/MESI.pdf MESI] protocol is a 4-state protocol, in which a cache block can have an 'Exclusive' state apart from the Modified, Shared and Invalid state as in MSI protocol. [[File:MESInew.jpg\|400px\|thumbnail\|State Transition Diagram for MESI protocol]]
	*'''Modified''' : The cache line contains valid data for an external memory location. However, the data does not match the data in the external since the processor has modiified the data since it was loaded from external memory. A cache that contains a modified line is responsible for ensuring that the data is properly maintained.		*'''Modified''' : The cache line contains valid data for an external memory location. However, the data does not match the data in the external since the processor has modiified the data since it was loaded from external memory. A cache that contains a modified line is responsible for ensuring that the data is properly maintained.
	*'''Exclusive''' : The cache line contains valid data for some external memory location. The data exactly matches the data in the external memory location. Thus the cache block is clean, valid and exists only in one cache.		*'''Exclusive''' : The cache line contains valid data for some external memory location. The data exactly matches the data in the external memory location. Thus the cache block is clean, valid and exists only in one cache.

Abhatta4: /* MSI Protocol */

2013-03-19T19:28:48Z

MSI Protocol

← Older revision		Revision as of 19:28, 19 March 2013
Line 9:		Line 9:
	= MSI Protocol =		= MSI Protocol =
	[http://www.scribd.com/doc/50676653/19/MSI-protocol MSI] protocol is a three-state write-back invalidation protocol which is one of the simplest and earliest-used snooping-based cache coherence-protocols. According to this protocol, a cache block can be in one of the Modified (M), Shared (S), and Invalid (I) states.		[http://www.scribd.com/doc/50676653/19/MSI-protocol MSI] protocol is a three-state write-back invalidation protocol which is one of the simplest and earliest-used snooping-based cache coherence-protocols. According to this protocol, a cache block can be in one of the Modified (M), Shared (S), and Invalid (I) states.
	[[File:MSInew.jpg\|~~500 px~~\|thumbnail\|State transition diagram for MSI protocol]]		[[File:MSInew.jpg\|600px\|thumbnail\|State transition diagram for MSI protocol]]
	*'''Modified''' state indicates that the variable in the cache has been modified and therefore has a different value from that found in the main memory. A cache line in this state thus needs to be written back to the block to memory during eviction.		*'''Modified''' state indicates that the variable in the cache has been modified and therefore has a different value from that found in the main memory. A cache line in this state thus needs to be written back to the block to memory during eviction.
	*'''Shared''' state indicates that the block exists in one or more caches, and is clean, implying that its value is consistent with the one in main memory. So a cache block in this state can be evicted without having to write it back to the main memory.		*'''Shared''' state indicates that the block exists in one or more caches, and is clean, implying that its value is consistent with the one in main memory. So a cache block in this state can be evicted without having to write it back to the main memory.

Abhatta4: /* MSI Protocol */

2013-03-19T19:14:39Z

MSI Protocol

← Older revision		Revision as of 19:14, 19 March 2013
Line 9:		Line 9:
	= MSI Protocol =		= MSI Protocol =
	[http://www.scribd.com/doc/50676653/19/MSI-protocol MSI] protocol is a three-state write-back invalidation protocol which is one of the simplest and earliest-used snooping-based cache coherence-protocols. According to this protocol, a cache block can be in one of the Modified (M), Shared (S), and Invalid (I) states.		[http://www.scribd.com/doc/50676653/19/MSI-protocol MSI] protocol is a three-state write-back invalidation protocol which is one of the simplest and earliest-used snooping-based cache coherence-protocols. According to this protocol, a cache block can be in one of the Modified (M), Shared (S), and Invalid (I) states.
	[[File:~~MSI-sk~~.jpg\|thumbnail\|State transition diagram for MSI protocol]]		[[File:MSInew.jpg\|500 px\|thumbnail\|State transition diagram for MSI protocol]]
	*'''Modified''' state indicates that the variable in the cache has been modified and therefore has a different value from that found in the main memory. A cache line in this state thus needs to be written back to the block to memory during eviction.		*'''Modified''' state indicates that the variable in the cache has been modified and therefore has a different value from that found in the main memory. A cache line in this state thus needs to be written back to the block to memory during eviction.
	*'''Shared''' state indicates that the block exists in one or more caches, and is clean, implying that its value is consistent with the one in main memory. So a cache block in this state can be evicted without having to write it back to the main memory.		*'''Shared''' state indicates that the block exists in one or more caches, and is clean, implying that its value is consistent with the one in main memory. So a cache block in this state can be evicted without having to write it back to the main memory.

Nartal: /* Introduction */

2013-03-19T00:17:50Z

Introduction

← Older revision		Revision as of 00:17, 19 March 2013
Line 1:		Line 1:
	= Introduction =		= Introduction =
	Symmetric multiprocessing ([http://searchdatacenter.techtarget.com/definition/SMP SMP]) involves a multiprocessor computer hardware architecture where two or more identical processors are connected to a single shared main memory via system bus. An SMP provides symmetric access to all of main memory from any processor and is the building block for larger parallel systems.		Symmetric multiprocessing ([http://searchdatacenter.techtarget.com/definition/SMP SMP]) involves a multiprocessor computer hardware architecture where two or more identical processors are connected to a single shared main memory via system bus. An SMP provides symmetric access to all of main memory from any processor and is the building block for larger parallel systems.
	~~<center>~~[[Image:Busbased SMP.jpg\|~~width=10%~~\|~~height=10%]]~~</~~center~~>		[[Image:Busbased SMP.jpg\|frame\|center\|<b>Figure 1:</b> Typical Bus-Based Processor Model]]
	<br>		<br>
	If each processor has a cache that reflects the state of various parts of memory, it is possible that two or more caches may have copies of the same line. It is also possible that a given line may contain more than one lockable data item. If two threads make appropriately serialized changes to those data items, the result could be that both caches end up with different, incorrect versions of the line of memory. In other words, the system's state is no longer coherent because the system contains two different versions of what is supposed to be the content of a specific area of memory. Various protocols have been devised to address the issue of cache coherence problem, such as MSI, MESI, MOESI, [http://www.enotes.com/topic/MERSI_protocol MERSI], MESIF, Synapse, Berkeley, [https://parasol.tamu.edu/~rwerger/Courses/654/cachecoherence1.pdf Firefly] and [http://www.cs.utah.edu/~rajeev/cs7820/pres/08-7820-03.pdf Dragon] protocol. In this wiki article, MSI, MESI, MESIF, MOESI and Synapse protocol implementations on real architectures will be discussed.<ref>[http://www.windowsnetworking.com/articles_tutorials/cache-coherency.html Cache Coherence]</ref>		If each processor has a cache that reflects the state of various parts of memory, it is possible that two or more caches may have copies of the same line. It is also possible that a given line may contain more than one lockable data item. If two threads make appropriately serialized changes to those data items, the result could be that both caches end up with different, incorrect versions of the line of memory. In other words, the system's state is no longer coherent because the system contains two different versions of what is supposed to be the content of a specific area of memory. Various protocols have been devised to address the issue of cache coherence problem, such as MSI, MESI, MOESI, [http://www.enotes.com/topic/MERSI_protocol MERSI], MESIF, Synapse, Berkeley, [https://parasol.tamu.edu/~rwerger/Courses/654/cachecoherence1.pdf Firefly] and [http://www.cs.utah.edu/~rajeev/cs7820/pres/08-7820-03.pdf Dragon] protocol. In this wiki article, MSI, MESI, MESIF, MOESI and Synapse protocol implementations on real architectures will be discussed.<ref>[http://www.windowsnetworking.com/articles_tutorials/cache-coherency.html Cache Coherence]</ref>

Nartal: /* Introduction */

2013-03-19T00:17:02Z

Introduction

← Older revision		Revision as of 00:17, 19 March 2013
Line 1:		Line 1:
	= Introduction =		= Introduction =
	Symmetric multiprocessing ([http://searchdatacenter.techtarget.com/definition/SMP SMP]) involves a multiprocessor computer hardware architecture where two or more identical processors are connected to a single shared main memory via system bus. An SMP provides symmetric access to all of main memory from any processor and is the building block for larger parallel systems.		Symmetric multiprocessing ([http://searchdatacenter.techtarget.com/definition/SMP SMP]) involves a multiprocessor computer hardware architecture where two or more identical processors are connected to a single shared main memory via system bus. An SMP provides symmetric access to all of main memory from any processor and is the building block for larger parallel systems.
	<center>[[Image:Busbased SMP.jpg\|width=50%\|height=50%]]</center>		<center>[[Image:Busbased SMP.jpg\|width=10%\|height=10%]]</center>
	<br>		<br>
	If each processor has a cache that reflects the state of various parts of memory, it is possible that two or more caches may have copies of the same line. It is also possible that a given line may contain more than one lockable data item. If two threads make appropriately serialized changes to those data items, the result could be that both caches end up with different, incorrect versions of the line of memory. In other words, the system's state is no longer coherent because the system contains two different versions of what is supposed to be the content of a specific area of memory. Various protocols have been devised to address the issue of cache coherence problem, such as MSI, MESI, MOESI, [http://www.enotes.com/topic/MERSI_protocol MERSI], MESIF, Synapse, Berkeley, [https://parasol.tamu.edu/~rwerger/Courses/654/cachecoherence1.pdf Firefly] and [http://www.cs.utah.edu/~rajeev/cs7820/pres/08-7820-03.pdf Dragon] protocol. In this wiki article, MSI, MESI, MESIF, MOESI and Synapse protocol implementations on real architectures will be discussed.<ref>[http://www.windowsnetworking.com/articles_tutorials/cache-coherency.html Cache Coherence]</ref>		If each processor has a cache that reflects the state of various parts of memory, it is possible that two or more caches may have copies of the same line. It is also possible that a given line may contain more than one lockable data item. If two threads make appropriately serialized changes to those data items, the result could be that both caches end up with different, incorrect versions of the line of memory. In other words, the system's state is no longer coherent because the system contains two different versions of what is supposed to be the content of a specific area of memory. Various protocols have been devised to address the issue of cache coherence problem, such as MSI, MESI, MOESI, [http://www.enotes.com/topic/MERSI_protocol MERSI], MESIF, Synapse, Berkeley, [https://parasol.tamu.edu/~rwerger/Courses/654/cachecoherence1.pdf Firefly] and [http://www.cs.utah.edu/~rajeev/cs7820/pres/08-7820-03.pdf Dragon] protocol. In this wiki article, MSI, MESI, MESIF, MOESI and Synapse protocol implementations on real architectures will be discussed.<ref>[http://www.windowsnetworking.com/articles_tutorials/cache-coherency.html Cache Coherence]</ref>