Exercises — Cache coherence at scale (directory-based)

MESI/MOESI ::: Per-cache-line state machines. Modified = dirty, sole owner, memory stale. Exclusive = clean, sole owner, memory valid — the holder may write silently. Shared = clean, possibly many read-only copies. Invalid = not present. MOESI adds Owner: a dirty block shared for reading while one cache stays responsible for write-back. NUMA ::: Non-Uniform Memory Access: memory is split across sockets/nodes; a core reaches its local node fast and remote nodes slower. Addresses are interleaved so consecutive blocks map to different nodes (the "home" of a block). Interconnect topologies ::: The wiring between cores/directories — ring, mesh, crossbar. Determines how many hops a message takes; directory latency = number of hops to home + hops to owner. Memory consistency models ::: Rules for the order in which one core's memory operations become visible to others across different addresses. Distinct from coherence, which is per-address. Cache line false sharing ::: When two independent variables share one cache line, coherence treats them as one block — writes ping-pong ownership even though no real data is shared.

(a) The sharers set $\{1,4,7\}$ lists three caches (cores 1, 4, 7). (b) In Shared state all copies are read-only, so by the invariant memory is valid (it holds the definitive value). (c) No. Writing requires transitioning to Modified, which forces invalidation of the other sharers — that must go through the home directory (HD). A silent write would leave stale copies in cores 4 and 7.

