Cache coherence at scale (directory-based): Worked examples

This page is the drill floor. The parent note told you how directory protocols work; here we run the machine through every kind of situation it can meet — every starting state, every degenerate corner, a real word problem, and an exam trap — and check the arithmetic on each one.

Before we touch an example, one promise: we will use no symbol you haven't met. Let us re-earn the three things that appear over and over.

The scenario matrix

Every case a directory protocol can face is a combination of (starting state) × (operation), plus the degenerate and real-world corners. Here is the full grid; each cell names the example that covers it.

#	Starting state	Operation	Degenerate / twist	Covered by
1	Uncached	Read	first-ever touch (base case)	Ex 1
2	Shared	Read	add a sharer, no data movement	Ex 2
3	Modified (other owner)	Read	owner must write back	Ex 3
4	Shared (many sharers)	Write	invalidate all + ack-count	Ex 4
5	Modified (other owner)	Write	invalidate-forward, ownership transfer	Ex 5
6	Shared, you already hold it	Write (upgrade)	zero data transfer, self not invalidated	Ex 6
7	any	—	storage cost limiting cases ( $N = 1$ , huge $M$ )	Ex 7
8	any	—	NUMA home routing by address bits (word problem)	Ex 8
9	Shared	Write	exam twist: race — two writers at once	Ex 9

Nine cells, nine examples. Read the "Forecast:" line and guess before unfolding the steps.

The worked examples

Worked example Ex 1 — Cell 1: Uncached + Read (the base case)

Statement. Block X at 0xA000 is Uncached, memory holds X=42. Core 0 issues a read. Forecast: Where does the data come from, and what is the ending state?

Core 0 → HD: Read-Req(0xA000). Why this step? A read miss always goes to the home directory first — the requester has no idea who (if anyone) holds the block; the HD is the single source of truth.
HD reads its state = Uncached. No cache holds X, so memory is authoritative. HD fetches X=42 from memory and sends Data-Reply(X=42). Why this step? In Uncached there is nobody to forward to; the HD serves data directly.
HD updates: State → Shared, Sharers = {0} (only bit 0 lit). Why this step? Core 0 now holds a read-only copy and memory is still valid — that is exactly the definition of Shared.

Verify: Ending state Shared, sharers = {0}, value delivered = 42, memory unchanged = 42. One copy out, no writes, so memory must still equal 42. ✔

Worked example Ex 3 — Cell 3: Modified (other owner) + Read (owner writes back)

Statement. Block Y at 0xB000. State=Modified, Owner=Core 5, and Core 5's cached value is Y=77 while memory is stale (holds Y=10). Core 2 reads Y. Forecast: Who supplies the data — memory or core 5? What is memory after?

Core 2 → HD: Read-Req(0xB000).
HD sees Modified, Owner=5. Memory (10) is wrong; only Core 5 has the truth (77). HD forwards the request to Core 5. Why this step? The directory never stores data — it only knew Core 5 is the owner. So the owner, not the HD, must supply the fresh bytes.
Core 5 → Core 2: Data-Reply(Y=77), and Core 5 → HD: Write-Back(Y=77). Why this step? Core 2 needs the current value now; the write-back also repairs memory so future Uncached reads are correct.
HD updates: memory = 77, State → Shared, Sharers = {2, 5}. Why this step? Two caches now hold read-only copies and memory finally matches — that is Shared.

Verify: Data delivered = 77 (came from owner, not the stale 10); memory repaired 10 \to 77; sharers = {2,5}, count 2; state Modified → Shared. The stale memory value 10 was never delivered. ✔

Worked example Ex 4 — Cell 4: Shared (many) + Write (invalidate all, ack-count)

Statement. Block Z at 0xC000. State=Shared, Sharers={1,7,9}, Z=5. Core 3 writes Z=88. Forecast: How many Inv-Ack messages must HD wait for before granting the write?

