Centralised Directory

Module 11 · Chapter 11.1 · Directory-Based Coherency

Project thread — Module 10 used the directory; this module studies it. 11.1 is the centralised directory — one structure. 11.2 distributes it across the home nodes.

1. Learning Outcomes

By the end of this chapter you should be able to:

• Contrast directory-based coherency with broadcast (snoop-everyone) coherency.
• State what a directory records — per line, the sharer set and the owner.
• Explain the benefit — targeted snoops instead of broadcasts, and a single source of truth.
• State the limits — a single-point bottleneck and finite capacity.
• Diagnose the stale reader from a directory that silently forgets a holder.
• Implement a representative directory lookup in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

How a system tracks who holds what decides how it scales. The simplest scheme, broadcast snooping, asks every cache about every coherence access — correct, but its traffic grows with the number of cores until the fabric drowns. The directory is the answer: a record of exactly who holds each line, so the home can snoop only the holders. Directory-based coherency is why large multi-core systems are possible at all, and CHI is built on it.

The centralised directory is where the idea starts — one structure, one place, tracking everything. It is worth understanding on its own because its benefits (precise targeting, a single source of truth) and its limits (a bottleneck, finite capacity) frame the entire module. Every later refinement — distributing the directory, partitioning it, sizing it — is a response to the centralised directory's limits. Learn it first, and the rest of the module reads as fixes to problems you already understand.

3. Key Terms

4. Previous Chapter Connection

Module 10 leaned on "the home's directory" constantly — it recorded the owner (Chapter 10.3) and the sharer set (Chapter 10.4), and the home routed snoops and writebacks by it. Those chapters used the directory; this module explains it.

The directory's whole purpose is what 10.4 hinted at: the home snoops exactly the recorded sharers, not everyone. That is directory-based coherency — targeted action from a tracked record — versus broadcast coherency, which asks all caches. This chapter is the centralised form of that record: one structure holding it all. The consistency and accuracy rules you saw in Module 10 (the set must be complete, the owner consistent) are properties of this directory — and its physical form, centralised here, is the new subject.

5. Core Concept — one record enabling targeted snoops

A directory records who holds each line so the home can act precisely; the centralised directory holds that record in one place.

• What it records. For each line, the directory holds the sharer set (which caches have a copy) and the owner (which cache, or memory, owns the dirty data) — the coherence state across all caches (Chapters 10.3, 10.4).
• Targeted, not broadcast. With the record, the home snoops only the caches that hold the line. Without it, coherence must broadcast — ask every cache — because it does not know who holds what. Targeting saves bandwidth that grows worse and worse with core count.
• Centralised: one structure. A centralised directory keeps the whole record in a single structure at one location. It is a single source of truth — one copy of the tracking, so consistency is simple.
• The limits. That single point is a bottleneck: every coherence action consults it, so its bandwidth and capacity cap the system. It cannot track unlimited lines, and it serializes access — which is exactly why real systems distribute it (Chapter 11.2).

The synthesis:

A directory records, per line, the sharer set and owner, so the home snoops only the holders — targeted action instead of a broadcast to every cache. The centralised directory keeps this record in one structure: a single source of truth, simple and precise. Its limits are the flip side of centralising — a bottleneck in bandwidth and a finite capacity — which push toward distributing the directory.

6. Engineering Mental Model — the front-desk sign-out log

An office with one shared front desk that keeps a sign-out log of who has borrowed which document.

• Without the log, finding all copies of a document means asking everyone — walk the whole floor, desk by desk. That is broadcast: correct, but it does not scale as the office grows.
• With the log, the front desk knows exactly who has each document, so it contacts only those people — targeted. One glance replaces a floor-wide search.
• But there is one desk, and everyone must go through it for every borrow and return. On a busy day it is a queue — the single desk is the bottleneck. And the log is a finite binder; it cannot list infinitely many borrowings.

The log is a huge win over asking everyone — until the single desk becomes the jam. That trade — precise targeting versus a single-point bottleneck — is the centralised directory.

7. Engineering Diagram — the single directory

Every cache consults the one directory — that is its strength (a single source of truth, precise targeting) and its weakness (a single point every action passes through). The three "lookup" arrows converging on one node are the whole story: precision at a bottleneck.

8. Directory versus Broadcast

