Snoop Mechanisms

Module 2 · Chapter 2.8 · Coherency Protocol Foundations

Project thread — 2.7 invalidated the sharers and assumed the Home Node knew who they were. This chapter is how it knows: broadcast to everyone, or a directory that tracks them. That choice is why CHI scales where ACE's broadcast does not.

1. Learning Outcomes

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

• Distinguish broadcast snooping (ask everyone) from directory snooping (ask only holders).
• Explain why broadcast snoop traffic grows with the core count and becomes the scalability wall.
• Trace a directory lookup producing a targeted snoop to only the caches that hold a line.
• Identify why a snoop filter may over-approximate (false positives) but never under-approximate.
• Implement a representative directory snoop generator in SystemVerilog, Verilog-2001, and VHDL.
• Verify that a snoop targets only actual holders and never the requester.

2. Why Should I Learn This?

Snoop bandwidth is the wall coherent systems hit as core counts grow. With broadcast, every coherent request touches every cache; at 64 cores, a single write can generate 63 snoops, and the aggregate becomes the interconnect's dominant traffic. The mechanism that avoids it — a directory — is exactly why CHI exists and why it uses distributed Home Nodes.

Understanding broadcast versus directory is understanding the central architectural decision of a coherent SoC. It also frames a subtle correctness rule: a snoop filter may waste effort snooping a cache that does not hold the line, but it must never miss one that does.

3. Key Terms

4. Previous Chapter Connection

Chapter 2.7 said a write invalidates every sharer and waits for their acks — but it assumed the Home Node already knew who the sharers were. That knowledge is not free. It is either avoided by asking everyone (broadcast) or maintained as state (a directory).

This chapter fills the gap. The invalidation of 2.7 needs a list of targets; snoop mechanisms are how that list is produced. And the quality of that list — precise, over-approximate, or wrong — decides both the traffic and the correctness of every invalidation.

5. Core Concept — ask everyone, or ask a record

To snoop the holders of a line, the fabric can either interrogate every cache or consult a record.

• Broadcast. Send the snoop to all caches. Each checks its own tags: a holder responds, a non-holder ignores it. No state to maintain — the caches are the directory. But every request costs a snoop to every cache, so snoop traffic scales with the number of cores, O(N) per request. Simple, and fine for a few cores; a bottleneck for many.
• Directory. Keep, per line, a record of which caches hold it (a sharer set) and who owns it. On a request, look up the record and snoop only the caches in it — usually zero, one, or two. Traffic scales with the number of actual sharers, not the machine size. The cost is directory storage (bits per line) and a lookup step.

The tradeoff in one line:

Broadcast trades traffic for simplicity; directory trades storage for traffic. At small scale, broadcast's simplicity wins. As cores multiply, snoop bandwidth dominates, and the directory's targeted snoops are the only thing that scales — which is why CHI is directory-based.

One rule governs any sharer record, exact or approximate:

Never a false negative. A snoop filter or directory may list a cache that no longer holds the line (a wasted snoop — safe). It must never omit a cache that does (a missed invalidation — a coherency break). Records may over-approximate; they may not under-approximate.

6. Engineering Mental Model — the group email vs the CC list

You need to tell everyone holding a copy of a document to shred it.

• Broadcast is emailing the entire company every time: whoever has a copy acts, everyone else deletes an irrelevant message. No list to maintain, but the mail volume grows with headcount.
• Directory is keeping an accurate CC list of who checked out the document and emailing only them. Far less mail, but you must keep the list current.
• The unbreakable rule for the CC list: it may include someone who already returned their copy (they get a harmless extra email), but it must never leave off someone who still has one — or their copy survives the shred order.

7. Engineering Diagram — broadcast versus directory

CPU0 writes line A, which only CPU2 holds. Compare who gets snooped.

Same request, same single holder — three snoops versus one. Multiply by every coherent request across every core and that gap is the difference between a design that scales and one that does not.

8. Worked Example — snoop traffic as cores grow

CPU0 writes a line held by exactly one other cache, in machines of different sizes.

Broadcast's snoops grow as N − 1; the directory's track the actual sharers (here, 1) regardless of N. The directory pays for it in storage — a sharer bit per cache per tracked line — and a lookup, but that cost is fixed per line, while broadcast's cost grows with every core added. Past a handful of cores, the directory is the only mechanism that keeps snoop bandwidth bounded.

