Distributed Directory

Module 11 · Chapter 11.2 · Directory-Based Coherency

Project thread — 11.1 exposed the centralised bottleneck. This chapter distributes the directory across home nodes. 11.3 covers how each slice encodes its sharers.

1. Learning Outcomes

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

• Explain how distributing the directory across home nodes removes the centralised bottleneck.
• State that each home owns a slice of the address space and tracks only its lines.
• Describe the address-to-home mapping — a line's address determines its home.
• State the rules — the mapping is deterministic, total, and identical at every requester.
• Diagnose the coherence split when requesters disagree on a line's home.
• Implement a representative address-to-home function in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

The centralised directory's single point is fatal at scale — one structure cannot serve dozens or hundreds of cores. The distributed directory is the fix that makes large coherent systems real: split the record across many home nodes, each responsible for a portion of memory, so no one structure carries all the traffic. Every large CHI system is built this way; understanding the distribution is understanding how coherence scales.

The subtlety is deceptively simple and absolutely load-bearing: which home tracks a line. If every agent agrees — the same address always maps to the same home — then that home is the single, consistent point of serialization and tracking for the line, and coherence holds. If agents disagree, the line is tracked in two places that never reconcile, and coherence silently splits. So the distribution rests on one canonical rule, and this chapter is about getting that rule right.

3. Key Terms

4. Previous Chapter Connection

Chapter 11.1 showed the centralised directory's benefits — targeted snoops, a single source of truth — and its fatal limit: one structure is a bottleneck. This chapter removes the bottleneck without losing the benefits.

The mechanism is partitioning. Instead of one directory, there are many — one per home node — and each tracks only the lines in its slice of the address space. The targeting of 11.1 is preserved (each slice is still a precise record), but the traffic is spread, so no single structure is overwhelmed. What is new is the address-to-home mapping: with one directory, "the home" was obvious; with many, a line's address must select its home — and every requester must select the same one.

5. Core Concept — partition by address, map canonically

A distributed directory splits the coherence record across home nodes, each owning a slice of the address space, and a line's address selects its home.

• Each home owns a slice. The address space is partitioned; each home node is responsible for the lines in its slice, and tracks only those. No home tracks everything.
• The address selects the home. A line's address maps, by a fixed function, to exactly one home node — its home. That home is the sole tracker and serialization point for the line (Chapter 6.7 routed to it; here it also owns the directory for it).
• Traffic spreads. Because different addresses map to different homes, coherence transactions fan out across all the homes — no single structure is the bottleneck. The system scales with the number of homes.
• The mapping must be canonical. Every requester must compute the same home for a given address — one deterministic, total function used identically everywhere. Otherwise a line is tracked in two places.

The synthesis:

A distributed directory partitions the record across home nodes, each owning an address-space slice and tracking only its lines. A line's address maps to exactly one home — its sole directory and serialization point — so traffic spreads and the centralised bottleneck is gone, while targeting is kept. The load-bearing rule: the address-to-home mapping is one canonical, deterministic, total function, identical at every requester.

6. Engineering Mental Model — regional records offices

Replace the single front desk (Chapter 11.1) with regional records offices.

• The country is divided into regions, and each region has its own records office that keeps the sign-out log for documents belonging to that region. No office keeps everything.
• To find who has a document, you consult the office for its region — determined by the document's ID. Different documents route to different offices, so no single office is swamped.
• The essential rule: everyone must use the same region map. If you and I disagree about which region a document belongs to, we file our borrowings at different offices — and neither office has the whole picture. The document is now "tracked" in two places that never talk.

Many offices remove the single-desk queue, but only if there is one agreed map from document to office. Distribution scales; a shared, canonical map keeps it coherent.

7. Engineering Diagram — the directory partitioned by address

One function maps every address to one home's slice. The three arrows fan the address space across three homes — spreading the traffic that a single central directory would have absorbed alone. The map is shared: every requester routes a given line to the same home.

8. Centralised versus Distributed

The two directory organizations, compared.

The rule to carry: distributing the directory trades a single structure for many, each tracking a slice, so traffic spreads and the bottleneck disappears. The cost is a new obligation — a canonical address-to-home mapping that every requester computes identically. Get that mapping right and distribution is pure win (scaling without losing targeting); get it wrong and coherence splits.

9. The Canonical Address-to-Home Mapping

The one rule the distribution depends on deserves its own statement.

• Deterministic. The same address always maps to the same home — no randomness, no state dependence. A line has one home for its whole life.
• Total. Every address maps to some home; no address is unhomed. The partition covers the entire space.
• Identical everywhere. Every requester uses the same function. Requester A and requester B must send the same line's transactions to the same home.
• One home per line. The consequence: each line has exactly one directory tracking it and one serialization point — the properties coherence needs (Chapters 7.6, 10.3), now distributed.

The point to carry:

Distribution works because the address-to-home map turns "which directory tracks this line?" into a pure function of the address that everyone evaluates the same way. That single agreement is what preserves the guarantees a centralised directory had for free: one tracker, one serialization point, one source of truth per line — just spread across many homes by address. Break the agreement — let the map differ across requesters, be non-deterministic, or leave a gap — and a line loses its single home, and with it every coherence property that depended on there being exactly one.

