Cache Coherence

Every design choice in the cache lessons assumed one processor. A write-back cache could sit on a dirty line for a million cycles, telling no one, because nobody else could look: memory had one client. Multicore breaks the assumption. Each core gets a private L1 — it must, since a single shared L1 could never serve four cores at L1 speed — and the moment two private caches can each hold a copy of address x, the machine has two places where x lives and no built-in reason for them to agree.

The stale-copy problem

Consider two cores sharing memory through a bus, each with a private write-back cache. A variable x starts at 0 in memory.

1. Core 0 reads x. Miss; the line loads into core 0's cache. It reads 0.
2. Core 1 reads x. Miss; the line loads into core 1's cache too. Reads 0. Two clean copies exist; so far, fine.
3. Core 0 writes x = 1. Write-back policy: the write lands in core 0's cache and sets the dirty bit. Memory still says 0. Core 1's cache still says 0.
4. Core 1 reads x. Hit: its copy is present and marked valid, so the cache returns 0, a value that is no longer true.

No component misbehaved. The write-back cache did what write policies said to do; core 1's hit logic did what hit logic does. The bug is architectural: the system has multiple copies and no rule connecting them.

Coherence is a per-location promise. It says nothing about the ordering of operations to different addresses — that harder contract, memory consistency, is the next lesson.

Snooping: every cache watches the bus

The classic enforcement mechanism exploits the topology already in the figure: all caches reach memory through one shared bus, and a bus is a broadcast medium: every device sees every transaction. So give each cache a second port, a snoop port, that watches bus traffic and checks each transaction's address against its own tags. If some other cache is reading a line I hold dirty, I must supply the fresh data; if some other cache wants to write a line I hold, my copy is about to become stale and must be invalidated.

To act on what it snoops, a cache needs bookkeeping: each line carries a small protocol state, and the states plus their transitions form a state machine that every cache runs independently for every line. Two kinds of events drive it: requests from this cache's own processor (PrRd, PrWr) and transactions snooped off the bus (BusRd, a read miss being serviced; BusRdX, read-for-ownership, meaning someone intends to write).

MSI: the minimal protocol

Three states are enough for correctness.

• M (Modified). This cache holds the only copy, and it is dirty. Reads and writes hit locally, silently. Memory is stale.
• S (Shared). This cache holds a clean copy; other caches may too. Reads hit; a write must first announce itself.
• I (Invalid). No usable copy here.

The transitions define the protocol. From I, a processor read issues BusRd and lands in S; a processor write issues BusRdX, which fetches the line and kills everyone else's copy, and lands in M. From S, a write issues an upgrade (BusRdX) and moves to M. And the snooping side: a cache in M that sees a BusRd for its line must flush the dirty data onto the bus and drop to S; on seeing BusRdX it flushes and drops to I. A cache in S that snoops BusRdX invalidates silently.

Replay the broken trace under MSI. Steps 1–2 leave both caches in S. Step 3, core 0's write, is no longer silent: S requires a BusRdX first, core 1 snoops it and invalidates (S to I), and core 0 proceeds to M. Step 4, core 1's read, now misses, its copy being gone, and the BusRd it issues is snooped by core 0, which flushes x = 1 and drops to S. Core 1 reads 1. The one-copy illusion holds, at the cost of bus traffic.

MESI: stop paying for private data

MSI has an inefficiency: a thread that reads its own data and then writes it (the overwhelmingly common case; every local computation does this) pays a bus transaction for the write, because a lone reader still sits in S and S cannot tell shared with others from shared with nobody. MESI splits the state.

• E (Exclusive). Clean, and provably the only cached copy: granted when a read miss finds no other cache holding the line (a wired-OR shared signal on the bus answers this during the fill).

The payoff is one transition: E to M on a write is silent. No bus transaction, no snoop, because exclusivity was established at fill time and nobody else can have acquired a copy without this cache snooping their BusRd — which would have demoted it to S. Private data now costs exactly what it cost on a uniprocessor.

Summarizing the four states as predicates over (dirty, other sharers possible, write-hits-silently):

MSI is this table without the E row; every silent write on private data then falls back to the S row's BusRdX.

It helps to watch every state change at once. Take the sequence core 0 writes x, core 1 reads x, core 1 writes x, core 0 reads x, on a line that starts cached nowhere, and track both caches' protocol state for the line under MESI. Each row is one operation; the bus column names the transaction it generates (a dash means the operation is silent).

The table shows two facts. First, every write to a line another core holds forces a bus transaction and knocks that other core down to I — this is the coherence traffic the fourth C, below, charges for. Second, the first write hit M through E-free path only because no other cache held the line; had core 1 read x before core 0's write, core 0's fill would have seen the sharer signal, landed in S instead of E, and paid a BusRdX to upgrade — the exact transaction MESI's E state exists to avoid when a thread reads-then-writes its own private data.

Every x86 core you own runs MESI or a descendant. The production variants add one state each, tuning which cache answers a miss and who writes back, never correctness:

Directory protocols replace the broadcast bus with a lookup table for machines too big to share one bus, but the per-line state machine survives essentially intact; the final lesson returns to this.

