ACE Limitations

Module 3 · Chapter 3.5 · Why CHI Exists

Project thread — 3.4 built ACE's broadcast coherency. This chapter shows why broadcast does not scale, and points at the directory. 3.6 quantifies the snoop-bandwidth wall; the rest of the track builds the directory-based answer.

1. Learning Outcomes

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

• Explain why ACE coherency is fundamentally broadcast — snoop every cache in the domain.
• Identify the three costs that grow with core count: snoop traffic, snoop latency, and wasted (missed) snoops.
• Describe how a snoop filter reduces broadcast — and why it is only a partial, centralized patch.
• Contrast broadcast (snoop all) with a directory (snoop only the holders).
• Implement a representative snoop filter in SystemVerilog, Verilog-2001, and VHDL.
• State the safety rule a filter or directory must never break: never under-snoop a holder.

2. Why Should I Learn This?

This is the chapter where "why CHI" stops being a slogan and becomes a number-shaped argument. CHI's defining choice — a distributed directory instead of broadcast snoops — only makes sense once you feel the broadcast wall: the traffic, the wait-for-everyone latency, the mountain of snoops that hit nothing. Understand this and every later CHI concept (Home Nodes, the directory, targeted snoops) reads as the obvious fix.

It is also a real design decision engineers make: broadcast coherency is simpler and fine at small scale; directories cost storage but win at many cores. Knowing where the crossover is — and why — is exactly the judgment this chapter builds.

3. Key Terms

4. Previous Chapter Connection

Chapter 3.4 built ACE: snoop channels, coherent transactions, a five-state model, and a coherent interconnect that broadcasts a snoop to the domain and merges the responses. That broadcast is what makes ACE correct — the interconnect learns about every copy before it answers.

It is also what makes ACE stop scaling. This chapter takes the exact mechanism 3.4 celebrated — snoop everyone, wait for all — and follows it as core count rises. The mechanism does not break; it just gets expensive, in three specific ways, until a different structure is needed.

5. Core Concept — three costs that grow with cores

Broadcast coherency has three costs, and all three grow with the number of caches N.

• Snoop traffic is O(N). Each coherent request produces a snoop to every cache in the domain and a response from each. Total snoop messages scale with N times the coherent-request rate. At many cores the snoop network — not the data — becomes the bottleneck.
• Latency tracks the slowest responder. The interconnect cannot answer until every snooped cache has responded. One busy or distant cache sets the tail latency of that access. More caches means more chances for a slow one.
• Most snoops are wasted. For a typical line, only zero, one, or two caches hold it — yet broadcast snoops all of them. As N grows, the fraction of snoops that hit nothing approaches one. Almost all of the work is wasted.

Snoop filters help:

• A snoop filter at the interconnect tracks which caches might hold each line (a presence vector). On a request, it snoops only those caches — suppressing the ones it knows are absent. This cuts wasted snoops sharply.

But the filter is a patch, not a cure:

A snoop filter is a centralized structure that must cover every line every cache could hold. It costs storage that grows with total cache capacity, it sits at one point in the interconnect (a scaling and topology bottleneck of its own), and on any uncertainty it must fall back to broadcasting to stay correct. It reduces the constant, not the fundamental shape. The real fix is to make holder-tracking complete and distributed — a directory — and to route snoops over a scalable network. That is CHI.

6. Engineering Mental Model — the fire drill versus the guest list

Two ways to find who is in a building.

• Broadcast (ACE): pull the fire alarm. Everyone stops and reports to the assembly point, and you wait until the last person is accounted for. It works, and for a small office it is fine — but in a tower it is slow, disruptive, and almost everyone you evacuated was irrelevant to your question.
• Directory (CHI): keep a guest list at the door that records exactly who is inside. To find someone, you read the list and call only them — no alarm, no waiting on everyone, no disturbing the whole building.
• A snoop filter is a partial guest list kept at one desk: better than the alarm, but if the desk runs out of room it has to pull the alarm anyway to be safe.

The chapter's thesis in one line: broadcast is the fire alarm; CHI is the guest list, distributed across many doors.

7. Engineering Diagram — broadcast: snoop every cache

Three caches here, three snoops for one request. At sixteen cores it is fifteen snoops — and the interconnect waits for the slowest of all fifteen.

8. The Directory Alternative — snoop only the holder