Core 3 → HD: Write-Req(0xC000).
HD sees Shared, Sharers={1,7,9}. It sends Invalidate to each sharer: cores 1, 7, 9 — three messages, point-to-point (not a broadcast). Why this step? A write must leave exactly one valid copy. Every existing read-only copy would become stale the instant Core 3 writes, so all must be destroyed first.
Cores 1, 7, 9 drop their copies and each reply Inv-Ack. HD counts 3 acks. Why this step? If HD granted the write after only 2 acks, the third core might still serve the old Z=5 to someone — two different live values = coherence violation.
HD → Core 3: Write-Ack. HD updates: State → Modified, Owner={3}.
Core 3 writes Z=88, marks its line Modified. Memory now stale (still 5).

Verify: Invalidates sent = 3; acks awaited = 3 (must equal number of sharers); ending sharer count = 1 (only Core 3); state Shared → Modified; memory = 5 (stale, correct behaviour — no write-back yet). ✔

Worked example Ex 5 — Cell 5: Modified (other owner) + Write (invalidate-forward)

Statement. Block W at 0xD000. State=Modified, Owner=Core 4, Core 4 holds W=200, memory stale. Core 6 writes W=1. Forecast: How many caches end up holding a valid copy? Who?

Core 6 → HD: Write-Req(0xD000).
HD sees Modified, Owner=4. It sends Invalidate-Forward to Core 4. Why this step? Only Core 4 has a copy (a modified one). We must both grab its latest data and kill its copy, since Core 6 is about to become sole owner.
Core 4 invalidates its line and forwards the current data (W=200) toward the transaction, then acks the HD. Why this step? Core 6 will overwrite the value, but the protocol still transfers the block so Core 6's cache line is populated before the store.
HD → Core 6: Write-Ack. HD updates: State stays Modified, Owner={6}.
Core 6 writes W=1.

Verify: Exactly 1 valid copy at the end, held by Core 6; previous owner count 1 \to 0; state Modified → Modified (owner changed 4 → 6); final cached value = 1. ✔

Worked example Ex 6 — Cell 6: Shared + Write by a current sharer (upgrade, degenerate)

Statement. Block V at 0xE000. State=Shared, Sharers={2,5,8}, V=30. Core 5 — already a sharer — writes V=31. Forecast: Does Core 5 get invalidated? Does data need to move to Core 5?

