The CHI Directory Model

Module 11 · Chapter 11.6 · Directory-Based Coherency

Project thread — 11.1–11.5 detailed directory structures. This chapter draws the line between what CHI specifies and what it leaves open, closing the module. Module 12 turns to ordering and consistency.

1. Learning Outcomes

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

• Distinguish what CHI specifies (protocol, states, ordering, coherence) from what it leaves implementation-defined (directory structure).
• State the coherence guarantee — single-writer-multiple-reader (SWMR) — every directory must uphold.
• List directory choices CHI does not fix — bit-vector vs coarse, inclusive vs not, size, filtering.
• Explain why an agent must rely only on specified behaviour.
• Diagnose a portability bug from depending on an implementation-defined directory detail.
• Implement a representative SWMR check in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

The previous chapters could give the impression that CHI is the directory — bit-vectors, owner IDs, sizing. This chapter corrects that: CHI specifies the protocol, not the directory. It defines what messages mean, what states exist, how transactions order, and the coherence guarantee they uphold — and it leaves the directory's structure to the implementer. Understanding this line is what separates using CHI correctly from over-fitting to one design.

The practical stakes are portability and interoperability. A CHI agent that works against one implementation may fail against another if it depends on a directory behaviour CHI never promised — a particular snoop count, an inclusive directory, a precise sharer set. Compliance means upholding the specified behaviour, and using CHI means depending only on it. This chapter teaches the discipline of building to the specification, not to an implementation — the difference between an agent that interoperates and one that quietly assumes.

3. Key Terms

4. Previous Chapter Connection

Chapters 11.1–11.5 built directories with specific structures — centralised or distributed, bit-vector or coarse, sized this way or that. It would be easy to conclude those are CHI. This chapter draws the boundary: those were implementation choices, and CHI specifies none of them.

What CHI does specify is what all those directories had in common — the coherence guarantee they each upheld. The centralised directory, the distributed one, the bit-vector, the coarse encoding all kept the same invariant: a read returns the latest write, with a single writer at a time. That invariant, and the protocol that maintains it, is CHI; the directory is how an implementation chooses to keep it. This chapter names that separation explicitly — and the discipline it demands: build to the invariant, not to one directory.

5. Core Concept — CHI specifies the protocol, not the directory

CHI defines the observable protocol and the coherence guarantee; the directory structure that upholds them is implementation-defined.

• Specified: the protocol. CHI fixes the messages (requests, snoops, responses), the cache states (Module 10), the ordering rules (Module 7), and the coherence guarantee — single-writer-multiple-reader and the data-value invariant.
• Not specified: the directory. How an implementation tracks coherence — bit-vector or coarse (Chapter 11.3), inclusive or non-inclusive, centralised or distributed (Chapter 11.2), its size and snoop-filtering — is a free choice.
• The only requirement: uphold the guarantee. Any directory is compliant as long as it maintains CHI's specified behaviour. Two very different directories are both correct if both keep SWMR.
• The discipline: depend only on the specified. An agent must rely on specified behaviour — messages, states, ordering, coherence — and never on an implementation-defined directory detail, which another compliant design may not share.

The synthesis:

CHI is a protocol specification: it defines the messages, states, ordering, and the coherence guarantee (SWMR), and requires every implementation to uphold them. It does not specify the directory structure — bit-vector or coarse, inclusive or not, its size or filtering are implementation-defined, free so long as the guarantee holds. The discipline that follows: rely only on specified behaviour, never on a directory detail, because what is true of one compliant implementation may be false of another.

6. Engineering Mental Model — a building code, not a blueprint

CHI is a building code, not a blueprint.

• A building code specifies requirements: the structure must bear a certain load, exits must be reachable, wiring must be safe. It says what must be true, not how to build it.
• A blueprint specifies a particular building: these walls, this beam, that staircase. Two code-compliant buildings can have entirely different blueprints.
• CHI is the code: it specifies the coherence guarantees and the protocol every agent must obey. The directory is part of the blueprint — one implementation's way of meeting the code.
• A tenant who wired an appliance assuming "the staircase is always on the north side" — true of their building but not the code — would be surprised in the next building. Depending on a blueprint detail rather than a code requirement is exactly the portability bug.