The two figures are the whole argument. Broadcast contacts every cache; the directory contacts one. CPU1 and CPU3 are deliberately left unconnected in Figure 2 — that absence is the saving.

9. Worked Example — snoop cost as cores scale

Count the snoops per coherent read as N grows, for a line held by exactly one other cache. Representative — real filters and directories vary, but the shape is the point.

Broadcast snoops grow as N − 1; a directory stays at 1 (the actual holder). A perfect snoop filter approaches the directory — but it must store enough to know absence for every line, and when it cannot (capacity pressure), it falls back to broadcast. Two facts to carry: broadcast's cost is structural (it scales with cores), and the directory's cost is storage (it scales with tracked lines) — which is the trade CHI makes on purpose.

10. Transaction Walkthrough — one coherent read at sixteen cores

Follow a single ReadShared in a 16-core ACE system, line held only by CPU7:

1. Issue. CPU0 issues ReadShared to the interconnect.
2. Broadcast. The interconnect sends a snoop (AC) to all fifteen other caches — it does not know who holds the line.
3. Responses. Fourteen caches respond "I don't have it" (CR miss); CPU7 responds "hit" and supplies data (CR/CD). The interconnect must collect all fifteen responses.
4. Wait for the slowest. If CPU11 is busy and answers late, the whole request waits for CPU11 — even though CPU11 had nothing.
5. Complete. The interconnect returns data to CPU0.

Fifteen snoops, fifteen responses, one useful. With a directory, step 2 becomes "snoop CPU7," steps 3–4 collapse to one response, and the fourteen idle caches are never touched.

11. RTL / Hardware View — a representative snoop filter

Here is the partial mitigation in hardware: a snoop filter that stores, per line, a presence vector of which caches hold it, and returns the set to snoop — not all N. Representative and simplified: direct-mapped, no capacity-conflict handling (that gap is the DebugLab).

// Representative snoop filter (educational, not a full ACE filter).
// Per line, a presence vector records which caches hold it. A request returns
// exactly that vector as the snoop mask — so absent caches are NOT snooped.
module snoop_filter #(
  parameter int NCACHES = 4,
  parameter int ENTRIES = 16
)(
  input  logic               clk,
  input  logic               rst_n,
  input  logic               req_valid,
  input  logic [3:0]         req_index,          // line index
  output logic [NCACHES-1:0] snoop_mask,         // caches to snoop (subset of holders)
  input  logic               upd_valid,          // a cache installed/evicted a line
  input  logic [3:0]         upd_index,
  input  logic [1:0]         upd_cache,          // which cache changed
  input  logic               upd_install         // 1 = install (set), 0 = evict (clear)
);
  logic [NCACHES-1:0] presence [0:ENTRIES-1];
  integer i;
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      for (i = 0; i < ENTRIES; i = i + 1) presence[i] <= '0;
    end else if (upd_valid) begin
      presence[upd_index][upd_cache] <= upd_install;  // track this cache's copy
    end
  end
  // Snoop only the caches the filter believes hold the line.
  assign snoop_mask = req_valid ? presence[req_index] : '0;
endmodule

The same behavior in Verilog-2001:

