Cache Coherence
Coherence keeps every core's copy of a line honest, and it is not free: whenever a core writes a line another core holds, something has to travel. MESI has four states where MSI has three, and the extra one exists for a single reason. A core that reads a line nobody else holds, and then writes it, would under MSI have to announce that write on the bus. Under MESI the read already marked the line exclusive, so the write is silent. This page runs the same access pattern through both and counts the difference.
New to two caches holding one address? Start here
Every processor keeps its own copy of recently used memory, in whole cache lines rather than single bytes. So the same address can sit in four caches at once, and each one may have been written to.
Something has to make that look like one memory. The rule is that a line may be read by many and written by one, and the protocol on this page is the bookkeeping that enforces it: which cache is allowed to write, who has to be told, and what has to be given up first.
Two things at once
A program you write reads top to bottom, one step after the last. Once two of them run at the same time, that stops being true of the pair: their steps interleave, in an order nobody chose and nothing wrote down.
The hard part is that the order is not random so much as unconstrained. Any interleaving the hardware permits is one you have to treat as possible, even if no test you ever run happens to produce it: nothing promises that a scheduler will eventually choose it, and nothing promises it will not, on someone else's machine, months later, on the run you were not watching. So the machines in this topic are not about making the right order happen. They are about which orders are possible, which of those are wrong, and what it costs to rule them out.
The machine for this idea on its own is Race, if you would rather press it than read about it.
One letter, and what it buys
1 An access pattern across four cores, including the evictions that make a line leave a cache
Pick what the cores do. Each pattern is a list of reads, writes and evictions against one line, and every number below is counted from running it.
| # | Who | Does what |
|---|
Evictions are in there because a line does not sit in a cache forever. Without them a core writes once and owns the line for the rest of the pattern, which is true of a line nobody ever evicts and true of almost no real program.
2 Every core's state after every step, under whichever protocol is showing
Every core's state, step by step, under
| # | What happens | c0 | c1 | c2 | c3 | On the bus | Running total |
|---|
3 What crossed the bus, counted by kind, with MSI and MESI side by side
DerivedThe bill, both ways
| Transaction | MSI | MESI |
|---|
4 The patterns where the fourth state buys nothing, which is the half that explains it
Where the fourth state buys nothing
Switch to the pattern where two cores take turns on one line. The counts come out the same, because the line was never exclusive to anybody and there was never a silent upgrade to make. The same is true of a line handed from core to core: every core writes, so every core must own it, and no amount of extra states changes that.
An optimisation is only understood when you can also say where it does not help. MESI never issues MORE transactions than MSI, and it issues fewer on the pattern a single core spends most of its life doing: read a line, write it, lose it to something else, read it again. On a line two cores genuinely share it issues exactly as many. Fewer transactions is less coherence traffic. On a bus-limited machine that can mean less waiting, which is where the speed would come from; this page counts transactions and not cycles, so it does not claim the time. Where the line was already shared it changes nothing.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| on a line read then written after each eviction, MESI saves an upgrade every time | yes | three read-then-write pairs with an eviction between them: MSI spends 8 transactions, MESI spends 5, and the difference is exactly the 3 upgrades MESI does not need to announce |
| and on a line two cores are actually sharing, it saves nothing | yes | both spend 12 transactions, because the line was never exclusive to anybody |
| MESI never costs more than MSI on any pattern here | yes | all 3 patterns cost the same or less |
| no two caches ever hold the line modified at the same time | yes | checked at every step of 3 patterns under both protocols |
| every state a core reaches is one the rules can produce | yes | only M, E, S and I appear |
| and every move between states is one the protocol allows | yes | no core ever takes a line from invalid to modified without a bus transaction |
| both protocols leave behind the value the writes add up to | yes | each pattern settles to its own number of writes, under both protocols |
| a line handed from core to core costs both protocols the same | yes | 9 transactions each, 4 of them writebacks: nothing about a fourth state helps here |
What is real here, and what is not
One implementation, one flag
MSI and MESI are the same code here with a single boolean between them, and that boolean controls exactly one line: whether a read of a line nobody else holds lands in Exclusive or in Shared. Two separate implementations would be two places for the protocols to disagree for reasons that have nothing to do with the E state, and the entire claim of this page is a comparison.
The counts are transactions, not cycles or nanoseconds
A writeback moves a whole line to memory and an upgrade moves only permission, so they do not cost the same. This page counts them separately and never adds them into a time. What a transaction costs depends on the interconnect, the memory, and how far away the other core is, and none of that is modelled.
One line, and real machines have millions
Everything here is about a single cache line. Capacity, associativity, the number of sets, and what happens when two lines contend for the same set are all absent. False Sharing, in this same group, is about what happens when two variables land in one line, which is the other half of this story.
Snooping, not directories
The model assumes every core sees every transaction, which is what a bus does and is how the 1984 paper describes it. Large modern machines use directories instead, precisely because a bus everybody snoops does not scale. The stable states can be the same; the traffic is routed rather than broadcast, and real directory protocols add metadata and transient states of their own.
The model was wrong once, and a check caught it
A write to a line the core does not hold counts a read for ownership, and the read half is not decoration: the core has to fetch the current value before modifying it. An earlier version counted the transaction and skipped the fetch, so every core incremented its own stale copy and a line handed between four cores settled to two after five writes. Comparing MSI against MESI could not see it because both did it. Comparing both against the number of writes could.
Sound: no
Bus transactions are a count, not a duration anybody could hear.
Sources
- Carnegie Mellon 15-740, Cache Coherence, 2019 — the states and their transitions, and the attribution to Papamarcos and Patel's 1984 paper, which introduced the fourth state and which ACM keeps behind a cookie wall.
- perf-c2c(1), which exists to find the traffic this page counts, and reports it as cache-to-cache transfers.
- Logical Art, the studio this belongs to.