Exercises — Cache coherence problem

When multiple private caches hold copies of the same memory address, a write by one core can leave the other caches (and possibly main memory) holding stale values, so different cores read different numbers for the same address.

• (a) is coherence — it is about a single address across caches (this is the write-serialization rule).
• (b) is consistency — it is about ordering across different addresses. See Memory Consistency Models for (b). Coherence = what value; consistency = when/what order across locations.

False. Write-through keeps memory fresh, but it does not touch another core's cache. That other cache can still return its own stale copy. Write-through closes the memory-vs-cache gap; coherence is the cache-vs-cache gap. See Write-through vs Write-back.

B reads 5. This is wrong; the true value is 20. Memory is also still 5 because write-back has not flushed A's dirty line yet. Two independent bugs — cache-vs-cache and memory-vs-cache.

• Step 3: A writes X=20 → A broadcasts an invalidate → Cache B marks its X copy Invalid.
• Step 4: B reads X → its copy is Invalid → this is a forced miss → B fetches the fresh value → gets 20. ✅

The invalidate converted B's silent staleness into a loud miss, and the miss is exactly what pulls the correct value. See MESI Protocol.

• After step 3, A broadcasts the new value 20; B's copy is updated in place to X=20 (still valid).
• Step 4 read is a hit returning 20 — no miss. ✅

Update spends a broadcast at write time to save the reader a miss later. Whether that trade wins depends on the sharing pattern (next level).

Write-invalidate:

• Write 1: A does not yet own the line exclusively → 1 invalidate to knock out B. Now A has exclusive ownership.
• Writes 2, 3, 4: A already owns it exclusively → 0 events each.
• B's read: B's copy is invalid → 1 read miss.
• Total $=1+0+0+0+1=2$ events.

Write-update:

• Writes 1–4: each pushes the new value to B → 4 update broadcasts.
• B's read: copy already fresh → 0.
• Total $=4+0=4$ events.

Invalidate wins 2 vs 4. Repeated writes by one core to one line is the killer case for update.

Write-update:

• Write: 1 update broadcast (B's copy now fresh).
• Reads 1–5: all hits → 0 events.
• Total $=1$.

Write-invalidate:

• Write: 1 invalidate.
• Read 1: B's copy invalid → 1 miss (fetches fresh 20; now valid again).
• Reads 2–5: hits → 0.
• Total $=1+1=2$.

Update wins 1 vs 2. When a reader needs the value right after each write, update dodges the miss.

Invariant we want — any two cores that both think their copy is valid must agree: $\forall i,j:{\text{Valid}}_i(X)\wedge {\text{Valid}}_j(X)\Rightarrow {\text{cache}}_i(X)={\text{cache}}_j(X)$ A write on core $i$ performs ${\text{cache}}_i(X):=\text{new}$, changing only $i$'s copy. If some other valid copy $j$ existed with the old value, the two sides of the equation now differ — invariant broken.

Two repairs (eliminate the stale valid copy): $\text{Write-Invalidate: }\forall j\ne i:{\text{Valid}}_j(X)\leftarrow \text{false}$ $\text{Write-Update: }\forall j\ne i:{\text{cache}}_j(X)\leftarrow \text{new}$

• (a) Invalidate. Many writes by one owner → after the first invalidate the writer owns the line and later writes are free. Update would broadcast every write.
• (b) Update. One write then an immediate read each cycle → update keeps B's copy fresh and avoids the read miss (Exercise 3.2 logic).
• (c) Either is cheap, invalidate preferred. One write per hour is negligible traffic; with many sharers, an update would broadcast to all of them, while invalidate sends one invalidation and lets sharers re-fetch lazily only if they still care.

Each time A writes X it invalidates B's copy of the whole line (coherence tracks lines, not individual variables), so B's next access to Y misses and re-fetches. Then B writes Y and invalidates A's line, forcing A to re-fetch to touch X. The line "ping-pongs" between the caches although the cores never share real data.

This is ==false sharing==. The fix is to place X and Y on different cache lines (padding/alignment). See False Sharing.

In snooping, every cache listens to a shared broadcast medium; each coherence action (invalidate/update/miss) is seen by all caches. Bus bandwidth is fixed, so as cores increase, total broadcast traffic grows and the single bus saturates — a scalability wall (see Bus Traffic & Scalability).

The alternative is a directory protocol: a directory records which caches hold each line, so a write sends messages only to the actual sharers (point-to-point over a scalable interconnect) instead of broadcasting to everyone. See Snooping vs Directory Coherence.

• Write-invalidate, because the dominant pattern is single-writer bursts. Exercise 3.1 showed invalidate collapses N writes to 1 event; update would pay N broadcasts. Overwhelmingly the right base policy.
• Directory-based, because 32 cores on a shared broadcast bus would saturate (Exercise 4.3). A directory sends invalidations only to actual sharers over a point-to-point interconnect, scaling with sharing degree, not core count.
• Net: an invalidate + directory design (the shape of real many-core coherence). It pairs the cheap-burst policy with the scalable delivery mechanism.

• (1) A reads → miss, fetch → A valid. (1)
• (2) B reads → miss, fetch → A,B valid. (1)
• (3) C reads → miss, fetch → A,B,C valid (shared). (1)
• (4) A writes 9 → 1 invalidate broadcast → B and C both marked Invalid; A now exclusive/modified. (1)
• (5) B reads → copy invalid → miss, fetch fresh 9 (A supplies) → B valid, holds 9. (1)
• (6) C reads → copy invalid → miss, fetch fresh 9 → C valid, holds 9. (1)

Total $=3+1+1+1=6$ bus events. Note: one invalidate covered both sharers (single broadcast on a snoop bus); the two later read misses are the price of having invalidated them.

Let X=5, A and B both cache it.

• Program order (self-read): A writes 7 to its cache; if A's cache silently evicts and a later A-read misses to stale memory (still 5), A fails to read its own write. Violated without write propagation to memory.
• Write propagation: A writes 7; B keeps reading its cached 5 forever — A's write is never seen by B. Violated.
• Write serialization: A writes 7, B writes 8, with no serializing point, C may observe 7-then-8 while D observes 8-then-7. Violated — no agreed global order for that line. Each condition is exactly the guarantee a coherence protocol restores.