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.
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
The 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 bus traffic, so where MESI wins it does run faster; 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 states are the same; the traffic is routed rather than broadcast.
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.