Scalability Challenges

Module 3 · Chapter 3.6 · Why CHI Exists

Project thread — 3.5 showed broadcast does not scale; this chapter quantifies the snoop-bandwidth wall and the snoop storm. 3.7 turns to the topology answer — coherent fabrics.

1. Learning Outcomes

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

• Compute snoop message count per coherent request and system-wide, as core count scales.
• Explain why broadcast snoop demand grows as O(N²) while a shared medium's bandwidth is fixed.
• Define a snoop storm and identify the workloads (locks, shared lines) that trigger one.
• Read a queue-depth waveform showing the snoop backlog saturating under a burst.
• Model snoop bandwidth as a service-rate-limited queue in SystemVerilog, Verilog-2001, and VHDL.
• Justify the directory-plus-NoC answer with the bandwidth argument, not just intuition.

2. Why Should I Learn This?

This chapter turns "broadcast does not scale" into arithmetic you can defend in a design review. The O(N²) snoop-demand argument, and the snoop storm it produces, are the quantitative core of the case for CHI. Once you can put numbers on it, the directory stops being a nice idea and becomes a necessity above a certain core count.

It is also directly practical: snoop storms are a real cause of performance cliffs in multi-core systems — a shared lock or a hot cache line that suddenly serializes the whole machine through the coherency fabric. Recognizing the signature (coherent latency exploding under load while compute sits idle) is a debugging skill.

3. Key Terms

4. Previous Chapter Connection

Chapter 3.5 established the shape of the problem: broadcast snoops every cache, waits for all responses, and wastes most snoops. It counted snoops per request as N−1 and pointed at the directory.

This chapter adds the second dimension — rate. It is not just that one request costs N−1 snoops; it is that N cores issue such requests concurrently, and they must all share one snoop medium of fixed bandwidth. Multiply per-request cost by request rate by core count and the demand curves away from what any shared medium can serve. That is the wall, and its worst case is the snoop storm.

5. Core Concept — the snoop-bandwidth wall

Three quantities turn broadcast from "costly" into "does not scale."

• Per-request cost is O(N). One coherent request broadcasts N−1 snoops and collects N−1 responses — about 2(N−1) snoop messages.
• System-wide demand is O(N²). With N cores each generating coherent requests, total snoop demand scales as N × (N−1) ≈ N². Double the cores and snoop traffic roughly quadruples.
• Snoop bandwidth is fixed. A shared snoop medium — a broadcast bus or ring — has a bandwidth that does not grow with the traffic offered to it. Demand rises as N²; supply is flat.

When demand exceeds supply, the backlog builds:

A snoop storm happens when bursty coherent activity pushes snoop demand above snoop bandwidth. The snoop queue fills, new coherent requests hit backpressure, and every coherent access waits behind the backlog. Compute can sit idle while the machine serializes on coherency traffic. This is not a corner case — a hot lock or a shared counter, touched by many cores, produces exactly this pattern.

The directory changes the arithmetic:

• A directory cuts snoops from O(N) to O(sharers) — usually one or two — so system demand falls from O(N²) toward O(N × average-sharers). Paired with a network-on-chip, whose aggregate bandwidth grows with nodes, supply scales with demand. That pairing — directory plus NoC — is CHI.

6. Engineering Mental Model — one phone line for the whole office

Imagine coordinating a large office through one shared phone line.

• Every decision requires calling everyone and waiting for all to answer (a broadcast snoop). With a few people, fine.
• As the office grows, calls pile up on the single line. Two people, four calls; ten people, ninety calls — the calls grow with the square of the headcount, but the line still carries one call at a time.
• On a busy morning (a storm — everyone needs a decision at once), the line jams. Nobody can get through; work halts, not because people are busy working, but because they are all waiting on the line.
• The fix is not a faster single line. It is a directory (call only the two people who matter) plus many lines (a network that adds capacity as you add people). That is CHI's directory-plus-NoC.

7. Engineering Diagram — the snoop medium as bottleneck

All four cores share one medium. Add cores and each coherent request still crosses this single interconnect — which is why its fixed bandwidth, not the cores, sets the ceiling.

8. Worked Example — snoop bandwidth as N scales

