List of cache coherency protocols
Examples of coherency protocols for cache memory are listed here. For simplicity, all "miss" Read and Write status transactions, which all only come from state "I", in the diagrams are not shown. They are shown directly on the new state. Many of the following protocols have only historical value. At the moment the main protocols used are the R-MESI type / MESIF protocols and the [|HRT-ST-MESI] or a subset or an extension of these.
Cache coherency problem
In systems such as Multiprocessor, [|multi-core] and NUMA systems, where a dedicated cache exists for each processor, core or node, a consistency problem may occur when the same piece of data is stored in more than one cache. This problem arises when the data value is modified in one cache but has not been modified in the other caches, leading to an unknown "ground truth" value of the piece of data across the entire system, where each cache's version of the piece of data is treated as equally valid. This problem can be solved in two ways:- Invalidate all the copies on other caches
- Update all the copies on other caches to the new correct value, while the Main Memory may be updated immediately or not updated until absolutely necessary.
The schemes can be classified based on:
- Snoopy scheme vs Directory scheme and vs Shared caches
- Write-through vs Write-back protocol
- Update vs Invalidation protocol
- Intervention vs not Intervention
- Dirty-sharing vs not-Dirty-sharing protocol
- Bus watching or Snooping – generally used for bus-based SMP – Symmetric Multiprocessor System/multi-core systems
- Directory-based – Message-passing – may be used in all systems, but typically used in [|NUMA system] and in large multi-core systems
- Shared cache – generally used in multi-core systems
Snoopy coherency protocol
SMP – symmetric multiprocessor systems
Systems operating under a single OS with two or more homogeneous processors and with a centralized shared Main Memory
Each processor has its own cache that acts as a bridge between processor and Main Memory. The connection is made using a System Bus or a Crossbar or a mix of two previous approaches, bus for Address and crossbar for Data.
The bottleneck of these systems is the traffic and the Memory bandwidth. Bandwidth can be increased by using a larger data bus path, data crossbar, memory interleaving and out of order data transaction. The traffic can be reduced by using a cache that acts as a "filter", eliminating the need for each processor cache to directly access the shared memory for every transaction; thus, the cache is an essential element for utilizing shared-memory in SMP systems.
In multiprocessor systems with separate caches that share a common memory, the same [|datum] can be stored in more than one cache. A data consistency problem may occur when the datum is modified in only one of the caches.
The protocols to maintain the coherency for multiple processors are called [|cache-coherency protocols].
In SMP, the coherency is usually based on the "Bus watching" or "Snoopy" approach.
In a snooping system, all the caches monitor the bus transactions to intercept the bus data and determine if it has a copy of that data.
Various cache-coherency protocols are used to maintain data coherency between caches.
These protocols are generally classified based only on the cache states and the transactions between them, but this could create some confusion.
This definition is incomplete because it lacks important and essential information about the actions that each protocol produces. These actions can be invoked by the processor or the bus controller. The type of actions is implementation dependent. The states and transaction rules do not capture everything about a protocol. For instance, protocol [|MESI] with shared-intervention on unmodified data is different from MESI without intervention. At the same time, some protocols with different states can be practically the same. For instance, the 4-state MESI [|Illinois] and 5-state MERSI IBM / MESIF-Intel protocols are only different implementations of the same functionality.
The most common protocols are the 4-state MESI and the 5-state MOESI, each letter standing for one of the possible states of the cache. Other protocols use some [|proper subset] of these but with different implementations along with their different but equivalent terminology. The terms MESI, MOESI or any subset of them generally refer to a class of protocols instead of a specific one.
Cache states
The states MESI and MOESI are often and more commonly called by different names.- M=Modified or D=Dirty or DE=Dirty-Exclusive or EM=Exclusive Modified
- * modified in one cache only – write-back required at replacement.
- * data is stored only in one cache but the data in memory is not updated.
- O=Owner or SD=Shared Dirty or SM=Shared Modified or T=Tagged
- * modified, potentially shared, owned, write-back required at replacement.
- * data may be stored in more than one cache but the data in memory is not updated. Only one cache is the "owner", other caches are set "Valid". On bus read request, the data is supplied by the "owner" instead of the memory.
- E=Exclusive or R=Reserved or VE=Valid-Exclusive or EC=Exclusive Clean or Me=Exclusive
- * clean, in one cache only.
- * Data is stored only in one cache and clean in memory.
- S=Shared or V=Valid or SC=Shared Clean
- * shared or valid
- * Data potentially shared with other caches. The data can be clean or dirty. The term "clean" in SC is misleading because can be also dirty.
- I=Invalid.
- * Cache line invalid. If the cache line is not present it is considered equivalent to invalid, therefore invalid data means data present but invalid or not present in cache.
- F=Forward or R=Recent
- * Additional states of [|MESI protocol]
- * Last data read. It is a special "Valid" state that is the "Owner" for non modified shared data, used in some extended MESI protocols. The R/F state is used to allow "intervention" when the value is clean but shared among many caches. This cache in the R/F state is responsible for intervention. On a bus read request, the data is supplied by this cache instead of being supplied by the main memory. MERSI and MESIF are the same protocol with different terminology. Sometimes R is referred to as "shared last ".
- * The state R = Recent is used not only in the MERSI = R-MESI protocol, but in several other protocols as well. This state can be used in combination with other states, such as in RT-MESI, HR-MESI, HRT-MESI, HRT-ST-MESI. All protocols that use this state will be refereed as R-MESI type.
- H=Hover – H-MESI
- * The Hover state allows a cache line to maintain an address Tag in the directory even though the corresponding value in the cache entry is an invalid copy. If the corresponding value happens on the bus during a valid "Read" or "Write" operation, the cache entry is updated to be the valid copy and its state is changed from H to S.
- * This state can be used in combination with other states. For instance HR-MESI, HT-MESI, HRT-MESI, HRT-ST-MESI.
Various coherency protocols
| Protocols | |
| SI protocol | Write-Through |
| MSI protocol | Synapse protocol |
| MEI protocol | IBM PowerPC 750, MPC7400 |
| MES protocol | Firefly protocol |
| MESI protocol | Pentium II, PowerPC, Intel Harpertown |
| MOSI protocol | Berkeley protocol |
| MOESI protocol | AMD64, MOESI, T-MESI IBM |
| Terminology used | |
| Illinois protocol | D-VE-S-I |
| Write-once or Write-first | D-R-V-I |
| Berkeley protocol | D-SD-V-I |
| Synapse protocol | D-V-I |
| Firefly protocol | D-VE-S DEC |
| Dragon protocol | D-SD -SC-VE Xerox |
| Bull HN ISI protocol | D-SD-R-V-I |
| MERSI / MESIF protocol |
|
| HRT-ST-MESI protocol | H=Hover, R=Recent, T=Tagged, ST=Shared-Tagged – IBM– Note: The main terminologies are SD-D-R-V-I and MOESI and so they will be used both. |
| POWER4 IBM protocol | Mu-T-Me-M-S-SL-I
|