The day the caches disagreed: coherence, snooping and the MSI machine

Two caches, one X

Start from your first course: main memory is far too slow for the processor, so a cache keeps recently used blocks close to it. It lowers the average memory access latency and raises the effective bandwidth (p. 444). In a multiprocessor every core has private caches — L1 and L2 — and often shares an L3.

For private data — a thread's stack, its local variables — a private cache works exactly as in a single processor: no other core cares about the block. Shared data is different, and Hennessy & Patterson name two reasons to cache it anyway (§5.2; the notes do not use the words):

• Migration: a block moves into the cache of the core that uses it, so its accesses stop travelling to memory or across the interconnect — lower latency, less traffic.
• Replication: a block that several cores read gets a copy in each of their caches, so the readers do not queue for one copy.

Both benefits have one price: the same block now lives in several places. Table 31 of the notes shows what that costs, for one location X and two processors.

At T = 3 A writes 0 into its own copy. Nothing touches B's copy, so at T = 4 B reads 1 at hit speed. This is the cache coherence problem: "If one processor updates its cached copy, others may see an old value", and without extra mechanisms "this breaks the shared-memory programming model" (p. 444).

With write-back caches, the last column, memory keeps the 1 too: the only correct copy of X is in A's cache. The two write policies are those of lesson 23.

What a coherent memory promises

Table 31 breaks a promise. The notes state it in three conditions (p. 447), the same as Hennessy & Patterson's.

On p. 444 the notes sum coherence up in two terms: condition 2 is write propagation — every processor eventually sees the new value — and condition 3 is write serialization. Condition 1 is the uniprocessor rule that you read back your own writes. Table 31 fails condition 2: B reads its stale 1 for as long as the block stays in its cache.

Coherence in one line: reads return the most recent value written to the address, and only one writer can "own" the data at a time; all other copies must be invalidated or updated (p. 447).

Coherence is not consistency

Coherence speaks about one location at a time. Memory consistency is a separate question: when does a write become visible to the other processors, and in what order do writes to different locations appear (p. 444)? The notes' example (pp. 444–445):

P0:  A = 1;          P1:  print(B);
     B = 2;               print(A);

A and B start at 0. If P1 prints B = 2, must it then print A = 1? Under sequential consistency, yes: the result must look like one interleaving of the two programs, each in its own order, so P1 can print (B, A) = (0, 0), (0, 1) or (2, 1), never (2, 0). Weaker, relaxed models allow (2, 0), for example when write buffers or out-of-order execution reorder P0's writes or P1's reads. Each location stays coherent all the while — A and B receive one write each. So "even if the system is coherent, without consistency rules we don't know when other processors see writes, or in what order" (p. 445). The "enough time" of condition 2 is what a consistency model pins down; this lesson is about coherence.

Two cures: invalidate or update

To stop B from reading its 1, the hardware must act when A writes. Two independent questions decide how (p. 445): what the other caches are told — the coherence policy — and how they are told — the hardware organisation (Fig. 1).

Snooping broadcasts every request on a shared bus and suits small symmetric multiprocessors with one uniform memory (SMP/UMA); a directory sends messages only to the caches that hold a copy and suits large DSM/NUMA machines (p. 445; the machines are those of lesson 34, the directory is lessons 37–38). The policy says what those messages carry:

The before / after pair shows the invalidate cure at the moment of B's read.

Table 32 of the notes (p. 448) is this cure with write-back caches; its numbers are swapped — X starts at 0 and A writes 1. The notes drop the bus column of Hennessy & Patterson's original. It is back here, because the bus is what you must reason about.

Row 4 holds two facts that everything below relies on. The data comes from A's cache, not from memory: A holds the only fresh copy. And memory becomes 1 although no processor stored to it: while A answers, memory takes the block from the bus — A's block is written back.

Why invalidate won

Both cures are correct; they differ in traffic. Hennessy & Patterson trace the difference to three characteristics of programs, and the first two favour invalidation:

1. Several writes to the same word with no read in between: invalidate pays one transaction, update pays one per write.
2. Writes to several words of the same block: invalidate pays once per block, update once per word.
3. The delay between a write and another processor's read of the value is shorter with update, because the value is already in the reader's cache: the reader hits instead of missing. That is update's one advantage, and it pays off for producer–consumer sharing.

Programs write the same blocks again and again, so the notes' verdict holds: invalidate saves bandwidth and dominates, update lowers read latency "but consumes lots of bandwidth" (p. 452). Update protocols did exist — Firefly and Dragon are the classic ones — but today's processors invalidate. The meter makes the three characteristics countable.

Snooping: every cache listens to the bus

