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.

Note: Coherency generally applies only to data and not to instructions.
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

Three approaches are adopted to maintain the coherency of data.Bus watching or Snooping – generally used for bus-based SMP – Symmetric Multiprocessor System/multi-core systemsDirectory-based – Message-passing – may be used in all systems, but typically used in [|NUMA system] and in large [|multi-core] systemsShared cache – generally used in multi-core systems

Snoopy coherency protocol

Protocol used in bus-based systems like a SMP systems

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.

Special states: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 (IBM) / MESIF (Intel) protocol	R=Recent – IBM PowerPC G4, MPC7400 F=Forward – Intel Intel Nehalem
[\|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-S_L-I Mu=Unsolicited Modified – Modified Exclusive – T=Tagged – Modified Owner not Exclusive M=Modified Exclusive – Me=Valid Exclusive – S=Shared – S_L=Shared Last – Sourced local – I=Invalid – Special state – Asking for a reservation for load and store doubleword.

Snoopy coherency operations

Bus Transactions
Data Characteristics
Cache Operations

Bus transactions

The main operations are:Write ThroughWrite-BackWrite AllocateWrite-no-Allocate Cache Intervention

* Shared Intervention
* Dirty InterventionInvalidationWrite-broadcast Intervention-broadcasting

Write Through

The cache line is updated both in cache and in MM, or only in MM.
Simple to implement, high bandwidth consumption. It is best used for single write or infrequent write situations.

Write-Back

Data is written only into cache. Data is written back to MM only when the data is replaced in cache or when required by other caches.
It is best used when multiple writes occur on the same cache line.
Intermediate solution: Write Through for the first write, Write-Back for the next.

Write AllocateOn miss, the data is read from the "owner" or from MM, then the data is written into cache .
Write-no-Allocate On miss, the data is written only into MM, not involving the cache. In the same spirit, the [|Bull HN ISI] protocol, writes data only into the "owner" cache line if the line is in state D or SD, but writes only into MM otherwise.

Write-no-Allocate is usually associated with Write Through.Cache InterventionInvalidation Write-broadcast Intervention-broadcasting
'''Write: invalidate vs broadcast'''

Data characteristics

There are three characteristics of cached data:ValidityExclusivenessOwnershipValidityExclusivenessOwnership
– Implementation depending.
Note: Not to confuse the more restrictive "owner" definition in MOESI protocol with this more general definition.

Cache operations

The cache operations are:Read HitRead MissWrite HitWrite MissRead HitRead MissWrite Hit

'''Write Miss'''

Coherency protocols

MESI protocol

States MESI = D-R-V-I

Processor operations
Bus transactions
'''Operations'''

MOESI protocol

States MEOSI = D-R-SD-V-I = T-MESI IBM

Processor operations
Bus transactions
OperationsWrite AllocateIntervention: from M-O-E Write InvalidateCopy-Back: M-O replacement

Illinois protocol

States MESI = D-R-V-I

'''Operations'''

Write-once (or write-first) protocol

States D-R-V-I

Processor operations
Bus transactions
OperationsWrite AllocateIntervention: from DWrite Through: first write hit in V stateWrite InvalidateCopy-Back: D replacement

Bull HN ISI protocol

States D-SD-R-V-I

Patented protocol

Processor operations
Bus transactions
OperationsWrite-no-allocate: on missWrite update: on missWrite Through: for the first write, then copy backWrite Update / Write InvalidateIntervention: from SD-DCopy-Back: D replacement or SD replacement with invalidate

Synapse protocol

States D-V-I

Processor operations
Bus transactions
OperationsWrite AllocateIntervention: no interventionWrite Invalidate: No Invalidate transactionCopy-Back: D replacement

Berkeley protocol

States D-SD-V-I

Processor operations
Bus transactions
OperationsWrite AllocateIntervention: from D-SDWrite InvalidateCopy-Back: D-SD replacement

Firefly (DEC) protocol

States D-VE-S

Processor operations
Bus transactions
OperationsWrite AllocateIntervention: from D-VE-S Write-broadcasting – Write throughCopy-Back: D replacement and on any transaction with a cache D

Dragon (Xerox) protocol

States D-SD-VE-SC
Note – the state SC, despite the term "clean", can be "clean" or "dirty" as the S state of the other protocols. SC and S are equivalents

Processor operations
Bus transactions
OperationsWrite AllocateIntervention: from D-SD Write-broadcastingCopy-Back: D-SD replacement

MERSI (IBM) / MESIF (Intel) protocol

States MERSI or R-MESI

States MESIF

Patented protocols – IBM – Intel

OperationsWrite AllocateIntervention: from M-E-R/FWrite InvalidateCopy-Back: M replacement

MESI vs MOESI

MESI and MOESI are the most popular protocols
It is common opinion that MOESI is an extension of MESI protocol and therefore it is more sophisticate and more performant.
This is true only if compared with standard MESI, that is MESI with "not sharing intervention". MESI with "sharing intervention", as MESI Illinois like or the equivalent 5-state protocols [|MERSI / MESIF], are much more performant than the MOESI protocol.
In MOESI, cache-to-cache operations is made only on modified data. Instead in MESI Illinois type and MERSI / MESIF protocols, the cache-to-cache operations are always performed both with clean that with modified data. In case of modified data, the intervention is made by the "owner" M, but the ownership is not loosed because it is migrated in another cache. The only difference is that the MM must be updated. But also in MOESI this transaction should be done later in case of replacement, if no other modification occurs meanwhile. However this it is a smaller limit compared to the memory transactions due to the not-intervention, as in case of clean data for MOESI protocol.
The most advanced systems use only [|R-MESI / MESIF] protocol or the more complete RT-MESI, HRT-ST-MESI, and POWER4 IBM protocols, which are an enhanced merging of MESI and MOESI protocols.
Note: Cache-to-cache is an efficient approach in multiprocessor/multicore systems that have direct connections between caches, but it is less efficient in [|Remote caches], such as in [|NUMA systems] where a standard MESI is preferable. For example, POWER4 IBM's protocol with Shared Intervention is only done "local"ly, not between remote modules.

RT-MESI protocol

States RT-MESI

IBM patented protocol

Characteristics:

Processor operations

Bus transactions
OperationsWrite AllocateIntervention: from T-M-R-EWrite InvalidateCopy-Back: T-M replacement

RT-ST-MESI protocol

It is an improvement of RT-MESI protocol and it is a subset of HRT-ST-MESI protocol
An additional improvement can be obtained using more than a S_T state, S_T1, S_T2, … S_Tn.

HRT-ST-MESI protocol

IBM patented full HRT-ST-MESI protocol
- I state = Invalid Tag – Invalid Data

- H state = Valid Tag – Invalid Data
- I state is set at the cache initialization and its state changes only after a processor Read or Write miss. After it will not return more in this state.
- H has the same functionality of I state but in addition with the ability to capture any bus transaction that match the Tag of the directory and to update the data cache.
- After the first utilization I is replaced by H in its functions
– Note: The Tag for definition is always valid, but until the first updating of the cache line it is considered invalid in order to avoid to update the cache also when this line has been not still required and used.

POWER4 IBM protocol

States M-T-Me-S-I -Mu-S_L = RT-MESI+Mu

Used in [|multi-core/module systems] – multi L2 cache
This protocol is equivalent to the RT-MESI protocol for system with multi L2 cache on [|multi-module systems]
"Shared intervention" from S_L is done only between L2 caches of the same module
"Dirty intervention" from T is done only between L2 caches of the same module
'''Operations'''

General considerations on the protocols

Under some conditions the most efficient and complete protocol turns out to be the HRT-ST-MESI protocol.