The librarian: directory-based protocols, roles and messages

Why a thousand cores cannot shout

Start from the machine that every exam paper draws (Fig. 1): four nodes N0–N3, each with a processor P, a cache C, a main-memory module MM and a directory D, all joined by an interconnection network. Lesson 34 met it as a DSM, one address space spread over four memories, where the address alone decides the home node: with 4 KiB per node, 0x2200 lives in MM2, so its home is N2.

The D boxes exist because snooping cannot follow at this scale. It relies on a broadcast medium: every request reaches every cache, and the single bus puts all requests in one order. That same broadcast stops it from growing: every transaction costs a lookup in every cache, so the work grows with the number of processors P, and the one bus saturates after a few dozen of them (lesson 33). A DSM has no single bus to snoop anyway: its nodes talk over point-to-point links.

The way out is to remember instead of asking. Fig. 2 shows the difference on eight cores, when core 2 writes a block that cores 0 and 3 hold.

The notes define the idea in one sentence (p. 462): a directory-based protocol "uses a centralized directory to keep track of the state of each memory block". Unlike snooping, it stores "the sharing state of each memory block in a single, well-defined location, called directory".

Where is that well-defined location? Next to the block itself. In a DSM each memory module has its own directory: if a block resides in N0's memory, its entry is in N0's memory controller (p. 462). Each node's directory tracks "all the blocks physically mapped to that memory" (p. 464), and nothing else. A request therefore travels to one node, chosen by the address, and that node contacts only the caches its entry names: point-to-point messages, no broadcast.

Lesson 34 compared a DSM to a university's libraries, one per faculty. Keep the picture: each library keeps a lending card for every book of its own collection. To borrow a book you ask the library that owns it, never the whole campus, and the librarian phones only the people written on the card. Book = block, library = home node, card = directory entry, librarian = directory controller.

A directory keeps one entry per block, at the block's home, next to its memory: logically one place per block, physically spread over all the nodes, so requests travel point to point instead of being broadcast.

The lending card: state, sharer bits and owner

Follow one block, B0, whose home is N0, through three moments: at first no cache has it; then P1 and P2 read it; then P2 writes it. Table 1 shows the entry in D0 and the copy in each of the four caches after each moment, in the format of the papers.

The entry has two fields (p. 463).

The papers always write the bits left to right in node order, N0 N1 N2 N3 (Fig. 3): "Sharer Bits: 1001" means that the caches of N0 and N3 hold copies. Reading the vector backwards is the cheapest way to lose a whole exercise.

Why does the home need a state at all, if the bits already say who holds a copy? Because the bits alone cannot tell a reader from a writer: 0010 could be a single read-only copy in C2, or C2 as the owner of a dirty copy (row 3 of Table 1). The state says where the valid data is. In Uncached and Shared, memory is up to date, so the home can serve a reader from its own memory. In Modified it is stale: the only fresh copy sits in the owner's cache, and the home must get it back first (lesson 38 runs that case).

The notes add a third field, the owner (p. 464), and then ask why: in Modified the single 1-bit already names it. The field is redundant; it only spares the controller a scan of a long vector. At the exam you read the owner off the bits: "Modified | 0010" means owner N2.

Directory states are not cache states

The three directory states echo the three states of MSI (lesson 35), "but tracked centrally" (p. 463): each cache knows only its own copy, the directory has the global view of the block. The July 2024 paper asks for both lists: the states "of a block in the local cache" and "in the home directory".

Home, local, remote: three parts in every request

A coherence transaction always starts at a processor. Take P2 loading a word of block B0, whose address lies in N0's memory:

; on P2, R1 = 0x0040 (block B0, home N0)
LD  F2, 0(R1)

C2 misses. Three questions decide everything that follows: whose memory holds the block, which node asks, and which nodes hold copies. Their answers are the three roles of the notes (p. 464), and the July 2024 paper asks for their definitions word for word, starting with "What is the definition of home node?".

Each role is read off something different. The home comes from the address: 0x0040 lies in MM0, so H = N0, whoever asks. The local node comes from the instruction: P2 executed the load, so L = N2. The remote nodes come from the card: with "Directory N0 Block B0 | Shared | 1001" the copies are in N0 and N3, so R = N0 and N3.

Look again at N0: it is home and remote at once, because its own cache holds a copy of a block of its own memory. "For a given transaction, a node can take on multiple roles" (p. 464), and two combinations recur in the papers. The local node can be the home: the July 2024 quiz has "Read Miss B1 from local cache N1" with B1 homed in N1, so the request and its reply never leave N1. The home can be a remote: that is the June 2026 exercise, the entry above with a write miss from N2. A local node that writes its own Shared copy is not a remote of its own request.

Why must every request go through the home, even when the requester could guess where a copy is? Because only the home's directory knows who holds copies, so only the home can contact exactly those nodes and keep the entry right. And because all requests for one block meet at one place, the home can serve them one at a time: the order that the bus gave snooping for free has to come from somewhere, and in a directory protocol it comes from the home.

Home from the address, local from the instruction, remote from the sharer bits — and one node may play two parts.

