List of cache coherency protocols

In systems such as Multiprocessor, multi-core and NUMA systems, where a dedicated cache exists for each processor, core or node, a consistency problem may occur when the same piece of data is (copied and) stored in more than one cache. This problem arises when the data value is modified in one cache but has not been modified in the other caches, leading to an unknown "ground truth" value of the piece of data across the entire system, where each cache's version of the piece of data is treated as equally valid. This problem can be solved in two ways: • Invalidate all the copies on other caches ("broadcast-invalidate") • Update all the copies on other caches (write-broadcasting) to the new correct value, while the Main Memory (MM) may be updated immediately ("write-through") or not updated until absolutely necessary ("write-back" or "write-deferred"). Note: Coherency generally applies only to data (as operands) and not to instructions (see Self-Modifying Code). The schemes can be classified based on: • Snoopy scheme vs Directory scheme and vs Shared caches • Write-through vs Write-back (WB is ownership-based) protocol • Update vs Invalidation protocol • Intervention vs not Intervention • Dirty-sharing vs not-Dirty-sharing protocol (MOESI vs MESI) Three approaches are adopted to maintain the coherency of data. • Bus watching or Snooping – generally used for bus-based SMP – Symmetric Multiprocessor System/multi-core systems • Directory-based – Message-passing – may be used in all systems, but typically used in NUMA system and in large multi-core systems • Shared cache – generally used in multi-core systems == Snoopy coherency protocol ==

Protocol used in bus-based systems like a SMP systems SMP – symmetric multiprocessor systems Systems operating under a single OS (Operating System) with two or more homogeneous processors and with a centralized shared Main Memory Each processor has its own cache that acts as a bridge between processor and Main Memory. The connection is made using a System Bus or a Crossbar ("xbar") or a mix of two previous approaches, bus for Address and crossbar for Data (Data crossbar). The bottleneck of these systems is the traffic and the Memory bandwidth. Bandwidth can be increased by using a larger data bus path (more wires between MM and each component), data crossbar, memory interleaving (multi-bank parallel access) and out of order data transaction. The traffic can be reduced by using a cache that acts as a "filter", eliminating the need for each processor cache to directly access the shared memory for every transaction; thus, the cache is an essential element for utilizing shared-memory in SMP systems. In multiprocessor systems with separate caches that share a common memory, the same datum can be stored in more than one cache. A data consistency problem may occur when the datum is modified in only one of the caches. The protocols to maintain the coherency for multiple processors are called cache-coherency protocols. In SMP, the coherency is usually based on the "Bus watching" or "Snoopy" (after the Peanuts' character Snoopy ) approach. In a snooping system, all the caches monitor ("snoop") the bus transactions to intercept the bus data and determine if it (each specific cache) has a copy of that data. Various cache-coherency protocols are used to maintain data coherency between caches. These protocols are generally classified based only on the cache states (from 3 to 5 and 7 or more) and the transactions between them, but this could create some confusion. This definition is incomplete because it lacks important and essential information about the actions that each protocol produces. These actions can be invoked by the processor or the bus controller (e.g. intervention, invalidation, broadcasting, etc.). The type of actions is implementation dependent. The states and transaction rules do not capture everything about a protocol. For instance, protocol MESI with shared-intervention on unmodified data is different from MESI without intervention (see below). At the same time, some protocols with different states can be practically the same. For instance, the 4-state MESI Illinois and 5-state MERSI (R-MESI) IBM / MESIF-Intel protocols are only different implementations of the same functionality (see below). The most common protocols are the 4-state MESI and the 5-state MOESI, each letter standing for one of the possible states of the cache. Other protocols use some proper subset of these but with different implementations along with their different but equivalent terminology. The terms MESI, MOESI or any subset of them generally refer to a class of protocols instead of a specific one. Cache states The states MESI and MOESI are often and more commonly called by different names. • M=Modified or D=Dirty or DE=Dirty-Exclusive or EM=Exclusive Modified • modified in one cache only – write-back required at replacement. • data is stored only in one cache but the data in memory is not updated (invalid, not clean). • O=Owner or SD=Shared Dirty or SM=Shared Modified or T=Tagged • modified, potentially shared, owned, write-back required at replacement. • data may be stored in more than one cache but the data in memory is not updated (invalid, not clean). Only one cache is the "owner", other caches are set "Valid" (S/V/SC). On bus read request, the data is supplied by the "owner" instead of the memory. • E=Exclusive or R=Reserved or VE=Valid-Exclusive or EC=Exclusive Clean or Me=Exclusive • clean, in one cache only. • Data is stored only in one cache and clean in memory. • S=Shared or V=Valid or SC=Shared Clean • shared or valid • Data potentially shared with other caches. The data can be clean or dirty. The term "clean" in SC is misleading because can be also dirty (see Dragon protocol). • I=Invalid. • Cache line invalid. If the cache line is not present (no tag matching) it is considered equivalent to invalid, therefore invalid data means data present but invalid or not present in cache. Special states: • F=Forward or R=Recent • Additional states of MESI protocol • Last data read. It is a special "Valid" state that is the "Owner" for non modified shared data, used in some extended MESI protocols (MERSI or R-MESI IBM, MESIF – Intel). The R/F state is used to allow "intervention" when the value is clean but shared among many caches. This cache in the R/F state is responsible for intervention (shared intervention ). On a bus read request, the data is supplied by this cache instead of being supplied by the main memory. MERSI and MESIF are the same protocol with different terminology (F instead of R). Sometimes R is referred to as "shared last " (SL). • The state R = Recent is used not only in the MERSI = R-MESI protocol, but in several other protocols as well. This state can be used in combination with other states, such as in RT-MESI, HR-MESI, HRT-MESI, HRT-ST-MESI. All protocols that use this state will be refereed as R-MESI type. • H=Hover – H-MESI (additional state of MESI protocol) • The Hover (H) state allows a cache line to maintain an address Tag in the directory even though the corresponding value in the cache entry is an invalid copy. If the corresponding value happens on the bus (i.e., if address Tag on bus matches address Tag in cache) during a valid "Read" or "Write" operation, the cache entry is updated to be the valid copy and its state is changed from H to S. • This state can be used in combination with other states. For instance HR-MESI, HT-MESI, HRT-MESI, HRT-ST-MESI. – 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 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. ::: – 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 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 advanced systems use only R-MESI / MESIF protocol or the more complete RT-MESI, HRT-ST-MESI, and POWER4 IBM protocols, which are an enhanced merging of MESI and MOESI protocols. Note: Cache-to-cache is an efficient approach in multiprocessor/multicore systems that have direct connections between caches, but it is less efficient in Remote caches, such as in NUMA systems where a standard MESI is preferable. For example, POWER4 IBM's protocol with Shared Intervention is only done "local"ly, not between remote modules. RT-MESI protocol   States RT-MESI   IBM patented protocol • Characteristics: ::- 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 ==