Coherent Fabrics

Module 3 · Chapter 3.7 · Why CHI Exists

Project thread — 3.6 argued the snoop count must fall (directory). This chapter argues the medium must change (mesh NoC). 3.8 closes the module by stating CHI's design goals.

1. Learning Outcomes

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

• Trace the interconnect topology evolution: shared bus → ring → crossbar → mesh NoC.
• Compare topologies on latency, bisection bandwidth, and area as node count scales.
• Explain why a mesh NoC scales where a shared medium cannot — packets, hops, growing bisection.
• Describe how coherent traffic becomes packets routed hop by hop, with distributed Home Nodes.
• Implement a dimension-order (X-Y) mesh router in SystemVerilog, Verilog-2001, and VHDL.
• State why dimension-order routing is deadlock-free, and how breaking it hangs the fabric.

2. Why Should I Learn This?

Chapter 3.6 solved half the scaling problem — cut the snoop count with a directory. But even one snoop chokes on a shared medium under load. The other half is topology: the wires themselves must become a network whose bandwidth grows with the system. CHI is defined as a protocol for such a fabric — packet-based, layered, credited — and none of that makes sense without knowing what a mesh NoC is and why it won.

It is also foundational for everything after this module. CHI's Home Nodes, request/response/snoop/data channels, and flow control are all shaped by running over a mesh of routers. Learn the fabric now and CHI's structure will look inevitable.

3. Key Terms

4. Previous Chapter Connection

Chapter 3.6 quantified the snoop-bandwidth wall and named a two-part fix: a directory to cut snoop count, and a network-on-chip to scale bandwidth. It handled the first part. This chapter handles the second.

The distinction matters: even with a directory reducing snoops to one or two, those messages still have to travel. On a shared bus or ring they contend for one medium; the medium, not the snoop count, becomes the limit. Only a topology whose bandwidth grows with the system removes that limit — and that is what a mesh NoC provides, and what CHI is built to run on.

5. Core Concept — from one wire to a network

Interconnect topology evolved under one pressure: aggregate bandwidth that scales with nodes.

• Shared bus. One medium, one transfer at a time (Chapter 3.2). Minimal wiring, but bandwidth is fixed and contention grows with masters. Fine for a few nodes.
• Ring. Nodes linked in a loop; a transfer hops around. Distributed arbitration and pipelining beat a bus, but average latency grows with node count (about half the ring), and bisection bandwidth stays low. Scales to roughly a dozen nodes.
• Crossbar. An all-to-all switch: any node reaches any other in one hop at full bandwidth. Ideal latency — but area and wiring grow as N², so it does not scale past small N.
• Mesh network-on-chip. A 2-D grid of routers, each attached to a node. Traffic moves as packets, routed hop by hop. Area grows as N, average hop count as √N, and — crucially — bisection bandwidth grows with the grid width. This is the scalable point in the design space.

The mesh wins because supply scales with demand:

On a mesh, adding nodes adds routers and links, so the network's aggregate and bisection bandwidth grow with the system. Coherent messages are independent packets that route concurrently over many paths — no shared medium to serialize on. Sharding the directory across distributed Home Nodes means directory bandwidth scales too. Directory (Chapter 3.6) plus mesh NoC (here) is the fabric CHI runs on.

6. Engineering Mental Model — roads, not a single doorway

Compare moving people through a building.

• A shared bus is a single doorway: everyone queues through one opening. Simple, and hopeless at scale.
• A ring is a circular corridor: you walk around to your destination — better flow, but a long way round as the building grows.
• A crossbar is a private hallway from every room to every other room: instant, but the walls to build them all consume the whole floor (N² area).
• A mesh NoC is a city street grid: intersections (routers) and blocks (links). You travel corner to corner (hops), many people move at once on different streets, and adding neighborhoods adds streets — capacity grows with the city. That is why cities use grids, and why many-core chips use meshes.

7. Engineering Diagram — a mesh network-on-chip

