Directory Efficiency

Module 15 · Chapter 15.5 · CHI Performance

Project thread — 15.4 sought ways to lower per-core memory demand. 15.5 makes the directory efficient; 15.6 uses the sharer set it provides.

1. Learning Outcomes

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

• Explain that the directory is a finite snoop filter with a hit rate.
• State that a directory hit gives a precise snoop; a miss forces a broadcast.
• Describe how a directory eviction of a live line forces a back-invalidation.
• Explain why an undersized directory collapses performance on two fronts.
• Diagnose the broadcast-and-churn storm from an undersized directory.
• Implement a representative directory-efficiency model in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

The directory's whole purpose is to make coherence precise — to snoop only the caches that actually hold a line, instead of broadcasting to all of them. But that precision is conditional: it works only when the directory has an entry for the line. The directory is a finite structure, so it can miss, and on a miss it knows nothing — forcing the home to fall back to a broadcast. The directory's hit rate is therefore the single number that decides whether coherence is cheap (precise) or expensive (broadcast).

Undersizing the directory is uniquely destructive because it fails on two fronts at once. A miss forces a broadcast — snoop traffic scales with the node count instead of the sharer count, flooding the snoop channel. And evicting a directory entry for a line still live in a cache forces a back-invalidation — the protocol must throw away a good cached line because it can no longer track it, shrinking the effective cache. So an undersized directory both floods the fabric and churns the caches. This chapter is the hit rate and why the directory must be sized to the aggregate cache footprint.

3. Key Terms

4. Previous Chapter Connection

This chapter is the performance view of the directory you built in Module 11. Chapter 11.1 introduced the directory and its back-invalidation (a directory eviction forcing a cache eviction); Chapter 11.5 covered directory scalability and coverage. Here those become a single metric — the hit rate — and its effect on snoop cost and cache retention.

It also connects to Chapter 15.4. There, the lever for scaling more cores was lowering per-core memory demand d; an efficient directory is one of the biggest such levers, because a miss does not just cost a broadcast — the back-invalidation it triggers turns a cache hit into a miss, sending that core to memory and raising d. So a well-sized directory keeps the effective cache large, which keeps memory demand low, which pushes the multi-core knee right. This chapter is where coherence efficiency becomes memory-demand reduction.

5. Core Concept — the hit rate drives precision and retention

Directory efficiency is its hit rate: a hit gives a precise snoop, a miss forces a broadcast, and an eviction of a live line forces a back-invalidation.

• Hit → precise snoop. On a directory hit, the home knows exactly which caches hold the line, so it snoops only the sharers — O(sharers), typically one or two.
• Miss → broadcast. On a directory miss (the entry was evicted under capacity pressure), the home does not know the sharers, so it must broadcast the snoop to all caches — O(N).
• Eviction of a live line → back-invalidation. Because the directory is a finite cache, tracking a new line may evict an entry for a line still live in a cache — forcing a back-invalidation of that cache line (Chapter 11.1).
• Undersizing collapses both. A directory smaller than the aggregate cache footprint has a low hit rate, so it broadcasts often and back-invalidates live lines — flooding the fabric and shrinking the effective cache.

The synthesis:

Directory efficiency is its hit rate. A hit lets the home snoop only the sharers (precise, O(sharers)); a miss forces a broadcast to all caches (O(N)); and evicting a directory entry for a live line forces a back-invalidation that throws away a good cached copy. An undersized directory has a low hit rate, so it broadcasts and back-invalidates — collapsing performance on two fronts. Size it to cover the aggregate cache footprint.

6. Engineering Mental Model — a guest registry at a hotel

Think of a hotel front desk keeping a registry of which rooms each guest occupies (the directory tracking which caches hold each line).

• When a package arrives and the registry has the guest, the desk delivers it straight to their room — one trip (a precise snoop to the known sharer).
• If the registry has no entry for the guest (a miss), the desk does not know the room, so it must knock on every door to find them — a broadcast to all rooms.
• The registry has limited pages. To write in a new guest when it is full, the desk erases an existing guest's entry — but that guest is still in their room. Now the hotel evicts that guest to keep the registry consistent (a back-invalidation of a live line): a paying guest thrown out because the registry ran out of pages.
• A too-small registry means constant door-knocking (broadcasts) and constant evictions of real guests (back-invalidations) — chaos on two fronts.

A registry sized to the hotel's occupancy delivers packages precisely and never evicts a guest. An undersized directory does the opposite. Size the registry to the guests.