In a small multiprocessor all processors and the memory hang on one bus (p. 449). The bus is a broadcast medium: a request placed on it is seen by every cache controller at the same time. So every controller snoops: it watches every transaction, and if one concerns a block it holds, it reacts — it invalidates its copy, or supplies its data. One transaction informs everybody, and no directory or central record is needed.

The bus gives one more thing, which the notes file under the costs with only a nod to correctness: a single global order. One transaction at a time means that every controller sees all requests in the same order — and that is write serialization, condition 3, for free. If two processors write the same block at once, both ask for the bus; the winner's Invalidate kills the loser's copy, and the loser's write becomes a miss that fetches the winner's value.

The same broadcast is why snooping does not scale (p. 449):

• Bandwidth. Every coherence transaction goes to all processors; with more processors the traffic grows until the bus saturates.
• Electrical limits. Every attached controller adds load — fan-out — and capacitance, so a signal needs longer to reach the farthest receiver and the bus cycle must slow down.
• Serialization. The global order that gives correctness also forbids two coherence actions in parallel.

In practice snooping serves "2-8 CPUs" (p. 449); the notes' answer to the January 2026 paper allows "typically up to 16 or 32" (p. 495). Tens or hundreds of cores need a directory (lessons 37–38); why one bus saturates is in lesson 33.

Duplicate tags: snooping without stealing cycles

Every bus transaction must be checked against the tags of every cache (p. 450). But the tag array is already busy: the local processor looks it up on every load and store. Without help, either the processor stalls while the snoop uses the tags, or the snoop waits — and a late reaction risks a coherence violation. Two users, one resource, one cycle: a structural hazard.

The fix is a duplicate tag array, the snoop tag store, used only by the snooper (Fig. 3). Each entry holds the tag and the coherence state, no data, so it has as many entries as the main tag array but is far smaller than the cache. Bus transactions are checked there, every cycle, while the main tags keep serving the processor; every allocation, eviction and state change is written into both copies. The price is silicon area; the gain is a pipeline that does not stall "just from coherence traffic" (p. 451).

The MSI machine

MSI is the basic write-invalidate protocol for write-back caches on a snooping bus (p. 453). Each block of each private cache runs its own small finite-state machine. A cache block already carries a valid bit and a dirty bit; MSI gives that pair three meanings (p. 453):

Two sources move the machine (p. 453): requests of the local processor, and requests of other caches seen on the bus. The notes and Hennessy & Patterson call the bus transactions Read Miss, Write Miss and Invalidate, the names the exam papers give the directory messages. This lesson keeps them, writes the local processor's read and write as PrRd and PrWr, and labels every arrow "event / action".

Walk the warm-up's block through the machine before the general picture: two caches, memory holds X = 1.

The whole machine in two tables

Exactly three processor accesses put a request on the bus (p. 457): a read miss (I → S, Read Miss), a write miss (I → M, Write Miss) and a write hit in S (S → M, Invalidate). Every other hit is silent.

A write hit in M needs nothing: the cache already owns the only copy. The one other CPU-side use of the bus is not a request but a write-back, when a block in M is replaced. On the bus side, a Read Miss leaves a Shared copy alone — memory supplies the data — but makes a Modified copy supply the block and drop to S; a Write Miss kills any copy, an Invalidate a Shared one.

The hidden arrows: replacement

Fig. 38 of the notes leaves out the transitions that every exam table uses. The papers assume "one cache block per processor", so an access to the other block misses and evicts the block that is there. From the evicted block's point of view: M → I with a write-back — memory becomes up to date — and S → I silently, because a clean copy loses nothing. Then the new block enters through the normal miss arrow, I → S or I → M.

Three ways to leave M, three write-backs

A block is written back only when it leaves M (p. 457; the eviction case appears only in the notes' definition of M, p. 453):

1. M → S on a snooped Read Miss: the owner supplies the block, and memory takes it.
2. M → I on a snooped Write Miss: the owner supplies the block, then drops its copy.
3. M → I on a replacement: the dirty block is written back before the line is reused.

Hence the rule behind the column "Memory at bl. 0 up to date?" of every exam table: memory is up to date exactly while no cache holds the block in M. It turns No at the write that moves a block into M, and back to Yes at the write-back that moves it out.

Back to the warm-up. With MSI, A's write at T = 3 found X in S and put an Invalidate on the bus: B's copy went to I. B's read at T = 4 missed and put a Read Miss on the bus; A snooped it, supplied the 0 and wrote the block back, M → S. Between T = 3 and T = 4 memory was wrong and nothing broke, because no processor could read the wrong copy. Coherence is a promise about what every read returns, not about what memory holds.