The Home Node sits in the mesh, not at the end of a bus. Its directory (Chapter 3.6) is one slice of the address space; other Home Nodes hold other slices, so directory lookups spread across the grid instead of funneling through one point.

8. Worked Example — topologies as nodes scale

Compare the four topologies on the metrics that decide scaling. Representative asymptotics, not exact figures.

The mesh is the only row with no disqualifying term: latency grows slowly (√N), bisection bandwidth grows with the grid, and area stays linear. Two facts to carry: the bus and ring fail on bandwidth (fixed), the crossbar fails on area (N²), and the mesh trades a little latency for bandwidth that scales — the trade a many-core coherent fabric must make.

9. Transaction Walkthrough — a packet crosses the mesh

Follow a coherent request from CPU at (0,0) to the Home Node at (1,1) under X-Y routing:

1. Packetize. The request becomes a packet carrying its destination coordinates — the Home Node that owns this address, at (1,1).
2. Route X first. At router (0,0), the destination X (1) is greater than the current X (0), so the packet leaves East to (1,0).
3. Then route Y. At (1,0), X now matches (1 = 1), and destination Y (1) is greater than current Y (0), so the packet leaves South to (1,1).
4. Arrive. At (1,1) both coordinates match — the packet is delivered to the local port: the Home Node.
5. Concurrency. Meanwhile, other packets route over other links entirely — no shared medium serializes them.

Two hops, chosen locally at each router by comparing coordinates. No global arbiter, no broadcast — just independent packets flowing over a grid whose capacity grows with its size.

10. RTL / Hardware View — a dimension-order mesh router

The heart of a mesh is the routing decision: at each router, pick the output port from the packet's destination and the router's own position. Here is dimension-order (X-Y) routing — route in X until aligned, then in Y. Representative and combinational — the routing function, not a full router with buffers and arbitration.

// Representative dimension-order (X-Y) mesh router decision (educational).
// Route in X until the column matches, then in Y, then deliver locally.
// X-Y (dimension-order) routing is deadlock-free: it never creates a cyclic
// dependency between channels.
module xy_router #(
  parameter int W = 3                     // coordinate width (grid up to 2^W)
)(
  input  logic [W-1:0] my_x,  my_y,       // this router's position
  input  logic [W-1:0] dst_x, dst_y,      // packet destination
  output logic [2:0]   out_port           // 0=Local,1=North,2=South,3=West,4=East
);
  localparam logic [2:0] LOCAL = 3'd0, NORTH = 3'd1, SOUTH = 3'd2,
                         WEST  = 3'd3, EAST  = 3'd4;
  always_comb begin
    if      (dst_x > my_x) out_port = EAST;    // resolve X first
    else if (dst_x < my_x) out_port = WEST;
    else if (dst_y > my_y) out_port = SOUTH;   // X aligned: resolve Y
    else if (dst_y < my_y) out_port = NORTH;
    else                   out_port = LOCAL;    // arrived
  end
endmodule

The same behavior in Verilog-2001:

// Representative dimension-order (X-Y) mesh router decision (Verilog-2001).
module xy_router #(
  parameter W = 3
)(
  input      [W-1:0] my_x, my_y,
  input      [W-1:0] dst_x, dst_y,
  output reg [2:0]   out_port
);
  localparam LOCAL = 3'd0, NORTH = 3'd1, SOUTH = 3'd2, WEST = 3'd3, EAST = 3'd4;
  always @* begin
    if      (dst_x > my_x) out_port = EAST;
    else if (dst_x < my_x) out_port = WEST;
    else if (dst_y > my_y) out_port = SOUTH;
    else if (dst_y < my_y) out_port = NORTH;
    else                   out_port = LOCAL;
  end
endmodule

And in VHDL:

-- Representative dimension-order (X-Y) mesh router decision (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity xy_router is
  generic ( W : integer := 3 );
  port (
    my_x,  my_y  : in  unsigned(W-1 downto 0);
    dst_x, dst_y : in  unsigned(W-1 downto 0);
    out_port     : out std_logic_vector(2 downto 0)   -- 0=L,1=N,2=S,3=W,4=E
  );
end entity;
 
architecture rtl of xy_router is
begin
  process(my_x, my_y, dst_x, dst_y)
  begin
    if    dst_x > my_x then out_port <= "100";   -- East
    elsif dst_x < my_x then out_port <= "011";   -- West
    elsif dst_y > my_y then out_port <= "010";   -- South
    elsif dst_y < my_y then out_port <= "001";   -- North
    else                    out_port <= "000";   -- Local (arrived)
    end if;
  end process;
end architecture;

All three resolve X before Y and deliver locally only when both coordinates match. That fixed order is not a detail — it is what makes the network deadlock-free.

11. Verification View — dimension order is the deadlock-freedom guarantee

Two properties: the packet is delivered locally exactly when it has arrived, and X is always resolved before Y (the ordering that prevents routing cycles).

// Bind to xy_router.
localparam logic [2:0] LOCAL = 3'd0;
 
// 1. Local delivery happens exactly at the destination.
property p_local_iff_arrived;
  @(*) (out_port == LOCAL) == ((dst_x == my_x) && (dst_y == my_y));
endproperty
// (checked as an immediate assertion in a combinational testbench)
 
// 2. A Y-direction move (North/South) is taken ONLY when X already matches —
//    dimension order. This is the invariant that forbids cyclic channel deps.
always_comb begin
  if (out_port == 3'd1 || out_port == 3'd2)   // North or South
    assert (dst_x == my_x);
end

The system point, beyond the two checks:

A network deadlocks when packets hold links and wait for links in a cycle — A waits for B, B waits for C, C waits for A — and none can move. Dimension-order routing forbids this by construction: because every packet turns from X to Y but never from Y back to X, the channel-dependency graph has no cycle, so no deadlock can form. The guarantee is structural, not statistical. Break the fixed turn order and the guarantee is gone (the DebugLab).

• What it proves: correct delivery and dimension order — the routing function is deadlock-free.
• What it does not prove: buffer sizing, fairness, or livelock under adaptive schemes (out of scope here).
• Bug signature: packets that stop making progress network-wide with buffers full — a routing-induced deadlock.

12. Testbench — route toward a fixed destination

Drives a router at (1,1) with several destinations and checks the chosen port.

module tb_xy_router;
  localparam int W = 3;
  logic [W-1:0] my_x, my_y, dst_x, dst_y;
  logic [2:0] out_port;
  int errors = 0;
  localparam logic [2:0] LOCAL=0, NORTH=1, SOUTH=2, WEST=3, EAST=4;
 
  xy_router #(.W(W)) dut (.*);
 
  task automatic check(input logic [W-1:0] dx, input logic [W-1:0] dy,
                       input logic [2:0] exp, input string tag);
    my_x = 3'd1; my_y = 3'd1; dst_x = dx; dst_y = dy; #1;
    if (out_port !== exp) begin
      errors++; $display("FAIL [%s] out_port=%0d exp=%0d", tag, out_port, exp);
    end else
      $display("PASS [%s] dst=(%0d,%0d) out_port=%0d", tag, dx, dy, out_port);
  endtask
 
  initial begin
    check(3'd2, 3'd1, EAST,  "east: dst_x>my_x");
    check(3'd0, 3'd1, WEST,  "west: dst_x<my_x");
    check(3'd1, 3'd2, SOUTH, "south: x match, dst_y>my_y");
    check(3'd1, 3'd0, NORTH, "north: x match, dst_y<my_y");
    check(3'd1, 3'd1, LOCAL, "local: arrived");
    check(3'd0, 3'd0, WEST,  "x first: resolve x before y");
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS [east: dst_x>my_x] dst=(2,1) out_port=4
PASS [west: dst_x<my_x] dst=(0,1) out_port=3
PASS [south: x match, dst_y>my_y] dst=(1,2) out_port=2
PASS [north: x match, dst_y<my_y] dst=(1,0) out_port=1
PASS [local: arrived] dst=(1,1) out_port=0
PASS [x first: resolve x before y] dst=(0,0) out_port=3

13. DebugLab — the router that turns Y before X

packet  holds link   wants link   note
  P0     A -> B        B -> C      waiting on P1
  P1     B -> C        C -> D      waiting on P2
  P2     C -> D        D -> A      waiting on P3
  P3     D -> A        A -> B      waiting on P0  <- cycle closed

14. Common Mistakes

• Judging a topology by latency alone. Assumption: fewer hops is always better. Bug: picking a crossbar that does not fit (N² area). Prevention: weigh latency against bisection bandwidth and area together.
• Thinking a ring scales. Assumption: a ring beats a bus, so it scales. Bug: O(N) latency and fixed bisection at many nodes. Prevention: rings suit a dozen nodes, not many-core.
• Ignoring bisection bandwidth. Assumption: link speed is what matters. Bug: a fast shared link still bottlenecks. Prevention: bisection bandwidth is the scaling metric — it must grow with nodes.
• Assuming any routing is deadlock-free. Assumption: packets always find a way. Bug: cyclic channel dependency hangs the fabric (the DebugLab). Prevention: use dimension-order or another proven deadlock-free scheme.
• Treating the Home Node as central. Assumption: one directory at one place. Bug: recreating the bottleneck. Prevention: Home Nodes are distributed across the mesh; the directory is sharded.
• Separating protocol from fabric. Assumption: coherency and topology are independent. Bug: a protocol that cannot ride a NoC. Prevention: CHI is designed as a packet protocol for a mesh — they are co-designed.

15. Engineering Checklist

• Place the interconnect on the bus → ring → crossbar → mesh spectrum and know its scaling term.
• Use bisection bandwidth, not link speed, as the scaling metric.
• Expect mesh latency to grow as √N and area as N — the scalable trade.
• Ensure routing is deadlock-free (dimension-order, or virtual channels for adaptive).
• Distribute Home Nodes / directory across the fabric — never one central point.
• Treat coherency protocol and NoC fabric as co-designed, not layered afterthoughts.

16. Key Takeaways

• Topology evolved bus → ring → crossbar → mesh under one pressure: bandwidth that scales with nodes.
• Bus and ring fail on fixed bandwidth; the crossbar fails on O(N²) area; the mesh NoC scales — O(√N) latency, O(N) area, bisection bandwidth that grows with the grid.
• Coherent traffic becomes packets routed hop by hop; independent packets use many paths, with no shared medium to serialize on.
• Home Nodes (and their directories) are distributed across the mesh, so directory bandwidth scales too.
• Dimension-order routing is deadlock-free by construction — resolve X then Y; breaking the turn order can hang the fabric.
• Directory (3.6) plus mesh NoC (here) is the fabric CHI runs on — the reasoning is representative, not vendor numbers.

17. Quick Revision

Coherent fabrics. Topology evolution: shared bus (one transfer at a time, fixed bandwidth) → ring (hops, O(N) latency, low bisection) → crossbar (one hop, full bandwidth, but O(N²) area) → mesh network-on-chip (grid of routers, packets hop by hop, O(√N) latency, O(N) area, bisection bandwidth grows with the grid). Coherent messages are packets routed independently; Home Nodes and their directories are distributed across the mesh so directory bandwidth scales. Dimension-order (X-Y) routing — resolve X then Y — is deadlock-free because it never creates a cyclic channel dependency; abandoning it can wedge the fabric. Directory (3.6) plus mesh NoC (here) is the substrate CHI is built on. Representative reasoning, not vendor numbers.

Coming Next

Chapter 3.8 — Why CHI Was Created. Module 3 has assembled the whole case: coherence protocols (Module 2), the AMBA generations and their walls (3.1–3.4), the broadcast-scaling limit (3.5–3.6), and the mesh-fabric answer (this chapter). The final chapter of the module gathers it into CHI's explicit design goals — scalability, a layered packet protocol, directory coherency, and quality-of-service — closing "Why CHI Exists" and setting up Module 4, where we start building CHI itself.