Snoop Reduction

Module 15 · Chapter 15.6 · CHI Performance

Project thread — 15.5 kept the directory hit rate high so sharer info exists. 15.6 uses that info to target snoops; 15.7 looks at fabric utilisation.

1. Learning Outcomes

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

• State that snoop-based coherence broadcasts to all caches — O(N) per transaction.
• Explain that a directory snoops only the sharers — O(sharers), typically 1–2.
• Describe the O(N) → O(sharers) reduction as the primary scalability lever.
• Explain that the home must use the sharer vector to target, not broadcast.
• Diagnose the wasted directory from broadcasting despite having the sharer set.
• Implement a representative snoop-targeting model in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

Snoop traffic is what limits how far coherence scales. In a broadcast protocol, every coherence action asks all caches "do you have this line?" — so with N caches, each transaction generates on the order of N snoop messages, and the snoop channel's load grows with the system. That is why pure broadcast snooping falls apart beyond a handful of cores: the snoops themselves become the bottleneck.

The directory exists to break that scaling, and this chapter is the payoff. Because the directory tracks the sharers, the home can snoop only the caches that actually hold the line — usually one or two — turning O(N) traffic into O(sharers). This single reduction is the primary reason a directory protocol like CHI scales to 64+ nodes where broadcasting cannot. But the reduction is not automatic: the home must actually read the sharer vector and target the snoop. A design that has the sharer set (a directory hit) but broadcasts anyway throws away the directory's entire benefit. This chapter is that reduction and the discipline of using it.

3. Key Terms

4. Previous Chapter Connection

This chapter is the direct payoff of everything the directory provides. Chapter 11.3 built the sharer vector; Chapter 15.5 kept the directory hit rate high so that vector is available. This chapter finally uses it — to send snoops only where they are needed.

The contrast with broadcast snooping is the reason CHI exists (Chapter 3.x, "Why CHI"). Broadcast coherence is simple but scales as O(N) in snoop traffic; a directory adds the bookkeeping to make coherence O(sharers). Chapters 15.5 and 15.6 are the two halves of that bookkeeping paying off: 15.5 ensures you have the sharer information (coverage/hit rate), and 15.6 ensures you use it (targeting). Both are required — a covered directory whose sharer vector is ignored is as wasteful as an undersized one, just for a different reason. This chapter closes the coherence-efficiency story before the module turns to raw fabric utilisation (15.7).

5. Core Concept — snoop only the sharers

A directory cuts snoop traffic from a broadcast (all N caches) to a targeted snoop of only the sharers the directory tracks — the primary scalability lever.

• Broadcast is O(N). Snoop-based coherence sends every coherence action to all caches — N snoop messages per transaction — because it does not know who holds the line.
• The directory knows the sharers. The directory's sharer vector records exactly which caches hold each line — so the home does not have to ask everyone.
• Targeted is O(sharers). The home reads the sharer vector and snoops only the caches whose bit is set — typically one or two — so snoop traffic scales with the sharer count, not the node count.
• Use the vector, do not broadcast. The reduction happens only if the home targets the snoop. Having the sharer set (a directory hit) but broadcasting anyway wastes the directory entirely.

The synthesis:

Snoop-based coherence broadcasts to all N caches — O(N) snoop traffic per transaction — which does not scale. A directory records the sharers, so the home snoops only them — O(sharers), typically 1–2. This O(N) → O(sharers) reduction is the primary scalability lever of CHI. But it requires the home to read the sharer vector and target the snoop; broadcasting despite having the vector throws the directory's benefit away.

6. Engineering Mental Model — a group text vs a direct message

Think of needing to reach the two people who borrowed your book (the sharers), among a group of many.

• Broadcast (snoop-based). You send a group text to everyone — "does anyone have my book?" All N people receive it, and the N−2 who do not have it must each reply "not me." Lots of messages, most useless.
• Directory. You kept a note of exactly who borrowed it — two names (the sharer vector). You do not need to ask the group.
• Targeted (directory-based). You direct-message the two borrowers. Two messages, two relevant replies. The other people are never bothered.
• The waste of broadcasting anyway. Now imagine you have the note but send the group text regardless. Everyone is interrupted, N−2 people reply "not me" for nothing, and your note — the whole point of keeping it — was pointless.

The note is the sharer vector; the group text is a broadcast. Keeping the note (15.5) only helps if you use it to direct-message (15.6). Broadcasting with the note in hand is pure waste.

7. Engineering Diagram — broadcast vs targeted

Top: broadcast — 8 snoops, 6 wasted. Bottom: the sharer vector drives a targeted snoop — 2 snoops, both relevant. The directory turns the top row into the bottom row, if the home reads the vector. The DebugLab keeps the vector but takes the top row anyway.

8. Broadcast vs Targeted Cost

