Foundations — Multicore coherence protocols

Before you can read the parent note comfortably, you must be able to look at any word — cache, block, snoop, BusRdX, M/S/I — and instantly see the picture it stands for. This page builds every one of those from nothing. Read top to bottom: each idea is a brick the next one stands on.

1. Core — a worker that computes

Plain words: A core is one independent "brain" on the chip. A modern CPU has several cores so it can do several things truly at the same time.

The picture: Imagine several people (cores) sitting at desks, each solving problems.

Why the topic needs it: Coherence problems only exist because there is more than one core. One core alone never disagrees with itself.

We write cores as $P_0,P_1,P_2,\dots$ — the letter P stands for "processor" (an older word for core), and the little number below (the subscript) just names which one, like desk numbers.

2. Main memory and the cache — the big book and the desk notepad

Plain words: Main memory (DRAM) is one giant shared storage — every core can reach it, but it is slow. A cache is a tiny, fast, private copy-store that sits next to each core.

The picture: The big book on a shelf across the room = main memory. The notepad on your own desk where you jot down pages you're using = your cache.

Why the topic needs it: Fetching from the shelf every time is painfully slow (about 100 nanoseconds vs about 1 nanosecond for the notepad — a nanosecond is one-billionth of a second). So each core keeps copies. Copies are exactly what can go stale. No cache → no coherence problem.

See Cache memory hierarchy for why fast memory must be small and slow memory must be large.

3. Cache line / block — you copy a whole page, not one letter

Plain words: Memory is not copied one byte at a time. It is copied in fixed chunks called cache lines (or blocks), typically 64 bytes each.

The picture: When you copy from the shelf book, you photocopy a whole page, not a single word — even if you only needed one word on it.

Why the topic needs it: This single fact causes false sharing (parent Example 3). Two unrelated variables a and b on the same 64-byte line fight each other, because the protocol tracks the whole line, never individual bytes.

4. Stale data — a copy that no longer matches the truth

Plain words: A copy is stale when someone changed the real value elsewhere but your copy still shows the old one.

The picture: You photocopied a page showing "$x=5$". Another core rewrote the shelf book (or its own copy) to "$x=7$". Your notepad still says 5 — it is stale.

Why the topic needs it: Preventing stale reads is the whole job. The parent's definition of coherence — "a read returns the most recent write" — is literally "you never read stale data".

5. The bus and snooping — a shared loudspeaker everyone hears

Plain words: The bus is a single shared wire connecting all caches to memory. Only one message travels on it at a time. Snooping means every cache listens to every message, even ones not addressed to it.

The picture: All desks share one loudspeaker. When any core wants to read or change a shared page, it announces it over the loudspeaker. Everyone else snoops — overhears — and reacts.

Why the topic needs it: Snooping is how a core learns that someone else touched a value it also holds. Because only one message fits on the bus at a time, writes get put in a single order everyone agrees on — this is the parent's write serialization. (When too many cores want to talk, Bus arbitration decides who goes first; the alternative to broadcasting is a directory.)

6. The bus messages — the exact words cores shout

The parent uses four shorthand names. Here is each, in plain words:

Why two separate write messages (BusRdX vs BusUpgr)? They answer different questions:

• If I don't have the line yet → I need both the data and the right to write → BusRdX.
• If I already have a clean copy → I only need the permission (invalidate others), not the data → BusUpgr (cheaper, no data transfer).

This is exactly why the parent's "S → M" step uses BusUpgr but "I → M" uses BusRdX. The difference is do I already hold the data?

7. State — a sticky note on each cached line

Plain words: Each line in a cache carries a tiny label describing what rights I have over it. The parent calls these states and names them with single capital letters.

The picture: A colored sticky note on each photocopied page: red = "invalid, don't trust this", yellow = "shared, read-only", green = "I own it, I can scribble freely".

Why the topic needs it: The whole protocol is a machine that flips these labels in response to bus messages. Everything the parent draws as arrows between M, S, E, I is just "when I hear this message, change this sticky note to that one".

8. The ordering symbol $\prec$ — "weaker than"

The parent writes: $\text{I}\prec \text{S}\prec \text{E}\prec \text{M}$

Plain words: The symbol $\prec$ means "comes before / is weaker than". Read left to right, each state grants more ownership rights and requires fewer announcements before you write.

The picture: A staircase climbing from "no rights" (I) up to "full private ownership" (M). Every step right = you can do more with less shouting.

Why the topic needs it: It compresses the whole point of MESI into one line — moving rightward is "getting stronger", and the protocol's optimizations are all about climbing that staircase cheaply.

9. Dirty vs clean — does the shelf need updating?

Plain words: A copy is clean if it still equals what's on the shelf (main memory). It is dirty if you changed your copy but haven't written the change back yet.

The picture: A clean page = identical to the shelf book. A dirty page = you scribbled a new answer that the shelf book doesn't have yet.

Why the topic needs it: This is the only real difference between E and M (parent's third mistake). E is clean → if you throw it away, no write-back needed. M is dirty → you must write back before discarding, or the change is lost.

The prerequisite map

Read it upward-to-the-right: cores plus private caches plus fixed-size lines create the problem; a shared snooped bus carries the messages; those messages flip per-line states; the states assembled form MESI.

Equipment checklist

Cover the right side and test yourself. If any answer surprises you, reread that section before the parent note.

Ready? With these bricks in place, the parent note's arrows between states will read like plain sentences. Continue to 4.1.27 Multicore coherence protocols (Hinglish) for a language-mixed walkthrough, and see Atomic operations and fences and Memory consistency models for what coherence doesn't solve.