9. Transaction Walkthrough — a directory-targeted snoop

Trace CPU0's write of a line CPU2 holds, through a directory Home Node. Representative behavioral flow, not a byte-level trace.

1. CPU0 → RN0 → Home Node: request unique. The HN owns A's address range (CHI distributes ranges across HNs). Tracking: it opens a transaction for A.
2. Directory lookup. The HN reads A's sharer record: holders are {CPU2}. This is the step broadcast skips — and the reason only one cache will be snooped.
3. HN → RN2: snoop-invalidate A. Only CPU2 is targeted. CPU1 and CPU3 receive nothing — no wasted snoop, no ack from a non-holder to wait on.
4. RN2 invalidates and acks. CPU2's copy goes to Invalid (returning data if dirty, per 2.6). The HN's invalidate-ack gate (2.7) needed exactly one ack because the directory said one holder.
5. Directory update + grant. The HN records A's new sharer set as {CPU0} and grants CPU0 exclusive access. The record now reflects reality — which is what keeps the next request precise.

10. RTL / Hardware View — a directory snoop generator

A representative directory for one line: it holds a sharer bitmask and, on a request, produces the snoop vector — the set of other caches that actually hold the line. Broadcast would snoop all N − 1; this snoops only the holders. Behavioral and simplified: one request per cycle, one line, exact tracking.

// Representative directory snoop generator (educational, not a full directory).
// Tracks the sharer set for one line and snoops only the OTHER caches that hold it.
module directory_snoop_gen #(
  parameter int N = 4                       // number of caches
)(
  input  logic                 clk,
  input  logic                 rst_n,
  input  logic                 req_valid,
  input  logic                 req_write,   // 1 = write / invalidate, 0 = read
  input  logic                 req_evict,   // requester drops its copy
  input  logic [$clog2(N)-1:0] req_id,      // requesting cache
  output logic [N-1:0]         sharers,     // caches currently holding the line
  output logic [N-1:0]         snoop_vec    // caches to snoop this request
);
  logic [N-1:0] req_mask;
  always_comb begin
    req_mask          = '0;
    req_mask[req_id]  = 1'b1;                // one-hot requester
  end
 
  // Snoop only the OTHER caches that actually hold the line — never all N.
  assign snoop_vec = req_valid ? (sharers & ~req_mask) : '0;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) sharers <= '0;
    else if (req_valid) begin
      if (req_evict)      sharers <= sharers & ~req_mask;  // requester leaves
      else if (req_write) sharers <= req_mask;             // sole holder after a write
      else                sharers <= sharers | req_mask;   // read: requester joins sharers
    end
  end
endmodule

The same behavior in Verilog-2001:

