Cache coherency protocols (examples)
Examples of coherency protocols for cache memory are listed here. For simplicity, all "miss" Read and Write status transactions which obviously come from state "I" (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 as Multiprocessor system, multi-core and  NUMA system, where a dedicated cache for each processor, core or node is used, a consistency problem may occur when a same data is stored in more than one cache. This problem arises when a data is modified in one cache. 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), while the memory may be updated (write through) or not updated (write-back).

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 (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 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 previously approach, bus for address and crossbar for Data (Data crossbar).

The bottleneck of these systems is the traffic and the Memory bandwidth. Bandwidth can be increasing by using large data bus path, data crossbar, memory interleaving (multi-bank parallel access) and out of order data transaction. The traffic can reduced by using a cache that acts as a "filter" versus the shared memory, that is the cache is an essential element for shared-memory in SMP systems.

In multiprocessor systems with separate caches that share a common memory, a same datum can be stored in more than one cache. A data consistency problem may occur when a data is modified in one cache only.
The protocols to maintain the coherency for multiple processors are called cache-coherency protocols.

Usually in SMP the coherency is based on the "Bus watching" or "Snoopy" (after the Peanuts' character Snoopy ) approach.
In a snooping system, all the caches monitor (or snoop) the bus transactions to intercept the data and determine if they have a copy on its cache.

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 as the actions that these produce. These actions can be invoked from processor or bus (e.g. intervention, invalidation, broadcasting, updating, etc.). The type of actions are implementation depending. Protocols having the same states and the same transaction rules may be different, for instance protocol MESI with shared-intervention on unmodified data and MESI without intervention (see below). Protocols with different states may be practically the same protocol, for instance the 4-state MESI Illinois  and 5-state MERSI (R-MESI) IBM / MESIF-Intel protocols are only a different implementation of the same functionality (see below).

The most common and popular protocols are considered the 4-state cache known as acronyms MESI and 5-state MOESI, this just only for easy pronunciation, terms derived from the name of the states used. Other protocols use the same states or un subset of these but with different implementations and often with different but equivalent terminology. With the term MESI or MOESI or a subset of these, generally it is referred to a class of protocols instead of a specific protocol.

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 a 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 is responsible for intervention (shared intervention ). On bus read request, the data is supplied by this cache instead of the memory. MERSI and MESIF are the same protocol with different terminology (F instead of R). Some time R is referred as "shared last " (SL).
 The state R = Recent is used not only in MERSI = R-MESI protocol but in several other protocols. This state can be used in combination with other states. For instance 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 correspondent value happens on the bus (address Tag matching) due a valid "Read" or "Write" operation, the entry is updated with a valid copy and its state is changed in 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

Snoopy coherency operations 

 Bus Transactions
 Data Characteristics
 Cache Operations

Bus transactions 

The main operations are:

 Write Through
 Write-Back
 Write Allocate
 Write-no-Allocate
 Cache Intervention
 Shared Intervention
 Dirty Intervention
 Invalidation
 Write-broadcast
 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 consuming. It is better for single write.

Write-Back
 Data is written only in cache. Data is Write-Back to MM only when the data is replaced in cache or when required by other caches (see Write policy).
 It is better for multi-write 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 in cache (updating-partial write) (see Write policy).

Write-no-Allocate
 On miss the data is written only in MM without to involve the cache, or as in Bull HN ISI protocol, in the "owner" that is in D or SD cache (owner updating), if they are, else in MM.
 Write-no-Allocate usually is 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 more faster than a MM access, and in addition it save memory bandwidth (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
 – On Write Hit with S (V) or O (SD) (shared) state, a bus transaction is sent to invalidate all the copies on the other caches (Write-invalidate).

 Write-broadcast (Write-update)
 – On Write Hit  with S (V) or O (SD) (shared) state, a write is forward to other caches to update their copies (e.g. Intel Nehalem Dragon protocol, Firefly  (DEC).

 – Note – The updating operation on the other caches some time is called also Snarfing.  The caches snoop the bus and if there is a hit in a cache, this cache snarfs the data that transits on the bus and update its cache. Also the updating of the H in (H-MESI) state can be defined as snarfing. In the first case this happens in a write broadcast operation, on the second case both in read and write operations.

 Intervention-broadcasting
 – On an Intervention transaction, a cache with H state (H-MESI) updates its invalid copy with the value sent on the bus and its state is changed in S.

 Write invalidate vs broadcast
 – Write Invalidate is better when multiple writes, typically partial write, are done by a processor before that the cache line is read by another processor.
 – Write-broadcast (updating) is better when there is a single producer and many consumers of data, but it is worse when a cache is filled with data that will be not next read again (bus traffic increasing, cache interference increasing).

- Invalidation is the common solution.

Data characteristics 

There are three characteristics of cached data:

 Validity
 Exclusiveness
 Ownership

 Validity
 – Any not invalid cache line, that is MOES / D-SD-R-V.
 Exclusiveness
 – Data valid only in one cache (data not shared) in M (D) or E (R) state, with MM not clean in case of M (D) and clean in case of E (R).
 Ownership
 – The cache that is  responsible to supply the request data instead of a MM (Intervention) – Depending on the protocol, cache who must make the intervention can be S-E-M in MESI Illinois, or R/F-E-M in R-MESI type / MESIF or M (D) or O (SD) or also E (R) (*) in MOESI-type protocols, (e.g.  AMD64, Bull HN ISI – see "Read Miss" operation below).

(*) – 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 Hit
 Read Miss
 Write Hit
 Write Miss

 Read Hit

 – Data is read from cache. The state is unchanged
 – Warning: since this is an obvious operation, afterwards it will not be more considered, also in state transaction diagrams.

 Read Miss

 – The data read request is sent to the bus
 – There are several situations:

 Data stored only in MM

 – The data is read from MM.
 – The cache is set  E (R) or S (V)
 – E (R) if a special bus line ("Shared line ") is used to detect "no data sharing ". Used in all protocols having E (R) state except for Write-Once and Bull HN ISI protocols (see "Write Hit" below).

 Data stored in MM and in one or more caches in S (V) state or  in R/F in R-MESI type / MESIF protocols.
 – There are three situations:
 – Illinois protocol – a  network priority is used to temporary and arbitrary assign the ownership to a S copy.  - Data is supplied by the selected cache. Requesting cache is set S (shared intervention with MM clean).
 – R-MESI type / MESIF protocols – a copy is in R/F state (shared owner)  – The data is supplied by the R/F cache. Sending cache is changed in S and the requesting cache is set R/F (in read miss the "ownership" is always taken by the last requesting cache) – shared intervention.
 – In all the other cases the data is supplied by the memory and the requesting cache is set S (V).

 Data stored in MM and only in one cache in E (R) state.
 – Data is supplied by a E (R) cache or by the MM, depending on the protocol.  – From E (R) in extended MESI (e.g. Illinois, Pentium (R) II ), R-MESI type / MESIF and from same MOESI implementation (e.g. AMD64)  – The requesting cache is set S (V), or R/F in R-MESI type / MESIF protocols and E (R) cache is changed in S (V) or  in I in MEI protocol.
 – In all the other cases the data is supplied by the MM.
 Data modified in one or more caches with MM not clean
 Protocol MOESI type – Data stored in M (D) or in O (SD) and the other caches in S (V)
 – Data is sent to the requesting cache from the "owner" M (D) or O (SD). The requesting cache is set S (V) while  M (D) is changed in O (SD).
 – The MM is not updated.
  Protocols MESI type and MEI – Data stored in M (D) and the other caches in S (V) state
 – There are two solutions:
 – Data is sent from the M (D) cache to the requesting cache and also to MM (e.g. Illinois, Pentium (R) II )
 – The operation is made in two steps: the requesting transaction is stopped, the data is sent from the M (D) cache to MM then the wait transaction can proceed and the data is read from MM (e.g. MESI and MSI Synapse protocol).
 – All cache are set  S (V)

 Write Hit

 – The data is written in cache
 – There are several situations:
 Cache in S (V) or R/F or O (SD) (sharing)
 – Write invalidate
 – Copy back
 – The data is written in cache and an invalidating transaction is sent to the bus to invalidate all the other caches
 – The cache is set M (D)
 – Write Through (Write-Once, Bull HN ISI)
 – Data is written in cache and in MM invalidating all the other caches. The cache is set R (E)
 – Write broadcasting (e.g. Firefly, Dragon)
- The data is written in cache and a broadcasting transaction is sent to the bus to update all the other caches having a copy
 – The cache is set M (D) if the "shared line" is off, otherwise is set O (SD). All the other copies are set S (V)

 Cache in E (R) or M (D) state (exclusiveness)
 – The write can take place locally without any other action. The state is set (or remains) M (D)

 Write Miss

 – Write Allocate
 –  Read with Intent to Modified operation (RWITM) 
 – Like a Read miss operation plus an invalidate command, then the cache is written (updated)
 – The requesting cache is set M (D), all the other caches are invalidated
 –  Write broadcasting (e.g. Firefly, Dragon)
 – Like with a Read Miss. If "shared line" is "off" the data is written in cache and set M (D), otherwise like with a Write Hit – Write Broadcasting
 – Write-no-Allocate
 – The data is sent to MM, or like in Bull HN ISI protocol, only to the D (M) or SD (O) cache if they are, bypassing the cache.

Coherency protocols 

 – warning – For simplicity all Read and Write "miss" state transactions that obviously came from I state (or Tag miss), in the diagrams are not depicted. They are depicted directly on the new state.

 – Note – Many of the following protocols have only historical value. At the present the main protocols used are R-MESI type / MESIF  and HRT-ST-MES (MOESI type) or a subset of this.

————————————————————————————————————————

MESI protocol 

  States MESI = D-R-V-I

 – Use of a bus "shared line" to detect "shared" copy in the other caches

Processor operations

 Read Miss

 There are two alternative implementations: standard MESI (not intervention) and extended MESI (with intervention)

 1 – MESI  "no Intervention" (e.g. PowerPC 604 )

 – If there is a M  copy in a cache, the transaction is stopped and wait until the M cache updates the MM, then the transaction can continue and the data is read from MM. Both caches are set S

 – else the data is read from MM. If the "shared line" is "on" the cache is set S else E

 2 – MESI  "Intervention" from M and E  (e.g. Pentium (R) II )

 – If there is a M or E  copy (exclusiveness) in a cache, the data is supplied to the requesting cache from M or from E (Intervention). If the sending cache is M the data is also written at the same time in MM (copy back). All caches are set S

 – else the data is read from MM. If the "shared line" is "on" the cache is set S else E

 Write Hit

 – If the cache is M or E  (exclusiveness), the write can take place locally without any other action
 – else the data is written in cache and an invalidating transaction is sent to the bus to invalidate all the other caches
 – The cache is set M

 Write Miss
 – RWITM operation is sent to the bus. The operation is made in two step: a "Read Miss" with "invalidate" command to invalidate all the other caches, then like with a "Write Hit" with the state M (see Cache operation-Write Miss).

Bus transactions

 Bus Read

 – if  M  and "no Intervention" the data is sent to MM (Copy Back)
 – if  M  and "Intervention"  the data is sent to requesting cache and to MM (Copy Back)
 – if  E (*) and  "Intervention" the data sent to requesting cache
 – The state is changed (or remains) in S

 Bus Read – (RWITM)
 – As like with "Bus read"
 – The cache is set "Invalid" (I)

 Bus Invalidate Transaction
 The cache is set "Invalid" (I)

Operations
 –  Write Allocate
 – Intervention: from M – E (*)
 – Write Invalidate
 – Copy-Back: M replacement

 (*) – extended MESI

————————————————————————————————————————

MOESI protocol 

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

 – Use of bus "shared line"  to detect "shared" copy on the other caches

Processor operations

Read Miss
 – If there is a M or O or E (*) copy in another cache the data is supplied by this cache (intervention). The requesting cache is set S , M  is changed in O and E  in S
 – else the data is read from MM.
 – If  "shared line" is "on" the requesting cache is set S else E

Write Hit
 – If the cache is M or E  (exclusiveness), the write can take place locally without any other action
 – else O or S (sharing) an "Invalidation" transaction is sent on the bus to invalidate all the other caches.
 – The cache is set (or remains) M

Write Miss
 – A RWITM operation is sent to the bus
 – Data is supplied from the "owner" or from MM as with Read Miss, then cache is written (updated)
 – The cache is set  M  and all the other caches are set I

Bus transactions

 Bus Read
 – If the cache is M or O or E (*) the data is sent to requesting cache (intervention). If the cache is E  the state is changed in S, else is set (or remains) O
 – else the state is changed or remains in S

 Bus Read – (RWITM)
 – If the cache is M or O or E (*) the data is sent to the bus (Intervention)
 – The cache is set "Invalid" (I)

 Bus Invalidate Transaction
 – The cache is set "Invalid" (I)

Operations

 Write Allocate
 Intervention: from M-O-E (*)
 Write Invalidate
 Copy-Back: M-O replacement

 – (*) implementation depending for E

————————————————————————————————————————

Illinois protocol 

  States MESI = D-R-V-I

 – Characteristics:
 – It is an extension of MESI protocol
 – Use of a network priority for shared intervention (intervention on shared data)
 – Differences from MESI: in addition to E and M, intervention also from S (see Read Miss – point 1)

Operations
- Write Allocate
- Intervention: from M-E-S
- Write Invalidate
- Copy-Back: M replacement

————————————————————————————————————————

Write-once (or write-first) protocol 

  States D-R-V-I  (MESI) 

 – Characteristics:
 – No use of  "shared line"  (protocol for standard or unmodifiable bus)
 – Write Through on first  Write Hit in state V, then Copy Back

Processor operations

 Read Miss

 – If there is a D copy in another cache, the data is supplied by this cache (intervention) and in the same time it is written also in MM (Copy-Back).
 – else the data is read from MM
 – all caches are set V

 Write Hit
 – If the cache is D or R (exclusiveness), the write can take place locally without any other action and the state is set (or remains) D
 – else V (first Write Hit) the data is written in cache and in MM (Write Through) invalidating all the other caches (Write-Invalidate). – The cache is set R

 Write Miss
 – Like a Read Miss but with "invalidate" command (RWITM) plus a Write Hit in D state (updating). The cache is set D and all the other caches are set "Invalid" (I)

 – Note – Write Through is performed only in "Write Miss". It is point out that in this case a bus transaction in any case is needed to invalidate the other caches and therefore it can be taken advantage of this fact to update also the MM. In "Write Hit" instead no more transaction is needed so a "Write Through" it would become a useless operation in case that the cache were updated again.

Bus transactions

 Bus Read
 – If the cache is D the data is sent  to requesting cache (intervention) and to MM (copy-back). The cache is set V
 – else the state is changed or remains in V

 Bus Read – (RWITM)
 – If the cache is D the data is sent to the bus (Intervention)
 – The cache is set "Invalid" (I)

 Bus Invalidate Transaction
 – The cache is set "Invalid" (I)

Operations

 Write Allocate
 Intervention: from D
 Write Through: first write hit in V state
 Write Invalidate
 Copy-Back: D replacement

————————————————————————————————————————

Bull HN ISI protocol 

(Bull-Honeywell Italia)

  States D-SD-R-V-I  (MOESI) 
  Patented protocol (F. Zulian)

 – Characteristics:
 – MOESI extension of the Write-Once protocol
 - Write-no-allocate on miss with D or SD updating
 - No use of RWITM
 - No use of  "shared line"

Processor operations

 Read Miss
 - Like with MOESI with "Shared Line" "on" and intervention only from the "owner" D or SD but not from R

 Write Hit
 - If the cache is D or R, like with MOESI,  the write can take place locally without any other action. The cache is set (or remains) D
 - If SD or V (first write), like with Write-Once, the data is written in cache and in MM (Write Through) invalidating all the other caches (Write-Invalidate) – The cache is set R

 -  Write Miss
 - The data is sent to the bus bypassing the cache (Write-no-allocate)
 - If there is an "owner" copy D or SD, the "owner" is updated (see Write-no-Allocate – owner updating) while the other caches are invalidated. The "owner" is set (or remains) D. The memory remains "dirty"
 - else the data is sent to MM invalidating all the other caches (Write-Invalidate)

Bus transactions

 Bus Read

 - Like with MOESI with intervention only from "owner" D or SD

 Bus Read (Write Update / Write Invalidate)
 - If the cache is D or SD, the cache is updated, else is set "Invalid" (I)

Operations
 Write-no-allocate: on miss
 Write update: on miss
 Write Through: for the first write, then copy back
 Write Update / Write Invalidate
 Intervention: from SD-D
 Copy-Back: D replacement or SD replacement with invalidate

Obs. - This is the only protocol that has O-E (SD-R) transactions and it is also the only one that makes use of the Write-no-allocated on miss.

————————————————————————————————————————

Synapse protocol 

  States D-V-I  (MSI)

 - Characteristics:
 - The characteristic of this protocol is ti have a single-bit tag with each cache line in MM, indicating that a cache have the line in D state.
 - This bit prevents a possible race condition if the D cache does not respond quickly enough to inhibit the MM from responding before being updating.
 - The data comes always from MM
 - No use of  "shared line"

Processor operations

Read Miss

 - If there is a D copy in another cache, the read transaction is rejected (no acknowledgement). The D copy is written back to MM and changes its state in V, then the requesting cache resends a new read transaction and the data is read from MM.
 - else the data is read from MM.
 - The cache is set V

Write Hit
 - If the cache is D , the write can take place locally without any other action.
 - else V,  like with Read Miss does, including a data transfer from memory with in addition an invalidate command (RWITM). This is done only to invalidate the other V copies because this protocol does not support an invalidation transaction.
 - The cache is set D. All the other caches copy are set "Invalid" (I)

Write Miss (RWITM)
 - Like with Read Miss, but with invalidate command. The cache line comes from MM, then the cache is written (updated). The cache is set D. All the other caches are set "Invalid" (I).

Bus transactions

 Bus Read
 - If the cache is D, the data is sent  to MM (Copy Back). The cache is set V
 - else the state remains in V

 Bus Read (RWITM)
 - If the cache is D the data is sent to MM (Copy Back)
 - The cache (D or V) is set "Invalid" (I)

Operations
 Write Allocate
 Intervention: no intervention
 Write Invalidate: (RWITM)
 No Invalidate transaction
 Copy-Back: D replacement

————————————————————————————————————————

Berkeley protocol 

  States D-SD-V-I  (MOSI)

 - Characteristics:
 - As with MOESI without E state
 - No use of  "shared line"

Processor operations

 Read Miss
 - The data is supplied by the "owner", that is from D or from SD else from MM. D is changed in SD
 - The cache is set V

 Write Hit
 - If the cache is D (exclusiveness), the write can take place locally without any other action
 - else (SD or V), an "Invalidation" transaction is sent on the bus to invalidate the other caches.
 - The cache is set (or remains) D

 Write Miss
 - RWITM operation is sent to the bus
 - Like with Read Miss, the data comes from the "owner", D or SD or from MM, then the cache is updated
 - The cache is set D. all the other caches are set I

Bus transactions

 Bus Read
 - If the cache is D or SD the data is sent  to requesting cache (intervention). The cache is set (or remains) in SD
 - else the cache remains in V

 Bus Read – (RWITM)
 - If the cache is D or SD the data is sent to the bus (Intervention)
 - The cache is set "Invalid" (I)

 Bus Invalidate Transaction
 - The cache is set "Invalid" (I)

Operations

 Write Allocate
 Intervention: from D-SD
 Write Invalidate
 Copy-Back: D-SD replacement

————————————————————————————————————————

Firefly (DEC) protocol 

  States D-VE-S (MES)

 - Characteristics:
 - No "Invalid" state
 - "Write-broadcasting"+"Write Through"
 - Use of  "shared line"
 - "Write-broadcasting" avoid the necessity of "Invalid" state
 - Simultaneous intervention from all caches (shared and dirty intervention – on not modified that modified data)
 - This protocol requires a synchronous bus

Processor operations

 Read Miss
 - Any  other cache is the "owner", that is all the other caches with a copy supplied simultaneously the date on the bus (simultaneous intervention – the bus timing is fixed so that they all respond in the same cycle), otherwise the data is supplied from MM.
 - If there is a cache D, the data is sent simultaneously also to MM (Copy Back)
 - If there are  copies in the other caches, the "Shared line" is set "on"
 - If "Shared line" is "on" all the caches are set S else the requesting cache is set VE.

 Write Hit
 -  If the cache is D or VE (exclusiveness), the write can take place locally without any other action and the cache is set D
 -  else S, a "Write-broadcasting" is sent to the bus to update all the other caches and the MM (Write Through)
 - If there is a copy in another cache, the "Shared line" is set  "on". If "Shared line" is set  "off"  the cache is set VE else all caches are set S

 Write Miss
 - The operation is made in two steps. Read Miss then Write Hit.
 - If the data comes from a cache (Shared Line "on") a "Write-broadcasting" is sent to the bus to update all the other caches and the MM (Write Through). All the caches are set S
 - else the cache is set D

Bus transactions

 Bus Read
 - If hit (D or VE or S) the data is sent to the bus (intervention) and in case of D the data is written also in MM. The cache is set S

 Bus Read
 - If hit (D or VE or S) the data is sent to the bus (Intervention).
 - All the caches are set S

 Write Broadcasting
 - The cache is updated with new data. The state remains S

Operations
 Write Allocate
 Intervention: from D-VE-S (from all "valid" caches)
 Write-broadcasting – Write through
 Copy-Back: D replacement and on any transaction with a cache D

————————————————————————————————————————

Dragon (Xerox) protocol 

  States D-SD-VE-SC (MOES)

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

 - Characteristics:
 - No "Invalid" state
 - "Write-broadcasting" (no "Write Through")
 - Use of  "shared line"
 - "Write-broadcasting" avoid the necessity of "Invalid" state

Processor operations

 Read Miss
 - The data is supplied by the "owner", that is from D or from SD else from MM. D is changed in SD
 - If  "shared line" is "on" the cache is set SC else VE

 Write Hit
 - If the cache is D or VE (exclusiveness), the write can take place locally without any other action. The cache is set (or remains) D
 - else SD or SC (sharing) the data is written in cache and a "Write-broadcasting" is sent to the bus to update all the other caches – The MM is not updated (no Write through)
 - If there is a copy in another cache, the "Shared line" is set "on"
 - If the "Shared Line" is "on" the cache is set SD, else D. All the other caches possible copy are set SC

 Write Miss
 - Like with Read Miss, the data comes from the "owner", D or SD or from MM, then the cache is updated
 - If there is a copy in another cache, the "Shared line" is set "on".
 - If the "Shared Line" is "on" the updated data is broadcast to the other caches and the state is set SD. All the other caches are set SC
 - else the cache is D

Bus transactions

- Bus Read
 - If the cache is D or SD the data is sent  to requesting cache (intervention). The cache is set (or remains) SD
 - else the cache remains SC

 Bus Read
 - If the cache is D or SD the data is sent to the bus (Intervention)
 - The cache is set SC

 Write Broadcasting
 - The cache is updated with new data. The cache remains SC

Operations
 Write Allocate
 Intervention: from D-SD  (but not from VE)
 Write-broadcasting
 Copy-Back: D-SD replacement

————————————————————————————————————————

MERSI (IBM) / MESIF (Intel) protocol 

  States MERSI or R-MESI  
  States MESIF 
  Patented protocols – IBM (1997) – Intel (2002)

 - MERSI and MESIF are the same identical protocol (only the name state is different ,F instead of R)

 - Characteristics:
 - The same functionality of  Illinois protocol
 - A new state R (Recent) / F (Forward) is the "owner " for "shared-clean" data (with MM updated).
 - The "shared ownership" (on clean data) is not assigned by a network priority like with Illinois, but it is always assigned to the last cache with Read Miss, setting its state R/F
 - The "ownership" is temporary loosed in case of R/F replacement. The "ownership" is reassigned again to the next Read Miss with caches "shared clean"
 - Use of the "shared line"

Operations
 Write Allocate
 Intervention: from M-E-R/F
 Write Invalidate
 Copy-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 (R/F cache in MERSI / MESIF  or a selected cache as Illinois type). 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. (see e.g. "Performance evaluation between MOESI (Shanghai) and MESIF  Nehalem-EP")

The most advance systems use only R-MESI / MESIF protocol or the more complete RT-MESI, HRT-ST-MESI and POWER4 IBM protocols that are an enhanced merging of MESI and MOESI protocols

Note: Cache-to-cache is an efficient approach in multiprocessor/multicore systems direct connected between them, but less in Remote cache as in NUMA systems where a standard MESI is preferable. Example in POWER4 IBM protocol "shared intervention" is made only "local" and not between remote module.

————————————————————————————————————————

RT-MESI protocol 

  States RT-MESI 
  IBM patented protocol

 Characteristics:
- MESI and MOESI merging
 - Shared Intervention + Dirty Intervention (both on clean and dirty data)
 - Same functionality of R-MESI protocol with a new state T=Tagged, equivalent to O state
 - "Dirty-Owner" migration
 - The "owner" (both Shared or Dirty) is always the last requesting cache (the new "owner" (LRU) has less probability to be deallocated soon compared to the old one)
 - The "owners" are T, M, E, R (all except S)
 - Use of the "shared line"

Processor operations

 Read Miss
 -  If there is a M or T (dirty-ownership) copy in another cache, the data is supplied by this cache (dirty intervention). The requesting cache is set T  and the previous  M or T are changed in S
 -  If there is a E or R (shared-ownership) copy in another cache, the data is supplied by this cache (shared intervention). The requesting data is set R and E or R are changed in S
 - else the data is read from MM and the cache is set R.

 Write Hit
 - If the cache is M or E  (exclusiveness), the write can take place locally without any other action
 - else T or R or S (sharing) an "Invalidation" transaction is sent on the bus to invalidate all the other caches.
 - The cache is set (or remains) M and all the other caches are set I

 Write Miss
 - RWITM operation is sent to the bus
 - Data is supplied from the "owner" or from the MM as with Read Miss, then the data  is written (updated) in cache.
 - The cache is set M and all the other caches are set I

Bus transactions

 Bus Read
 - If the cache is T or M or R or E the data is sent to requesting cache (intervention).
 - The cache is set (or remains) in S

 Bus Read – (RWITM)
 - If the cache is T or M or R or E the data is sent to requesting cache (intervention)
 - The cache is set "Invalid" (I)

 Bus Invalidate Transaction
 - The cache is set "Invalid" (I)

Operations

 Write Allocate
 Intervention: from T-M-R-E
 Write Invalidate
 Copy-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

 ST = Shared-Tagged

 - Use of the "Shared-Tagged" state allows to maintain intervention after deallocation of a Tagged cache line

 - In case of T replacement (cache line deallocation), the data needs to be written back to MM and so to lose the "ownership". To avoid this, a new state ST can be used. In Read Miss the previous T is set ST instead of S. ST is the candidate to replace the ownership in case of T deallocation. The T "Copy back" transaction is stopped (no MM updating) by the ST cache that changes its state in T. In case of a new read from another cache, this last is set T, the previous T is changed in ST and the previous ST is changed in S.

An additional improvement can be obtained using more than a ST state, ST1, ST2, … STn.

 - In Read Miss, T is changed in ST1 and all the indices of the others STi are increased by "1.
 - In case of T deallocation, ST1 stops the "Copy Back" transaction, changes its state in T and all the indices of the others STi are decrease by "1".
 - In case of a deallocation, for instance STk, the chain will be interrupted and all the STi with index greater of "k" are automatically loosen in term of ST and will be considered de facto only as simple S states also if they are set as ST. All this because only ST1 intervenes to block and to replace itself with T. For instance if  we have a situation type T, ST1, ST3, ST4 with ST2 replaced, if  T will be replaced the new situation will be T,  ST2, ST3 without any ST1.

————————————————————————————————————————

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

 - The main features are :
  - Write Back
  - Intervention both in sharing-clean and dirty data – from T-M-R-E
  - Reserve states of the Tagged (Shared-Tagged)
  - Invalid H state (Hover) auto-updating

(*) – 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-SL = RT-MESI+Mu

 - Use of the "shared line"

 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

 SL   - "Shared Last" equivalent to R on RT-MESI
 Me  - "Valid Exclusive" = E
 Mu – unsolicited modified state
 - special state – asking for a reservation for load and store doubleword (for 64-bit implementations)
 "Shared intervention" from SL 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

 - Write Allocate
 - Intervention: from M-T-VE-SL = M-O-E-SL
 - Write Invalidate
 - Copy-Back: M-T replacement

 - Note : T and SL – Intervention only on the locale  module

————————————————————————————————————————

General considerations on the protocols 

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

 - Write Back
 - Intervention both with dirty than shared-clean data
 - Reserve states of the Tagged state (Shared-Tagged)
 - Invalid H (Hover) state auto-updating

References 

Computer memory
Cache (computing)