Everything so far assumed a complete directory: full state for every block, including the exact set of caches that (may) hold shared copies. But that assumption quietly contradicts the reason directories exist — scalability. In a system with many caches, a complete sharer list costs storage proportional to the cache count, per block, even packed as a bit vector. Modest systems can afford it; architects of large ones want cheaper representations.
Two important techniques — discussed separately here, but combinable in practice — trade precision for storage. Explore all three layouts of Figure 8.8 live (state and owner fields never change; only the sharer list shrinks):
Directory entry storage vs. system size (Fig 8.8, live)
Each bit = ONE cache. Exact Invalidations, but the sharer list grows linearly: 256 bits at C=256.
Each bit = 8 caches (a superset of the true sharers). A GetM invalidates all 8 caches in every set bit — up to 7 of them needlessly.
4 pointers of log₂256 = 8 bits each. Exact — until sharer #5 shows up; then mechanism X decides (Broadcast / No-Broadcast / Software).
Bar widths are proportional to bits per entry. Drag C to the right and watch the complete directory blow up while the limited pointer entry barely moves — that asymmetry is this whole section.
8.5.1 Coarse directory
The complete list lets the directory send Invalidations to exactly the caches in S. A coarse directory coarse directory A sharer-list bit represents K caches instead of one: less state, extra unnecessary Invalidations. defined in Chapter 8 — open in glossary keeps a conservative superset instead: each sharer-list bit stands for a set of K caches, and the bit is set if any of those K (may) hold the block in S.
The trade is clean:
- Saved: the sharer list shrinks from C bits to C/K bits.
- Paid: a GetM makes the directory send Invalidations to all K caches of every set bit — plus the cache-controller bandwidth to process Invalidations at caches that never held the block. Correctness is never at risk (every true sharer is covered); only bandwidth is.
8.5.2 Limited pointer directory
Studies show many blocks have zero or one sharer — so why pay C bits for a list that’s almost always nearly empty? A limited pointer directory limited pointer directory i pointers of log2C bits instead of a C-bit vector; overflow handled by Dir_iB (broadcast; Dir0B = stateless always-broadcast), Dir_iNB (evict a sharer), or Dir_iSW (software trap). defined in Chapter 8 — open in glossary keeps just i entries (i < C), each a full pointer of log₂C bits: total i·log₂C bits, exact as long as sharers are few.
The interesting question is what happens when sharer #(i+1) arrives. The notation DiriX names the answer: i = pointer count, X = the overflow mechanism. Three well-studied options:
Broadcast — DiriB
On overflow, set a new “too many sharers” state; a later GetM broadcasts Invalidation to all C caches — even if only K (i<K<C) actually share, wasting C−K messages. The limiting case Dir₀B drops all pointers and broadcasts on every coherence operation. The original Dir₀B kept two state bits: MSI plus a “Single Sharer” state that dodges the broadcast on an S→M upgrade (shades of Exclusive), while plain I dodges it when memory owns the block. AMD’s Coherent HyperTransport goes further still — no directory state at all, every request broadcast to all caches (§8.8.2).
No Broadcast — DiriNB
On overflow, the directory asks a current sharer to invalidate itself, freeing a pointer for the newcomer. Widely shared blocks pay dearly — each new reader past the i-th evicts an active one, which re-fetches and evicts another. Especially painful with coherent instruction caches: code is exactly the kind of block that is frequently, widely shared.
Software — DiriSW
On overflow, trap to a software handler — which can do anything, e.g. maintain the full sharer list in software data structures. Maximum flexibility; but trap cost and implementation complexity have kept commercial adoption limited.
Check yourself
1.Why does a 'complete directory' contradict the very motivation for directory protocols?
2.In a coarse directory, one sharer-list bit stands for K caches. What is the cost of the K-fold storage saving?
3.A limited pointer directory has i pointers and a sharer #(i+1) arrives. What do the three DiriX flavors do?
4.Why is DiriNB 'especially problematic for systems with coherent instruction caches'?
5.What is Dir0B, and who shipped a version of it?