Four optimizations, four different levers: distribute the bottleneck, un-stall the controllers, question a network guarantee, and reconsider an eviction convention.
8.7.1 Distributed directories
One directory attached to one monolithic LLC is a central bottleneck — and the general cure for central bottlenecks is distribution. Each block’s directory stays fixed in one place; different blocks simply live at different directories. Every block has a home home The directory (or directory/LLC bank) statically responsible for a block's memory and directory state — e.g., block B's home is directory B mod N. defined in Chapter 8 — open in glossary — the directory holding its memory and directory state — usually computed by plain arithmetic: with N directories, block B’s home might be B mod N.
Node 0
controller
controller
Node 1 … N−1
controller
controller
Multiple independent directories mean coherence bandwidth that scales with N instead of funneling through one resource — and, importantly, zero impact on the coherence protocol. On a modern multicore the same move is spelled differently: bank the LLC and directory cache, giving each block a home bank.
8.7.2 Non-stalling directory protocols
Our protocols so far stall whenever a forwarded request catches a cache in the wrong transient state — e.g., IMA. Every stalled message blocks the queue behind it. The non-stalling variant instead absorbs the message into the state name:
- IMA + Fwd-GetS → IMAS: “finish my write (await Inv-Acks), then send data to the reader and the directory and settle in S.”
- IMAS + Inv → IMASI: the chain grows — serve the reader, then invalidate.
- Same family for upgrades from S: SMAS, SMASI, SMAI. And ISD now processes an Inv too (→ ISDI: perform the one load when data lands, then invalidate immediately).
The general law: removing stalls costs transient states — the controller must remember what it would have postponed.
Table 8.8 (recreated): non-stalling MSI directory protocol — cache controller
| Core | Forwarded | Responses | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| State | Load | Store | Replacement | Fwd-GetS | Fwd-GetM | Inv | Put-Ack | Data from Dir (ack=0) | Data from Dir (ack>0) | Data from Owner | Inv-Ack | Last-Inv-Ack |
Cell format: action / next state (next state omitted when unchanged) · blank = event ignored · shaded = impossible. Click any cell or state chip.
Click a transition cell for its plain-English explanation, or a state chip for its invariants.
The directory, by contrast, still stalls (SD on GetS/GetM) — exactly Table 8.2’s behavior, reproduced here as the book’s Table 8.9. Removing its stalls would take an impractically large number of transient states, the same wall chapter 7’s memory controllers hit:
Table 8.9 (recreated): non-stalling MSI directory protocol — directory controller (unchanged from Table 8.2)
| Requests | Responses | ||||||
|---|---|---|---|---|---|---|---|
| State | GetS | GetM | PutS (not last) | PutS (last sharer) | PutM+data from Owner | PutM+data from Non-Owner | Data (from old owner) |
Cell format: action / next state (next state omitted when unchanged) · blank = event ignored · shaded = impossible. Click any cell or state chip.
Click a transition cell for its plain-English explanation, or a state chip for its invariants.
8.7.3 Interconnects without point-to-point ordering
Back in §8.2 we required the Forwarded Request network to provide point-to-point ordering point-to-point ordering Messages between the same source and destination arrive in send order; assumed on the forwarded-request network, and incompatible with unrestricted adaptive routing. defined in Chapter 8 — open in glossary — delivery between any pair of endpoints in the order sent. Here is the race that guarantee was buying off — step through it (the MOSI protocol, C1 owning the block in M):
Figure 8.12: point-to-point ordering — forwards arrive in serialization order.
1 / 7The setup
C1's cache owns the block in M. C2 sends GetS to the directory; C3 sends GetM. The directory serializes C2's GetS FIRST, C3's GetM second — and forwards both to C1, in that order.
Why would anyone give up such a convenient guarantee? Because enforcing it forbids adaptive routing adaptive routing Letting messages choose paths dynamically to avoid congestion; same-pair messages may then arrive out of order. defined in Chapter 8 — open in glossary — letting each message pick its path dynamically to dodge congestion:
Our protocols as presented are simply incompatible with an unordered Forwarded Request network; making them compatible means handling races like the one above — typically with extra handshaking (the directory waits for each forwarded request to be acknowledged before sending that cache another).
8.7.4 Silent vs. non-silent evictions of S blocks
Our baseline made every S eviction explicit: PutS, then wait for the Put-Ack. The alternative — silent eviction silent eviction Evicting a block without sending any message; permitted for non-owned states (S, sometimes E) in some protocols. defined in Chapter 6 — open in glossary — is a genuine design choice (the same debate applies to E, if E is treated as non-owned):
The case for silent PutS
The explicit PutS/Put-Ack pair burns interconnect bandwidth even when it buys nothing: evict S, then re-load the same block before anyone writes it, and the round-trip served no purpose at all. Silence is free.
The case for explicit PutS our baseline’s choice
A precise sharer list pays three ways: (1) later GetMs skip the useless Inv + Inv-Ack round-trip to the departed cache; (2) a MESI directory that counts sharers exactly can detect “none left” and re-arm the Exclusive-data grant; (3) Recall-based directory caches stop recalling blocks that are already gone. And a second, subtler win: it eliminates a race — silently evict S, re-issue a GetS, and an Inv can arrive before your data. Old copy or new one? The simple fix is pessimism (invalidate the moment data arrives — ISDI above); better fixes complicate the protocol.
Check yourself
1.How does distributing the directory (Fig 8.11) affect the coherence protocol itself?
2.In the non-stalling protocol, a cache in IM^A receives a Fwd-GetS. What happens, and what's the payoff?
3.Why did the authors NOT remove stalls from the directory controller too?
4.Without point-to-point ordering on the Forwarded Request network, C1 (owner in M) is sent a Fwd-GetS (for C2) then a Fwd-GetM (for C3). What can go wrong?
5.What are the concrete benefits of an explicit (non-silent) PutS?