Multicore coherence protocols
WHY does this problem exist?
WHAT: Modern CPUs have private L1/L2 caches per core to hide slow main memory (DRAM ≈ 100 ns vs L1 ≈ 1 ns).
WHY it breaks: Caches are copies. If Core 0 caches x=5, then writes x=7 only into its cache, Core 1's cache still holds the stale x=5. Without coordination, two cores reading x get different answers → program logic collapses.
Coherence ≠ consistency. Coherence is about one location; memory consistency is about the ordering across different locations. This note is about coherence.
HOW we enforce it: the snooping bus idea
WHY a bus? Early multicores share a broadcast medium. Every cache snoops (listens to) every transaction. When Core 1 writes a block, Core 0 hears it and reacts.
Two broad strategies:
| Strategy | What happens on a write | Cost |
|---|---|---|
| Write-invalidate | Writer broadcasts "invalidate"; all other copies are dropped | 1 invalidate per write-burst |
| Write-update | Writer broadcasts the new value to every copy | bus traffic per write |
Invalidate wins in practice (a core often writes many times before another reads), so the famous protocols are invalidate-based.
Building MSI from scratch
We need to label each cached block with a state. Derive the minimum needed states by reasoning:
- A block I don't have → I (Invalid).
- A block I have and others might have, but nobody has written it → safe to read but not write without permission → S (Shared).
- A block I have written → I own the only valid copy, can read/write freely → M (Modified).
That's the minimal trio: MSI.
State transitions (the rules, derived)
On a processor read (PrRd):
- I → S: issue BusRd (read miss). If another cache has M, it must supply data and downgrade.
- S/M → stay.
On a processor write (PrWr):
- I → M: issue BusRdX (read-exclusive) → all others invalidate.
- S → M: issue BusUpgr (invalidate others), no data fetch needed.
- M → stay.
On a snooped bus event:
- Someone's BusRd while I'm in M → I supply data, go to S (now shared, memory updated).
- Someone's BusRdX/BusUpgr → I go to I (invalidated).
MESI: the killer optimization
So on a read miss, the bus checks a shared signal:
- No other cache has it → load as E.
- Some cache has it → load as S.
MESI is what real Intel/ARM chips use (with extensions).
MOESI: add 'O' (Owned)
WHY: In MESI, when an M block is read by another core, it writes back to memory then both go S. O lets the owner keep a dirty copy and supply it to sharers directly (cache-to-cache), deferring the costly memory write-back. Used by AMD.
Worked examples
Common mistakes (steel-manned)
Flashcards
What two properties define cache coherence?
Difference between coherence and consistency?
What do the MSI states mean?
Why does write-invalidate beat write-update in practice?
What problem does the E (Exclusive) state in MESI solve?
E vs M state difference?
What is false sharing?
What does the O (Owned) state in MOESI add?
On a PrWr from S state in MSI, what bus transaction is issued?
Why must MSI downgrade an M-state core when another core reads?
Recall Feynman: explain to a 12-year-old
Imagine 4 kids each copy the same page from a shared notebook. If one kid scribbles a new answer on his copy, the others still have the old one. So they make a rule: before you change your copy, you shout "everybody, cross out that page!" Now whenever someone wants it again, they get the fresh version. That shouting-and-crossing-out rule is the coherence protocol. The fancy "E" trick is: if a kid knows he's the only one with a copy, he can change it quietly without shouting.
Connections
- Cache memory hierarchy — coherence operates on cache lines from here.
- Memory consistency models — coherence's "big sibling" handling cross-address ordering.
- False sharing and padding — the performance pitfall of line-granularity coherence.
- Snooping vs Directory protocols — directories scale coherence beyond a shared bus (NUMA).
- Atomic operations and fences — built on top of coherence + consistency.
- Bus arbitration — how the broadcast medium serializes transactions.
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Dekho, multicore CPU me har core ke paas apna private cache hota hai taaki slow DRAM ka wait na karna pade. Problem yeh hai ki ek hi memory address ki copy do-teen caches me ho sakti hai. Agar Core 0 ne apne cache me x=7 likh diya aur Core 1 ke cache me purana x=5 pada hai, toh dono cores ko alag value dikhegi — program galat ho jayega. Isiliye humein ek coherence protocol chahiye jo guarantee kare ki sabko ek hi consistent value dikhe.
Iska solution hai har cache block ko ek state dena. Sabse simple hai MSI: M (Modified — sirf meri copy valid hai, maine likha hai), S (Shared — clean read-only copy, dusro ke paas bhi ho sakti hai), I (Invalid — kuch nahi hai). Jab koi core write karta hai toh wo bus pe "invalidate" broadcast karta hai, aur baaki sab apni copy phenk dete hai. Bus pe sab "snoop" yaani sunte rehte hai aur react karte hai.
MESI me ek extra state E (Exclusive) add hota hai — clean hai aur sirf mere paas hai. Iska faayda? Agar tum E me ho aur write karna chaho, toh bina koi bus message bheje chupchaap M me jaa sakte ho. Yeh bahut traffic bachata hai. AMD wale ek aur O (Owned) state add karte hai jo dirty data ko directly cache-to-cache de deta hai bina memory me write-back kiye.
Ek important baat: coherence sirf ek hi address ke liye ordering guarantee karta hai. Multithreading correct hone ke liye tumhe phir bhi mutex/atomic/fences chahiye — woh consistency model ka kaam hai. Aur ek classic trap hai false sharing: do alag variables agar same 64-byte cache line me ho, toh dono cores beech me line ping-pong karwate rahenge, performance kharab. Fix: variables ko alag line me padding se daal do.