Visual walkthrough — Multicore coherence protocols
This page is the visual companion to Multicore coherence protocols. If a word here feels unexplained, it is built below before it is used.
Step 1 — Two caches, one address, and the moment it breaks
WHAT. Picture two CPU cores. Each has a tiny private notebook called a cache — a fast local copy of a few memory addresses (see Cache memory hierarchy). Main memory (DRAM) is the slow shared book everyone copies from.
WHY. Reading DRAM costs about ns; reading your own cache costs about ns. So every core keeps its own copy to go fast. The cost of that speed is duplication — the same address x can sit in many notebooks at once.
PICTURE. In the figure, memory holds x = 5. Core 0 copies it. Core 0 then writes x = 7 into only its own notebook (the orange cell). Core 1 still reads its stale x = 5 (the red cell). Two cores, two different answers for the same address — the program's logic collapses.
Step 2 — The bus: a room where everyone hears everything
WHAT. We connect the caches with a shared wire called the bus — a single broadcast medium. Whenever any cache reads or writes memory, it must announce the transaction on the bus, and every other cache snoops (listens).
WHY. The staleness in Step 1 happened because Core 0's write was silent. If instead every write is shouted on a shared wire, the other caches can hear it and react. This "listen to everyone" design is snooping. The bus also forces a single global order on the shouts (that is Bus arbitration) — which is exactly the "same order" half of coherence.
PICTURE. The figure shows the two caches hanging off one horizontal bus line. Core 0's write is drawn as an orange broadcast pulse travelling along the wire; the arrow into Core 1 is the snoop — Core 1 hears the shout even though the message was not "for" it.
Now we must decide what Core 1 does when it hears a write. Two choices:
Step 3 — Deriving the minimum set of states
WHAT. We give every cached block a state — a label describing what rights this cache has over that block. We derive the smallest set of labels that could possibly work.
WHY. Reasoning from the questions each cache must answer:
- Do I even have valid data? If not, that is one state → I (Invalid).
- I have a clean copy others might also have. Safe to read, unsafe to write without warning → S (Shared).
- I have written; my copy is the only good one. Free to read and write → M (Modified).
Any fewer states and we could not tell "safe to read" from "safe to write." That trio — Modified, Shared, Invalid — is the protocol named MSI.
PICTURE. The figure lines up the three states on an ownership-strength axis. Left = weak (I owns nothing), right = strong (M owns everything). Each state is drawn as a coloured card listing its rights.
Step 4 — The transition rules, one arrow at a time
WHAT. We write down what causes a block to change state. Two kinds of trigger:
- A processor request from my own core:
PrRd(read),PrWr(write). - A snooped bus event — a shout I overhear from another core:
BusRd(someone wants to read),BusRdX(someone wants exclusive/write access),BusUpgr(someone already has it and wants to write).
WHY. Coherence is just: never let two caches think they can write, and never let a reader keep a stale copy. Each arrow below enforces one half of that.
PICTURE. The figure is the MSI state machine. Solid blue arrows = my own processor's actions; dashed red arrows = reactions to shouts I snooped. Self-loops (grey) are the silent cache hits that fire no bus traffic at all. Read each arrow as "trigger / bus action."
First, the silent self-loops — the common, cheap cases where I already have the rights I need, so nothing goes on the bus:
- — I hold a clean read-only copy and I only want to read; a plain cache hit, no announcement.
- — I own the only good copy; reading it needs no permission.
- — I already have exclusive write rights, so a further write stays local and silent.
Next, the transitions that do touch the bus, term-by-term:
- — I have nothing, I want to read, so I shout
BusRdto fetch a clean copy and land in S. - — I want to write from scratch;
BusRdXfetches the data and kills every other copy in one shout. - — I already hold the data, I only need to invalidate the others, so
BusUpgrcarries no data, just the "cross it out" command. - — I own the only good copy; another core wants to read, so I supply the data to it (a cache-to-cache hand-off; in real MESI the memory write-back is often deferred, see below) and drop to S (a second reader now exists).
- — someone is about to write, so I throw my copy away.
Step 5 — Eviction: what happens when a block is thrown out
WHAT. A cache is finite. When a new block needs a slot, an old block is evicted (kicked out). Whether that costs a memory write is decided purely by the block's state — clean vs dirty.
WHY. The whole point of the M state is "memory is stale." So the state label already tells us whether the true value lives only in this cache. Eviction just reads that label:
- Evict a block in I → nothing to do; it held no valid data.
- Evict a block in S → clean (memory already matches). Silently drop it; no write-back.
- Evict a block in M → dirty (this cache holds the only up-to-date value). We must write it back to memory first, or the data is lost forever.
PICTURE. Two eviction paths side by side: the S block dropped freely (green, no bus), the M block forced to write back to DRAM (orange arrow into memory) before it can leave.
Step 6 — Walk the full MSI sequence (every case)
WHAT. Run a concrete four-step trace so no state combination is left unseen: (I,I) → (S,I) → (S,S) → (M,I) → (S,S).
WHY. A state machine is only trustworthy if you can watch it survive a real interleaving of reads and writes across cores.
PICTURE. Each row of the figure is one time step; the two coloured chips are P0 and P1's states, with the bus shout labelled between them.
- P0 reads x → miss →
BusRd→ P0: S. (Read-only is enough; no writer yet.) - P1 reads x →
BusRd→ P1: S. Now (S, S) — two clean readers, legal. - P0 writes x → P0 is in S, so
BusUpgrinvalidates P1 → P0: M, P1: I. - P1 reads x →
BusRd; P0 snoops it, supplies the data cache-to-cache, and downgrades → P0: S, P1: S.
Every transition here is one arrow from Step 4. Nothing new was invented — we just replayed the rules.
Step 7 — The wasted shout, and inventing E
WHAT. Look closely at a lonely core: P0 reads an address no one else has, lands in S, then writes. In MSI that write must fire a BusUpgr — a shout to invalidate sharers that do not exist.
WHY. That shout is pure waste. If we had known P0 was the sole owner, the write could be silent. So we add a fourth state, E (Exclusive): clean, and provably the only copy. MSI plus this state is the protocol MESI — Modified, Exclusive, Shared, Invalid.
But how does a cache know it is the sole owner? We need one more piece of hardware.
PICTURE. Three rows. Top: MSI wastes a BusUpgr on the write. Middle: the shared-line hardware — other caches assert the wire on a BusRd, the reader samples LOW/HIGH. Bottom: MESI reads land in E when the line is LOW, so the later write flips E → M with zero bus traffic (the orange "silent" arrow).
The full ordering is now:
MESI is what real Intel and ARM chips run (see Atomic operations and fences for how software rides on top of it).
Step 8 — Where the picture lies to you: false sharing
WHAT. Coherence tracks whole cache lines (typically bytes), not individual variables. Two unrelated variables a and b can share one line.
WHY. If P0 keeps writing a and P1 keeps writing b, each write drags the whole line to M and invalidates the other core — even though a and b never actually interact. The line ping-pongs, and both cores stall on bus traffic.
PICTURE. One 64-byte line holds both a (blue) and b (orange). The zig-zag red arrows show the line bouncing M↔I between the two caches, once per write. The fix on the right: pad the variables (alignas(64)) so they sit on separate lines and never collide.
See False sharing and padding for the full treatment. And remember: coherence guarantees values, not program ordering across different addresses — that is the job of Memory consistency models.
The one-picture summary
WHAT. One panel that compresses the whole story: the MESI state machine with the E-optimisation highlighted, and the ownership axis underneath.
Recall Feynman: the whole walkthrough in plain words
Four kids each copy a page from one shared notebook. Step 1: if a kid scribbles a new answer on his copy, everyone else has the old one — that's the bug. Step 2: so they sit in one room with a loudspeaker (the bus) and must shout before changing anything. Step 3: each kid tags his page with a colour — "I've got nothing" (Invalid), "I've got a read-only copy others share" (Shared), or "I've scribbled on mine, it's the only good one" (Modified); those three colours are MSI. Step 4: the rules are just "shout 'cross it out!' before you write, and if you hear that shout, cross yours out; if you're the only writer and someone wants to read, hand it over and downgrade" — and if you already have the rights you need, you just read/write quietly with no shout. Step 5: when a kid runs out of desk space and must toss a page, he only has to copy it back into the shared notebook if he'd scribbled on it (Modified); a clean page is tossed for free. Step 6: we replay the whole thing with two kids. Step 7: clever trick — a special "am I the only one?" bell rings when a kid grabs a page; if it stays silent he tags the page Exclusive and can scribble later without shouting; Modified/Exclusive/Shared/Invalid together spell MESI. Step 8: the catch — the loudspeaker rule works on whole pages, not single lines, so two kids editing different lines of the same page keep needlessly shouting; give them separate pages and the shouting stops.
Recall Quick self-test
What does MESI stand for? ::: Modified, Exclusive, Shared, Invalid — the four block states. In MESI, why does a write from E need no bus transaction? ::: E means the block is clean and the only copy, so there are no other caches to invalidate and memory need not change — flip silently to M. How does a cache decide E vs S on a read miss? ::: It samples the shared-line signal: LOW (no other cache asserted it) means sole owner → E; HIGH means someone else holds it → S. When must an evicted block be written back to memory? ::: Only when it is in M (dirty); S, E, and I blocks are clean or empty and are dropped with no write-back. After P0 (M) hears another core's BusRd, what happens and why? ::: P0 supplies the data cache-to-cache and drops to S, because a second reader now exists so the copy is no longer exclusive.
Parent: Multicore coherence protocols · Prereqs: Cache memory hierarchy, Snooping vs Directory protocols, Bus arbitration, Memory consistency models, False sharing and padding, Atomic operations and fences