// Representative snoop filter (Verilog-2001).
module snoop_filter #(
  parameter NCACHES = 4,
  parameter ENTRIES = 16
)(
  input                  clk, rst_n,
  input                  req_valid,
  input      [3:0]       req_index,
  output     [NCACHES-1:0] snoop_mask,
  input                  upd_valid,
  input      [3:0]       upd_index,
  input      [1:0]       upd_cache,
  input                  upd_install
);
  reg [NCACHES-1:0] presence [0:ENTRIES-1];
  integer i;
  always @(posedge clk or negedge rst_n)
    if (!rst_n)
      for (i = 0; i < ENTRIES; i = i + 1) presence[i] <= {NCACHES{1'b0}};
    else if (upd_valid)
      presence[upd_index][upd_cache] <= upd_install;
 
  assign snoop_mask = req_valid ? presence[req_index] : {NCACHES{1'b0}};
endmodule

And in VHDL:

-- Representative snoop filter (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity snoop_filter is
  generic ( NCACHES : integer := 4; ENTRIES : integer := 16 );
  port (
    clk, rst_n  : in  std_logic;
    req_valid   : in  std_logic;
    req_index   : in  std_logic_vector(3 downto 0);
    snoop_mask  : out std_logic_vector(NCACHES-1 downto 0);
    upd_valid   : in  std_logic;
    upd_index   : in  std_logic_vector(3 downto 0);
    upd_cache   : in  std_logic_vector(1 downto 0);
    upd_install : in  std_logic
  );
end entity;
 
architecture rtl of snoop_filter is
  type presence_t is array(0 to ENTRIES-1) of std_logic_vector(NCACHES-1 downto 0);
  signal presence : presence_t := (others => (others => '0'));
begin
  process(clk, rst_n)
  begin
    if rst_n = '0' then
      presence <= (others => (others => '0'));
    elsif rising_edge(clk) then
      if upd_valid = '1' then
        presence(to_integer(unsigned(upd_index)))(to_integer(unsigned(upd_cache))) <= upd_install;
      end if;
    end if;
  end process;
 
  snoop_mask <= presence(to_integer(unsigned(req_index))) when req_valid = '1'
                else (others => '0');
end architecture;

All three return a snoop mask that is the tracked presence vector — so a line held by one cache yields one snoop, and a line held by none yields zero (broadcast fully avoided). That is the win; the danger is what happens when the filter's knowledge is wrong.

12. Verification View — a filter must never under-snoop

The filter's whole value is suppressing snoops — but it is only safe if it never suppresses a snoop to a real holder. Two properties: it snoops nothing extra beyond what it tracks, and (the safety rule) it must cover every actual holder.

// Bind to snoop_filter.
// 1. The snoop mask never includes a cache the filter does not track as present.
property p_mask_subset_of_presence;
  @(posedge clk) disable iff (!rst_n)
    req_valid |-> ((snoop_mask & ~presence[req_index]) == '0);
endproperty
assert property (p_mask_subset_of_presence);
 
// 2. SAFETY: every actual holder must be in the mask. `real_holders` is a
//    verification-only model of who truly holds the line; under-snooping it
//    (a holder absent from the mask) is a coherency violation.
property p_no_under_snoop;
  @(posedge clk) disable iff (!rst_n)
    req_valid |-> ((real_holders[req_index] & ~snoop_mask) == '0);
endproperty
assert property (p_no_under_snoop);

The system point, beyond the two checks:

Suppressing snoops is an optimization; completeness is a correctness requirement. A filter may snoop too many caches (wasteful, still correct) but must never snoop too few. The moment it cannot prove it knows all holders — a capacity conflict evicts an entry, a line's state is uncertain — it must conservatively broadcast. This "never miss a holder" invariant is exactly what a directory guarantees by construction, and it is why CHI can suppress snoops aggressively without ever being wrong.

• What it proves: the mask tracks presence and covers every real holder.
• What it does not prove: that the filter's presence data is itself complete under capacity pressure (the DebugLab) — that needs a conservative-broadcast fallback.
• Bug signature: a holder missing from the mask → a missed snoop → stale data returned (a Single-Writer violation).

13. Testbench — install, snoop, evict

Installs a line into one cache, checks the snoop mask targets only that cache, then evicts and checks the snoop is suppressed.

module tb_snoop_filter;
  localparam int NCACHES = 4;
  logic clk = 0, rst_n;
  logic req_valid, upd_valid, upd_install;
  logic [3:0] req_index, upd_index;
  logic [1:0] upd_cache;
  logic [NCACHES-1:0] snoop_mask;
  int errors = 0;
 
  snoop_filter #(.NCACHES(NCACHES)) dut (.*);
  always #5 clk = ~clk;
 
  task automatic update(input logic [3:0] idx, input logic [1:0] cache, input logic install);
    upd_valid = 1; upd_index = idx; upd_cache = cache; upd_install = install;
    @(posedge clk); #1; upd_valid = 0;
  endtask
 
  task automatic snoop(input logic [3:0] idx, input logic [NCACHES-1:0] exp, input string tag);
    req_valid = 1; req_index = idx; #1;
    if (snoop_mask !== exp) begin
      errors++; $display("FAIL [%s] snoop_mask=%b exp=%b", tag, snoop_mask, exp);
    end else
      $display("PASS [%s] snoop_mask=%b", tag, snoop_mask);
    req_valid = 0;
  endtask
 
  initial begin
    rst_n = 0; @(posedge clk); rst_n = 1;
    snoop(4'h3, 4'b0000, "empty line -> no snoop");   // nobody holds it
    update(4'h3, 2'd2, 1'b1);                          // CPU2 installs line 3
    snoop(4'h3, 4'b0100, "held by CPU2 -> snoop CPU2 only");
    update(4'h3, 2'd0, 1'b1);                          // CPU0 also installs
    snoop(4'h3, 4'b0101, "held by CPU0+CPU2 -> snoop both");
    update(4'h3, 2'd2, 1'b0);                          // CPU2 evicts
    snoop(4'h3, 4'b0001, "CPU2 evicted -> snoop CPU0 only");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS [empty line -> no snoop] snoop_mask=0000
PASS [held by CPU2 -> snoop CPU2 only] snoop_mask=0100
PASS [held by CPU0+CPU2 -> snoop both] snoop_mask=0101
PASS [CPU2 evicted -> snoop CPU0 only] snoop_mask=0001

14. DebugLab — the filter that under-snoops

req_index  real_holders  snoop_mask  note
   0x9       0b1000       0b0000     CPU3 holds it, but mask is empty
                                     -> CPU3 never snooped -> its dirty data missed

15. Common Mistakes

• Thinking broadcast is fine because it works. Assumption: correct equals scalable. Bug: snoop network saturates at high core count. Prevention: broadcast is correct but O(N) in traffic and waits for all responders.
• Ignoring the wait-for-all latency. Assumption: latency is the average snoop. Bug: tail latency set by the slowest cache. Prevention: the interconnect completes only after every response; one slow cache stalls the access.
• Believing a snoop filter fully solves scaling. Assumption: filters make broadcast free. Bug: capacity limits force fallback broadcasts; the filter itself is centralized. Prevention: a filter reduces the constant, not the structure — a directory changes the structure.
• Letting a filter under-snoop. Assumption: if the filter says absent, skip the snoop. Bug: missed dirty holder, stale read (the DebugLab). Prevention: on any uncertainty, broadcast — never suppress a snoop you cannot prove is safe.
• Confusing "no entry" with "no holder." Assumption: an evicted filter entry means nobody holds the line. Bug: lost holder. Prevention: absence of knowledge is not absence of a copy.
• Assuming directories are strictly better. Assumption: always use a directory. Bug: paying directory storage where broadcast would do. Prevention: broadcast is simpler at small scale; directories win as cores grow — know the crossover.

16. Engineering Checklist

• Count snoops per coherent access as N − 1 under broadcast; ask if that scales for your core count.
• Remember the request completes only after all snoop responses — budget the tail, not the average.
• Estimate the wasted-snoop fraction — how often the line is held by nobody or one cache.
• If using a snoop filter, ensure a conservative broadcast fallback on eviction/uncertainty.
• Never under-snoop: covering every holder is correctness, not optimization.
• Reach for a directory (CHI) when broadcast traffic or tail latency becomes the bottleneck.

17. Key Takeaways

• ACE coherency is broadcast: every coherent request snoops every cache in the domain and waits for all responses.
• Three costs grow with cores: snoop traffic (O(N)), tail latency (slowest responder), and wasted snoops (most hit nothing).
• Snoop filters suppress absent-cache snoops by tracking presence — a big help, but a centralized, capacity-limited patch that must broadcast on uncertainty.
• The safety rule for any filter or directory: never under-snoop a holder — over-snoop is wasteful but correct; under-snoop is a coherency violation.
• The scalable answer is a distributed directory that snoops only the actual holders over a scalable network — that is CHI.
• The reasoning here is representative — the shape of the wall, not vendor numbers.

18. Quick Revision

ACE limitations. ACE coherency is broadcast: snoop every cache in the domain, wait for all responses. Three costs scale with cores N: snoop traffic (≈ N − 1 per request), tail latency (completion waits on the slowest responder), and wasted snoops (most caches do not hold the line). A snoop filter tracks a per-line presence vector and snoops only believed-holders — reducing wasted snoops — but it is centralized, capacity-limited, and must broadcast on uncertainty; it never may under-snoop a real holder (a Single-Writer violation). The scalable fix is a distributed directory that tracks exactly who holds each line and snoops only them, over a scalable network — CHI. Representative reasoning, not vendor numbers.

Coming Next

Chapter 3.6 — Scalability Challenges. This chapter named the broadcast costs; the next one quantifies them. We will look at how snoop bandwidth grows into a "snoop storm" as cores and coherent traffic rise, why the interconnect topology itself becomes a limit, and how those pressures sharpen the case for a directory-based, network-on-chip coherent fabric — the design space CHI occupies.