Scalability

Module 15 · Chapter 15.3 · CHI Performance

Project thread — 15.2 found one link's bottleneck. 15.3 scales the whole fabric to many nodes; 15.4 looks at per-core scaling.

1. Learning Outcomes

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

• Explain that a centralized resource caps aggregate throughput regardless of node count.
• State that this is the Amdahl serial fraction expressed in hardware.
• Describe how address interleaving across many home nodes distributes the load.
• Explain how a mesh provides bisection bandwidth that grows with node count.
• Diagnose the flat scalability curve from a single centralized home.
• Implement a representative home-selection model in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

Small-system performance and large-system performance are governed by different things. On a few nodes, latency and channel bandwidth (Chapters 15.1–15.2) dominate. At 64 nodes and beyond, the question becomes whether aggregate throughput keeps growing as you add nodes — and that is decided entirely by whether any resource is centralized. One shared point that every transaction touches makes the whole system scale like that one point: not at all.

The math is unforgiving. A centralized home or bus has fixed throughput; adding cores adds demand but not service capacity, so aggregate throughput plateaus and per-core throughput collapses. This is Amdahl's law in silicon — a serial fraction caps speedup no matter how much parallelism surrounds it. CHI is architected to have no such point: addresses are interleaved across many homes, the interconnect is a mesh, and the directory is distributed. Understanding this is understanding why CHI targets many-core SoCs at all — and how a single accidental centralization (a bad address hash) can throw all of it away.

3. Key Terms

4. Previous Chapter Connection

This chapter scales up the mechanisms of Modules 5 and 11. Home nodes (Chapter 5.x) serialize per-address coherence; directories (Chapter 11.1) track sharers. On a small system one home suffices — but at scale, one home is a serial bottleneck, and the fix is the distributed directory of Chapter 11.2, now seen through a throughput lens.

The address-to-home mapping is the key mechanism, and you met it in Chapter 11.2: an address determines its home by hashing address bits. This chapter reframes that mapping as the load-balancer it is — a good hash spreads transactions evenly across homes so they run in parallel, and a bad (or absent) one funnels everything to one home. Where Chapter 11.2 established distribution for capacity and locality, this chapter establishes it for scalable throughput — the reason CHI can grow to 64+ nodes at all.

5. Core Concept — distribute the bottleneck or plateau

Aggregate throughput scales with node count only if no resource is centralized; CHI distributes the home, directory, and interconnect so throughput grows with N.

• A centralized resource caps throughput. If every transaction passes through one home (or bus), aggregate throughput is fixed at that one resource's capacity — independent of N.
• Adding nodes cannot help. More cores add offered load but not service capacity at the centralized point, so the curve plateaus and per-core throughput falls as 1/N.
• Interleaving distributes the home. CHI maps addresses to many homes by hashing address bits, so different addresses are served by different homes in parallel — aggregate home throughput grows with the number of homes.
• The mesh distributes bandwidth. A mesh interconnect has bisection bandwidth that grows with node count, unlike a shared bus whose bandwidth is fixed. Directory tracking is distributed alongside the homes.

The synthesis:

Aggregate throughput scales with node count N only if no resource is centralized. A single home or shared bus has fixed throughput, so adding nodes adds load but not capacity — the scalability curve plateaus (Amdahl's serial fraction). CHI distributes the bottleneck: addresses interleaved across many homes, a mesh interconnect, a distributed directory — so aggregate throughput grows ~O(N). A single centralized point throws all of it away.

6. Engineering Mental Model — one checkout vs many

Think of a supermarket handling a growing crowd of shoppers (nodes).

• With one checkout lane (a centralized home), it does not matter how many shoppers arrive — they are served one at a time at a fixed rate. Double the shoppers and the line just gets twice as long; throughput is unchanged.
• Adding more shoppers (cores) to a one-lane store adds demand, not capacity. The lane is the serial bottleneck; everything queues behind it.
• Open many lanes (distributed homes) and assign shoppers to lanes by a rule that spreads them evenly (address interleaving) — now shoppers check out in parallel, and total throughput grows with the number of lanes.
• The rule matters: if every shopper is sent to lane 1 (a bad hash), the other lanes sit idle and you are back to one-lane throughput. The distribution is only as good as the assignment.

One lane is the centralized home; many well-balanced lanes are interleaved homes. Scaling the store means opening lanes and spreading shoppers across them.

7. Engineering Diagram — centralized vs distributed homes

Top row: one home, all traffic, a flat curve. Bottom row: many homes, interleaved addresses, a rising curve. The only structural difference is how many homes the addresses are spread across — and that difference is the whole scalability story.

8. Centralized vs Distributed

The two architectures contrasted.

The rule to carry: any resource on the path of every transaction must be distributed, or it becomes the serial fraction that caps the system. The home (serializing per-address coherence), the directory (tracking sharers), and the interconnect (carrying flits) are all such resources — and CHI distributes all three. Interleaving spreads homes; the mesh spreads interconnect bandwidth; the distributed directory spreads tracking. Miss any one and it becomes the plateau, however well the others scale.

9. Interleaving as a Load Balancer

The address-to-home mapping is what makes distribution work.

• Hash address bits to a home. The home for an address is chosen by hashing some of its bits — typically middle bits, so consecutive cache lines spread across different homes.
• Even spread means parallel service. A good hash sends roughly 1/N of traffic to each of N homes, so they work in parallel and aggregate throughput is N× one home.
• A bad hash re-centralizes. If the hash sends most traffic to one home (e.g. keying on bits that rarely vary), that home is a hotspot — effectively centralized again, and the curve flattens (Chapter 15.7 revisits hotspots).
• Interleave granularity matters. Interleaving at cache-line granularity spreads a sequential stream across all homes; interleaving at a coarse granularity can leave a hot region on one home.

The point to carry:

Scalability is a structural property, and structure is set by the address map, not by adding hardware. You can build 64 home nodes, a full mesh, and a distributed directory — every ingredient for O(N) scaling — and still get a flat curve if the address-to-home hash funnels traffic to one home. The homes exist, but the map does not use them. This is why the interleaving hash is one of the most performance-critical lines in the whole design: it is the single point that decides whether the distributed hardware is actually used in parallel or merely present. A well-designed hash spreads any realistic address stream — sequential, strided, random — evenly across homes; a naive one (say, the top address bits, which a single large buffer never changes) sends a whole workload to one home. The lesson generalizes: distribution requires both the resources and a mapping that spreads load across them, and the mapping is the part most easily gotten wrong.

10. Scaling a System — flat vs rising

The same hardware, two address maps, as node count grows.

1. 8 nodes, one home. All addresses map to home 0. Home 0 serves at its fixed rate; aggregate throughput = one home's capacity.
2. Grow to 64 nodes, still one home. Eight times the cores, all still funneling to home 0. Home 0 is 100% utilized; the other 63 potential homes are idle. Aggregate throughput: unchanged — a flat curve.
3. 8 nodes, interleaved homes. Addresses spread across 8 homes. Aggregate throughput ≈ 8× one home — the homes serve in parallel.
4. Grow to 64 nodes, interleaved. Addresses spread across 64 homes; aggregate throughput ≈ 64× one home — the curve keeps rising with N.

The interleaved system scaled 8× from step 3 to step 4; the centralized one scaled 0× from step 1 to step 2. Same cores, same mesh — only the address map differed. The DebugLab is the centralized map at step 2.

11. RTL / Hardware View — home selection by interleaving

An address selects its home by hashing address bits, spreading load across the homes. Representative.

// Representative home-selection (address interleaving) model (educational).
// The home for an address is chosen by hashing address bits -- spreading consecutive
// cache lines across DIFFERENT homes so traffic is served in PARALLEL. A degenerate
// mapping (all addresses -> one home) re-centralizes and flattens scalability.
module chi_home_select #(parameter NUM_HOMES = 8, parameter AW = 44, parameter LW = 6) (
  input  logic [AW-1:0]              addr,        // physical address
  output logic [$clog2(NUM_HOMES)-1:0] home_id    // selected home node
);
  // Use bits just above the cache-line offset (LW) so consecutive lines interleave.
  // XOR in some higher bits to whiten the distribution against strided patterns.
  localparam SEL = $clog2(NUM_HOMES);
  logic [SEL-1:0] lo, hi;
  assign lo = addr[LW +: SEL];
  assign hi = addr[LW+SEL +: SEL];
  assign home_id = lo ^ hi;     // balanced hash across NUM_HOMES
