Directory Scalability Benefits

Module 11 · Chapter 11.5 · Directory-Based Coherency

Project thread — 11.2–11.4 built the directory's structure and storage. This chapter quantifies why it pays. 11.6 covers what CHI does and does not specify about it.

1. Learning Outcomes

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

• State the trade — directories spend storage to save snoop bandwidth.
• Compare broadcast snoop traffic (O(N)) with directory-targeted traffic (O(sharers)).
• Explain why the trade improves as core count rises.
• State why the directory must be sized to the working set.
• Diagnose how under-provisioning the directory repays the saved storage in bandwidth.
• Implement a representative scalability model in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

This is the chapter that justifies the whole module. Directories cost real silicon — storage for every tracked line — and a natural instinct is to minimize that storage. This chapter shows why that instinct is exactly backwards: the storage is not overhead to be shaved but the mechanism that buys the far more valuable resource, snoop bandwidth. Understanding the trade is understanding why every large coherent system pays for a directory.

The argument is quantitative and it scales. Broadcast traffic grows with the number of cores; directory traffic grows with the (usually small) number of sharers. So the more cores you have, the more lopsided the trade becomes in the directory's favour — until, at scale, broadcast is simply impossible and the directory is the only option. And the corollary matters for design: a directory too small to hold the working set stops targeting and falls back to broadcast, giving back the bandwidth it was built to save. This chapter is the case for the directory, and the warning against skimping on it.

3. Key Terms

4. Previous Chapter Connection

Chapter 11.1 said a directory enables targeted snoops instead of broadcast; Chapters 11.3 and 11.4 showed the storage that targeting costs — bit-vectors, coarse groups, owner IDs. This chapter puts a number on the benefit that storage buys.

