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.
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:
Note: Coherency generally applies only to data (as operands) and not to instructions (see Self-Modifying Code).
The schemes can be classified based on:
Three approaches are adopted to maintain the coherency of data.
Protocol used in bus-based systems like a SMP 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).[1] [2] [3]
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 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.[4]
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 by the processor or the bus controller (e.g. intervention, invalidation, broadcasting, etc.). The type of actions are implementation dependent. The states and transaction rules do not capture everything about a protocol. For instance protocol MESI with shared-intervention on unmodified data and MESI without intervention are different (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.
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 ModifiedSpecial states:
F=Forward or R=Recent| Protocols | ||
|---|---|---|
| SI protocol | Write Through | |
| MSI protocol | Synapse protocol | |
| MEI protocol | IBM PowerPC 750,[11] MPC7400 | |
| MES protocol | Firefly protocol | |
| Pentium II,[12] PowerPC, Intel Harpertown (Xeon 5400) | ||
| MOSI protocol | Berkeley protocol | |
| AMD64,[13] MOESI,[14] T-MESI IBM |
| Terminology used | ||
|---|---|---|
| D-VE-S-I (= extended MESI)[15] | ||
| D-R-V-I (= MESI) [16] [17] | ||
| D-SD-V-I (= MOSI) | ||
| D-V-I (= MSI) | ||
| D-VE-S (= MES) DEC | ||
| D-SD (SM ?)-SC-VE (= MOES) Xerox | ||
| Bull HN ISI protocol | D-SD-R-V-I (= MOESI) | |
| ||
| 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. | ||
| Mu-T-Me-M-S-SL-I (L2 seven states)[20] 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). |
The main operations are:
Write Through
Write-Back
Write Allocate
Write-no-Allocate
(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)
– 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).
– 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.
– 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 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.
There are three characteristics of cached data:
– Any not invalid cache line, that is MOES / D-SD-R-V.
– 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).
– 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[21] – see "Read Miss" operation below).
(*) – Implementation depending.
Note: Not to confuse the more restrictive "owner" definition in MOESI protocol with this more general definition.
The cache operations are:
– 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.– The data read request is sent to the bus
– There are several situations:
– 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).
– There are three situations:
– 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.
– There are two solutions:
– All cache are set S (V)
– The data is written in cache
– There are several situations:
– 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)
– The write can take place locally without any other action. The state is set (or remains) M (D)
– 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.
– 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.
————————————————————————————————————————
States MESI = D-R-V-I
– Use of a bus "shared line" to detect "shared" copy in the other caches
There are two alternative implementations: standard MESI (not intervention) and extended MESI (with intervention)
1 – MESI "no Intervention" (e.g. PowerPC 604 [22])
– 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
– 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
– 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).
– 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
– As like with "Bus read"
– The cache is set "Invalid" (I)
The cache is set "Invalid" (I)
– Write Allocate
– Intervention: from M – E (*)
– Write Invalidate
– Copy-Back: M replacement
(*) – extended MESI
————————————————————————————————————————
States MEOSI = D-R-SD-V-I = T-MESI IBM
– Use of bus "shared line" to detect "shared" copy on the other caches
– 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
– 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
– 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
– 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
– If the cache is M or O or E (*) the data is sent to the bus (Intervention)
– The cache is set "Invalid" (I)
– The cache is set "Invalid" (I)
– (*) implementation depending for E
————————————————————————————————————————
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)
- Write Allocate
- Intervention: from M-E-S
- Write Invalidate
- Copy-Back: M replacement
————————————————————————————————————————
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
– 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
– 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
– 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.
– 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
– If the cache is D the data is sent to the bus (Intervention)
– The cache is set "Invalid" (I)
– The cache is set "Invalid" (I)
————————————————————————————————————————
(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"
- Like with MOESI with "Shared Line" "on" and intervention only from the "owner" D or SD but not from R
- 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)
- Like with MOESI with intervention only from "owner" D or SD
- If the cache is D or SD, the cache is updated, else is set "Invalid" (I)
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.
————————————————————————————————————————
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"
- 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
- 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).
- If the cache is D, the data is sent to MM (Copy Back). The cache is set V
- else the state remains in V
- If the cache is D the data is sent to MM (Copy Back)
- The cache (D or V) is set "Invalid" (I)
————————————————————————————————————————
States D-SD-V-I (MOSI)
- Characteristics:
- As with MOESI without E state
- No use of "shared line"
- 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
- 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
- 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
- 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
- If the cache is D or SD the data is sent to the bus (Intervention)
- The cache is set "Invalid" (I)
- The cache is set "Invalid" (I)
————————————————————————————————————————
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
- 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.
- 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
- 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
- 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
- If hit (D or VE or S) the data is sent to the bus (Intervention).
- All the caches are set S
- The cache is updated with new data. The state remains S
————————————————————————————————————————
States D-SD-VE-SC (MOES)
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
- 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
- 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
- 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 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
- If the cache is D or SD the data is sent to the bus (Intervention)
- The cache is set SC
- The cache is updated with new data. The cache remains SC
————————————————————————————————————————
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"
————————————————————————————————————————
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.
————————————————————————————————————————
States RT-MESI
IBM patented protocol
- 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
- 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.
- 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
- 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
- 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
- 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)
- The cache is set "Invalid" (I)
————————————————————————————————————————
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.
————————————————————————————————————————
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.
————————————————————————————————————————
States M-T-Me-S-I -Mu-SL = RT-MESI+Mu
- Use of the "shared line"
- special state – asking for a reservation for load and store doubleword (for 64-bit implementations)
- 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
————————————————————————————————————————
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