Build to the code (the specification), and your fixture works in every compliant building. Build to one blueprint (one directory's behaviour), and it works only there.

7. Engineering Diagram — specified above, implementation-defined below

The top node is the specified contract every agent may rely on; the bottom row is implementation-defined — each a free choice ("free") an implementer makes. The arrows point down: the specification permits many directories, but an agent must not reach down and depend on which one.

8. What CHI Specifies versus Leaves Open

The boundary, itemized.

The rule to carry: everything an agent interoperates through — messages, states, ordering, the coherence guarantee — is specified; everything about how the directory is built is implementation-defined. The one to watch is the last row: the exact set of snoops or their count is a directory detail (it may over-approximate, Chapter 11.3), so an agent must tolerate any compliant snoop pattern, not assume a specific one.

9. The Coherence Guarantee Every Directory Must Uphold

The specified invariant — the thing all directories share — deserves its own statement.

• Single-writer-multiple-reader (SWMR). For any line, at any time, either one cache may write it (and no others hold it) or any number may read it (and none writes) — never both.
• Data-value invariant. A read returns the value of the latest write in the line's coherence order. Reads and writes appear in a single consistent order per line.
• Directory-agnostic. These hold regardless of the directory's structure — a bit-vector, a coarse directory, an inclusive or non-inclusive one all keep the same guarantee.
• This is what CHI specifies. The protocol exists to uphold SWMR and the data-value invariant; the directory is one implementation's machinery for doing so.

The point to carry:

The coherence guarantee is the fixed point of the whole module: every directory structure of Chapters 11.1–11.5 was a different way of maintaining the same SWMR and data-value invariant. That is what makes them all CHI-compliant despite their differences — and what an agent may rely on. So the correct mental model is that CHI specifies an invariant and a protocol to keep it, and delegates the how to the implementation. Build against the invariant and you are portable across every compliant directory; build against a directory and you are portable across none but that one.

10. Reading the Boundary — what to rely on

Decide what an agent may depend on.

1. "A snoop will invalidate the copies." Specified — the protocol guarantees the coherence effect. Rely on it.
2. "Exactly two snoops will be sent." Implementation-defined — the snoop count depends on the directory's encoding (coarse may over-approximate). Do not rely on it.
3. "After a ReadUnique, no other cache holds the line." Specified — SWMR guarantees it. Rely on it.
4. "The directory tracks every line I cache." Implementation-defined — inclusivity is a free choice. Do not rely on it.
5. "A read returns the latest write." Specified — the data-value invariant. Rely on it.

Items 1, 3, 5 are the coherence guarantee — safe to depend on. Items 2, 4 are directory internals — depending on them is a portability bug, because a different compliant implementation may behave otherwise.

11. RTL / Hardware View — the SWMR invariant

What every compliant directory must uphold reduces to one checkable invariant: single-writer-multiple-reader. The directory structure is free; this must always hold. Representative.

// Representative single-writer-multiple-reader (SWMR) check (educational).
// This is what CHI SPECIFIES and every directory implementation must uphold,
// regardless of its structure: at most one writer, and if there is a writer, no
// readers. The directory (bit-vector, coarse, inclusive or not) is free as long
// as swmr_ok stays true.
module chi_swmr_check #(parameter W = 8) (
  input  logic [W-1:0] num_writers,  // caches holding the line WRITABLE (UD/UC-to-write)
  input  logic [W-1:0] num_readers,  // caches holding a read-only copy (SC)
  output logic         swmr_ok,      // the SWMR invariant holds
  output logic         compliant     // the (any-structure) directory is coherent
);
  // At most one writer; and a writer excludes readers.
  logic single_writer, writer_excludes_readers;
  assign single_writer           = (num_writers <= 1);
  assign writer_excludes_readers = (num_writers == 0) || (num_readers == 0);
  assign swmr_ok   = single_writer && writer_excludes_readers;
  // Compliance is upholding the specified invariant -- independent of directory structure.
  assign compliant = swmr_ok;