(a) Uncached — nobody caches it, memory is the sole valid copy. Entry $⟨\text{Uncached},\{\}⟩$. (b) Modified — the sharers set is a singleton $\{5\}$, so core 5 is the owner; memory stale (core 5's copy is definitive). Entry $⟨\text{Modified},\{5\}⟩$. (c) Shared — multiple read-only copies, memory valid. Entry $⟨\text{Shared},\{2,8\}⟩$.

False. The directory holds only metadata — state + the sharers set. On a read miss in Uncached/Shared state (memory valid), the data comes from main memory; in Modified state (memory stale) it comes from the owning cache (the singleton sharer). The directory never duplicates the payload.

1. Core 6 → HD (home directory): Read-Req(0xB000) — message 1.
2. HD sees Uncached (memory valid) → fetches from memory, replies Data(Y=7) to core 6 — message 2.
3. HD updates: $⟨\text{Shared},\{6\}⟩$.
4. Core 6 installs $Y=7$ as Shared. Final entry: $⟨\text{Shared},\{6\}⟩$. Message count = 2 (Read-Req + Data reply). No acks exist on a read, so end-to-end this is genuinely 2.

1. Core 9 → HD: Read-Req(0xC000) — message 1.
2. HD sees Modified (memory stale), sole sharer = core 3 → forwards request to core 3 — message 2.
3. Core 3 → Core 9: Data-Reply(Z=88) — message 3.
4. Core 3 → HD: Data-WriteBack(Z=88) (memory now updated to 88, becomes valid) — message 4.
5. HD updates: $⟨\text{Shared},\{3,9\}⟩$. Final entry: $⟨\text{Shared},\{3,9\}⟩$; memory $Z=88$. The old owner stays a sharer — it did not invalidate, it downgraded to read-only. Message count = 4 (Read-Req + Forward + Data-Reply + Write-Back — every crossing counted, per our ground rule).

1. Core 2 → HD: Write-Req(0xE000) — message 1.
2. HD sees Uncached → no sharers exist, so there is nothing to invalidate and no acks to wait for. HD replies Write-Ack(V=5) (supplying the current value from memory so core 2 can merge/overwrite) — message 2.
3. HD updates: $⟨\text{Modified},\{2\}⟩$ (core 2 is now the sole owner; memory becomes stale once core 2 writes).
4. Core 2 stores $V=77$, marks the line Modified; memory stays stale at 5 until write-back. Final entry: $⟨\text{Modified},\{2\}⟩$. Message count = 2 (Write-Req + Write-Ack). Difference from the Shared write: the Uncached→Modified path skips the whole invalidate-and-count-acks phase because the sharers set is empty. It is the cheapest write path — grant ownership immediately.

Core 5 is a sharer but only holds a read-only copy, so it still needs an upgrade (Shared → Modified).

1. Core 5 → HD: Write-Req(0xD000) (an upgrade request).
2. HD sends Invalidate to the other sharers: cores 0, 2, 8 (not to core 5 — it becomes the new owner).
3. Cores 0, 2, 8 each → HD: Inv-Ack. HD collects 3 acks.
4. After all 3 acks, HD → Core 5: Write-Ack, then updates $⟨\text{Modified},\{5\}⟩$. Final entry: $⟨\text{Modified},\{5\}⟩$. Acks collected = 3. (Full message count end-to-end: 1 Write-Req + 3 Invalidate + 3 Inv-Ack + 1 Write-Ack = 8.)

(a) When a read miss finds the block Uncached (no other sharers), the directory knows core 4 is the only holder. Granting Exclusive lets core 4 later write silently (E→M with no directory traffic), avoiding a future upgrade round-trip. This is a pure latency optimization. (b) A Shared holder must send a Write-Req and wait for Write-Ack before writing. An Exclusive holder may transition E→M locally — no message needed, because the directory already knows no one else has a copy. (c) Core 7's read reaches the HD; the HD sees the block is Exclusive at core 4. Since E is clean (memory valid), core 4 simply downgrades E→Shared and the data can come from memory (or from core 4). Result: $⟨\text{Shared},\{4,7\}⟩$, and memory does NOT need updating — E was never dirty. (Contrast Modified, which forces a write-back because memory was stale.)

Why 2 State bits. A field of $b$ bits can name $2^b$ distinct values. Our base protocol has 3 states (Uncached, Shared, Modified). We need $b$ with $2^b\ge 3$: $b=1$ gives only $2^1=2$ (too few), $b=2$ gives $2^2=4\ge 3$ (enough, one code spare). So 2 bits suffice. Adding Exclusive makes 4 states, and $2^2=4$ exactly — still 2 bits, using the previously-spare code. A 5th state (e.g. MOESI's Owner) would need $2^3=8$ ⇒ 3 bits. That is why the parent's formula bakes in 2. Storage. Full-map entry width $=2+N=2+128=130$ bits. $\text{Size}=M\times (2+N)=2^{25}\times 130\text{ bits}.$ $2^{25}\times 130=33,554,432\times 130=4,362,076,160$ bits. In MB: $\frac{4,362,076,160}{2^{23}}=\frac{4,362,076,160}{8,388,608}=520$ MB. Answer: 520 MB. Notice it scales linearly in both $M$ and $N$ — this is why full-map dies at high core counts.

To compare like with like we count the request-side fan-out (how many endpoints the request reaches) for both schemes; this is stated explicitly so it is not confused with the end-to-end counts of L2. (a) Snooping: 1 broadcast reaching $N-1=63$ caches → 63 endpoints. (b) Directory: 1 request to home + up to $k=3$ sharer messages → $1+3=4$ endpoints. (c) Ratio $=63/4\approx 15.75\times$ fewer. (d) Per miss, snooping is $O(N)$ (broadcast touches all $N-1$ cores) while the directory is $O(1+k)=O(1)$ (bounded by $k$, independent of $N$). The famous $O(N^2)$ is aggregate: $N$ cores each generating $O(N)$-fan-out misses ⇒ $O(N^2)$ system-wide — that is a whole-system rate, not the per-miss cost.

Under LSB-0 numbering, bit 0 is the rightmost bit. The 256B offset occupies bits 0–7 (since $2^8=256$); the 2 socket-select bits sit just above, at bits 8–9. $\text{0x8300}=1000001100000000_2$. Low 8 bits (offset) $=00000000$. Bits 8–9: shift right by 8 → 0x8300 >> 8 = 0x83 = 1000\ 0011; its low 2 bits $=11_2=3$. Home = Socket 3. (Interleaving above the offset spreads consecutive blocks across sockets while keeping each block's bytes local.)

Step 1 — Core 0 read: Uncached → HD replies $X=42$, entry becomes $⟨\text{Shared},\{0\}⟩$ (memory valid). Step 2 — Core 3 read: Shared → HD adds core 3, replies $X=42$, entry $⟨\text{Shared},\{0,3\}⟩$. Step 3 — Core 1 write:

• Core 1 → HD Write-Req. HD sends Invalidate to sharers $\{0,3\}$ (2 invalidations).
• Core 0 → HD Inv-Ack; Core 3 → HD Inv-Ack. HD collects 2 acks.
• Only after both acks does HD send Write-Ack to Core 1 and set $⟨\text{Modified},\{1\}⟩$.
• Core 1 now stores $X=99$; memory becomes stale until later write-back. When may Core 1 store? After it receives Write-Ack, i.e. after the HD confirmed both stale readers are gone. Storing earlier would let core 0 or 3 read the old 42 concurrently with the new 99 — a coherence violation.

Part 1 — why B stops seeing the old flag. Assume flag starts Shared (both cores cache it read-only, value 0). When Core A executes store flag = 1:

1. A cannot write from Shared; it sends Write-Req to the HD.
2. The HD sends Invalidate to B's copy of flag and waits for B's Inv-Ack before granting A the write (Write-Ack), exactly the rule of Ex 4.1.
3. B's cached flag is now Invalid, so B's next loop iteration misses and must re-fetch — it physically cannot keep reading the stale 0. Once A's write completes, that re-fetch returns 1 and the spin exits. This handshake is what enforces the per-block coherence invariant: a single agreed value of flag visible to all. Part 2 — what coherence does NOT give you. Coherence orders operations to one address (flag). It says nothing about whether A's earlier store data becomes visible to B before A's store flag = 1. If the hardware reorders A's two stores, B could see flag == 1 yet load a stale data. Fixing cross-address ordering is the job of the memory consistency model (e.g. a release fence on A's store, an acquire on B's load). See Memory consistency models. Takeaway: coherence (this note) + a consistency model together make the flag/data handshake correct; neither alone suffices.

Chip A (8 cores, shared bus): choose snooping. Broadcast latency is a single low-latency hop; per-miss traffic is only $O(N)=7$ endpoints — cheap. Directory indirection would add a hop with no bandwidth payoff. (Matches Intel Core i7.) Chip B (96 cores, 6 chiplets, no bus): choose directory. There is physically no shared bus to snoop, and broadcast to 95 caches would saturate the interconnect. Point-to-point (home + few sharers) keeps per-miss traffic $O(1)$. Distribute the directory across chiplets so no single slice is a hot-spot. (Matches AMD EPYC.) Principle: protocol follows scale and topology, not "newness".

(a) Each sharer ID needs $\lceil {\log }_{2}256\rceil =8$ bits. Four pointers $=4\times 8=32$ bits, plus 2 state bits $=34$ bits per entry. (b) Full-map per entry $=2+N=2+256=258$ bits. Limited-pointer is $34$ bits — about $258/34\approx 7.6\times$ smaller. (c) Overflow hazard: if a 5th core wants to share, there's no slot. See Ex 5.3 for exactly what the hardware does then.

(a) The entry has exactly $k=4$ pointer slots and all four are occupied by $\{1,6,20,44\}$. There is no encoding for a 5th distinct sharer ID — the hardware assumed a maximum of $k$. So core 100 cannot simply be added. (b) Two standard policies:

• Broadcast fallback (coarse vector): the entry flips to a special "too many sharers" mode — it stops tracking individuals and marks the block as "shared by everyone (or by a coarse group of cores)." Cost: future invalidations must broadcast to that whole group, losing the point-to-point win for this block.
• Eviction / forced invalidation: the directory picks one current sharer (say core 1), sends it an Invalidate, collects the ack, frees the slot, and inserts core 100. Cost: a false invalidation — core 1 loses a perfectly valid read-only copy and will miss if it reads $P$ again. (c) When core 200 writes $P$ (Shared → Modified):
• Under broadcast fallback, the HD must send Invalidate to the entire coarse group and collect all their acks — potentially dozens of messages, even though only 4–5 cores truly cached $P$.
• Under eviction, the sharer set never exceeded 4, so the write invalidates only those ≤4 tracked cores — cheap invalidation, but some earlier reader (core 1) already paid with a false invalidation. Design lesson: limited pointers trade storage (34 vs 258 bits, Ex 5.2) for occasional traffic/false invalidations at overflow. Pick $k$ to cover the common sharing degree so overflow is rare.

The directory tracks coherence at block granularity, not variable granularity. So:

• Core 4 writes its var → block goes Modified, sharers $\{4\}$; core 7's copy is invalidated.
• Core 7 writes its var → HD invalidates core 4, ownership ping-pongs to sharers $\{7\}$.
• Repeat → the block bounces between the two owners on every write. This is false sharing: the variables are independent, but the block is shared, so the coherence protocol serializes them. Cost = repeated invalidations + owner-forwarding hops, even though no true data dependence exists. Fix (design mastery): pad the two variables into separate cache lines so their directory entries are independent. See Cache line false sharing.

How many caches hold $⟨\text{Shared},\{1,4,7\}⟩$? ::: Three. In Modified state, where is the "owner" stored? ::: It is the single element of the Sharers set — no separate owner field. What does "memory stale" mean and which state has it? ::: A cache holds a newer value than memory, so memory is not the definitive copy — true in Modified. On a read miss to a Modified block, who supplies the data? ::: The owning cache (via forward + write-back), not the directory. End-to-end messages for a read miss on an Uncached block? ::: 2 (Read-Req + Data reply; no acks on reads). What can an Exclusive holder do that a Shared holder cannot? ::: Write silently (E→M) with no directory messages. Invalidations on a write from sharer 5 with sharers $\{0,2,5,8\}$? ::: 3 (all sharers except the writer). Why does the State field need only 2 bits (base protocol)? ::: 2 bits encode $2^2=4$ codes, enough for 3 (or 4 with Exclusive) states. Full-map directory size for $N=128$, $M=2^{25}$ blocks? ::: 520 MB. Per-miss request fan-out: snooping vs directory (big-O)? ::: $O(N)$ vs $O(1)$; the $O(N^2)$ is aggregate, not per-miss. What happens when a limited ($k$-pointer) directory's sharer set overflows? ::: Broadcast fallback (coarse vector) or evict a sharer via forced/false invalidation. What per-line trap makes disjoint variables expensive? ::: False sharing.