--- title: Cache Coherence module: Multithreading & Multicore moduleNumber: 9 lessonNumber: 3 order: 903 summary: > Give each core its own cache and the same address can live in two places at once, with copies that disagree. We reproduce the stale-copy bug with a two-core trace, then fix it the way hardware does: snooping caches that watch a shared bus and keep every line in a protocol state. We build MSI in full, upgrade it to MESI, contrast invalidation with updating, add coherence misses as the fourth C, and end with false sharing: the performance bug where cores fight over a line while never touching the same byte. topics: [Multithreading & Multicore] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §6.4 Cache Memories; §12.4 Shared Variables in Threaded Programs" - book: Bistriceanu ref: "Computer Architecture Notes — §8 The Memory Hierarchy: The Cache" --- Every design choice in the [cache lessons](/computer-architecture/memory-hierarchy/cache-memories-direct-mapped) 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. $$ % caption: The stale-copy bug. After core 0's write-back write of x = 1 lands % caption: only in its own cache, core 1 still hits on its old copy and reads 0. % caption: Nothing in a single-core cache design ever corrects it. \begin{tikzpicture}[font=\footnotesize,>=stealth, cpu/.style={draw, minimum width=17mm, minimum height=7mm, align=center}, cache/.style={draw, fill=acc!8, minimum width=17mm, minimum height=7mm, align=center}, mem/.style={draw, fill=acc!8, minimum width=30mm, minimum height=7mm, align=center}] \definecolor{acc}{HTML}{2348F2} \node[cpu] (c0) at (0,2.4) {core 0}; \node[cpu] (c1) at (5.4,2.4) {core 1}; \node[cache] (k0) at (0,1.1) {x = 1 (dirty)}; \node[cache] (k1) at (5.4,1.1) {x = 0 (stale)}; \draw (c0) -- (k0); \draw (c1) -- (k1); \draw[thick, black] (-1.6,-0.1) -- (7.0,-0.1); \node[anchor=west] at (7.1,-0.1) {bus}; \draw (k0) -- (0,-0.1); \draw (k1) -- (5.4,-0.1); \node[mem] (m) at (2.7,-1.2) {memory: x = 0}; \draw (2.7,-0.1) -- (m); \node[anchor=west, text=acc] at (6.4,1.75) {\scriptsize hit! returns 0}; \draw[->, acc] (6.35,1.62) -- (6.15,1.35); \end{tikzpicture} $$ No component misbehaved. The write-back cache did what [write policies](/computer-architecture/memory-hierarchy/set-associative-and-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. > **Definition (Cache coherence).** A memory system is coherent if, for each > location, (1) a read returns the most recent write to that location in some > serial order all processors agree on, and (2) writes to the location are seen > by all processors in that same order. Informally: it must behave as if each > address had exactly one copy. 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](/computer-architecture/multithreading-and-multicore/memory-consistency-and-synchronization). ## 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. $$ % caption: The MSI protocol at one cache, for one line. Solid edges: this % caption: processor's own reads and writes. Dashed edges: reactions to snooped % caption: bus traffic. From M, a snooped read forces a flush of the dirty data. \begin{tikzpicture}[font=\footnotesize,>=stealth, st/.style={draw, circle, minimum size=9mm, inner sep=0pt, thick}, lb/.style={fill=white, inner sep=1pt, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[st, draw=acc, text=acc] (M) at (0,3.4) {M}; \node[st] (S) at (-3.4,0) {S}; \node[st] (I) at (3.4,0) {I}; % processor-side (solid): this cache's own reads and writes \draw[->, thick] (I) to[bend right=30] node[lb, right=3pt, pos=0.5] {write: BusRdX} (M.east); \draw[->, thick] (S) to[bend left=30] node[lb, left=3pt, pos=0.5] {write: BusRdX} (M.west); \draw[->, thick] (I.south) to[bend left=22] node[lb, below=3pt] {read: BusRd} (S.south); % snoop-side (dashed): reactions to bus traffic \draw[->, dashed, black] (M.south west) to[bend right=8] node[lb, pos=0.78, right=3pt] {BusRd: f\/lush} (S.north east); \draw[->, dashed, black] (M.south east) to[bend left=8] node[lb, pos=0.78, left=3pt] {BusRdX: f\/lush} (I.north west); \draw[->, dashed, black] (S) to[bend right=18] node[lb, above=2pt] {BusRdX} (I); % self loops \draw[->, thick] (M.north west) to[out=150, in=90, looseness=7] node[lb, above left=1pt] {read, write} (M.north); \draw[->, thick] (S.north west) to[out=140, in=200, looseness=7] node[lb, left=2pt] {read} (S.south west); \end{tikzpicture} $$ 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): | state | valid | dirty | other sharers | write hits silently | |:---|:---:|:---:|:---:|:---:| | **M** (Modified) | yes | yes | no | yes | | **E** (Exclusive) | yes | no | no | yes | | **S** (Shared) | yes | no | maybe | no (needs `BusRdX`) | | **I** (Invalid) | no | — | — | — | MSI is this table without the **E** row; every silent write on private data then falls back to the **S** row's `BusRdX`. $$ % caption: MESI. A read miss that f\/inds no other sharer f\/ills in E; the % caption: later write upgrades E to M silently, with no bus transaction. All % caption: other edges match MSI, with E demoting to S or I when snooped. \begin{tikzpicture}[font=\footnotesize,>=stealth, st/.style={draw, circle, minimum size=9mm, inner sep=0pt, thick}, lb/.style={fill=white, inner sep=1pt, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[st, draw=acc, text=acc] (M) at (0,3.6) {M}; \node[st, draw=acc, text=acc] (E) at (6.4,3.6) {E}; \node[st] (S) at (0,0) {S}; \node[st] (I) at (6.4,0) {I}; % the silent upgrade (the point of MESI) \draw[->, acc, very thick] (E) -- node[lb, above=3pt, text=acc] {write: silent, no bus} (M); % fills from I \draw[->, thick] (I) -- node[lb, left=3pt, pos=0.5] {read, no sharer} (E); \draw[->, thick] (I) -- node[lb, below=3pt, pos=0.5] {read, shared} (S); \draw[->, thick] (I) -- node[lb, pos=0.22, above=6pt] {write: BusRdX} (M); % S to M \draw[->, thick] (S) -- node[lb, left=3pt] {write: BusRdX} (M); % snoop demotions (dashed) \draw[->, dashed, black] (E) to[bend left=14] node[lb, pos=0.82, above=5pt] {BusRd} (S); \draw[->, dashed, black] (E.east) to[out=-40, in=40, looseness=1.6] node[lb, right=3pt] {BusRdX} (I.east); \draw[->, dashed, black] (M.west) to[out=195, in=165, looseness=1.6] node[lb, left=3pt] {BusRd: f\/lush} (S.west); \draw[->, dashed, black] (S.south) to[out=-35, in=215, looseness=0.8] node[lb, below=3pt] {BusRdX} (I.south) ; \end{tikzpicture} $$ 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). | operation | bus | core 0 | core 1 | |:---|:---:|:---:|:---:| | _(start)_ | — | I | I | | core 0 writes `x` | BusRdX | **M** | I | | core 1 reads `x` | BusRd (core 0 flushes) | S | **S** | | core 1 writes `x` | BusRdX (upgrade) | I | **M** | | core 0 reads `x` | BusRd (core 1 flushes) | **S** | S | 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: | protocol | extra state | purpose | |:---|:---|:---| | MSI | — | minimal correct protocol | | MESI | **E** (Exclusive) | silent write on unshared clean data | | MESIF (Intel) | **F** (Forward) | one designated sharer answers a miss, not all | | MOESI (AMD) | **O** (Owned) | share a dirty line without writing back first | 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](/computer-architecture/multithreading-and-multicore/multicore-organization) 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](/computer-architecture/memory-hierarchy/set-associative-and-write-policies): the writer usually writes again before anyone reads. ## The fourth C The [direct-mapped lesson](/computer-architecture/memory-hierarchy/cache-memories-direct-mapped) 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 `long`s; the protocol cannot see which of them you touched. So two threads can contend for a line while sharing **no data at all**. ```c [false_sharing.c] 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. $$ % caption: F\/alse sharing. Top: both counters land in one 64-byte line, and % caption: each core's write invalidates the other core's copy: the line % caption: ping-pongs. Bottom: 56 bytes of padding give each counter its own % caption: line, and the cores never interact. \begin{tikzpicture}[font=\footnotesize,>=stealth, cell/.style={draw, minimum height=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % before: one line \node[anchor=east] at (-0.3,2.5) {one line}; \node[cell, minimum width=14mm, fill=acc!8] (h) at (0.7,2.5) {hits}; \node[cell, minimum width=14mm, fill=acc!25] (ms) at (2.1,2.5) {misses}; \node[cell, minimum width=42mm] at (4.9,2.5) {unused 48 bytes}; \draw[->, acc, thick] (0.0,3.8) -- (h.north); \node[anchor=south] at (0.0,3.85) {\scriptsize core 0 writes}; \draw[->, acc, thick] (2.8,3.8) -- (ms.north); \node[anchor=south] at (2.9,3.85) {\scriptsize core 1 writes}; \node[anchor=west, text=acc] at (7.3,2.5) {\scriptsize line bounces}; % after: two lines \node[anchor=east] at (-0.3,0.8) {line 0}; \node[cell, minimum width=14mm, fill=acc!8] at (0.7,0.8) {hits}; \node[cell, minimum width=49mm] at (3.85,0.8) {pad, 56 bytes}; \node[anchor=east] at (-0.3,-0.2) {line 1}; \node[cell, minimum width=14mm, fill=acc!25] at (0.7,-0.2) {misses}; \node[cell, minimum width=49mm] at (3.85,-0.2) {pad, 56 bytes}; \node[anchor=west, text=acc] at (7.3,0.3) {\scriptsize no sharing}; \end{tikzpicture} $$ The fix is layout, the same technique as [alignment](/computer-architecture/machine-level-x86-64/arrays-structs-and-alignment): give each writer its own line. ```c [padded.c] 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 **O**wned 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 **F**orward 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. > **Takeaway.** Private caches replicate data, and coherence is the invariant > that the replicas never observably disagree: reads return the latest write, > per location, in one agreed order. Snooping caches enforce it by watching the > bus and running a per-line state machine — MSI for correctness, MESI so > private data incurs no bus traffic, invalidation over update so repeat writers > write for free. The cost model gains a fourth C: coherence misses, including > false sharing, where the line, not the data, is contended, and the fix is > padding writers onto separate lines. 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](/computer-architecture/multithreading-and-multicore/memory-consistency-and-synchronization), next.