The two approaches contrasted, for a line held by k of N caches.

The rule to carry: the savings are N − k snoops per transaction, and for typical sharing (k ≈ 1–2) that is almost all of them. Most lines are held by very few caches, so targeting eliminates the vast majority of snoop traffic — the difference between coherence that scales and coherence that does not. Broadcasting spends N snoops to reach k holders and burdens the N − k non-holders with useless snoop-and-response work; targeting spends exactly k. As N grows, the broadcast cost grows with it while the targeted cost stays flat — which is the entire scalability argument for a directory.

9. Using the Sharer Vector

How targeting actually works, and why it needs the vector.

• Read the sharer bits. On a directory hit, the home reads the sharer vector — a bit per cache — and identifies the caches whose bit is set (the holders).
• Snoop only the set bits. The home sends a snoop to each set-bit cache and to no others. The message count is popcount(sharer_vector) — the number of sharers.
• Non-sharers are never touched. Caches whose bit is clear receive nothing — no snoop, no response, no wasted work. This is the whole saving.
• Broadcasting ignores the vector. A home that snoops all N caches regardless of the vector produces the same result but at O(N) cost — the directory's information is present but unused.

The point to carry:

Snoop reduction is where the directory's storage cost pays for itself in traffic, and the trade is deeply favorable: a few bits of sharer vector per line saves, on every coherence action to that line, N − k snoop messages — each of which is a full fabric transaction with a request and a response. The asymmetry is enormous: bits of storage against messages of bandwidth, paid repeatedly for the life of the line. This is why directory protocols win at scale — the storage grows slowly (bits per line) while the traffic saved grows with N. But the trade only closes if the home acts on the bits. A directory that stores sharer vectors and then broadcasts anyway has paid the storage cost and reaped none of the traffic benefit — the worst of both worlds. The discipline is simple to state and easy to violate under schedule pressure ("broadcast is simpler, ship it"): if you have the sharer vector, target the snoop. The bits are only an optimization if the logic downstream honors them.

10. A Coherence Action — broadcast vs targeted

The same write to a line held by 2 of 8 caches, resolved two ways.

1. Broadcast approach. The home snoops all 8 caches. 2 respond with the line's state; the other 6 respond "I don't have it" (invalid/no-data). 8 snoops, 8 responses, 6 of each wasted.
2. SNP channel load, broadcast. 8 snoop messages for a 2-sharer line — a 4× overhead. Scale to 64 caches and it is 64 snoops for the same 2 sharers — a 32× overhead.
3. Targeted approach. The home reads the sharer vector (2 bits set), and snoops only those 2 caches. 2 snoops, 2 responses, all relevant.
4. SNP channel load, targeted. 2 messages regardless of whether N is 8 or 64 — the cost is flat in the node count. The directory's benefit is fully realized.

The targeted approach sent 2 snoops where the broadcast sent 8 (or 64) — the reduction that lets the system scale. The DebugLab is the broadcast approach with the sharer vector available and ignored.

11. RTL / Hardware View — snoop targeting

The home snoops only the caches whose sharer bit is set; the count is the popcount of the vector. Representative.

// Representative snoop-targeting model (educational).
// Given a directory hit's sharer vector, snoop ONLY the caches whose bit is set. The
// targeted message count is popcount(sharer_vec). Broadcasting (snoop all NUM_NODES)
// ignores the vector and inflates snoop traffic to O(N) for a 1-2 sharer line.
module chi_snoop_targeting #(parameter NUM_NODES = 8) (
  input  logic [NUM_NODES-1:0]         sharer_vec,   // directory sharer bitmap
  output logic [NUM_NODES-1:0]         snoop_mask,   // which caches to snoop (= sharers)
  output logic [$clog2(NUM_NODES+1)-1:0] targeted_cnt, // popcount(sharer_vec)
  output logic [$clog2(NUM_NODES+1)-1:0] broadcast_cnt,// N (what a broadcast would cost)
  output logic [$clog2(NUM_NODES+1)-1:0] saved         // N - popcount
);
  // Snoop exactly the sharers -- never a non-sharer.
  assign snoop_mask   = sharer_vec;
  always_comb begin
    targeted_cnt = '0;
    for (int i = 0; i < NUM_NODES; i++)
      targeted_cnt += sharer_vec[i];      // popcount
  end
  assign broadcast_cnt = NUM_NODES[$clog2(NUM_NODES+1)-1:0];
  assign saved         = broadcast_cnt - targeted_cnt;
endmodule

The same behavior in Verilog-2001:

// Representative snoop-targeting model (Verilog-2001).
module chi_snoop_targeting #(parameter NUM_NODES = 8, parameter CW = 4) (
  input  [NUM_NODES-1:0] sharer_vec,
  output [NUM_NODES-1:0] snoop_mask,
  output reg [CW-1:0]    targeted_cnt,
  output [CW-1:0]        broadcast_cnt,
  output [CW-1:0]        saved
);
  integer i;
  assign snoop_mask = sharer_vec;         // snoop only the sharers
  always @* begin
    targeted_cnt = {CW{1'b0}};
    for (i = 0; i < NUM_NODES; i = i + 1)
      targeted_cnt = targeted_cnt + sharer_vec[i];   // popcount
  end
  assign broadcast_cnt = NUM_NODES[CW-1:0];
  assign saved         = broadcast_cnt - targeted_cnt;
endmodule

And in VHDL:

-- Representative snoop-targeting model (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity chi_snoop_targeting is
  generic ( NUM_NODES : integer := 8 );
  port (
    sharer_vec    : in  std_logic_vector(NUM_NODES-1 downto 0);
    snoop_mask    : out std_logic_vector(NUM_NODES-1 downto 0);
    targeted_cnt  : out integer range 0 to NUM_NODES;
    broadcast_cnt : out integer range 0 to NUM_NODES;
    saved         : out integer range 0 to NUM_NODES
  );
end entity;
 
architecture rtl of chi_snoop_targeting is
begin
  snoop_mask <= sharer_vec;               -- snoop only the sharers
  process (sharer_vec)
    variable cnt : integer range 0 to NUM_NODES;
  begin
    cnt := 0;
    for i in 0 to NUM_NODES-1 loop
      if sharer_vec(i) = '1' then cnt := cnt + 1; end if;   -- popcount
    end loop;
    targeted_cnt  <= cnt;
    broadcast_cnt <= NUM_NODES;
    saved         <= NUM_NODES - cnt;
  end process;
end architecture;

All three set snoop_mask = sharer_vec — snooping exactly the sharers — and report the savings versus a broadcast. The DebugLab drives snoop_mask to all-ones regardless of the vector.

12. Verification View — snoops go only to sharers

The properties tie snoops to the vector: only sharers are snooped, and the count is the popcount.

// Bind to chi_snoop_targeting.
// 1. A cache is snooped ONLY if it is a sharer (never a non-sharer).
property p_only_sharers_snooped;
  @(*) (snoop_mask & ~sharer_vec) == '0;
endproperty
 
// 2. Every sharer IS snooped (no sharer missed).
property p_all_sharers_snooped;
  @(*) (sharer_vec & ~snoop_mask) == '0;
endproperty
 
// 3. The targeted count equals the popcount, and savings = N - popcount.
property p_saving_is_real;
  @(*) (saved == broadcast_cnt - targeted_cnt) && (targeted_cnt <= broadcast_cnt);
endproperty

The system point, beyond the checks:

The two masking properties together — snoop every sharer, snoop only sharers — are what make targeting both correct and efficient, and it is worth seeing that they pull in opposite directions. "Snoop only sharers" is the efficiency property (do not bother non-holders); "snoop every sharer" is the correctness property (do not miss a holder, or coherence breaks). A broadcast trivially satisfies correctness (it snoops everyone, so no sharer is missed) but maximally violates efficiency. The directory lets you satisfy both by making snoop_mask exactly equal to sharer_vec — the tightest set that still covers every holder. This is the general shape of a good filter: it must be complete (no false negatives — every sharer snooped, which is a coherence requirement) while being as precise as possible (few false positives — non-sharers spared, which is the performance win). The directory's correctness (Chapter 15.5's coverage) is what permits the aggressive precision; you can only safely stop snooping the non-sharers because the directory guarantees they are non-sharers. Efficiency here is licensed by correctness.

• What it proves: snoops hit exactly the sharer set; savings = N − popcount.
• What it does not prove: the sharer vector is accurate — that is the directory's correctness (Module 11).
• Bug signature: snoop_mask = all-ones while sharer_vec has few bits — a broadcast despite the vector.

13. Testbench — a 2-sharer line must draw 2 snoops, not N

Drives a sparse sharer vector and checks the snoop count is the popcount, not N.

module tb_chi_snoop_targeting;
  localparam NUM_NODES = 8, CW = 4;
  logic [NUM_NODES-1:0] sharer_vec, snoop_mask;
  logic [CW-1:0] targeted_cnt, broadcast_cnt, saved;
  int errors = 0;
 
  chi_snoop_targeting #(.NUM_NODES(NUM_NODES)) dut (.*);
 
  initial begin
    // Line held by 2 of 8 caches (bits 1 and 5).
    sharer_vec = 8'b0010_0010; #1;
    if (snoop_mask !== sharer_vec) begin errors++; $display("FAIL snooped non-sharers"); end
    else $display("PASS snoop_mask = sharers only (%b)", snoop_mask);
    if (targeted_cnt !== 2) begin errors++; $display("FAIL targeted_cnt=%0d exp 2", targeted_cnt); end
    else $display("PASS targeted=%0d, broadcast=%0d, saved=%0d", targeted_cnt, broadcast_cnt, saved);
 
    // A widely-shared line (5 of 8) still targets exactly the 5, not all 8.
    sharer_vec = 8'b1011_0101; #1;
    if (targeted_cnt !== 5 || snoop_mask !== sharer_vec) begin errors++; $display("FAIL 5-sharer case"); end
    else $display("PASS 5-sharer: targeted=%0d saved=%0d", targeted_cnt, saved);
 
    // No sharers -> no snoops at all.
    sharer_vec = 8'b0; #1;
    if (targeted_cnt !== 0) begin errors++; $display("FAIL empty vector snooped"); end
    else $display("PASS no sharers -> 0 snoops");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS snoop_mask = sharers only (00100010)
PASS targeted=2, broadcast=8, saved=6
PASS 5-sharer: targeted=5 saved=3
PASS no sharers -> 0 snoops
ALL TESTS PASSED

14. DebugLab — broadcasting despite having the sharer vector

directory hit: sharer_vec = 2 bits set (2 of 64 caches hold the line)
buggy home: snoop_mask = all-ones -> snoops ALL 64 caches (ignores sharer_vec)
  -> 64 snoop messages for a 2-sharer line (32x overhead)
  -> 62 non-sharers each respond "I have nothing" (useless work)
  -> SNP channel saturated; scales as O(N), not O(sharers)
correct: snoop_mask = sharer_vec -> 2 snoops -> O(sharers), flat in N

15. Common Mistakes

• Broadcasting with the vector in hand. Assumption: broadcast is simpler. Bug: O(N) traffic, wasted directory (the DebugLab). Prevention: target the sharer vector.
• Snooping non-sharers. Assumption: extra snoops are harmless. Bug: useless work on N−k caches. Prevention: snoop only set bits.
• Missing a sharer. Assumption: a partial mask is fine. Bug: a holder not snooped — coherence breaks. Prevention: snoop every sharer.
• Storing sharers but not using them. Assumption: the directory alone helps. Bug: storage cost, no traffic benefit. Prevention: honor the vector.
• Ignoring non-sharer response load. Assumption: only snoops cost. Bug: N−k useless responses too. Prevention: targeting removes both.
• Confusing with coverage. Assumption: 15.5 covers it. Bug: having vs using the vector conflated. Prevention: 15.5 = have it; 15.6 = use it.

16. Engineering Checklist

• On a directory hit, read the sharer vector.
• Snoop only the caches whose sharer bit is set.
• Snoop every sharer (no holder missed) — correctness.
• Snoop no non-sharer (no wasted work) — efficiency.
• Confirm the snoop count is the popcount, not the node count.
• Verify snoop traffic stays flat as node count grows.

17. Key Takeaways

• Snoop-based coherence broadcasts to all caches — O(N) per transaction.
• A directory snoops only the sharers — O(sharers), typically 1–2.
• The O(N) → O(sharers) reduction is CHI's primary scalability lever.
• The home must use the sharer vector to target — not broadcast.
• Broadcasting despite having the vector wastes the directory entirely.
• Snoop every sharer, only sharers; the model here is representative.

18. Quick Revision

Snoop reduction. Snoop-based coherence broadcasts every coherence action to all caches, so an N-cache system sends on the order of N snoop messages per transaction — the snoop channel scales with node count, which is why broadcast snooping does not scale. A directory records each line's sharer vector, so the home can snoop only the caches that actually hold the line — popcount(sharer_vector) messages, typically one or two. This O(N) → O(sharers) reduction is CHI's primary scalability lever: it turns snoop traffic that grows with the system into snoop traffic that stays flat in the node count. But the reduction is realized only if the home reads the sharer vector and targets the snoop — snooping every sharer (correctness) and only sharers (efficiency). The failure to avoid: having the sharer vector from a directory hit and broadcasting anyway — snooping all N caches for a 1–2 sharer line, saturating the SNP channel, forcing N−k non-sharers to answer "I have nothing," and reaping none of the directory's traffic benefit despite paying its storage cost. Store the vector and honor it. This is distinct from coverage (Chapter 15.5, whether you have the vector); here it is about using it. Representative model; 15.7 closes the module on fabric utilisation.

Coming Next

Chapter 15.7 — Fabric Utilisation. Snoop reduction and directory efficiency lower traffic; the last chapter asks how evenly that traffic actually spreads across the interconnect. Chapter 15.7 covers fabric utilisation — why real workloads create hotspots where one link saturates while average utilisation looks low, why aggregate-bandwidth figures mislead, and how to find and balance the hotspot that caps throughput.