Seven messages, four directions

On a bus every cache overhears every transaction. A directory protocol is "message-oriented" instead: each coherence event is handled by explicit request and response messages between the local, home and remote nodes (p. 465). You met some of them as arrows in the widget: for B0 with Shared | 1001, a miss of P2 is a Read Miss or a Write Miss to N0, and N0 answers with a Data Value Reply. Hennessy & Patterson list all the messages with their contents — P the requesting node, A the block address, D the data — and the papers use the same names (Table 2).

Read the contents column first. Read Miss and Write Miss carry P and A, because the home must know whom to add to the sharer bits. The home's commands carry only A: they ask for an action on a block. Only two messages carry the block itself: the Data Value Reply that brings it to the requester, and the Data Write-Back that brings a dirty block home.

Invalidate appears twice, once in each direction. The local → home Invalidate is a request: the local cache holds the block in Shared and the processor writes it — a write hit, so there is nothing to fetch — and the local node asks the home to remove every other copy. The home → remote Invalidate is the command that does it: each sharer drops its copy, Shared → Invalid.

Fetch and Fetch/Invalidate both go to the owner of a Modified block, both ask for the fresh data back, and they differ in what the owner keeps. A Fetch serves a Read Miss: the owner may keep a read-only copy and goes Modified → Shared. A Fetch/Invalidate serves a Write Miss: the requester is about to become the new owner, so the old owner goes Modified → Invalid.

The owner answers both with a Data Write-Back to the home, carrying the dirty block; the home updates its memory and only then replies to the requester. The same Data Write-Back also travels on its own, when an owner evicts a Modified block.

The Data Value Reply closes every miss, and it always comes from the home: from its own memory in Uncached and Shared, after the owner's Data Write-Back in Modified. A local node that misses on a write needs it too, since it must have the block before writing into it. Table 34 writes "Home/Remote → Local" for it, but an owner that replies straight to the requester is a shortcut of real machines (three hops instead of four), not the protocol of the papers.

Now group the eight rows by direction, as Fig. 4 does.

These are the answers to the July 2024 question. Local → home: Read Miss, Write Miss, Invalidate. Home → local: Data Value Reply. Home → remote: Invalidate, Fetch, Fetch/Invalidate. Remote → home: Data Write-Back alone, the June 2025 quiz. And the "why" of June 2026 — after a write miss on a Shared block, does any remote node send a message to the home? No: Shared copies are clean, memory already holds the same data, and a sharer just drops its copy. Only an owner in Modified ever returns data. (The "Ack" that the notes' walkthrough draws on p. 471 is how real machines confirm an invalidation; it carries no data and is not one of the seven messages.)

The home is at one end of every message: requests come in from the local node, commands go out to the remote nodes, and data travels only home → local or owner → home.

The price of the lending card

The benefit of the directory is that the home talks only to the nodes on the card: a write to a block with two sharers disturbs two caches, whether the machine has 8 nodes or 1024. Traffic grows with the number of real sharers, not with P. The cost is the card itself, one entry for every block of memory. How big is it? Take 64 nodes and 64-byte blocks. (Background: the notes do not compute it.)

1. Count the entries. A memory of \(M\) bytes in blocks of \(B\) bytes has \(M / B\) blocks, and the directory keeps one entry per block:

   \[ N_{\text{entries}} = \frac{M}{B} \]

2. Size one entry. Three states need 2 bits; the sharer vector needs one bit per node:

   \[ \text{bits per entry} = P + 2 \]

3. Multiply: the whole directory, summed over all the homes, has

   \[ \frac{M}{B}\,(P + 2) \ \text{bits.} \]

4. Divide by the data it describes, \(8M\) bits. The memory size cancels: the overhead depends only on \(P\) and \(B\).

   \[ \text{overhead} = \frac{(M/B)\,(P + 2)}{8M} \] \[ = \frac{P + 2}{8B} \]

5. Put in 64 nodes and 64-byte blocks:

   \[ \frac{64 + 2}{8 \cdot 64} = \frac{66}{512} \approx 12.9\,\% \]

   The same block needs 258 bits with \(P = 256\) (50.4 %) and 1026 bits with \(P = 1024\) (200.4 %).

At 64 nodes the card costs 13 % of the memory: a price worth paying for a machine of that size. But the card grows with P while the block does not. At 256 nodes the card is half the block, at 510 nodes it equals it, and at 1024 it is twice the block: the catch of the hook is literally true. A full bit vector stops scaling at a few hundred nodes.

Large machines keep the idea and shrink the card (background, not in the notes): a few node pointers, one bit per group of nodes (a coarse vector), or entries only for the blocks that some cache holds (a sparse directory). Each pays with an occasional broadcast or a needless invalidation.

The puzzle, solved

So is the cure worse than the disease? Only at the wrong dose. Point-to-point messages through the home remove the broadcast for any number of nodes; the plain bit-vector card is cheap at a few dozen nodes, acceptable at a few hundred and absurd at a thousand, where machines compress it. What never changes is the cast: a home that keeps the card, a local node that asks, remote nodes that hold copies, and seven messages between them.