Count snoop messages per coherent request and the relative system-wide demand, assuming each core issues coherent requests at a similar rate.

From 4 to 32 cores (8×), per-request snoop cost grows ~10×, but system-wide demand grows ~80× — the quadratic term. Meanwhile a shared snoop medium's bandwidth is unchanged. Two facts to carry: the pain is in the system column (N²), and no amount of per-request tuning bends a quadratic back to linear — you must reduce the snoop count (directory) and scale the medium (NoC).

9. The Snoop Storm — saturation on a waveform

A burst of coherent requests makes the snoop backlog visible: the queue fills faster than the snoop bus can drain it, saturates, and only then recovers.

The gap between the burst (cycles 0–2) and completion (cycle 7) is pure coherency-fabric latency — the cores did no more work, they waited for the snoop backlog. Scale the core count and both the backlog height and the wait grow.

10. Transaction Walkthrough — a shared-lock storm

The classic trigger: many cores contending on one lock line.

1. Contention. Sixteen cores spin on a lock — each repeatedly issues a coherent read (and, on acquire attempts, a read-for-ownership) of the same line.
2. Broadcast per attempt. Every attempt broadcasts snoops to the other fifteen caches. Sixteen cores spinning means a continuous flood of snoops for one line.
3. Queue fills. Snoop demand for this single hot line alone can exceed the snoop bus's service rate. The queue climbs to capacity and asserts backpressure.
4. Everything stalls. Backpressure blocks unrelated coherent traffic too — the whole fabric is behind the storm. Coherent latency for every core climbs.
5. Collapse. Throughput drops even though the cores are mostly idle, spinning — the machine is serialized on snoop bandwidth for one lock.

A directory would snoop only the lock's actual holders (one or two), and a NoC would keep unrelated traffic on other paths — the storm never forms.

11. RTL / Hardware View — a snoop-bandwidth queue model

Here is the storm as hardware: a queue whose depth is the pending-snoop backlog. Coherent requests enqueue several snoops each; the snoop bus dequeues a fixed few per cycle. When arrival outruns service, depth climbs and saturates. Representative and simplified — a bandwidth abstraction, not a real snoop network.

// Representative snoop-bandwidth queue (educational, not a real snoop network).
// Each coherent request enqueues (NCACHES-1) snoops; the bus services SERVICE
// per cycle. depth is the backlog; it grows when arrival > service (a storm)
// and clamps at CAP, where the interconnect must apply backpressure.
module snoop_queue #(
  parameter int NCACHES = 4,
  parameter int SERVICE = 2,       // snoops issued per cycle (fixed bandwidth)
  parameter int CAP     = 32       // queue capacity
)(
  input  logic       clk,
  input  logic       rst_n,
  input  logic       coh_req,      // a coherent request arrives this cycle
  output logic [5:0]  depth,       // pending snoops (the backlog)
  output logic        saturated    // queue full -> backpressure
);
  logic [5:0] q;
  wire [5:0] arriving = coh_req ? (NCACHES - 1) : 6'd0;         // broadcast fan-out
  wire [5:0] serviced = (q > SERVICE) ? SERVICE[5:0] : q;        // drain up to SERVICE
  wire [5:0] next     = q + arriving - serviced;                 // serviced <= q: no underflow
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) q <= 6'd0;
    else        q <= (next > CAP) ? CAP[5:0] : next;             // clamp at capacity
  end
  assign depth     = q;
  assign saturated = (q >= CAP[5:0]);
endmodule

The same behavior in Verilog-2001:

// Representative snoop-bandwidth queue (Verilog-2001).
module snoop_queue #(
  parameter NCACHES = 4,
  parameter SERVICE = 2,
  parameter CAP     = 32
)(
  input        clk, rst_n, coh_req,
  output [5:0] depth,
  output       saturated
);
  reg  [5:0] q;
  wire [5:0] arriving = coh_req ? (NCACHES - 1) : 6'd0;
  wire [5:0] serviced = (q > SERVICE) ? SERVICE[5:0] : q;
  wire [5:0] next     = q + arriving - serviced;
  always @(posedge clk or negedge rst_n)
    if (!rst_n) q <= 6'd0;
    else        q <= (next > CAP) ? CAP[5:0] : next;
  assign depth     = q;
  assign saturated = (q >= CAP[5:0]);