endmodule

The same behavior in Verilog-2001:

// Representative home-selection model (Verilog-2001).
module chi_home_select #(parameter NUM_HOMES = 8, parameter AW = 44, parameter LW = 6,
                         parameter SEL = 3) (
  input  [AW-1:0]   addr,
  output [SEL-1:0]  home_id
);
  wire [SEL-1:0] lo = addr[LW +: SEL];
  wire [SEL-1:0] hi = addr[LW+SEL +: SEL];
  assign home_id = lo ^ hi;     // interleave across homes
endmodule

And in VHDL:

-- Representative home-selection model (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity chi_home_select is
  generic ( AW : integer := 44; LW : integer := 6; SEL : integer := 3 );
  port (
    addr    : in  std_logic_vector(AW-1 downto 0);
    home_id : out std_logic_vector(SEL-1 downto 0)
  );
end entity;
 
architecture rtl of chi_home_select is
  signal lo, hi : std_logic_vector(SEL-1 downto 0);
begin
  lo <= addr(LW+SEL-1 downto LW);            -- bits above the line offset
  hi <= addr(LW+2*SEL-1 downto LW+SEL);      -- next bits, to whiten
  home_id <= lo xor hi;                       -- balanced interleave
end architecture;

All three derive home_id from address bits above the line offset, spreading consecutive lines across homes. A design that instead ties home_id to a constant (or top bits that rarely vary) funnels traffic to one home — the DebugLab.

12. Verification View — the map spreads load across homes

The properties check the interleaving distributes addresses: consecutive lines differ, and the map uses all homes.

// Bind to chi_home_select.
// 1. Consecutive cache lines map to DIFFERENT homes (interleaving works).
property p_consecutive_lines_spread;
  logic [AW-1:0] a;
  @(*) (1) |-> (chi_home_select_f(a) != chi_home_select_f(a + (1<<LW)));
endproperty
// (checked by sweeping addresses: adjacent lines land on different homes)
 
// 2. Over a sweep of addresses, ALL home ids are produced (no idle homes).
//    coverage: home_id hits every value 0..NUM_HOMES-1.
 
// 3. A degenerate map (home_id constant) fails coverage -> only one home ever used.
//    This is the DebugLab configuration and must be caught.

The system point, beyond the checks:

Scalability is best verified by coverage, not by an assertion, because the property "throughput scales with N" is not a single-trace fact — it is a statement about the distribution of home assignments over the whole address space. So the verification artifact is a sweep: drive a realistic address stream (sequential, strided, random) through the home-select function and confirm the resulting home-id histogram is flat — every home gets roughly 1/N of the traffic. A degenerate or skewed hash shows up immediately as a spiky histogram, one home towering over the rest, which is the scalability curve's plateau in a different chart. This reframes a performance property as a balance property: the fabric scales iff the load is balanced across the distributed resources, and load balance is directly measurable from the address map long before silicon. The same sweep, run per workload, is also how Chapter 15.7's hotspots are found — an unbalanced histogram is a hotspot in waiting.

• What it proves: the map spreads consecutive lines and uses all homes.
• What it does not prove: a real workload's address stream is well-distributed — that requires profiling.
• Bug signature: a home-id histogram with one tall bar — a centralized hotspot.

13. Testbench — interleaving must use all homes

Sweeps addresses and checks the home distribution is balanced, not centralized.

module tb_chi_home_select;
  localparam NUM_HOMES = 8, AW = 44, LW = 6, SEL = 3;
  logic [AW-1:0] addr;
  logic [SEL-1:0] home_id;
  int hits [8];
  int errors = 0, i;
 
  chi_home_select #(.NUM_HOMES(NUM_HOMES), .AW(AW), .LW(LW)) dut (.*);
 
  initial begin
    foreach (hits[i]) hits[i] = 0;
    // Sweep 512 consecutive cache lines; a good interleave spreads them across homes.
    for (i = 0; i < 512; i++) begin
      addr = i << LW;          // consecutive cache lines
      #1;
      hits[home_id]++;
    end
    // Every home must receive some traffic (no idle homes), roughly balanced.
    for (i = 0; i < NUM_HOMES; i++) begin
      $display("home %0d: %0d lines", i, hits[i]);
      if (hits[i] == 0) begin errors++; $display("FAIL home %0d idle (centralized?)", i); end
    end
    // No single home should dominate (balanced within ~2x of the mean 512/8 = 64).
    for (i = 0; i < NUM_HOMES; i++)
      if (hits[i] > 128) begin errors++; $display("FAIL home %0d hotspot: %0d", i, hits[i]); end
 
    if (errors == 0) $display("ALL TESTS PASSED (balanced across %0d homes)", NUM_HOMES);
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

home 0: 64 lines
home 1: 64 lines
...
home 7: 64 lines
ALL TESTS PASSED (balanced across 8 homes)

14. DebugLab — all addresses to a single home

system: 64 homes, full mesh (capable of ~64x parallel service)
home-select: home_id = addr[43:41]   (top bits -- constant for this workload's region)
  -> every address in the working set -> home 0
  -> home 0: 100% utilized; homes 1..63: idle
add cores: offered load rises, home-0 capacity fixed -> throughput FLAT
correct: home_id = addr[8:6] ^ addr[11:9]  (bits above line offset)
  -> consecutive lines spread across all 64 homes -> ~64x aggregate throughput

15. Common Mistakes

• Centralizing the home. Assumption: one home is simpler. Bug: flat scaling (the DebugLab). Prevention: interleave across many homes.
• Hashing on invariant bits. Assumption: any bits work. Bug: a hotspot home. Prevention: hash varying bits above the line offset.
• Coarse interleave granularity. Assumption: block interleaving is fine. Bug: a hot region on one home. Prevention: line-granularity interleave.
• A shared bus at scale. Assumption: a bus suffices. Bug: fixed bisection bandwidth. Prevention: a mesh that grows with N.
• Distributing homes but not the directory. Assumption: homes are enough. Bug: the directory re-centralizes. Prevention: distribute the directory too.
• Counting hardware, not balance. Assumption: more homes = more throughput. Bug: unused homes. Prevention: verify a balanced map.

16. Engineering Checklist

• Distribute the home, directory, and interconnect — no single serial point.
• Interleave addresses across homes by hashing bits above the line offset.
• Choose a hash that spreads sequential, strided, and random streams evenly.
• Use a mesh so bisection bandwidth grows with node count.
• Sweep addresses and confirm a balanced home histogram.
• Verify aggregate throughput rises with N, not plateaus.

17. Key Takeaways

• Aggregate throughput scales with N only if no resource is centralized.
• A centralized home or bus is the Amdahl serial fraction — a fixed cap.
• CHI interleaves addresses across many homes to serve them in parallel.
• A mesh provides bisection bandwidth that grows with node count.
• A single centralized point flattens the scalability curve, wasting distributed hardware.
• Scalability is a property of the map, not the part count; the model here is representative.

18. Quick Revision

Scalability. Aggregate throughput scales with node count N only if no resource is centralized. Any point every transaction must pass through — a single home and its directory, or a shared bus — serializes the system: its throughput is fixed, so adding cores adds load but not capacity, and the scalability curve plateaus while per-core throughput falls as 1/N. This is Amdahl's serial fraction in hardware. CHI avoids it by distributing: addresses are interleaved across many home nodes (chosen by hashing bits above the cache-line offset, so consecutive lines spread across homes served in parallel); the interconnect is a mesh whose bisection bandwidth grows with N; and the directory is distributed alongside the homes. So aggregate throughput grows ~O(N). The failure to avoid: mapping all addresses to one home — through no interleaving or a hash on invariant bits — so every transaction serializes through that home, adding cores adds only load, and throughput stays flat while the lone home is 100% utilized and the other homes sit idle. Scalability is a property of the address map, not the part count — distribute the map, not just the hardware, and verify a balanced home histogram. Representative model; 15.4 turns to per-core scaling under shared-resource contention.

Coming Next

Chapter 15.4 — Multi-Core Scaling. Distributing the fabric lets aggregate throughput grow; per-core throughput is a separate story once cores contend for a shared resource. Chapter 15.4 covers multi-core scaling — why per-core performance falls as cores are added past the point where a shared resource (memory bandwidth) saturates, why total throughput then plateaus regardless of the fabric, and how to recognize the shared-resource ceiling.