endmodule

The same behavior in Verilog-2001:

// Representative SWMR check (Verilog-2001).
module chi_swmr_check #(parameter W = 8) (
  input  [W-1:0] num_writers,
  input  [W-1:0] num_readers,
  output         swmr_ok,
  output         compliant
);
  wire single_writer           = (num_writers <= 1);
  wire writer_excludes_readers = (num_writers == 0) || (num_readers == 0);
  assign swmr_ok   = single_writer && writer_excludes_readers;
  assign compliant = swmr_ok;
endmodule

And in VHDL:

-- Representative SWMR check (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity chi_swmr_check is
  generic ( W : integer := 8 );
  port (
    num_writers : in  unsigned(W-1 downto 0);
    num_readers : in  unsigned(W-1 downto 0);
    swmr_ok     : out std_logic;
    compliant   : out std_logic
  );
end entity;
 
architecture rtl of chi_swmr_check is
  signal sw, wer, ok : std_logic;
begin
  sw  <= '1' when num_writers <= 1 else '0';
  wer <= '1' when (num_writers = 0) or (num_readers = 0) else '0';
  ok  <= sw and wer;
  swmr_ok   <= ok;
  compliant <= ok;
end architecture;

All three check the specified invariant — at most one writer, and a writer excludes readers — that every compliant directory must keep, whatever its structure. The DebugLab shows the bug of relying on a directory detail this invariant does not promise.

12. Verification View — verify the specified invariant, not the structure

The properties are the specified guarantee, holding regardless of the directory.

// Bind to chi_swmr_check (and, in practice, to the coherence controller).
// 1. At most one writer for any line.
property p_single_writer;
  @(posedge clk) num_writers <= 1;
endproperty
 
// 2. A writer excludes all readers (single-writer-multiple-reader).
property p_writer_excludes_readers;
  @(posedge clk) (num_writers == 1) |-> (num_readers == 0);
endproperty
 
// 3. Compliance is exactly upholding SWMR — independent of directory structure.
property p_compliance_is_swmr;
  @(posedge clk) compliant == swmr_ok;
endproperty

The system point, beyond the checks:

A specification's real content is the line it draws between what it promises and what it delegates, and CHI draws that line at the directory. Verifying a CHI agent therefore means verifying the specified behaviour — SWMR, the data-value invariant, the message and ordering rules — and not verifying a particular directory structure, because the structure is not the contract. The corollary for design is stronger than a coding tip: an agent that depends on a directory detail has, in effect, verified against a stricter specification than CHI actually offers, and will fail the moment it meets a compliant implementation that made the detail differently. Portability is the discipline of proving your agent correct against the weakest behaviour CHI guarantees — SWMR — not the strongest a given directory happens to provide.

• What it proves: SWMR holds and compliance equals SWMR — structure-independent.
• What it does not prove: any particular directory structure — which CHI does not require.
• Bug signature: an agent whose correctness depends on a directory property beyond SWMR.

13. Testbench — SWMR holds; structure does not matter

Drives writer/reader combinations and checks SWMR, independent of any directory structure.

module tb_chi_swmr_check;
  localparam W = 8;
  logic [W-1:0] num_writers, num_readers;
  logic swmr_ok, compliant;
  int errors = 0;
 
  chi_swmr_check #(.W(W)) dut (.*);
 
  task automatic check(input logic [W-1:0] nw, nr, input logic exp_ok, input string name);
    num_writers = nw; num_readers = nr; #1;
    if (swmr_ok !== exp_ok || compliant !== exp_ok) begin
      errors++; $display("FAIL %s: ok=%0b", name, swmr_ok);
    end else $display("PASS %s: ok=%0b", name, swmr_ok);
  endtask
 
  initial begin
    check(8'd0, 8'd5, 1'b1, "0 writers, 5 readers -> SWMR ok (multi-reader)");
    check(8'd1, 8'd0, 1'b1, "1 writer, 0 readers -> SWMR ok (single-writer)");
    check(8'd1, 8'd3, 1'b0, "1 writer, 3 readers -> SWMR VIOLATED");
    check(8'd2, 8'd0, 1'b0, "2 writers -> SWMR VIOLATED");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS 0 writers, 5 readers -> SWMR ok (multi-reader): ok=1
PASS 1 writer, 0 readers -> SWMR ok (single-writer): ok=1
PASS 1 writer, 3 readers -> SWMR VIOLATED: ok=0
PASS 2 writers -> SWMR VIOLATED: ok=0
ALL TESTS PASSED

14. DebugLab — relying on an implementation-defined directory detail

agent assumes: "the directory is inclusive -> I am always snooped for lines I cache"
implementation A: inclusive directory  -> assumption holds -> agent works
implementation B: NON-inclusive (CHI-compliant) -> not always snooped as assumed
  -> agent's internal logic that relied on the assumption misbehaves
both A and B uphold SWMR (both are compliant); the agent over-assumed

15. Common Mistakes

• Assuming an inclusive directory. Assumption: the directory tracks all my lines. Bug: fails on non-inclusive (the DebugLab). Prevention: do not assume inclusivity.
• Relying on an exact snoop count. Assumption: a fixed number of snoops. Bug: coarse over-approximation breaks it. Prevention: tolerate any compliant pattern.
• Depending on a snoop order. Assumption: a particular order. Bug: another design orders differently. Prevention: rely on ordering CHI specifies, not directory-induced order.
• Treating the directory as part of the spec. Assumption: structure is standardized. Bug: over-fitting. Prevention: structure is implementation-defined.
• Verifying the structure, not the invariant. Assumption: check the bit-vector. Bug: misses the real contract. Prevention: verify SWMR.
• Building to one implementation. Assumption: my interconnect is CHI. Bug: no portability. Prevention: build to the specification.

16. Engineering Checklist

• Rely only on CHI-specified behaviour — messages, states, ordering, SWMR.
• Treat the directory structure as implementation-defined — a black box.
• Make no assumption about inclusivity, size, encoding, or exact snoop counts.
• Tolerate any compliant snoop pattern, including over-approximation.
• Verify the coherence invariant (SWMR), not a particular directory.
• Build for portability — correct against the weakest behaviour CHI guarantees.

17. Key Takeaways

• CHI specifies the protocol — messages, states, ordering, and the SWMR coherence guarantee.
• CHI does not specify the directory structure — bit-vector, coarse, inclusive or not, size are implementation-defined.
• Any directory is compliant as long as it upholds the specified coherence guarantee.
• An agent must rely only on specified behaviour, never on an implementation-defined directory detail.
• Depending on a directory detail is a portability bug — it may be false on another compliant design.
• Build to the invariant, not the directory; the model here is representative.

18. Quick Revision

The CHI directory model. CHI is a protocol specification: it defines the messages, the cache states, the ordering rules, and the coherence guarantee — single-writer-multiple-reader (SWMR) and the data-value invariant (a read returns the latest write). It does not specify the directory structure: whether the directory is a full bit-vector or coarse-grain, inclusive or non-inclusive, centralised or distributed, its size and snoop-filtering are all implementation-defined — free choices, correct as long as they uphold the specified coherence guarantee. Two very different directories are both CHI-compliant if both keep SWMR. The discipline that follows is portability: rely only on specified behaviour — the coherence effect, the states, the ordering — and never on an implementation-defined directory detail such as inclusivity, an exact snoop count, or a snoop order, because a detail true of one compliant implementation may be false of another. Build to the invariant CHI guarantees, not to one directory. Representative model; Module 12 turns to ordering and consistency.

Coming Next

Chapter 12.1 — Ordering Guarantees. The directory kept coherence per line; Module 12 widens the lens to ordering across accesses and lines. Chapter 12.1 opens the ordering and consistency module — what CHI guarantees about the order in which accesses appear, the difference between coherence (per-line) and consistency (across lines), and the ordering rules that let software reason about a multi-core system's memory. It is the bridge from coherence to the memory model built on top of it.