Invalidate or update? MESI destroys other copies on a write; the alternative — broadcast the new value and update every copy in place — loses in practice. Updates push a bus transaction for every write to a shared line, while invalidation pays once and then writes locally in M for free; updating keeps pumping data at caches that may never read the line again. Write-invalidate won for the same reason write-back beat write-through: the writer usually writes again before anyone reads.

The fourth C

The direct-mapped lesson sorted misses into three C's: cold (compulsory), conflict, capacity. Coherence adds a fourth: a coherence miss is a miss on a line this cache had, evicted not by pressure but by another core's write. No amount of extra capacity or associativity removes it; it is the protocol working as designed. When two cores take turns writing one line, the line ping-pongs: each write invalidates the other cache, each access misses, and every hit-speed access becomes a bus round trip.

For example, suppose two cores share a counter and increment it in a tight loop, taking turns. Each increment is a read-modify-write that needs the line in M; core 0's increment invalidates core 1, so core 1's next increment misses and must fetch the line from core 0's cache, which invalidates core 0, whose next increment misses in turn. Every single increment is now a coherence miss — a 40–80 ns cache-to-cache transfer where a private counter would be a 1 ns L1 hit, so throughput falls by $\approx 50\times$. The two cores together run slower than one core alone, which would keep the line in M and never miss. This is the fourth C in general: adding a writer adds invalidations, not throughput.

Coherence misses are why parallel code can scale worse as you add cores, more writers meaning more invalidations, and they come in a particularly unfair variety.

False sharing

Coherence tracks lines, not bytes. A 64-byte line holds eight longs; the protocol cannot see which of them you touched. So two threads can contend for a line while sharing no data at all.

struct stats {
  long hits;      /* incremented by thread 0 only */
  long misses;    /* incremented by thread 1 only */
} s;              /* 16 bytes: one cache line     */

void *count_hits(void *_)   { for (;;) s.hits++;   }
void *count_misses(void *_) { for (;;) s.misses++; }

The two counters are 8 bytes apart, so they share one 64-byte line. Thread 0's increment needs the line in M, invalidating core 1's copy; thread 1's next increment then misses, fetches the line, invalidates core 0; repeat forever. Logically the threads are independent (neither reads the other's counter), but physically they contend for one line. With $t_{\text{hit}}\approx 1$ ns (L1 hit) and $t_{\text{coh}}\approx 40\text{–}80$ ns (cache-to-cache transfer), the per-operation slowdown is $\frac{t_{\text{coh}}}{t_{\text{hit}}}\approx 40\text{–}80\times .$ Real loops rarely hit the full factor because not every iteration collides, but 5–10x on the overall loop is routine — and the profiler shows only memory access is slow, on a line of source that touches thread-private data.

The fix is layout, the same technique as alignment: give each writer its own line.

struct stats {
  long hits;
  char pad[56];   /* f\/ill out the rest of hits' 64-byte line */
  long misses;    /* now starts on its own line               */
} __attribute__((aligned(64))) s;

Sixty-four bytes of waste remove the whole slowdown: each counter now lives alone on its line, each core holds its line in M permanently, and every increment is a genuine L1 hit. The general rule for parallel data design: writers get exclusive lines. Per-thread accumulators, padded per-core slots in shared arrays, and combining results only at the end are all instances of this one rule.

Protocols, directories, and detection

The snooping protocols in this lesson have a precise pedigree, and the machinery that replaced the bus is the reason coherence still holds at 64 cores.

MESI is the Illinois protocol of Papamarcos and Patel (1984, ISCA), whose contribution was the E state — the observation that a clean line known to be unshared should upgrade to writable for free. MOESI, adding the Owned state so a dirty line can be shared without first writing back to memory, comes from Sweazey and Smith (1986) and is what AMD ships; Intel's MESIF adds a Forward state so that among several sharers exactly one is designated to answer a miss, avoiding the storm of every sharer responding at once. All four are refinements of the same three-state skeleton, tuned for which cache answers and who writes back, not for correctness.

The deeper change is topological. A broadcast bus that every cache snoops does not survive past a handful of cores, so large machines use a directory protocol: Censier and Feautrier (1978) proposed keeping, per memory block, an explicit list of which caches hold it, so a write sends invalidations only to the actual sharers instead of broadcasting to everyone. Directory coherence — surveyed thoroughly in Sorin, Hill, and Wood's A Primer on Memory Consistency and Cache Coherence (2011), the standard modern reference — is what lets a 64-core server or a multi-socket machine stay coherent, and the final lesson returns to it. The per-line state machine of MSI/MESI is unchanged; only the medium that carries the transactions differs.

False sharing graduated from folklore to a measured, fixable bug with tools that attribute coherence misses to source lines. Modern profilers (Linux perf c2c, cache-to-cache) sample the hardware's coherence events and point at the exact struct field two cores fight over, turning memory access is slow into these two counters share a line — the diagnosis this lesson's padding fix depends on.

Coherence keeps every core agreeing about each location taken alone. It makes no promise about the order in which one core's writes to different locations become visible to another — and real hardware reorders in ways that break intuitive assumptions. That is memory consistency, next.