10. Reading the Mapping — a line's home

Follow two requesters accessing the same line.

1. RN0 accesses line at address A. It computes the home: home(A) → HN1. It sends the transaction to HN1.
2. HN1 tracks it. HN1's directory records the line; HN1 is its serialization point.
3. RN2 accesses the same line A. It computes home(A) → HN1 — the same home, because the function is canonical.
4. One directory, one order. Both requesters reached HN1, which serializes and tracks the line. Coherence holds — there is exactly one home for A.
5. Spread. Meanwhile, line B maps to HN0 and line C to HN2 — different homes, parallel traffic, no bottleneck.

The line at A had one home because both requesters computed the same mapping. Had RN2 computed home(A) → HN2 instead, the line would be tracked at both HN1 and HN2 — the DebugLab.

11. RTL / Hardware View — an address-to-home function

The mapping is a small deterministic function: hash or slice the address into a home ID. Every requester instantiates the same function. Representative.

// Representative address-to-home mapping (educational).
// A deterministic, total function from a line address to its home node. EVERY
// requester must use this SAME function, so a given line always reaches the same
// home and directory. Here: hash the address bits and reduce modulo the home count.
module chi_addr_to_home #(parameter NUM_HN = 4, parameter AW = 32) (
  input  logic [AW-1:0]           line_addr,   // line address (cache-line granular)
  output logic [$clog2(NUM_HN)-1:0] home_id,   // the line's home node
  output logic                    valid         // the mapping produced a real home
);
  // A simple canonical hash: fold some address bits, reduce mod NUM_HN.
  // The exact function is free; that ALL requesters use the SAME one is the rule.
  logic [$clog2(NUM_HN)-1:0] h;
  assign h = line_addr[$clog2(NUM_HN)+5:6] % NUM_HN; // bits above the line offset
 
  assign home_id = h;
  // Total: every address maps to a valid home in range.
  assign valid   = (h < NUM_HN);
endmodule

The same behavior in Verilog-2001:

// Representative address-to-home mapping (Verilog-2001).
module chi_addr_to_home #(parameter NUM_HN = 4, parameter AW = 32, parameter HW = 2) (
  input  [AW-1:0] line_addr,
  output [HW-1:0] home_id,
  output          valid
);
  wire [HW-1:0] h = line_addr[HW+5:6] % NUM_HN;
  assign home_id = h;
  assign valid   = (h < NUM_HN);
endmodule

And in VHDL:

-- Representative address-to-home mapping (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity chi_addr_to_home is
  generic ( NUM_HN : integer := 4; AW : integer := 32; HW : integer := 2 );
  port (
    line_addr : in  std_logic_vector(AW-1 downto 0);
    home_id   : out std_logic_vector(HW-1 downto 0);
    valid     : out std_logic
  );
end entity;
 
architecture rtl of chi_addr_to_home is
  signal h : integer range 0 to NUM_HN-1;
begin
  h <= to_integer(unsigned(line_addr(HW+5 downto 6))) mod NUM_HN;
  home_id <= std_logic_vector(to_unsigned(h, HW));
  valid   <= '1';  -- total: every address maps to a valid home
end architecture;

All three are a pure function of the address — the same address always yields the same home. Instantiated identically at every requester, they guarantee one home per line. The DebugLab shows the split when two requesters use different functions.

12. Verification View — one home per address, everywhere

The properties that keep the distribution sound: the mapping is deterministic and total, and two requesters agree.

// Bind to chi_addr_to_home (or two instances a, b for two requesters).
// 1. The mapping is total — every address produces a valid home in range.
property p_total;
  @(*) valid && (home_id < NUM_HN[$clog2(NUM_HN)-1:0]);
endproperty
 
// 2. Deterministic: the same address always maps to the same home
//    (checked by holding line_addr and observing home_id unchanged).
 
// 3. Two requesters (two instances) agree on the home for any address.
//    a_home_id == b_home_id when a_line_addr == b_line_addr.
property p_requesters_agree;
  @(*) (a_line_addr == b_line_addr) |-> (a_home_id == b_home_id);
endproperty

The system point, beyond the checks:

The distributed directory is a lesson in replacing a shared structure with a shared function. Centralising put the agreement in a physical place — one directory everyone visited. Distributing removes the place but must keep the agreement, and it does so by making "which home?" a computation every requester performs identically. The correctness therefore migrates from "is there one directory?" to "does everyone compute the same home?" — and the latter is guaranteed not by hardware coincidence but by every agent instantiating the same deterministic, total mapping. The bottleneck was a structure; its replacement is a shared truth about a function.

• What it proves: the mapping is total and (across instances) agreed for equal addresses.
• What it does not prove: the function is actually identical across the chip — that is a design/integration guarantee.
• Bug signature: two requesters computing different homes for the same address — a split line.

13. Testbench — the mapping is deterministic and agreed

Maps several addresses and checks determinism and two-requester agreement.

module tb_chi_addr_to_home;
  localparam NUM_HN = 4, AW = 32, HW = 2;
  logic [AW-1:0] addr;
  logic [HW-1:0] home_a, home_b;
  logic valid_a, valid_b;
  int errors = 0;
 
  // Two requesters use the SAME function.
  chi_addr_to_home #(.NUM_HN(NUM_HN), .AW(AW), .HW(HW)) reqA (.line_addr(addr), .home_id(home_a), .valid(valid_a));
  chi_addr_to_home #(.NUM_HN(NUM_HN), .AW(AW), .HW(HW)) reqB (.line_addr(addr), .home_id(home_b), .valid(valid_b));
 
  task automatic check(input logic [AW-1:0] a, input string name);
    addr = a; #1;
    if (!valid_a || home_a !== home_b) begin
      errors++; $display("FAIL %s: A=%0d B=%0d", name, home_a, home_b);
    end else $display("PASS %s: home=%0d (both agree)", name, home_a);
  endtask
 
  initial begin
    check(32'h0000_0040, "addr 0x40");
    check(32'h0000_0080, "addr 0x80");
    check(32'hDEAD_BE40, "addr 0xDEADBE40");
    // Determinism: same address twice -> same home.
    addr = 32'h0000_0040; #1; home_a = home_a; // read
    check(32'h0000_0040, "addr 0x40 again (deterministic)");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS addr 0x40: home=1 (both agree)
PASS addr 0x80: home=2 (both agree)
PASS addr 0xDEADBE40: home=1 (both agree)
PASS addr 0x40 again (deterministic): home=1 (both agree)
ALL TESTS PASSED

14. DebugLab — requesters disagree on a line's home

line at address A
RN0: home(A) -> HN1   (RN0's mapping)
RN2: home(A) -> HN2   (RN2's DIFFERENT mapping)
HN1 directory tracks A for RN0's traffic
HN2 directory tracks A for RN2's traffic  -- two trackers, never reconciled
RN0 writes A at HN1 -> HN1 invalidates what IT tracks (not RN2's copy)
RN2 reads A at HN2 -> old value  -> STALE (coherence split)

15. Common Mistakes

• Inconsistent mappings across requesters. Assumption: any hash works locally. Bug: coherence split (the DebugLab). Prevention: one canonical function everywhere.
• A non-deterministic mapping. Assumption: routing can vary. Bug: a line with no fixed home. Prevention: deterministic — one home per line for life.
• A partial mapping. Assumption: some addresses are unhomed. Bug: untracked lines. Prevention: total — every address maps to a home.
• Mismatched home count. Assumption: the map ignores topology. Bug: an address maps out of range. Prevention: the map matches the actual homes.
• Assuming distribution changes coherence. Assumption: many homes weaken guarantees. Bug: mis-modeled behavior. Prevention: one home per line preserves the guarantees.
• Forgetting the per-home serialization. Assumption: distribution removes ordering. Bug: mis-ordering. Prevention: each home still serializes its slice (Chapter 7.6).

16. Engineering Checklist

• Partition the directory across home nodes, each tracking its slice.
• Map every line's address to exactly one home.
• Use one canonical address-to-home function — deterministic, total.
• Ensure every requester computes the same home for a given address.
• Match the mapping to the actual home count and topology.
• Keep each home the single serialization point for its slice.

17. Key Takeaways

• The distributed directory partitions the record across home nodes, removing the centralised bottleneck.
• Each home owns a slice of the address space and tracks only its lines.
• A line's address maps to exactly one home — its sole directory and serialization point.
• The mapping must be canonical: deterministic, total, and identical at every requester.
• If requesters disagree, a line is tracked by two directories that never reconcile — coherence splits.
• Partition by address, map canonically; the model here is representative.

18. Quick Revision

Distributed directory. To remove the centralised directory's bottleneck, the record is partitioned across many home nodes — each owns a slice of the address space and tracks only the lines in it. A line's address maps, by a fixed function, to exactly one home, which is its sole directory and serialization point; different addresses map to different homes, so coherence traffic spreads and no single structure is overwhelmed. The distribution keeps the targeting of a directory while gaining scaling. Its one load-bearing rule: the address-to-home mapping must be canonical — deterministic (one home per line for life), total (every address homed), and identical at every requester. If two requesters compute different homes for the same line, it is tracked by two directories that never reconcile: a write at one home misses the copies the other governs, and a reader sees stale data — a coherence split. One canonical map, one home per line. Representative model; 11.3 covers how each slice encodes its sharers.

Coming Next

Chapter 11.3 — Sharer Tracking. A distributed directory slice still has to record which caches share each line — and how it encodes that set is a storage-versus-precision trade. Chapter 11.3 covers sharer tracking — the full bit-vector (one bit per cache, exact but O(N) storage) versus coarse-grain encodings (one bit per group, cheaper but over-approximate) — and the rule that a sharer encoding may over-approximate safely but must never under-approximate, or a write misses a holder.