7. Engineering Diagram — hit vs miss consequences

A lookup goes one of two ways. Hit: exact sharers, precise snoop. Miss: unknown sharers, broadcast, and a possible back-invalidation. The hit rate decides how often you take the cheap path. Undersizing pushes lookups onto the expensive one.

8. Hit vs Miss Costs

The two lookup outcomes and their costs.

The rule to carry: the hit rate multiplies straight into snoop traffic and cache stability. With hit rate h, the average snoop cost is roughly h × sharers + (1 − h) × N — so as h falls, the O(N) broadcast term dominates and traffic explodes. Meanwhile the misses that come from directory capacity evictions also trigger back-invalidations, so a low h simultaneously floods the snoop channel and shrinks the effective cache. Both effects push the same way: raise h by sizing the directory to the aggregate cache footprint.

9. Sizing the Directory

How to keep the hit rate high.

• Cover the aggregate cache footprint. The directory must have at least as many trackable entries as there are cached lines across all caches — otherwise it cannot represent what the caches hold, and misses are structural.
• A directory miss is a coverage failure. Unlike a cache miss (the data was not cached), a directory miss on a cached line means the directory lost track of a line that is really there — a pure inefficiency.
• Undersizing is doubly costly. Too few entries → low hit rate → broadcasts and back-invalidations. The area saved on the directory is paid back many times over in fabric traffic and lost cache hits.
• Over-provision modestly. Size the directory to the aggregate cache capacity plus headroom, so capacity evictions (and their back-invalidations) are rare.

The point to carry:

The directory is a case where a small structure gates a large one, so its sizing has outsized leverage. The directory is far smaller than the caches it tracks — a few bits per line versus a full line of data — yet if it cannot cover those caches, it cripples them: every line it cannot track becomes a broadcast and a candidate for back-invalidation. This inverts the usual "bigger cache is better" intuition: adding cache capacity without growing the directory to cover it makes things worse, because the extra cached lines the directory cannot track generate broadcasts and churn. The correct mental model is that cache capacity and directory coverage must scale together — the directory is not an optional accelerator you can under-provision, but a structure whose coverage is a precondition for the caches beneath it to deliver their value. A cheap directory that fails to cover the caches is a false economy that shows up as fabric congestion and a mysteriously small effective cache.

10. Two Directories — covered vs undersized

The same 4-node system with 4096 total cached lines, two directory sizes.

1. Covered directory (4096+ entries). Every cached line is tracked. Lookups hit; snoops go to the 1–2 actual sharers. Snoop traffic is O(sharers); no capacity back-invalidations.
2. Snoop cost, covered. For a line shared by 2 caches: 2 snoops per coherence action. The snoop channel is lightly loaded.
3. Undersized directory (1024 entries, 25% coverage). Most cached lines are not tracked. Lookups miss ~75% of the time; on a miss the home broadcasts to all 4 caches.
4. Snoop cost, undersized. Average ≈ 0.25 × 2 + 0.75 × 4 = 3.5 snoops — and every new line tracked evicts a live entry, back-invalidating a cached line so cores re-fetch from memory.

The covered directory kept snoops precise and caches full; the undersized one doubled snoop traffic and churned the caches. The DebugLab is the undersized directory at steps 3–4.

11. RTL / Hardware View — a directory-efficiency model

Coverage decides the snoop cost and whether a back-invalidation fires. Representative analysis model.

// Representative directory-efficiency model (educational).
// If the directory COVERS the aggregate cached-line footprint, lookups hit and the home
// snoops only the sharers (precise). If undersized, lookups miss -> BROADCAST to all
// nodes, and tracking new lines back-invalidates live cache lines (churn).
module chi_dir_efficiency #(parameter W = 32) (
  input  logic [W-1:0] dir_entries,   // directory capacity (lines it can track)
  input  logic [W-1:0] cached_lines,  // aggregate cached lines across all caches
  input  logic [W-1:0] num_nodes,     // N caches (broadcast target count)
  input  logic [W-1:0] num_sharers,   // actual sharers of the line (precise target count)
  output logic         covered,       // directory covers the footprint
  output logic [W-1:0] snoop_cost,    // sharers if covered, else all nodes (broadcast)
  output logic         back_invalidate// undersized -> evicting live entries
);
  always_comb begin
    covered         = (dir_entries >= cached_lines);
    snoop_cost      = covered ? num_sharers : num_nodes;   // precise vs broadcast
    back_invalidate = (dir_entries < cached_lines);         // churn live lines
  end