The pieces are all in place: broadcast asks every cache (Chapter 11.1); the directory records who holds each line (Chapters 11.3, 11.4) so it can ask only them. This chapter compares the two as resource trades — bandwidth versus storage — and shows how the comparison shifts with core count. It also closes the loop on capacity (Chapter 11.1's back-invalidation): a directory sized below the working set cannot sustain targeting, so the trade only pays when the storage is provisioned for the workload.

5. Core Concept — pay storage, save bandwidth, and the trade scales

Coherence tracking spends one of two resources, and the directory chooses storage over bandwidth — a choice that improves with scale.

• Broadcast spends bandwidth. Without a record, every coherence transaction must ask all N caches — snoop traffic of O(N) per transaction. Multiply by the transaction rate, and the traffic grows with the core count.
• The directory spends storage. It pays memory (about lines × N bits for a bit-vector) to record who holds each line, and in return snoops only the holders — O(sharers) per transaction, usually a small number independent of N.
• The trade scales with N. As cores rise, broadcast traffic grows while targeted traffic does not — so the directory's advantage widens. At high core counts broadcast becomes infeasible; the directory is the only option.
• The storage is the point. The saving depends on the directory actually covering the working set. Under-provision it and it evicts entries, falls back to broadcast or back-invalidation, and the bandwidth returns.

The synthesis:

Directories trade storage for snoop bandwidth: pay directory memory (~lines × N) to snoop only the holders — O(sharers) — instead of broadcasting to all N caches — O(N). Because broadcast traffic grows with core count while targeted traffic does not, the trade goes overwhelmingly to the directory as systems scale. But the storage is the mechanism — a directory too small for the working set thrashes back to broadcast, repaying the saved storage in bandwidth.

6. Engineering Mental Model — a phone tree versus a directory

Two ways to reach the people who borrowed a document, as the office grows.

• Broadcast is a phone tree that calls everyone. To find all borrowers, you call every employee and ask. In a small office, fine. In a company of thousands, the call volume is crippling — and it grows with every hire.
• The directory is a contact list of actual borrowers. You keep a small list of exactly who has the document, and call only them — a handful of calls, no matter how large the company grows.
• The list costs filing space (storage) to maintain. But that space buys you out of the ever-growing call volume (bandwidth), and the bigger the company, the better that bargain looks.
• The catch: if the filing cabinet is too small to hold the lists, you lose track and fall back to calling everyone — the call volume returns. The cabinet must be big enough for the active documents.

Filing space traded for call volume, a bargain that improves with size — as long as the cabinet is big enough. That is the directory's scaling case.

7. Engineering Diagram — broadcast versus targeted

Broadcast snoops all N; the directory snoops the holders. The directory pays storage (about lines × N) to buy the bandwidth saving — and because N grows while the sharer count does not, the win widens with every added core.

8. The Resource Trade, Quantified

The two schemes as resource costs.

The rule to carry: broadcast is free in storage but O(N) in bandwidth; the directory is O(lines × N) in storage but O(sharers) in bandwidth. Since sharer counts stay small while N grows, the directory converts a bandwidth cost that worsens with scale into a storage cost that is fixed by the working set. Bandwidth is the resource that runs out first at scale — which is why the trade favours the directory more and more as cores rise.

9. Sizing the Directory — the storage is the mechanism

The corollary — that under-provisioning defeats the purpose — deserves its own statement.

• Targeting requires coverage. The directory can target only the lines it tracks. A line whose entry it does not hold must be broadcast (Chapter 11.1) or back-invalidated.
• Under-provisioning forces fallback. A directory smaller than the working set constantly evicts entries — and each eviction means a back-invalidation or a broadcast, re-spending the bandwidth the directory was meant to save.
• Thrashing can be worse than broadcast. Under heavy pressure, the eviction/back-invalidation churn adds its own traffic on top, so an under-sized directory can perform worse than plain broadcast.
• Size to the working set. The directory pays off only when it covers the actively cached lines. The storage is not overhead to trim; it is the mechanism that buys the bandwidth.

The point to carry:

The directory's benefit is conditional on its storage. Targeting is a saving the directory can only deliver for lines it actually tracks, so the storage is not a tax on the mechanism — it is the mechanism. Shrink it below the working set and you do not get a cheaper directory; you get a directory that keeps falling back to the broadcast it was built to replace, plus the overhead of thrashing. The correct framing is not "how little storage can we spend?" but "how much storage covers the working set?" — because only a covered working set turns O(N) broadcast into O(sharers) targeting.

10. Reading the Trade — broadcast versus a sized directory

Compare the snoop cost of one transaction, 64 caches, a line shared by 2.

1. Broadcast. With no directory, the transaction snoops all 64 caches to be safe — 64 snoops, of which 62 reach caches that do not hold the line.
2. Directory, sized. The directory holds the line's entry: sharers = 2. The home snoops only those 2 — a 32× reduction in snoops for this transaction.
3. Saving. N − sharers = 62 snoops avoided, this transaction alone. Multiply by the transaction rate: the bandwidth saved is enormous.
4. Directory, under-sized. If the directory does not hold the entry (evicted under capacity pressure), the home must broadcast — back to 64 snoops — plus the eviction/back-invalidation traffic. The saving is lost.
5. The lesson. The 32× win exists only while the directory covers the line. Provisioned, the directory crushes broadcast; under-provisioned, it reverts to it.

Step 2 is the directory's scaling win; step 4 is what under-provisioning throws away. The storage in the directory is what stands between them.

11. RTL / Hardware View — a scalability model

The trade reduces to a few counts: broadcast snoops (N), targeted snoops (sharers), and whether the directory is provisioned enough to actually target. Representative.

// Representative directory scalability model (educational).
// Broadcast snoops all N caches; a directory snoops only the sharers. The saving is
// N - sharers PER transaction -- but only if the directory is PROVISIONED to cover
// the working set. Under-provisioned, it falls back to broadcast (saving lost).
module chi_scalability #(parameter W = 8) (
  input  logic [W-1:0] num_caches,    // N
  input  logic [W-1:0] num_sharers,   // holders of this line
  input  logic [W-1:0] dir_entries,   // directory capacity (entries)
  input  logic [W-1:0] working_set,   // actively cached lines
  output logic [W-1:0] broadcast_snoops,  // N
  output logic [W-1:0] targeted_snoops,   // sharers
  output logic         provisioned,        // directory covers the working set
  output logic [W-1:0] effective_snoops,   // what actually happens
  output logic [W-1:0] snoops_saved         // N - effective
);
  assign broadcast_snoops = num_caches;
  assign targeted_snoops  = num_sharers;
  // Provisioned only if the directory can hold the working set.
  assign provisioned      = (dir_entries >= working_set);
  // A provisioned directory targets; otherwise it falls back to broadcast.
  assign effective_snoops = provisioned ? num_sharers : num_caches;
  assign snoops_saved     = broadcast_snoops - effective_snoops;
endmodule

The same behavior in Verilog-2001:

