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" ("invalid", or miss of Tag), 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 (MOESI type) 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 (copied and) 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 ("broadcast-invalidate") Update all the copies on other caches (write-broadcasting) to the new correct value, while the Main Memory (MM) may be updated immediately ("write-through") or not updated until absolutely necessary ("write-back" or "write-deferred").

Note: Coherency generally applies only to data (as operands) and not to instructions (see Self-Modifying Code).

The schemes can be classified based on:

Snoopy scheme vs Directory scheme and vs Shared caches Write-through vs Write-back (WB is ownership-based) protocol Update vs Invalidation protocol Intervention vs not Intervention Dirty-sharing vs not-Dirty-sharing protocol (MOESI vs MESI)

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 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

Protocol used in bus-based systems like a SMP systems

SMP – symmetric multiprocessor systems

Systems operating under a single OS (Operating System) 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 ("xbar") or a mix of two previous approaches, bus for Address and crossbar for Data (Data crossbar).

The bottleneck of these systems is the traffic and the Memory bandwidth. Bandwidth can be increased by using a larger data bus path (more wires between MM and each component), data crossbar, memory interleaving (multi-bank parallel access) 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" (after the Peanuts' character Snoopy ) approach. In a snooping system, all the caches monitor ("snoop") the bus transactions to intercept the bus data and determine if it (each specific cache) 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 (from 3 to 5 and 7 or more) 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 (e.g. intervention, invalidation, broadcasting, etc.). 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 (see below). 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 (R-MESI) IBM / MESIF-Intel protocols are only different implementations of the same functionality (see below).

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 (invalid, not clean). 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 (invalid, not clean). Only one cache is the "owner", other caches are set "Valid" (S/V/SC). 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 (see Dragon protocol). I=Invalid. Cache line invalid. If the cache line is not present (no tag matching) 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 (MERSI or R-MESI IBM, MESIF – Intel). 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 (shared 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 (F instead of R). Sometimes R is referred to as "shared last " (SL)."IBM PowerPC 476FP L2 Cache Core Databook" 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 (additional state of MESI protocol) The Hover (H) 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 (i.e., if address Tag on bus matches address Tag in cache) 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 (Xeon 5400) MOSI protocol Berkeley protocol MOESI protocol AMD64, MOESI, T-MESI IBM

Terminology used Illinois protocol D-VE-S-I (= extended MESI) Write-once or Write-first D-R-V-I (= MESI) Berkeley protocol D-SD-V-I (= MOSI)   Synapse protocol D-V-I (= MSI)     Firefly protocol D-VE-S (= MES) DEC Dragon protocol D-SD (SM ?)-SC-VE (= MOES) Xerox Bull HN ISI protocol D-SD-R-V-I (= MOESI) 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-SL-I  ( L2 seven states)

Mu=Unsolicited Modified – Modified Exclusive – (D/M) (*) T=Tagged – Modified Owner not Exclusive (SD/O) M=Modified Exclusive – (D) Me=Valid Exclusive – (R/E) S=Shared – (V) SL=Shared Last – Sourced local – (Shared Owner Local) I=Invalid – (I)

(*) Special state – Asking for a reservation for load and store doubleword (for 64-bit implementations).

Snoopy coherency operations

Bus Transactions Data Characteristics Cache Operations

Bus transactions

The main operations are:

Write Through Write-Back Write Allocate Write-no-Allocate (or Write Around) Cache Intervention Shared Intervention Dirty Intervention Invalidation Write-broadcast (or Write-update) Intervention-broadcasting

Write Through The cache line is updated both in cache and in MM, or only in MM (write no-allocate). 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 (see Write policy, "cache eviction"). 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-once and Bull HN ISI protocols).

Write Allocate On miss, the data is read from the "owner" or from MM, then the data is written into cache (updating-partial write) (see Write policy).

Write-no-Allocate (Write Around) 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 (owner updating), but writes only into MM otherwise. Write-no-Allocate is usually associated with Write Through. Cache Intervention (or shortly "intervention ")

– Shared Intervention – shared-clean intervention (on unmodified data) – On Read Miss the data is supplied by the owner E or R/F or also S instead of the MM (see protocols Illinois, IBM R-MESI type and Intel MESIF).

– Dirty Intervention (on modified data) – On Read Miss the data is supplied by the M (D) or O (SD) owner or by E (R) (*) instead of MM (e.g. MOESI protocol, RT-MESI, …).

(*) – Not for E (R) in the original proposal MOESI protocol and in some other implementations MOESI-Type.

– "Intervention " is better compared to the "not intervention " because cache-to-cache transactions are much faster than a MM access, and in addition it saves memory bandwidth that would otherwise occur on the MM bus (memory traffic reduction). Extended MESI Illinois and R-MESI type / MESIF are therefore much better than the MOESI protocol (see MESI vs MOESI below)

Invalidation (Write-invalidate, invalidate-broadcast, write-invalidate-broadcast, not to be confused with write-broadcast) – On Write Hit with S (V) or O (SD) (shared) state, a single bus transaction is sent to invalidate all the copies on the other caches.