![]() | This article has multiple issues. Please help improve it or discuss these issues on the talk page . (Learn how and when to remove these messages)
|
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 be 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.
Special states:
Protocols | |
---|---|
SI protocol | Write Through |
MSI protocol | Synapse protocol [4] |
MEI protocol | IBM PowerPC 750, [13] MPC7400 [6] |
MES protocol | Firefly protocol [4] |
MESI protocol | Pentium II, [14] PowerPC, Intel Harpertown (Xeon 5400) |
MOSI protocol | Berkeley protocol [4] |
MOESI protocol | AMD64, [15] MOESI, [16] T-MESI IBM [12] |
Terminology used | |
---|---|
Illinois protocol | D-VE-S-I (= extended MESI) [4] [17] |
Write-once or Write-first | D-R-V-I (= MESI) [4] [18] [19] |
Berkeley protocol | D-SD-V-I (= MOSI) [4] |
Synapse protocol | D-V-I (= MSI) [4] |
Firefly protocol | D-VE-S (= MES) DEC [4] |
Dragon protocol | D-SD (SM ?)-SC-VE (= MOES) Xerox [4] |
Bull HN ISI protocol | D-SD-R-V-I (= MOESI) [20] |
MERSI (IBM) / MESIF (Intel) protocol | |
HRT-ST-MESI protocol | H=Hover, R=Recent, T=Tagged, ST=Shared-Tagged – IBM [11] [12] – Note: The main terminologies are SD-D-R-V-I and MOESI and so they will be used both. |
POWER4 IBM protocol | Mu-T-Me-M-S-SL-I ( L2 seven states) [9]
(*) 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
There are three characteristics of cached data:
(*) – Implementation depending.
Note: Not to confuse the more restrictive "owner" definition in MOESI protocol with this more general definition.
The cache operations are:
States MESI = D-R-V-I
States MEOSI = D-R-SD-V-I = T-MESI IBM [12]
States MESI = D-R-V-I [4]
States D-R-V-I (MESI) [4] [18] [19]
(Bull-Honeywell Italia)
States D-SD-R-V-I (MOESI)
Patented protocol (F. Zulian) [20]
States D-V-I (MSI) [4]
States D-SD-V-I (MOSI) [4]
States D-VE-S (MES) [4]
States D-SD-VE-SC (MOES) [4]
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
States MERSI or R-MESI
States MESIF
Patented protocols – IBM (1997) [6] – Intel (2002) [8]
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" [21] )
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 [11] [12]
Processor operations
It is an improvement of RT-MESI protocol [12] and it is a subset of HRT-ST-MESI protocol [11]
An additional improvement can be obtained using more than a ST state, ST1, ST2, … STn.
IBM patented full HRT-ST-MESI protocol [11] [12]
- 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
(*) – 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 [9]
Under some conditions the most efficient and complete protocol turns out to be the HRT-ST-MESI protocol.