endmodule

And in VHDL:

-- Representative snoop-bandwidth queue (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity snoop_queue is
  generic ( NCACHES : integer := 4; SERVICE : integer := 2; CAP : integer := 32 );
  port (
    clk, rst_n : in  std_logic;
    coh_req    : in  std_logic;
    depth      : out std_logic_vector(5 downto 0);
    saturated  : out std_logic
  );
end entity;
 
architecture rtl of snoop_queue is
  signal q : unsigned(5 downto 0) := (others => '0');
begin
  process(clk, rst_n)
    variable arriving, serviced, nxt : unsigned(5 downto 0);
  begin
    if rst_n = '0' then
      q <= (others => '0');
    elsif rising_edge(clk) then
      if coh_req = '1' then arriving := to_unsigned(NCACHES - 1, 6);
      else                  arriving := (others => '0'); end if;
      if q > SERVICE then serviced := to_unsigned(SERVICE, 6);
      else                serviced := q; end if;
      nxt := q + arriving - serviced;               -- serviced <= q: no underflow
      if nxt > CAP then q <= to_unsigned(CAP, 6);
      else              q <= nxt; end if;
    end if;
  end process;
 
  depth     <= std_logic_vector(q);
  saturated <= '1' when q >= to_unsigned(CAP, 6) else '0';
end architecture;

All three make the storm mechanical: arrival adds NCACHES−1 per request, service removes a fixed SERVICE per cycle. Hold coh_req high and, whenever NCACHES−1 exceeds SERVICE, the backlog climbs to CAP and stays — saturation.

12. Verification View — the backlog is bounded but can pin at the cap

Two properties: the queue never exceeds capacity, and it drains when idle — but under sustained load it saturates, which is the whole point.

// Bind to snoop_queue (NCACHES=4, SERVICE=2, CAP=32).
// 1. The backlog never exceeds capacity (clamped).
property p_bounded;
  @(posedge clk) disable iff (!rst_n) depth <= CAP;
endproperty
assert property (p_bounded);
 
// 2. With no new requests and a non-empty queue, the backlog strictly drains.
property p_drains_when_idle;
  @(posedge clk) disable iff (!rst_n)
    (!coh_req && depth != 0) |=> (depth < $past(depth));
endproperty
assert property (p_drains_when_idle);

The system point, beyond the two checks:

These properties describe a stable queue — bounded, and draining when idle. The scalability failure is not a broken invariant; it is a saturated one. When the offered snoop rate (∝ N per request, across N cores) sits above the service rate for a sustained period, saturated stays high and depth pins at CAP. The hardware is behaving correctly and the system is still collapsing — because the demand is O(N²) and the supply is fixed. No RTL fix inside this block helps; the answer is a different architecture.

• What it proves: the backlog is bounded and recovers when the burst ends.
• What it does not prove: that the fabric can keep up under sustained many-core sharing — it structurally cannot (the DebugLab).
• Bug signature: saturated high for long stretches with coherent latency climbing while compute is idle.

13. Testbench — drive a burst and watch it saturate

Applies a sustained coherent-request burst (arrival 3/cycle) against SERVICE=2, then idles to observe draining.

module tb_snoop_queue;
  logic clk = 0, rst_n, coh_req;
  logic [5:0] depth;
  logic saturated;
 
  snoop_queue #(.NCACHES(4), .SERVICE(2), .CAP(32)) dut (.*);
  always #5 clk = ~clk;
 
  task automatic step(input logic req, input string tag);
    coh_req = req;
    @(posedge clk); #1;
    $display("[%s] coh_req=%b depth=%0d saturated=%b", tag, coh_req, depth, saturated);
  endtask
 
  initial begin
    rst_n = 0; step(0, "reset"); rst_n = 1;
    // Sustained burst: +3 per cycle, -2 serviced -> net +1 each cycle -> climbs.
    repeat (10) step(1, "burst");
    // Idle: no arrivals, -2 per cycle -> drains.
    repeat (20) step(0, "idle");
    $display("DONE");
    $finish;
  end
endmodule

Expected output (abridged — depth climbs under the burst, saturates near the cap, then drains to zero when idle):

[reset] coh_req=0 depth=0 saturated=0
[burst] coh_req=1 depth=1 saturated=0
[burst] coh_req=1 depth=2 saturated=0
[burst] coh_req=1 depth=3 saturated=0
...
[burst] coh_req=1 depth=10 saturated=0
[idle]  coh_req=0 depth=8 saturated=0
[idle]  coh_req=0 depth=6 saturated=0
...
[idle]  coh_req=0 depth=0 saturated=0
DONE

14. DebugLab — a shared lock that never lets go

cyc  coh_req  depth  saturated  note
 ..    1       30       0        climbing
 ..    1       32       1        at CAP -> backpressure
 ..    1       32       1        stays pinned while cores keep spinning
 ..    1       32       1        unrelated coherent traffic now stalled too

15. Common Mistakes

• Counting per-request cost only. Assumption: N−1 snoops per request is the whole story. Bug: missing the O(N²) system demand. Prevention: multiply by request rate and core count — the square term dominates.
• Assuming a faster bus fixes it. Assumption: more snoop bandwidth solves scaling. Bug: a fixed medium still loses to quadratic demand. Prevention: bend the curve (directory) and scale the medium (NoC), not just clock it faster.
• Ignoring backpressure's blast radius. Assumption: a storm only slows the hot line. Bug: a full snoop queue stalls unrelated coherent traffic too. Prevention: shared-medium saturation is global, not local.
• Blaming the workload alone. Assumption: just avoid shared locks. Bug: real software shares data; the fabric must cope. Prevention: the architecture, not only the workload, must scale.
• Reading saturation as a functional bug. Assumption: a pinned queue is broken RTL. Bug: chasing a fix in the wrong layer. Prevention: correct hardware can still saturate — the defect is architectural.
• Forgetting topology. Assumption: only snoop count matters. Bug: even few snoops choke on a shared medium. Prevention: a scalable topology (NoC) is half the answer (Chapter 3.7).

16. Engineering Checklist

• Estimate snoops per coherent request as N−1, and system demand as ∝ N².
• Compare offered snoop rate against the medium's fixed snoop bandwidth.
• Identify hot lines (locks, shared counters) that can trigger a storm.
• Watch for backpressure stalling unrelated coherent traffic under load.
• Plan for a directory to cut snoop count and a NoC to scale bandwidth above a core-count threshold.
• Read sustained saturation as an architectural limit, not an RTL bug.

17. Key Takeaways

• One coherent request costs O(N) snoops; N cores make system-wide snoop demand O(N²).
• A shared snoop medium has fixed bandwidth — demand rises as N², supply stays flat.
• A snoop storm is bursty coherent demand exceeding snoop bandwidth: the queue saturates and backpressure stalls the whole fabric.
• Hot shared lines (locks, counters) touched by many cores are the classic storm trigger — throughput collapses while cores spin idle.
• Saturation is not an RTL bug; it is the broadcast architecture hitting its ceiling — the fix is a directory (fewer snoops) plus a NoC (more bandwidth): CHI.
• The reasoning here is representative — the O(N²) shape and storm dynamics, not vendor numbers.

18. Quick Revision

Scalability challenges. One coherent request = N−1 snoops + N−1 responses ≈ 2(N−1) messages, so N cores drive O(N²) system-wide snoop demand. A shared snoop medium (bus/ring) has fixed bandwidth — demand grows quadratically, supply is flat. A snoop storm is a burst (e.g. many cores on one lock) whose snoop demand exceeds bandwidth: the snoop queue saturates, backpressure stalls even unrelated coherent traffic, and throughput collapses while cores spin idle. Correct hardware can still saturate — the limit is architectural. The fix: a directory (snoops → O(sharers), often 1) plus a network-on-chip (bandwidth scales with nodes) — that pairing is CHI. Representative reasoning, not vendor numbers.

Coming Next

Chapter 3.7 — Coherent Fabrics. The snoop storm makes half the case — snoop count must drop. The other half is topology: the shared bus or ring itself must give way to a scalable structure. The next chapter traces the move from shared buses to network-on-chip coherent fabrics, showing how a mesh of routers carries coherent traffic with bandwidth that grows as the system grows — the physical substrate CHI's directory-based protocol runs on.