// Representative directory snoop generator (Verilog-2001).
module directory_snoop_gen #(
  parameter N    = 4,
  parameter IDW  = 2                        // clog2(N)
)(
  input               clk,
  input               rst_n,
  input               req_valid,
  input               req_write,
  input               req_evict,
  input      [IDW-1:0] req_id,
  output reg [N-1:0]   sharers,
  output     [N-1:0]   snoop_vec
);
  wire [N-1:0] req_mask = ({{(N-1){1'b0}}, 1'b1}) << req_id;  // one-hot requester
 
  assign snoop_vec = req_valid ? (sharers & ~req_mask) : {N{1'b0}};
 
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) sharers <= {N{1'b0}};
    else if (req_valid) begin
      if (req_evict)      sharers <= sharers & ~req_mask;
      else if (req_write) sharers <= req_mask;
      else                sharers <= sharers | req_mask;
    end
  end
endmodule

And in VHDL:

-- Representative directory snoop generator (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity directory_snoop_gen is
  generic ( N : integer := 4; IDW : integer := 2 );  -- IDW = clog2(N)
  port (
    clk, rst_n : in  std_logic;
    req_valid  : in  std_logic;
    req_write  : in  std_logic;
    req_evict  : in  std_logic;
    req_id     : in  std_logic_vector(IDW-1 downto 0);
    sharers    : out std_logic_vector(N-1 downto 0);
    snoop_vec  : out std_logic_vector(N-1 downto 0)
  );
end entity;
 
architecture rtl of directory_snoop_gen is
  signal shr      : std_logic_vector(N-1 downto 0) := (others => '0');
  signal req_mask : std_logic_vector(N-1 downto 0);
begin
  -- one-hot requester
  process(req_id)
    variable m : std_logic_vector(N-1 downto 0);
  begin
    m := (others => '0');
    m(to_integer(unsigned(req_id))) := '1';
    req_mask <= m;
  end process;
 
  snoop_vec <= (shr and not req_mask) when req_valid = '1' else (others => '0');
 
  process(clk, rst_n)
  begin
    if rst_n = '0' then
      shr <= (others => '0');
    elsif rising_edge(clk) then
      if req_valid = '1' then
        if req_evict = '1' then      shr <= shr and not req_mask;
        elsif req_write = '1' then   shr <= req_mask;
        else                         shr <= shr or req_mask;
        end if;
      end if;
    end if;
  end process;
 
  sharers <= shr;
end architecture;

All three model the identical rule: the snoop vector is the sharer set minus the requester — only actual holders, never the whole machine.

11. Verification View — snoop only holders, never the requester

Three properties enforce a correct snoop set.

// Bind to directory_snoop_gen.
// 1. Idle: no snoop when there is no request.
property p_idle_no_snoop;
  @(posedge clk) disable iff (!rst_n) !req_valid |-> (snoop_vec == '0);
endproperty
assert property (p_idle_no_snoop);
 
// 2. Never snoop a non-holder — the snoop set is a subset of the sharers.
property p_only_holders;
  @(posedge clk) disable iff (!rst_n) (snoop_vec & ~sharers) == '0;
endproperty
assert property (p_only_holders);
 
// 3. Never snoop the requester itself.
property p_not_requester;
  @(posedge clk) disable iff (!rst_n) req_valid |-> !snoop_vec[req_id];
endproperty
assert property (p_not_requester);

The system invariant is a scoreboard / reference-model rule:

The snoop set for a request equals exactly the set of other caches that hold the line. A missing target (false negative) is a coherency break; an extra target (false positive) only wastes a snoop.

• What it proves: the directory snoops only real holders and never itself — targeted, correct snooping.
• What it does not prove: that the sharer set was kept current (a fill or transfer that skips the update creates a false negative — the DebugLab), nor the storage cost of exact tracking (a real snoop filter trades precision for area), nor cross-line ordering (Module 12).
• Bug signature when it fails: snoop_vec with a bit set that sharers does not have (snooping a non-holder — usually benign), or the far worse case a holder missing from sharers so its bit is never in snoop_vec (a missed invalidation).

12. Testbench — targeted snoops, not broadcast

Deterministic stimulus; the combinational snoop vector is sampled while the request is asserted.

module tb_directory_snoop_gen;
  localparam int N = 4;
  logic clk = 0, rst_n;
  logic req_valid, req_write, req_evict;
  logic [1:0] req_id;
  logic [N-1:0] sharers, snoop_vec;
  int errors = 0;
 
  directory_snoop_gen #(.N(N)) dut (.*);
  always #5 clk = ~clk;
 
  task automatic req(input logic wr, ev, input logic [1:0] id,
                     input logic [N-1:0] exp_snoop, exp_sharers_next, input string tag);
    logic [N-1:0] sv;
    req_valid = 1; req_write = wr; req_evict = ev; req_id = id;
    #1;
    sv = snoop_vec;                          // combinational — valid this cycle
    if (sv !== exp_snoop) begin
      errors++; $display("FAIL [%s] snoop_vec=%b exp=%b", tag, sv, exp_snoop);
    end
    @(posedge clk); #1;
    req_valid = 0; req_write = 0; req_evict = 0;
    if (sharers !== exp_sharers_next) begin
      errors++; $display("FAIL [%s] sharers=%b exp=%b", tag, sharers, exp_sharers_next);
    end else
      $display("PASS [%s] snoop_vec=%b sharers=%b (popcount snoop=%0d)", tag, sv, sharers, $countones(sv));
  endtask
 
  initial begin
    rst_n = 0; @(posedge clk); rst_n = 1;
    // CPU2 reads A -> sharer set { CPU2 }, no one else holds it -> no snoop.
    req(0,0, 2'd2, 4'b0000, 4'b0100, "read by 2: sharers={2}, snoop none");
    // CPU1 reads A -> joins sharers; snoop the existing holder CPU2.
    req(0,0, 2'd1, 4'b0100, 4'b0110, "read by 1: snoop {2}");
    // CPU0 writes A -> snoop the two OTHER holders {1,2}, becomes sole holder.
    req(1,0, 2'd0, 4'b0110, 4'b0001, "write by 0: snoop {1,2}, sole owner");
    // CPU0 evicts A -> sharer set empties.
    req(0,1, 2'd0, 4'b0000, 4'b0000, "evict by 0: sharers empty");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS [read by 2: sharers={2}, snoop none] snoop_vec=0000 sharers=0100 (popcount snoop=0)
PASS [read by 1: snoop {2}] snoop_vec=0100 sharers=0110 (popcount snoop=1)
PASS [write by 0: snoop {1,2}, sole owner] snoop_vec=0110 sharers=0001 (popcount snoop=2)
PASS [evict by 0: sharers empty] snoop_vec=0000 sharers=0000 (popcount snoop=0)
ALL TESTS PASSED

13. DebugLab — the directory that lost a sharer

event                       sharers (dir)   reality
CPU2 read A (fast path)     0000 (!)        CPU2 holds A   <-- directory not updated
CPU0 write A                snoop_vec=0000  CPU2 still live <-- snoop misses CPU2
CPU2 read A (later)                          returns stale value

14. Common Mistakes

• A directory false negative. Assumption: reads need not touch the directory. Bug: an unlisted holder is never snooped — a stale live copy (the DebugLab). Prevention: update the sharer set on every copy grant.
• Broadcasting at scale. Assumption: snoop everyone, keep it simple. Bug: O(N) snoop traffic per request becomes the interconnect bottleneck. Prevention: a directory (or snoop filter) targets only holders.
• Assuming a snoop filter is exact. Assumption: the filter lists holders precisely. Bug: designs that rely on exactness break when the filter over-approximates. Prevention: tolerate false positives; forbid false negatives.
• Snooping the requester. Assumption: snoop the whole sharer set. Bug: a cache snoops itself, wasting a slot or confusing its own state. Prevention: exclude the requester from the snoop vector.
• Under-sizing directory precision without noticing the cost. Assumption: a coarse sharer record is free. Bug: many false-positive snoops erode the directory's bandwidth advantage. Prevention: size precision to the sharing pattern; measure the false-positive rate.
• Treating this generator as a full directory. Assumption: a sharer bitmask is the whole HN. Bug: missing states, ownership, snoop-filter approximation, and multi-line capacity. Prevention: this is the targeting concept; the full HN directory is Module 11.

15. Engineering Checklist

• The snoop set for a request is exactly the other caches that hold the line.
• The sharer record is updated on every copy grant (read, fill, transfer) and on eviction.
• A snoop filter may over-approximate (false positives) but never under-approximate.
• The requester is excluded from its own snoop vector.
• Broadcast is reserved for small core counts; larger systems use a directory / snoop filter.
• The directory's precision is sized to the sharing pattern, and its false-positive rate is measured.

16. Key Takeaways

• Broadcast snoops every cache (no state, O(N) traffic); directory snoops only holders (storage + lookup, O(sharers) traffic).
• Snoop bandwidth is the scalability wall — the directory is why CHI scales, via distributed Home Nodes.
• A sharer record may over-approximate (wasteful false positives) but must never miss a holder (false negatives break coherency).
• The sharer set must be updated on every copy grant, or invalidations will miss unlisted holders.
• The snoop vector is the sharer set minus the requester — targeted, and never self-directed.
• This generator is representative — the snoop-targeting concept, not a complete directory.

17. Quick Revision

Snoop mechanisms. Broadcast: snoop every cache, no state, traffic O(N) per request — simple, but the scalability wall. Directory: keep a per-line sharer record, snoop only the holders, traffic O(sharers) — costs storage + a lookup, and scales. CHI is directory-based with distributed Home Nodes. A sharer record / snoop filter may over-approximate (false positive = wasted snoop, safe) but must never under-approximate (false negative = missed invalidation = coherency break). Update the record on every copy grant; exclude the requester from the snoop vector. Representative model, not a complete directory.

Coming Next

Chapter 2.9 — Reading State-Transition Tables. You have now built four protocols and the machinery around them. The next chapter teaches the notation they are documented in: how to read a canonical state-transition table — rows of current state, columns of events, cells of next-state-plus-action — so that any coherence protocol, including CHI's own, becomes something you can decode line by line rather than reverse-engineer.