// Representative directory scalability model (Verilog-2001).
module chi_scalability #(parameter W = 8) (
  input  [W-1:0] num_caches, num_sharers, dir_entries, working_set,
  output [W-1:0] broadcast_snoops, targeted_snoops, effective_snoops, snoops_saved,
  output         provisioned
);
  assign broadcast_snoops = num_caches;
  assign targeted_snoops  = num_sharers;
  assign provisioned      = (dir_entries >= working_set);
  assign effective_snoops = provisioned ? num_sharers : num_caches;
  assign snoops_saved     = broadcast_snoops - effective_snoops;
endmodule

And in VHDL:

-- Representative directory scalability model (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity chi_scalability is
  generic ( W : integer := 8 );
  port (
    num_caches       : in  unsigned(W-1 downto 0);
    num_sharers      : in  unsigned(W-1 downto 0);
    dir_entries      : in  unsigned(W-1 downto 0);
    working_set      : in  unsigned(W-1 downto 0);
    broadcast_snoops : out unsigned(W-1 downto 0);
    targeted_snoops  : out unsigned(W-1 downto 0);
    provisioned      : out std_logic;
    effective_snoops : out unsigned(W-1 downto 0);
    snoops_saved     : out unsigned(W-1 downto 0)
  );
end entity;
 
architecture rtl of chi_scalability is
  signal prov : std_logic;
  signal eff  : unsigned(W-1 downto 0);
begin
  prov <= '1' when dir_entries >= working_set else '0';
  eff  <= num_sharers when prov = '1' else num_caches;
  broadcast_snoops <= num_caches;
  targeted_snoops  <= num_sharers;
  provisioned      <= prov;
  effective_snoops <= eff;
  snoops_saved     <= num_caches - eff;
end architecture;

All three show the saving — N − sharers — realized only when the directory is provisioned; under-provisioned, effective_snoops reverts to broadcast and the saving is zero. The DebugLab is the under-provisioned case in practice.

12. Verification View — the saving is conditional on provisioning

The properties that capture the trade: targeting saves snoops, but only when provisioned.

// Bind to chi_scalability.
// 1. A provisioned directory realizes the targeted saving.
property p_provisioned_saves;
  @(*) (provisioned && (num_sharers < num_caches))
       |-> (effective_snoops == num_sharers && snoops_saved > 0);
endproperty
 
// 2. An under-provisioned directory falls back to broadcast (no saving).
property p_underprovisioned_broadcasts;
  @(*) (!provisioned) |-> (effective_snoops == num_caches && snoops_saved == 0);
endproperty
 
// 3. Effective snoops never exceed broadcast (targeting is never worse per-txn).
property p_never_worse;
  @(*) effective_snoops <= broadcast_snoops;
endproperty

The system point, beyond the checks:

The directory is the clearest case in the protocol of a resource conversion: it does not make coherence cheaper in the abstract, it moves the cost from a resource that scales badly (snoop bandwidth, O(N)) to one that scales well (storage, fixed by the working set). Whether that conversion is a win depends entirely on the relative scarcity of the two resources — and at high core counts bandwidth is scarce and storage is affordable, so the conversion is overwhelmingly favourable. This is why the directory is not an optimization to be tuned away but the enabling structure of scale. And it is why the storage must be sized to the working set: the conversion only happens for lines the directory covers, so an under-covered directory has simply failed to perform the conversion, paying storage while still spending the bandwidth.

• What it proves: provisioned directories realize the saving; under-provisioned ones broadcast; targeting is never worse.
• What it does not prove: the actual sharer distribution or workload — those are system parameters.
• Bug signature: an under-provisioned directory (dir_entries below the working set) spending broadcast bandwidth despite its storage.

13. Testbench — the trade across provisioning

Drives provisioned and under-provisioned directories and checks the effective snoops.

module tb_chi_scalability;
  localparam W = 8;
  logic [W-1:0] num_caches, num_sharers, dir_entries, working_set;
  logic [W-1:0] broadcast_snoops, targeted_snoops, effective_snoops, snoops_saved;
  logic provisioned;
  int errors = 0;
 
  chi_scalability #(.W(W)) dut (.*);
 
  task automatic check(input logic [W-1:0] nc, ns, de, ws,
                       input logic exp_prov, input logic [W-1:0] exp_eff, exp_saved, input string name);
    num_caches = nc; num_sharers = ns; dir_entries = de; working_set = ws; #1;
    if (provisioned !== exp_prov || effective_snoops !== exp_eff || snoops_saved !== exp_saved) begin
      errors++; $display("FAIL %s: prov=%0b eff=%0d saved=%0d", name, provisioned, effective_snoops, snoops_saved);
    end else $display("PASS %s: prov=%0b eff=%0d saved=%0d", name, provisioned, effective_snoops, snoops_saved);
  endtask
 
  initial begin
    // 64 caches, 2 sharers, directory covers the working set -> target, save 62.
    check(8'd64, 8'd2, 8'd128, 8'd100, 1'b1, 8'd2, 8'd62, "sized dir: target 2, save 62");
    // Same, but directory too small -> broadcast, save 0.
    check(8'd64, 8'd2, 8'd50, 8'd100, 1'b0, 8'd64, 8'd0, "under-sized: broadcast, save 0");
    // All caches share -> no saving even when sized.
    check(8'd8, 8'd8, 8'd128, 8'd100, 1'b1, 8'd8, 8'd0, "all share: no saving");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS sized dir: target 2, save 62: prov=1 eff=2 saved=62
PASS under-sized: broadcast, save 0: prov=0 eff=64 saved=0
PASS all share: no saving: prov=1 eff=8 saved=0
ALL TESTS PASSED

14. DebugLab — under-provisioning the directory to save area

working set = 100k actively cached lines
directory capacity = 20k entries   <-- far under the working set
-> constant capacity evictions
each eviction -> back-invalidate holders + line becomes untracked
untracked line -> BROADCAST on next access (all N caches)
snoop bandwidth ~ broadcast + eviction/back-invalidate churn
result: as bad as or worse than plain broadcast, and it does not scale

15. Common Mistakes

• Under-sizing to save area. Assumption: less storage is better. Bug: broadcast fallback / thrash (the DebugLab). Prevention: size to the working set.
• Choosing broadcast at scale. Assumption: broadcast is simpler. Bug: bandwidth explosion. Prevention: directories at high core counts.
• Treating storage as pure overhead. Assumption: minimize directory bits. Bug: the mechanism is gone. Prevention: the storage buys the bandwidth.
• Ignoring sharer distribution. Assumption: all lines are widely shared. Bug: mis-estimated saving. Prevention: most lines have few sharers.
• Forgetting the fallback cost. Assumption: eviction is free. Bug: back-invalidation churn. Prevention: cover the working set to avoid it.
• Assuming targeting is always cheaper per-txn than broadcast. Assumption: always fewer snoops. Bug: none when all caches share. Prevention: the win is O(sharers) < N, largest when sharing is narrow.

16. Engineering Checklist

• Frame coherence tracking as storage versus bandwidth.
• Prefer the directory — target the holders, not all N caches.
• Recognize the saving is N − sharers per transaction, largest when sharing is narrow.
• Size the directory to cover the working set.
• Avoid under-provisioning — it reverts to broadcast plus thrash.
• Treat directory storage as the mechanism, not overhead.

17. Key Takeaways

• Directories trade storage for snoop bandwidth — pay memory to snoop only the holders.
• Broadcast is O(N) per transaction; the directory is O(sharers) — usually far fewer.
• The trade improves with core count: broadcast traffic grows, targeted traffic does not.
• The storage is the mechanism — the saving exists only for lines the directory tracks.
• Under-provisioning the directory reverts to broadcast plus thrash, repaying the saved storage in bandwidth.
• Size to the working set; the storage is the point; the model here is representative.

18. Quick Revision

Directory scalability benefits. Directories trade storage for snoop bandwidth. Broadcast snooping asks every cache — O(N) snoops per transaction — so its traffic grows with the core count until the fabric is overwhelmed. A directory pays storage (about lines × N bits for a bit-vector) to record who holds each line, and in return snoops only the holders — O(sharers) per transaction, usually a small number independent of N — saving N − sharers snoops each time. Because broadcast traffic grows with cores while targeted traffic does not, the trade goes overwhelmingly to the directory as systems scale, until at high core counts broadcast is infeasible and the directory is the only option. The catch: the storage is the mechanism. A directory sized below the working set cannot track the active lines, so it evicts constantly and falls back to broadcast and back-invalidation — repaying the saved storage in the very bandwidth it was meant to avoid, sometimes worse than plain broadcast. Size the directory to cover the working set. Representative model; 11.6 covers what CHI does and does not specify about the directory.

Coming Next

Chapter 11.6 — The CHI Directory Model. This module built the directory in detail; the last chapter draws the line between what CHI specifies and what it leaves to the implementation. Chapter 11.6 covers the CHI directory model — that CHI defines the coherence protocol and its guarantees but not the directory's structure, so an implementation is free to choose bit-vector, coarse, inclusive or not — and why an agent must rely only on the specified behaviour, never on an implementation-defined directory detail.