8.6Directory Organization

Logically, the directory holds one entry for every block of memory. Traditional systems took that literally: with the directory controller integrated into the memory controller, they augmented memory itself — the SGI Origin added extra DRAM chips to store complete directory state alongside every memory block.

For a modern multicore with a large LLC, that design makes little sense. Off-chip directory accesses cost latency and power — even for data that’s cached on chip — and almost all memory blocks aren’t cached at any moment, so the vast DRAM directory is mostly dead weight. The fix is the classic one: cache the common case. A directory cache directory cache An on-chip cache of directory entries; DRAM-backed in traditional designs, inclusive (no backing store) in modern ones. defined in Chapter 8 — open in glossary keeps a subset of directory entries on chip, exploits the same locality that data caches do (while storing only coherence state, not data — so small ones hit often), and changes nothing about protocol functionality — only average latency. It matters more on multicores: when core-to-core messages take a handful of cycles, an off-chip directory access stops being amortized and becomes the bottleneck.

The key design question: what happens on a directory cache miss?

Table 8.7 (recreated): comparing directory cache designs.

8.6.1 Directory cache backed by DRAM

Keep the complete directory in DRAM as tradition demands, and add a separate on-chip cache to cut average latency. Straightforward — and triply flawed:

1. DRAM cost: state for the vast majority of blocks that aren’t cached anywhere.
2. Decoupling: the directory cache and LLC track independently, so you can hit in the LLC yet miss in the directory cache — paying a DRAM trip for data sitting right there on chip.
3. Writebacks: evicted directory entries must be written back to DRAM — more latency and power.

8.6.2 Inclusive directory caches

The better observation: only blocks cached on chip need directory entries at all. An inclusive directory cache inclusive directory cache Holds entries for a superset of all blocks cached on chip, so a miss means Invalid everywhere: embedded in an inclusive LLC (extra bits per block) or a standalone duplicate-tag structure (CxK associativity). defined in Chapter 8 — open in glossary holds entries for a superset of all on-chip blocks, making it a “perfect” directory cache: a miss proves the block is in state I in every cache — it is an answer, not a precursor to a slower lookup. No DRAM backing store exists.

Embedded in an inclusive LLC

If the LLC maintains inclusion over the L1s (every L1 block is also in the LLC), then “not in the LLC” already means “I in every L1.” So embed the directory in the LLC: add state bits to every LLC block.

The catch is LLC inclusion itself. For shared LLCs it generally requires Recall recall A directory-initiated eviction of a block from all caches, used when a limited-associativity directory-cache set fills; kept rare by sizing (at least 2x aggregate cache capacity) and non-silent PutS. defined in Chapter 8 — open in glossary requests to invalidate L1 copies whenever the LLC replaces a block. Worse, inclusion means storing redundant copies of everything the L1s hold — and on a multicore, aggregate L1 capacity can be a significant fraction of (or exceed!) the LLC.

Standalone inclusive directory cache

Drop the LLC-inclusion requirement: make the directory cache a standalone structure holding duplicate copies of every L1 tag — the union of the L1s’ contents is the set of on-chip blocks. More flexible; but now the storage is redundant tags, and the structure has a nasty shape:

There’s also bookkeeping complexity: the directory cache must track every L1 eviction, so caches must issue an explicit PutS — silent evictions are off the table (a thread §8.7.4 picks up). A common optimization piggy-backs the PutS onto the very GetS/GetX that displaces the block: same index bits, so naming which way was replaced suffices. This is called a “replacement hint” replacement hint A PutS piggybacked on a GetS/GetM naming the replaced way (same set index); required for duplicate-tag directory caches despite the name 'hint'. defined in Chapter 8 — open in glossary — misleadingly, since it is generally required, not optional.

Limiting the associativity — Recalls

Rather than build the worst-case C×K-way structure, cap it at A-way (A < C×K) and forbid the worst case: when a coherence request would add a block to a full directory-cache set, the directory first Recalls one of that set’s blocks — invalidating it from every cache that holds it, collecting acknowledgments — and only then processes the original request.

Recall-based designs live or die on sizing. Conway et al.’s rule of thumb: cover at least the aggregate capacity of the caches it includes — larger to push Recall rates down further. And they pair badly with silent S evictions: the directory would Recall blocks from caches that quietly dropped them long ago, for nothing.

8.6.3 Null directory cache (no backing store)

The cheapest directory cache null directory cache No directory state at all (Dir0B): every forwarded request is a broadcast, but the directory controller survives as the LLC controller and the protocol's ordering point. defined in Chapter 8 — open in glossary is none at all. Directory state only prunes the forwarding set — and as with coarse directories, incomplete pruning costs messages, never correctness. Take that to the limit: a Dir₀B protocol (§8.5.2) prunes nothing, needs no directory, and simply broadcasts every forwarded request to all caches. Simplistic — yet popular in small-to-medium systems, because the storage cost is zero.

If there’s no directory state, why keep a directory controller? Two reasons:

1. It’s really the LLC/directory controller — it still owns the LLC.
2. It is the ordering point: concurrent requests for the same block are serialized there, and it decides who was first. The protocol’s correctness never depended on the state — it depends on the serialization.