MESI protocol
Encyclopedia
The MESI protocol is a widely used cache coherency
and memory coherence
protocol. It is the most common protocol which supports write-back cache
. Its use in personal computers became widespread with the introduction of Intel's Pentium processor to "support the more efficient write-back cache in addition to the write-through cache previously used by the Intel 486
processor".
s):
Modified: The cache line is present only in the current cache, and is dirty; it has been modified from the value in main memory. The cache is required to write the data back to main memory at some time in the future, before permitting any other read of the (no longer valid) main memory state. The write-back changes the line to the Exclusive state.
Exclusive: The cache line is present only in the current cache, but is clean; it matches main memory. It may be changed to the Shared state at any time, in response to a read request. Alternatively, it may be changed to the Modified state when writing to it.
Shared: Indicates that this cache line may be stored in other caches of the machine and is "clean" ; it matches the main memory. The line may be discarded (changed to the Invalid state) at any time.
Invalid: Indicates that this cache line is invalid.
For any given pair of caches, the permitted states of a given cache line are as follows:
A cache may satisfy a read from any state except Invalid. An Invalid line must be fetched (to the Shared or Exclusive states) to satisfy a read.
A write may only be performed if the cache line is in the Modified or Exclusive state. If it is in the Shared state, all other cached copies must be invalidated first. This is typically done by a broadcast operation known as Request For Ownership (RFO).
A cache may discard a non-Modified line at any time, changing to the Invalid state. A Modified line must be written back first.
A cache that holds a line in the Modified state must snoop (intercept) all attempted reads (from all of the other caches in the system) of the corresponding main memory location and insert the data that it holds. This is typically done by forcing the read to back off (i.e. retry later), then writing the data to main memory and changing the cache line to the Shared state.
A cache that holds a line in the Shared state must listen for invalidate for request-for-ownership broadcasts from other caches, and discard the line (by moving it into Invalid state) on a match.
A cache that holds a line in the Exclusive state must also snoop all read transactions from all other caches, and move the line to Shared state on a match.
The Modified and Exclusive states are always precise: i.e. they match the true cache line ownership situation in the system. The Shared state may be imprecise: if another cache discards a Shared line, this cache may become the sole owner of that cache line, but it will not be promoted to Exclusive state. Other caches do not broadcast notices when they discard cache lines, and this cache could not use such notifications without maintaining a count of the number of shared copies.
In that sense the Exclusive state is an opportunistic optimization: If the CPU wants to modify a cache line that is in state S, a bus transaction is necessary to invalidate all other cached copies. State E enables modifying a cache line with no bus transaction.
protocols that combines a read and an invalidate broadcast. The operation is issued by a processor trying to write into a cache line that is not exclusive or not modified to itself, i.e., that is in the shared (S) or invalid (I) states of the MESI protocol. The operation causes all other processors to set the state of such line to I. A read for ownership transaction is a read operation with intent to write to that memory address. Therefore this operation is exclusive. It brings data to the cache and invalidates all other processor caches which hold this memory line.
Cache coherency
In computing, cache coherence refers to the consistency of data stored in local caches of a shared resource.When clients in a system maintain caches of a common memory resource, problems may arise with inconsistent data. This is particularly true of CPUs in a multiprocessing system...
and memory coherence
Memory coherence
Memory coherence is an issue that affects the design of computer systems in which two or more processors or cores share a common area of memory....
protocol. It is the most common protocol which supports write-back cache
CPU cache
A CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. The cache is a smaller, faster memory which stores copies of the data from the most frequently used main memory locations...
. Its use in personal computers became widespread with the introduction of Intel's Pentium processor to "support the more efficient write-back cache in addition to the write-through cache previously used by the Intel 486
Intel 80486
The Intel 80486 microprocessor was a higher performance follow up on the Intel 80386. Introduced in 1989, it was the first tightly pipelined x86 design as well as the first x86 chip to use more than a million transistors, due to a large on-chip cache and an integrated floating point unit...
processor".
States
Every cache line is marked with one of the four following states (coded in two additional bitBit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s):
Modified: The cache line is present only in the current cache, and is dirty; it has been modified from the value in main memory. The cache is required to write the data back to main memory at some time in the future, before permitting any other read of the (no longer valid) main memory state. The write-back changes the line to the Exclusive state.
Exclusive: The cache line is present only in the current cache, but is clean; it matches main memory. It may be changed to the Shared state at any time, in response to a read request. Alternatively, it may be changed to the Modified state when writing to it.
Shared: Indicates that this cache line may be stored in other caches of the machine and is "clean" ; it matches the main memory. The line may be discarded (changed to the Invalid state) at any time.
Invalid: Indicates that this cache line is invalid.
For any given pair of caches, the permitted states of a given cache line are as follows:
| M | E | S | I | |
|---|---|---|---|---|
| M | ||||
| E | ||||
| S | ||||
| I |
Operation
In a typical system, several caches share a common bus to main memory. Each also has an attached CPU which issues read and write requests. The caches' collective goal is to minimize the use of the shared main memory.A cache may satisfy a read from any state except Invalid. An Invalid line must be fetched (to the Shared or Exclusive states) to satisfy a read.
A write may only be performed if the cache line is in the Modified or Exclusive state. If it is in the Shared state, all other cached copies must be invalidated first. This is typically done by a broadcast operation known as Request For Ownership (RFO).
A cache may discard a non-Modified line at any time, changing to the Invalid state. A Modified line must be written back first.
A cache that holds a line in the Modified state must snoop (intercept) all attempted reads (from all of the other caches in the system) of the corresponding main memory location and insert the data that it holds. This is typically done by forcing the read to back off (i.e. retry later), then writing the data to main memory and changing the cache line to the Shared state.
A cache that holds a line in the Shared state must listen for invalidate for request-for-ownership broadcasts from other caches, and discard the line (by moving it into Invalid state) on a match.
A cache that holds a line in the Exclusive state must also snoop all read transactions from all other caches, and move the line to Shared state on a match.
The Modified and Exclusive states are always precise: i.e. they match the true cache line ownership situation in the system. The Shared state may be imprecise: if another cache discards a Shared line, this cache may become the sole owner of that cache line, but it will not be promoted to Exclusive state. Other caches do not broadcast notices when they discard cache lines, and this cache could not use such notifications without maintaining a count of the number of shared copies.
In that sense the Exclusive state is an opportunistic optimization: If the CPU wants to modify a cache line that is in state S, a bus transaction is necessary to invalidate all other cached copies. State E enables modifying a cache line with no bus transaction.
Request For Ownership
A Request For Ownership (RFO) is an operation in cache coherencyCache coherency
In computing, cache coherence refers to the consistency of data stored in local caches of a shared resource.When clients in a system maintain caches of a common memory resource, problems may arise with inconsistent data. This is particularly true of CPUs in a multiprocessing system...
protocols that combines a read and an invalidate broadcast. The operation is issued by a processor trying to write into a cache line that is not exclusive or not modified to itself, i.e., that is in the shared (S) or invalid (I) states of the MESI protocol. The operation causes all other processors to set the state of such line to I. A read for ownership transaction is a read operation with intent to write to that memory address. Therefore this operation is exclusive. It brings data to the cache and invalidates all other processor caches which hold this memory line.
See also
- Coherence protocol
- MSI protocolMSI protocolThe MSI protocol is a basic Cache coherence protocol that is used in multiprocessor systems. As with other cache coherency protocols, the letters of the protocol name identify the possible states in which a cache line can be. So, for MSI, each block contained inside a cache can have one of three...
, the basic protocol from which the MESI protocol is derived. - Write-once (cache coherency)Write-once (cache coherency)In cache coherency protocol literature, Write-Once was the first write-invalidate protocol defined. It has the optimization of executing write-update on the first write and a write-invalidate on all subsequent writes, reducing the overall bus traffic in consecutive writes to the computer memory. It...
, an early form of the MESI protocol. - MOSI protocolMOSI protocolThe MOSI protocol is an extension of the basic MSI cache coherency protocol. It adds the Owned state, which indicates that the current processor owns this block, and will service requests from other processors for the block....
- MOESI protocolMOESI protocolIn computing, MOESI is a full cache coherency protocol that encompasses all of the possible states commonly used in other protocols. In addition to the four common MESI protocol states, there is a fifth "Owned" state representing data that is both modified and shared. This avoids the need to...
- MESIF protocolMESIF protocolThe MESIF protocol is a cache coherency and memory coherence protocol developed by Intel for cache coherent non-uniform memory architectures. The protocol consists of five states, Modified , Exclusive , Shared , Invalid and Forward ....
- MERSI protocolMERSI protocolThe MERSI protocol is a cache coherency and memory coherence protocol used by the PowerPC G4. The protocol consists of five states, Modified , Exclusive , Read Only or Recent , Shared and Invalid . The M, E, S and I states are the same as in the MESI protocol...