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.
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.
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
SMP – Symmetric Multiprocessor System
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).[1][2][3]
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.
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 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.
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,[5][6] MESIF – Intel[7][8]). 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).[9][10]
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.[6][11][12] All protocols that use this state will be refereed as R-MESI type.
H=Hover – H-MESI (additional state of MESI protocol)[11]
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.[6][11][12]
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[20] 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[16] 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 withwrite-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.
Write-broadcast (Write-update)
– On Write Hit with S (V) or O (SD) (shared) state, a write is forwarded to other caches to update their copies (e.g. Intel Nehalem[22]Dragon protocol, Firefly (DEC).
– Note – The updating operation on the other caches is sometimes also called 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, updating itself. Also, the updating of the H in (H-MESI) state can be defined as snarfing. In the first case[clarification needed], this happens in a write-broadcast operation. On the second case[clarification needed], it happens 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 to S.[6]
Write: invalidate vs broadcast
– Write Invalidate is better when multiple writes, typically partial write, are done by a processor before that cache line is read by another processor.
– Write-broadcast (updating) is best used when there is a single producer (modifier) and many consumers (receivers) of data. It is worse when a cache is filled with data that will not be read again in the near future (increased bus traffic, increased cache interference).
- 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,[16]Bull HN ISI[20] – 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 [14]), 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 [14])
– 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
– 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
MESI Protocol – State Transaction Diagram
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 [24])
– 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 [14])
– 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
– 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 to O and E to 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.
– 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
– 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
- 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.
- 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)
- 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
- "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
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
- 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
MERSI – MESIF Protocol – State Transaction Diagram
States MERSI or R-MESI States MESIF Patented protocols – IBM (1997)[6] – Intel (2002)[8]
- MERSI and MESIF are the same identical protocol (only the name state is different ,F instead of R)
- 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"
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"[21])
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.
- 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
- 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.
- 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.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
