Question bank — Cache coherence at scale (directory-based)

Directory ::: A hardware table that, for each memory block, remembers who has a cached copy and what state it is in — it stores metadata only, never the data itself. Home node (HD) ::: The fixed node that "owns" a memory address's directory entry; every request for that address must go here first. Sharer ::: A cache currently holding a read-only copy of a block (state Shared). Owner ::: The single cache holding the only up-to-date (dirty) copy of a block (state Modified); memory is stale. Invalidate ::: A message telling a cache to throw away its copy so a writer can gain exclusive access.

The directory stores a copy of the block's data so it can answer reads quickly. ::: False. The directory holds only metadata (state + sharer list). On a Modified block the fresh data lives in the owner's cache, so the directory must forward the request — it has no data to hand out itself. A block in state Modified always has exactly one cache holding it. ::: True. Modified means exactly one owner has an exclusive dirty copy; if a second cache had it too, they could hold different values and coherence would break. When memory is in state Shared, the copy in main memory is stale. ::: False. Shared copies are read-only and identical to memory, so memory is valid. Memory only goes stale under Modified, where the owner may have written without writing back. Moving from Snooping to Directory reduces per-request latency. ::: False. It reduces bandwidth, not latency. A directory request must reach the home node and possibly be forwarded to an owner — extra hops that make each request slower than a single broadcast. A full-map directory's size depends on the number of cores but not on the amount of memory. ::: False. Size is $M\times (2+N)$ bits — it scales with both the block count $M$ and core count $N$. Doubling memory doubles the directory. In a full-map Modified entry, you still need a separate owner-ID field. ::: False. The single set bit in the sharer vector is the owner. A dedicated ${\log }_{2}N$ owner field would just duplicate information already present. A write to a Shared block can complete the moment the home directory receives the request. ::: False. The home must first invalidate every sharer and collect all Invalidate-Acks; only then may it grant the write, or an old reader could keep a stale value.

"On a read miss to a Modified block, the home directory reads the data from memory and replies." ::: Wrong — memory is stale under Modified. The home has no valid data; it forwards the request to the owner, who supplies the data and writes it back. "To invalidate all sharers, the directory broadcasts an Invalidate to every core." ::: Wrong — the whole point of a directory is to avoid broadcast. It sends Invalidate only to the cores named in the sharer list (typically 1–3), not all N. "Because sharers are read-only, the writer needn't wait for their acknowledgements." ::: Wrong — read-only copies still hold the old value. If the writer proceeds before their invalidations complete, those readers could serve stale data, violating coherence. "A distributed directory removes multi-hop routing since each node handles everything locally." ::: Wrong — distribution adds routing complexity: a request may have to traverse the interconnect to reach the correct home slice. It removes the single-bottleneck hotspot, not the hops. "Sparse/limited-pointer directories are strictly better because they use less memory." ::: Wrong — they trade storage for correctness pressure. When more than $k$ sharers exist, extras get evicted or the scheme falls back to false (over-broad) invalidations, hurting performance. "In the NUMA example, the low 8 bits of an address choose the home socket." ::: Wrong — with 256B interleaving the low 8 bits are the block offset (they stay on one socket). The socket is chosen by the bits above the offset (bits 8–9). "Snooping tracks per-block sharing state just like a directory." ::: Wrong — snooping keeps no central sharer table; each cache watches the bus and reacts. That statelessness is why it's simple but why it must broadcast.

Why does a Modified owner send data to the requester and a write-back to the home on a read miss? ::: The requester needs the fresh value now, and the home must update stale memory and downgrade state to Shared — otherwise memory would stay wrong after the block becomes shared. Why is broadcast traffic described as $O(N^2)$ while directory traffic is $O(N)$? ::: Each of $N$ cores may issue misses, and a broadcast reaches $N-1$ caches — $N\times (N-1)$. A directory sends each request to one home plus its sharers, which is why we say per-request cost is $O(\text{sharers})$, not $O(N)$. Isn't "a handful of sharers" just $N$ in disguise — couldn't all $N$ cores share one block, making directory traffic $O(N)$ too? ::: In the worst case (all $N$ read the same block) a write does invalidate all $N$, so one request is $O(N)$ — but that is a single write, not $N\times (N-1)$ traffic. In the common case sharing degree stays small (1–3) because true widely-shared read-only data is rare, so directory traffic is bounded by actual sharers, never by total core count as broadcast always is. Why must the directory count acks rather than just send invalidations and move on? ::: Fire-and-forget cannot guarantee the old readers have actually dropped their copies. Waiting for every ack is what makes "no stale reader survives a write" provable. Why do modern multi-chip systems (EPYC, Graviton) need directories rather than snooping? ::: There is no shared bus spanning separate chips to snoop on. Point-to-point directory messages are the only way to keep coherence across physically distinct dies. Why interleave memory above the block offset instead of at the very lowest bits? ::: Interleaving above the offset spreads consecutive blocks across sockets (balancing directory load) while keeping each block's bytes on one socket (preserving spatial locality). Why does the directory track sharers exactly rather than just a count? ::: On a write it must invalidate the specific caches holding copies. A mere count tells you how many exist but not which to message — forcing a broadcast and defeating the design.

What happens on a read miss when the state is Uncached? ::: The home simply reads from valid memory, replies with data, sets state to Shared, and records the requester as the sole sharer — no forwarding or invalidation needed. A write arrives for a block that is already Modified by a different owner — what does the home do? ::: It sends an Invalidate-Forward to the current owner, who invalidates (and writes back its dirty data), then the home grants the new writer exclusive Modified ownership. A core writes to a block it already holds in Shared — is any invalidation still required? ::: Yes, of the other sharers. Even though the writer has a copy, the remaining read-only holders must be invalidated before the write can proceed to Modified. What is the sharer list right after the very first read of a previously Uncached block? ::: Exactly one entry — the reading core. State becomes Shared with that single sharer, and memory remains valid. In a limited-pointer directory tracking up to $k$ sharers, what happens on the $(k+1)$-th sharer? ::: The scheme must either evict an existing sharer (forcing its invalidation) or degrade to a coarse/broadcast fallback — a deliberate accuracy-for-space trade-off. If a block is Shared with sharers {1,7,9} and core 7 silently evicts its copy, is the directory now wrong? ::: The directory over-approximates: it still lists 7, so a later write will needlessly invalidate 7. This is harmless for correctness (a spurious invalidate) but wastes one message.