8.2Baseline Directory System

8.2.1–8.2.2 The system and the directory entry

The system is chapter 2’s baseline with the memory controller promoted to LLC/directory controller and a directory added. The network topology is deliberately vague — mesh, torus, whatever — with one assumption: 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 on (at least) the forwarded-request network. For now: one directory entry per memory block, one monolithic LLC (§8.7.1 distributes it).

The baseline protocol is MSI; the block is owned by the directory unless some cache holds M. Each directory entry directory entry Per-block directory record: stable state, owner identity, and sharer list (baseline: 2-bit state, log2N-bit owner, N-bit one-hot sharer vector). defined in Chapter 8 — open in glossary :

Two high-level transactions deserve the spotlight before the tables:

• GetM with sharers: the directory sends the requestor Data plus the AckCount ackcount The sharer count the directory sends a GetM requestor so it knows how many Inv-Acks to await; MOSI adds a data-less AckCount message for upgrading owners. defined in Chapter 8 — open in glossary , sends Inv inv / inv-ack The directory sends an Invalidation to each sharer on a GetM; each sharer acknowledges DIRECTLY TO THE REQUESTOR — explicit acks replace snooping's implicit ones. defined in Chapter 8 — open in glossary to every sharer — and each sharer Inv-Acks the requestor directly. Only after Data and all Inv-Acks arrive is the transaction complete.
• PutM carries its data (unlike snooping’s PutM): otherwise the eviction would need a third message. The directory answers every Put with a Put-Ack put-ack The directory's acknowledgment that completes a Put transaction; until it arrives the evicting cache remains effectively in its old state. defined in Chapter 8 — open in glossary . And note: no silent S evictions — replacement sends an explicit PutS (§8.7.4 debates this choice).

Try it: the live directory

Watch the directory entry (state, owner, sharer bits) evolve and the messages flow in the site-wide message colors. The preset walks a 2-hop GetS, a GetM with Invalidation/Inv-Ack, a 3-hop Fwd-GetS, and an explicit PutS:

8.2.3 Avoiding deadlock

Message receptions cause message sends. If a request and the response it triggers compete for the same FIFO queues, cycles form: in the book’s Figure 8.4, C1 and C2 each try to send a Data response while their incoming queues sit full of requests — nobody drains, the system deadlocks. The classic fix: separate networks per message class virtual networks Separate physical or logical (virtual) networks per message class — requests, forwarded requests, responses — so one class can never block another, breaking deadlock cycles. defined in Chapter 8 — open in glossary (physical or virtual). This protocol needs three, because requests cause forwarded requests, which cause responses:

A response can then never block behind a request, breaking every cycle. (Full deadlock theory arrives in §9.3.)

8.2.4 The detailed specification

Three cells tell the section’s story — click them: ISD × Inv (the Data-vs-Inv cross-network race), IMA × Fwd-GetS (owner-on-paper without data — and why stalling is deadlock-safe), and SMAD × Inv (a lost upgrade race demoting to IM^AD, chapter 7’s window of vulnerability wearing directory clothes).

The directory’s subtleties: the split PutS-Last / PutS-NotLast events (only a precise sharer list can tell, and only Last reclaims ownership → I), PutM from Non-Owner (a stale PutM from a cache that already lost a race — acknowledged and otherwise ignored), and S^D, where the directory stalls new Gets while the old owner’s data is in flight.

8.2.5–8.2.6 Operation, races, and the simplification bill

The common cases run exactly as the simulator shows. The interesting corners are the races born of multiple in-flight transactions:

• Inv before Data (IS^D): the directory answered our GetS, then processed someone’s GetM — its Inv can beat its Data to us, since they ride different networks.
• Fwd-GetS before the Inv-Acks (IM^A): the directory made us owner the instant it processed our GetM; a forwarded request can reach us before the sharers’ acks do.
• Inv during an upgrade (SM^AD): the other GetM was ordered first — ack it, lose the copy, and continue as a full I→M.

The simplicity bill, paid twice: the controllers stall in these corners (a non-stalling variant with more transient states is §8.7.2’s business), and the directory sends full Data even to an S→M upgrader that already has valid data — the data-less AckCount message that fixes this waits for the MOSI protocol.