The two coherence-tracking schemes, side by side.

The rule to carry: a directory trades storage and a lookup for targeted snoops — it snoops the holders, not everyone, so its traffic scales with how many caches actually share a line rather than with the total core count. Broadcast needs no record but asks everyone; the directory needs a record but asks few. As cores grow, targeting wins decisively — which is why CHI is directory-based.

9. The Benefits and the Limits of Centralising

The centralised form has clear pros and clear cons.

• Benefit — single source of truth. One copy of the tracking record means there is nothing to keep consistent between copies; the directory simply is the truth (Chapter 10.3's consistency is trivial with one record).
• Benefit — precise targeting. The one record knows every holder, so every snoop is exactly targeted — no broadcast, minimal snoop traffic.
• Limit — a bottleneck. Every coherence action consults the single directory, so its bandwidth and serialization cap throughput. Many cores contend for one structure.
• Limit — finite capacity. One directory cannot track unlimited lines. When full, it must back-invalidate (force caches to drop lines) to reclaim entries — it cannot simply forget a holder.

The point to carry:

Centralising the directory buys simplicity and precision at the cost of scalability. One record is trivially consistent and perfectly targeted — but one record is also one queue and one finite store. The benefits are why a directory beats broadcast; the limits are why a centralised directory eventually loses to a distributed one. And the capacity limit carries a correctness sting: a finite directory must never silently forget a holder, because a forgotten holder is a cache the home will not snoop — it must back-invalidate instead.

10. Reading the Directory — a targeted snoop

Follow a write against a centralised directory.

1. Lookup. A core issues a ReadUnique. The home consults the one directory for the line's entry.
2. The record. The directory says the sharer set is RN0 and RN2 (a two-bit-set bitmask); RN1 does not hold the line.
3. Targeted snoop. The home snoops only RN0 and RN2 — not RN1, not every cache. Two snoops, not N.
4. Broadcast would have asked all. Without the directory, the home would have to snoop every cache to be safe — wasting the snoops to caches that do not hold the line.
5. The bottleneck. All of this — and every other line's coherence — funnels through the one directory, which is the scaling limit the next chapter addresses.

Step 3 is the benefit (targeted); step 5 is the limit (one point). Both come from the same single record. Now imagine step 2 was wrong because the directory forgot RN2 — the DebugLab.

11. RTL / Hardware View — a directory lookup

The directory's core function is a lookup that turns the recorded sharer set into a targeted snoop mask — versus the broadcast a directoryless design would use. Representative.

// Representative centralised directory lookup (educational).
// The directory records the sharer set (bitmask). A TARGETED snoop hits only the
// recorded holders; a BROADCAST would hit all N caches. If the directory has no
// entry for the line, it must fall back to broadcast (safe but costly).
module chi_directory_lookup #(parameter N = 4) (
  input  logic [N-1:0] dir_sharers,   // the directory's recorded sharer set
  input  logic         entry_present, // the directory tracks this line
  output logic [N-1:0] snoop_targets, // targeted: only the recorded holders
  output logic [N-1:0] broadcast_all, // the naive alternative: every cache
  output logic         must_broadcast,// no entry -> fall back to broadcast
  output logic [$clog2(N+1)-1:0] snoops_saved // N - popcount(sharers)
);
  assign broadcast_all  = {N{1'b1}};
  // With a tracked entry, snoop only the holders; else broadcast.
  assign must_broadcast = !entry_present;
  assign snoop_targets  = entry_present ? dir_sharers : broadcast_all;
 
  // Bandwidth saving: how many snoops targeting avoids versus broadcast.
  logic [$clog2(N+1)-1:0] popc;
  always_comb begin
    popc = '0;
    for (int i = 0; i < N; i++) popc += dir_sharers[i];
  end
  assign snoops_saved = entry_present ? (N[$clog2(N+1)-1:0] - popc) : '0;
endmodule

The same behavior in Verilog-2001:

// Representative centralised directory lookup (Verilog-2001).
module chi_directory_lookup #(parameter N = 4) (
  input  [N-1:0] dir_sharers,
  input          entry_present,
  output [N-1:0] snoop_targets,
  output [N-1:0] broadcast_all,
  output         must_broadcast,
  output [31:0]  snoops_saved
);
  integer i; reg [31:0] popc;
  assign broadcast_all  = {N{1'b1}};
  assign must_broadcast = !entry_present;
  assign snoop_targets  = entry_present ? dir_sharers : broadcast_all;
  always @* begin
    popc = 32'd0;
    for (i = 0; i < N; i = i + 1) popc = popc + dir_sharers[i];
  end
  assign snoops_saved = entry_present ? (N - popc) : 32'd0;
endmodule

And in VHDL:

-- Representative centralised directory lookup (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_directory_lookup is
  generic ( N : integer := 4 );
  port (
    dir_sharers    : in  std_logic_vector(N-1 downto 0);
    entry_present  : in  std_logic;
    snoop_targets  : out std_logic_vector(N-1 downto 0);
    broadcast_all  : out std_logic_vector(N-1 downto 0);
    must_broadcast : out std_logic;
    snoops_saved   : out integer
  );
begin
end entity;
 
architecture rtl of chi_directory_lookup is
begin
  broadcast_all  <= (others => '1');
  must_broadcast <= not entry_present;
  snoop_targets  <= dir_sharers when entry_present = '1' else (others => '1');
  process (dir_sharers, entry_present)
    variable popc : integer;
  begin
    popc := 0;
    for i in 0 to N-1 loop
      if dir_sharers(i) = '1' then popc := popc + 1; end if;
    end loop;
    if entry_present = '1' then snoops_saved <= N - popc; else snoops_saved <= 0; end if;
  end process;
end architecture;

All three produce a targeted snoop mask from the recorded sharers when the directory has an entry, and fall back to a broadcast when it does not — never guessing a reduced set for an untracked line. The DebugLab shows the stale read when a tracked entry silently loses a holder.

12. Verification View — targeting is safe only with a complete record

The properties that keep directory lookups sound: targeted snoops equal the record, and an absent entry forces a broadcast.

// Bind to chi_directory_lookup.
// 1. With an entry, the snoop targets are exactly the recorded sharers.
property p_targeted_equals_record;
  @(*) entry_present |-> (snoop_targets == dir_sharers);
endproperty
 
// 2. Without an entry, the home must broadcast — never a guessed subset.
property p_no_entry_broadcast;
  @(*) (!entry_present) |-> (must_broadcast && snoop_targets == broadcast_all);
endproperty
 
// 3. Targeting never exceeds broadcast (it is a subset of all caches).
property p_targeted_subset;
  @(*) (snoop_targets & broadcast_all) == snoop_targets;
endproperty

The system point, beyond the checks:

A directory is only safe to target from if its record is complete — the home snoops the recorded set and no one else, so a holder outside the record is a holder never snooped. This is why an absent entry must force a broadcast: with no record, the only safe assumption is that anyone could hold the line. The centralised directory's power — replacing a broadcast with a precise, small snoop — is therefore inseparable from a discipline: the record must be trusted only when it is known complete, and a finite directory that cannot hold every line must fall back to broadcast, or back-invalidate, rather than target a record it has silently truncated. Precision is earned by completeness.

• What it proves: targeting equals the record; an absent entry broadcasts; targeting is a subset.
• What it does not prove: the record is complete — that is the tracking discipline (Chapter 10.4) and capacity handling.
• Bug signature: a targeted snoop of a truncated record — a forgotten holder unsnooped.

13. Testbench — targeted versus broadcast

Drives a tracked entry and an absent one, checking the snoop targets and the saving.

module tb_chi_directory_lookup;
  localparam N = 4;
  logic [N-1:0] dir_sharers, snoop_targets, broadcast_all;
  logic entry_present, must_broadcast;
  logic [$clog2(N+1)-1:0] snoops_saved;
  int errors = 0;
 
  chi_directory_lookup #(.N(N)) dut (.*);
 
  task automatic check(input logic [N-1:0] sh, input logic ep,
                       input logic [N-1:0] exp_tgt, input logic exp_bc,
                       input int exp_saved, input string name);
    dir_sharers = sh; entry_present = ep; #1;
    if (snoop_targets !== exp_tgt || must_broadcast !== exp_bc || snoops_saved !== exp_saved) begin
      errors++; $display("FAIL %s: tgt=%b bc=%0b saved=%0d", name, snoop_targets, must_broadcast, snoops_saved);
    end else $display("PASS %s: tgt=%b bc=%0b saved=%0d", name, snoop_targets, must_broadcast, snoops_saved);
  endtask
 
  initial begin
    check(4'b0101, 1'b1, 4'b0101, 1'b0, 2, "entry {RN0,RN2} -> target 2, save 2");
    check(4'b1111, 1'b1, 4'b1111, 1'b0, 0, "entry all -> target all, save 0");
    check(4'b0000, 1'b0, 4'b1111, 1'b1, 0, "no entry -> broadcast all");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS entry {RN0,RN2} -> target 2, save 2: tgt=0101 bc=0 saved=2
PASS entry all -> target all, save 0: tgt=1111 bc=0 saved=0
PASS no entry -> broadcast all: tgt=1111 bc=1 saved=0
ALL TESTS PASSED

14. DebugLab — the directory silently forgets a holder

directory full -> evicts entry for line L (to make room)
  BUT RN2 still holds L (SC)  -- entry dropped silently, no back-invalidate
now directory has NO record that RN2 holds L
RN0 ReadUnique(L) -> home consults directory -> sharers look empty/reduced
  -> snoops only the recorded set (not RN2)
RN0 writes NEW;  RN2 still SC(old) -> RN2 reads old -> STALE

15. Common Mistakes

• Dropping a live entry silently. Assumption: an entry can be evicted freely. Bug: forgotten holder, stale read (the DebugLab). Prevention: back-invalidate first.
• Targeting an untracked line. Assumption: no entry means no holders. Bug: missed snoop. Prevention: broadcast when there is no entry.
• Broadcasting when a directory exists. Assumption: always ask everyone. Bug: wasted bandwidth. Prevention: target the recorded holders.
• Assuming infinite capacity. Assumption: the directory tracks everything. Bug: overflow mishandled. Prevention: size it, and back-invalidate on overflow.
• Ignoring the bottleneck. Assumption: one directory scales forever. Bug: throughput ceiling. Prevention: distribute the directory (Chapter 11.2).
• Multiple inconsistent records. Assumption: copies are fine. Bug: drift. Prevention: centralised is one source of truth — keep it that way, or distribute cleanly.

16. Engineering Checklist

• Record, per line, the sharer set and the owner in the directory.
• Target snoops to the recorded holders — do not broadcast when you have a record.
• Broadcast (or back-invalidate) when the directory has no entry for a line.
• Treat the centralised directory as a single source of truth.
• On capacity overflow, back-invalidate before dropping an entry — never forget a live holder.
• Recognize the single directory as a bottleneck — plan to distribute it at scale.

17. Key Takeaways

• A directory records who holds each line, so the home snoops only the holders — targeted, not broadcast.
• Directory-based coherency scales far better than broadcast as cores grow.
• A centralised directory keeps the record in one structure — a single source of truth, precise and simple.
• Its limits are a single-point bottleneck (bandwidth, serialization) and finite capacity.
• A finite directory must back-invalidate on overflow — never silently forget a live holder.
• Target from a complete record; distribute to scale; the model here is representative.

18. Quick Revision

Centralised directory. A directory records, per line, the sharer set and the owner, so the home snoops only the recorded holders — targeted action, versus broadcast snooping which asks every cache. Targeting is why directory-based coherency scales as cores grow. A centralised directory keeps the whole record in one structure at one location: a single source of truth (trivially consistent) that enables precise targeting. Its limits are the price of centralising — a single-point bottleneck (every coherence action routes through it, capping bandwidth and serializing access) and finite capacity (it cannot track every line). The capacity limit carries a correctness rule: targeting is safe only from a complete record, so a finite directory must never silently forget a live holder — on overflow it must back-invalidate the caches (or fall back to broadcast for untracked lines), so the record only shrinks when caches actually release the line. Precision earned by completeness; a bottleneck that motivates distribution. Representative model; 11.2 distributes the directory across the home nodes.

Coming Next

Chapter 11.2 — Distributed Directory. The centralised directory was precise but a bottleneck; the next chapter breaks it up. Chapter 11.2 covers the distributed directory — partitioning the record across many home nodes so no single structure carries all the traffic, how a line's address maps to the home that tracks it, and how distributing the directory removes the bottleneck while keeping the targeting that makes directories worthwhile.