Core 5 → HD: Write-Req(0xE000) (an upgrade: Core 5 already holds the read-only data).
HD sees Shared, Sharers={2,5,8}. It invalidates only the other sharers: cores 2 and 8. Core 5 is not invalidated — it keeps its copy to upgrade. Why this step? Core 5 already has valid bytes; destroying and re-sending them would be wasted traffic. Only other copies threaten coherence.
Cores 2, 8 send Inv-Ack; HD counts 2 acks (not 3 — the writer doesn't invalidate itself).
HD → Core 5: Write-Ack with no data payload (Core 5 already had V=30). State → Modified, Owner={5}.
Core 5 writes V=31.

Verify: Invalidates sent = 2 (sharers minus the writer, $3 - 1 = 2$ ); data bytes transferred to writer = 0; ending owner = {5}; final value = 31. This is the degenerate "you already own the photocopy" case. ✔

Worked example Ex 7 — Cell 7: Full-map storage cost, limiting inputs

Statement. Recall $Directory size = M \times (2 + N)$ bits, where $M$ = number of memory blocks, $N$ = number of cores. Compute three points: (a) $N = 1$ , $M = 1$ ; (b) $N = 64$ , $M = 16, 000, 000$ ; (c) the limit as $N \to \infty$ . Forecast: In (a), is the directory smaller or larger than the block itself? In (c), does size grow with $N$ or $N^{2}$ ?

(a) One core, one block: size $= 1 \times (2 + 1) = 3$ bits. Why this step? This is the tiniest degenerate directory. A 64-byte block is $512$ bits, so the directory metadata ( $3$ bits) is a rounding error next to the data — overhead is negligible at this scale.
(b) The parent's headline case: $16, 000, 000 \times (2 + 64) = 16, 000, 000 \times 66 = 1, 056, 000, 000$ bits $= 132$ MB. Why this step? This shows why full-map is "so large" — the $+ N$ bit-vector per block dominates once $N$ and $M$ are big.
(c) Limit $N \to \infty$ : size $\approx M \cdot N$ bits — linear in $N$ , since the constant $2$ becomes negligible. It is not $N^{2}$ . Why this step? This is the whole point of directories vs. snooping: storage grows like $N$ , and traffic grows like $N$ , never $N^{2}$ .

Verify: (a) $= 3$ bits; (b) $= 1, 056, 000, 000$ bits, and $1, 056, 000, 000/8/1, 048, 576 = 125.9 \dots$ MB (≈132 MB using the parent's $16 M \times 66$ rounding); (c) leading term linear in $N$ . ✔

Worked example Ex 8 — Cell 8: NUMA home routing (real-world word problem)

Statement. A 4-socket server interleaves memory in 256-byte chunks. An address splits as [ tag | socket-select (2 bits) | 256B offset (8 bits) ]. Which socket is home for 0x7F00? For 0x7E00? Forecast: Do two addresses 0x100 apart land on the same socket or different sockets?

Find the offset bits. $256 = 2^{8}$ , so the low 8 bits are the byte offset inside a block. They do not pick a socket. Why this step? Interleaving must keep all 256 bytes of one block on one socket (locality), so the offset lives below the socket-select field.
0x7F00 in binary: $0x7F00 = 0111111100000000$ . Drop low 8 bits (0000 0000), the next 2 bits (bits 8–9) are 11 = 3. → Socket 3.
0x7E00 = $0111111000000000$ . Low 8 bits 0000 0000; bits 8–9 are 10 = 2. → Socket 2. Why this step? 0x7F00 and 0x7E00 differ by 0x100 = 256 = exactly one block, so they are consecutive blocks and correctly land on different sockets — spreading directory load.

Verify: 0x7F00 >> 8 = 0x7F = 127; $127 mod 4 = 3$ → Socket 3. `0x7E00 >> 8 = 0x7E = 126 $;$ 126 \bmod 4 = 2$ → Socket 2. Consecutive blocks, different sockets. ✔

Worked example Ex 9 — Cell 9: Exam twist — two writers race on a Shared block

Statement. Block Q at 0xF000. State=Shared, Sharers={0,1}. Core 0 and Core 1 both issue Write-Req "simultaneously." How does the HD keep coherence, and what is the final owner? Forecast: Can both writes be granted? Who wins?

Both requests reach the HD. The HD is a single point of serialization — it processes one Write-Req at a time for a given address, so the two requests are ordered (say Core 0 first, Core 1 second). Why this step? Coherence needs a total order on writes to one location; the home directory provides it by being the single arbiter.
Core 0's request handled first: HD invalidates the other sharer, Core 1, waits for its Inv-Ack, grants Core 0 the write. State → Modified, Owner={0}. Why this step? Same as the upgrade case (Ex 6) — invalidate everyone but the winner, count acks, then grant.
Core 1's request handled second: the block is now Modified/Owner=0. This becomes a Modified + Write (Ex 5!): HD sends Invalidate-Forward to Core 0, transfers ownership. State stays Modified, Owner={1}. Why this step? Core 1's write was queued; the second-in-line writer must snatch ownership from the first, exactly like Cell 5.
Final state: Modified, Owner={1} (the request the HD ordered last).

Verify: Number of writers granted at once = 1 (never 2); acks awaited for Core 0's request = 1 (only other sharer, Core 1); final owner = {1} (last serialized); ending sharer count = 1. Serialization at HD prevents two simultaneous owners. ✔

Recall Quick self-test

Ex 3: on a read to a Modified block, who supplies data — memory or the owner? ::: The owner (memory is stale until the write-back). Ex 4: HD holds Shared with 3 sharers; a write arrives — how many Inv-Ack must it collect? ::: All 3, before granting the write. Ex 6: a current sharer upgrades to write — how many bytes of data move to it? ::: Zero; it already holds a valid copy, so only an ack (no payload). Ex 7: full-map directory storage grows like $N$ or $N^{2}$ ? ::: Linear in $N$ (the $+ N$ bit-vector), never $N^{2}$ . Ex 8: consecutive 256B blocks under interleaving land on the same or different sockets? ::: Different sockets, by design, to spread load. Ex 9: what stops two simultaneous writers from both owning the block? ::: The home directory serializes requests for one address — one arbiter, one order.

See also: Cache coherence protocols (MESI, MOESI) · NUMA architectures · Interconnect topologies · Memory consistency models · Cache line false sharing · back to the parent topic.