endmodule

The same behavior in Verilog-2001:

// Representative directory-efficiency model (Verilog-2001).
module chi_dir_efficiency #(parameter W = 32) (
  input  [W-1:0] dir_entries, cached_lines, num_nodes, num_sharers,
  output         covered,
  output [W-1:0] snoop_cost,
  output         back_invalidate
);
  assign covered         = (dir_entries >= cached_lines);
  assign snoop_cost      = covered ? num_sharers : num_nodes;
  assign back_invalidate = (dir_entries < cached_lines);
endmodule

And in VHDL:

-- Representative directory-efficiency model (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity chi_dir_efficiency is
  generic ( W : integer := 32 );
  port (
    dir_entries, cached_lines, num_nodes, num_sharers : in unsigned(W-1 downto 0);
    covered         : out std_logic;
    snoop_cost      : out unsigned(W-1 downto 0);
    back_invalidate : out std_logic
  );
end entity;
 
architecture rtl of chi_dir_efficiency is
  signal cov : std_logic;
begin
  cov <= '1' when dir_entries >= cached_lines else '0';
  covered         <= cov;
  snoop_cost      <= num_sharers when cov = '1' else num_nodes;
  back_invalidate <= '1' when dir_entries < cached_lines else '0';
end architecture;

All three make snoop_cost equal the sharer count when covered and the node count (broadcast) when not, and raise back_invalidate when undersized. The DebugLab is dir_entries << cached_lines.

12. Verification View — coverage gives precise snoops

The properties tie coverage to cost: covered means precise, undersized means broadcast and churn.

// Bind to chi_dir_efficiency. These are same-cycle (combinational) invariants,
// so they are immediate assertions in always_comb, not clocked concurrent properties.
always_comb begin
  // 1. When covered, the snoop is precise (only the sharers).
  p_covered_is_precise:   assert (!covered || (snoop_cost == num_sharers));
  // 2. When not covered, the snoop is a broadcast (all nodes) and back-invalidation fires.
  p_uncovered_broadcasts: assert (covered || ((snoop_cost == num_nodes) && back_invalidate));
  // 3. A directory covering the footprint never back-invalidates for capacity.
  p_covered_no_churn:     assert (!(dir_entries >= cached_lines) || !back_invalidate);
end

The system point, beyond the checks:

The directory illustrates a precision-versus-coverage law that recurs in every filter-style structure: a filter can only be as precise as it is complete. The directory's job is to narrow a broadcast to a targeted snoop, but it can only narrow the cases it covers — the moment coverage lapses, precision collapses all the way back to broadcast, because "I don't know who has it" leaves only "ask everyone." There is no graceful middle: a directory miss is not a slightly-less-precise snoop, it is a fully imprecise one. This all-or-nothing cliff is why the hit rate matters so much and why undersizing is so punishing — you do not lose precision proportionally to the shortfall, you lose it entirely on every uncovered line. The engineering consequence is that coverage is not a tunable trade-off to optimize but a threshold to clear: size the directory over the aggregate footprint, and precision is available on every lookup; fall under it, and precision evaporates on the uncovered fraction while back-invalidations churn the caches. Filters must cover their domain to be worth having.

• What it proves: coverage yields precise snoops; undersizing yields broadcasts and back-invalidation.
• What it does not prove: the real aggregate cached-line footprint — that requires workload profiling.
• Bug signature: dir_entries < cached_lines — broadcasts and churn.

13. Testbench — an undersized directory broadcasts and churns

Compares a covered and an undersized directory on snoop cost and back-invalidation.

module tb_chi_dir_efficiency;
  localparam W = 32;
  logic [W-1:0] dir_entries, cached_lines, num_nodes, num_sharers;
  logic covered; logic [W-1:0] snoop_cost; logic back_invalidate;
  int errors = 0;
 
  chi_dir_efficiency #(.W(W)) dut (.*);
 
  initial begin
    cached_lines = 4096; num_nodes = 8; num_sharers = 2;
 
    // Covered directory: entries >= footprint -> precise snoop, no churn.
    dir_entries = 4096; #1;
    if (!covered || snoop_cost !== 2 || back_invalidate) begin errors++; $display("FAIL covered case"); end
    else $display("PASS covered: snoop_cost=%0d (sharers), no back-inval", snoop_cost);
 
    // Undersized directory: entries << footprint -> broadcast + back-invalidation.
    dir_entries = 1024; #1;
    if (covered || snoop_cost !== 8 || !back_invalidate) begin errors++; $display("FAIL undersized case"); end
    else $display("PASS undersized: snoop_cost=%0d (broadcast all %0d), back_inval=%0b",
                  snoop_cost, num_nodes, back_invalidate);
 
    $display("INFO undersizing raised snoop cost %0dx and churns caches", 8/2);
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS covered: snoop_cost=2 (sharers), no back-inval
PASS undersized: snoop_cost=8 (broadcast all 8), back_inval=1
INFO undersizing raised snoop cost 4x and churns caches
ALL TESTS PASSED

14. DebugLab — an undersized directory

aggregate cached lines = 4096;  directory entries = 1024  (25% coverage)
lookup on a cached line: ~75% MISS (not tracked)
  -> MISS: home broadcasts snoop to all 8 caches (should be ~2 sharers) -> 4x traffic
  -> tracking a new line evicts a LIVE entry -> back-invalidation -> cached line dropped
  -> that core re-fetches from memory -> memory demand up, effective cache down
correct: directory entries >= 4096 -> lookups hit -> snoop only the ~2 sharers, no churn

15. Common Mistakes

• Undersizing the directory. Assumption: a small directory saves area. Bug: broadcasts + churn (the DebugLab). Prevention: cover the aggregate footprint.
• Growing cache without directory. Assumption: bigger cache is always better. Bug: untracked lines broadcast. Prevention: scale coverage with cache.
• Treating a directory miss like a cache miss. Assumption: the line was not cached. Bug: it is a tracking failure. Prevention: recognize coverage misses.
• Ignoring back-invalidations. Assumption: evictions are free. Bug: effective cache shrinks. Prevention: size to avoid capacity evictions.
• Optimizing snoops before coverage. Assumption: targeting fixes traffic. Bug: no entry to target (15.6 needs 15.5). Prevention: coverage first.
• Measuring only cache hit rate. Assumption: caches tell the story. Bug: directory misses hidden. Prevention: track the directory hit rate too.

16. Engineering Checklist

• Size the directory to cover the aggregate cached-line footprint (plus headroom).
• Track the directory hit rate as a first-class metric.
• Confirm hits yield precise snoops (O(sharers)).
• Confirm misses' broadcast cost is understood (O(N)).
• Minimize capacity back-invalidations of live lines.
• Grow directory coverage together with cache capacity.

17. Key Takeaways

• Directory efficiency is its hit rate.
• A hit gives a precise snoop (O(sharers)); a miss forces a broadcast (O(N)).
• Evicting a directory entry for a live line forces a back-invalidation.
• An undersized directory broadcasts and churns — collapsing performance on two fronts.
• Size the directory to cover the aggregate cache footprint.
• Coverage is a threshold, not a trade-off; the model here is representative.

18. Quick Revision

Directory efficiency. The directory is a finite snoop filter tracking which caches hold each line, and its efficiency is its hit rate. A directory hit lets the home read the exact sharers and send a precise snoop — O(sharers), typically one or two. A directory miss (the entry evicted under capacity pressure) leaves the home not knowing who holds the line, so it must broadcast the snoop to all caches — O(N). Worse, tracking a new line may evict a directory entry for a line still live in a cache, forcing a back-invalidation that discards a good cached copy and sends that core back to memory. So an undersized directory — fewer entries than the aggregate cached-line footprint — has a low hit rate and collapses performance on two fronts: snoop traffic scales as the node count instead of the sharer count, and back-invalidation churn shrinks the effective cache, raising per-core memory demand (Chapter 15.4). Coverage is a threshold, not a proportional trade-off — a miss is a fully imprecise snoop, not a slightly worse one. The fix: size the directory to cover the aggregate cache footprint (plus headroom), and grow coverage with cache capacity. Representative model; 15.6 covers using the sharer set to reduce snoop traffic.

Coming Next

Chapter 15.6 — Snoop Reduction. A high directory hit rate gives you the sharer set; snoop reduction is about actually using it. Chapter 15.6 covers snoop reduction — how a directory cuts snoop traffic from a broadcast to all caches down to targeted snoops of only the tracked sharers, why this is the primary scalability lever over snoop-based coherence, and why broadcasting despite having the sharer set wastes it.