Channel Routing & Topology

Module 6 · Chapter 6.7 · CHI Channels

Project thread — 6.6 named the common fields, including the Node IDs the fabric routes on. This chapter turns that routing role into a physical journey across the mesh, and closes Module 6. Module 7 walks whole transactions end to end.

1. Learning Outcomes

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

• Describe the CHI interconnect as a mesh of routers, each node at a coordinate.
• Explain how TgtID drives hop-by-hop routing — each router forwards one hop toward the target.
• State the dimension-order (XY) rule — route in X first, then Y — and why it is routing-deadlock-free.
• Distinguish routing deadlock from protocol deadlock, and name the cure for each.
• Justify why the four channels must ride separate virtual channels.
• Implement a representative XY router next-hop in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

Every transaction you have studied — read, write, snoop — is a set of packets that must physically cross the chip. Between two nodes sits a fabric of routers, and the packet reaches its destination one hop at a time. Understanding that journey is what turns "the fabric delivers by TgtID" from a slogan into a mechanism: you can trace a packet's path, reason about latency by counting hops, and see where congestion builds.

It also explains two failures that look identical from the outside — the fabric simply stops — but have different causes and different cures. Routing deadlock comes from the paths packets take; protocol deadlock comes from message classes blocking one another. CHI's topology answers both: dimension-order routing for the first, separate virtual channels for the second. Miss the distinction and you will chase a hang in the wrong place.

3. Key Terms

4. Previous Chapter Connection

Chapter 6.6 pulled out the fields every packet shares and pinned each to a role: TgtID does routing, (SrcID, TxnID) does correlation, the Opcode does identity. It stopped at the boundary of the sending node — TgtID names where the packet goes, but not how it gets there.

This chapter crosses that boundary. The fabric between nodes is a mesh, and TgtID is the address the mesh routes on, hop by hop. The four channels — REQ, RSP, SNP, DAT, detailed in 6.2–6.5 — each ride the fabric on their own virtual channel. So the routing role of the common Node IDs becomes a concrete path, and the four-channel structure becomes four independent lanes through the routers.

5. Core Concept — hop-by-hop routing over a mesh

The CHI interconnect is a mesh network-on-chip: routers laid out in a grid, links between neighbors, and every node — RN, HN, SN — attached at a coordinate.

• TgtID is the destination coordinate. A node's ID maps to its (X, Y) position in the mesh. The fabric routes a packet by its TgtID and nothing else (Chapter 6.6): each router reads the target coordinate and decides one hop.
• Routing is hop-by-hop. No router knows the whole path. A router compares the target's coordinates to its own and forwards the packet to one neighbor — one step closer. The next router repeats. The path emerges hop by hop.
• Dimension-order (XY). The rule is deterministic: reduce the X difference to zero first (go East or West), then reduce the Y difference (go North or South), then deliver Local. Routing X-before-Y forbids certain turns, which makes the set of possible paths acyclic — and an acyclic turn set cannot form the circular wait that is routing deadlock.
• Four channels, four virtual channels. REQ, RSP, SNP, and DAT each travel on a separate virtual channel. The lanes share physical links but have independent buffers, so a backed-up request can never block a response on the same wire.

The synthesis:

A CHI packet crosses the fabric as a sequence of hops. Each router routes it by TgtID alone, moving X first, then Y — a deterministic, minimal, routing-deadlock-free path. The four channels ride independent virtual channels, so no message class stalls another. Topology gives you two guarantees: dimension-order routing prevents routing deadlock; separate virtual channels prevent protocol deadlock.

6. Engineering Mental Model — a city grid with reserved lanes

Picture a city laid out as numbered streets and avenues.

• Every building has an address — an avenue (X) and a street (Y). A courier delivering by TgtID reads that address and nothing else.
• The courier follows a fixed rule: drive along the avenue until you reach the right one, then turn onto the street — never zig-zag. Because everyone follows the same avenue-then-street rule, couriers never form the circular jam where each is waiting on the next to move. That is dimension-order routing.
• The roads carry four reserved lanes — one each for requests, responses, snoops, and data. They share the same asphalt but never merge, so a queue of trucks in the request lane cannot trap an ambulance in the response lane. Those are the virtual channels.

Fixed turn rule plus reserved lanes: the traffic always flows. Break either — let couriers zig-zag, or let the lanes merge — and the grid can lock solid.

7. Engineering Diagram — a packet across the mesh

The source at (0,0) reaches the target at (2,0) in two Eastward hops — X offset resolved, Y offset already zero. Every router made a local decision; the minimal path emerged from the shared rule.

8. Four Channels, Four Virtual Channels

The links are physical; the lanes are logical. Each of the four channels gets its own virtual channel — an independent buffer — over the shared wires.

The rule to carry: one virtual channel per message class. Because a transaction's later messages (a response, its data) free the resources its earlier messages (the request) are holding, the classes form a dependency chain — and a chain that shares one buffer can close into a cycle. Separate lanes break the cycle.

9. Routing Rules — deterministic, minimal, per-hop

Three properties define CHI-style mesh routing.

• TgtID-driven, per hop. Each router reads only the packet's TgtID, maps it to the target coordinate, and compares it to its own. No global path, no source route — one local decision per hop (Chapter 6.6).
• Dimension-order, X then Y. Resolve the X offset first (East / West), then the Y offset (North / South), then deliver Local. This is minimal (no hop is wasted) and deterministic (the same TgtID always takes the same path from a given router).
• Acyclic turns → no routing deadlock. By always turning from X to Y and never Y to X, the set of permitted turns cannot form a cycle. Circular wait among paths is impossible, so the fabric cannot deadlock on routing alone.

The point to carry:

Dimension-order routing buys determinism and routing-deadlock freedom for free, at the cost of adaptivity — it cannot route around a hot spot. CHI accepts that trade for control traffic: a predictable, deadlock-free path matters more than dodging congestion. Deadlock freedom on paths is dimension-order's job; deadlock freedom on message classes is the virtual channels' job. The two mechanisms are orthogonal, and you need both.

10. Transaction Walkthrough — a request's path across the fabric

Follow a ReadShared from RN-F at (0,0) to HN-F at (2,0), then the data back.

1. Router (0,0). Reads TgtID → target (2,0). X offset is +2, so route East. Hop to (1,0).
2. Router (1,0). Target still (2,0). X offset is +1, route East. Hop to (2,0).
3. Router (2,0). X and Y offsets are zero → deliver Local to HN-F. The REQ rode the REQ VC the whole way.
4. HN-F responds. CompData is now a packet with TgtID = (0,0), riding the DAT VC. Router (2,0) sees X offset −2 → route West, and the data returns hop by hop to (0,0).
5. Independence. Throughout, a queue of other requests on the REQ VC never touched the DAT VC carrying the reply — the response lane stayed clear, so the transaction completed.

Two Eastward hops out, two Westward hops back — deterministic and minimal — on independent lanes that could not block each other.

11. RTL / Hardware View — an XY router next-hop

The core of a mesh router is one combinational decision: given the packet's TgtID (which encodes the destination coordinate) and this router's own coordinate, pick the output port. Dimension-order: X first, then Y, then Local. Representative and combinational.

// Representative dimension-order (XY) mesh router next-hop (educational).
// TgtID encodes the destination coordinate: dst_x = tgt_id[1:0], dst_y = tgt_id[3:2].
// Route X to zero first (EAST/WEST), then Y (NORTH/SOUTH), then LOCAL. Turning
// only from X to Y (never Y to X) keeps the turn set acyclic -> no routing deadlock.
module chi_xy_router #(
  parameter logic [2:0] LOCAL = 3'd0, EAST = 3'd1, WEST = 3'd2, NORTH = 3'd3, SOUTH = 3'd4
) (
  input  logic [3:0] tgt_id,        // destination Node ID -> coordinate
  input  logic [1:0] cur_x,         // this router's X
  input  logic [1:0] cur_y,         // this router's Y
  output logic [2:0] out_port
);
  logic [1:0] dst_x, dst_y;
  assign dst_x = tgt_id[1:0];
  assign dst_y = tgt_id[3:2];
 
  always_comb begin
    if      (dst_x > cur_x) out_port = EAST;    // resolve X first
    else if (dst_x < cur_x) out_port = WEST;
    else if (dst_y > cur_y) out_port = NORTH;   // then Y
    else if (dst_y < cur_y) out_port = SOUTH;
    else                    out_port = LOCAL;   // arrived
  end
endmodule

The same behavior in Verilog-2001:

// Representative dimension-order (XY) mesh router next-hop (Verilog-2001).
module chi_xy_router (
  input  [3:0] tgt_id,
  input  [1:0] cur_x,
  input  [1:0] cur_y,
  output reg [2:0] out_port
);
  localparam LOCAL = 3'd0, EAST = 3'd1, WEST = 3'd2, NORTH = 3'd3, SOUTH = 3'd4;
  wire [1:0] dst_x = tgt_id[1:0];
  wire [1:0] dst_y = tgt_id[3:2];
 
  always @* begin
    if      (dst_x > cur_x) out_port = EAST;
    else if (dst_x < cur_x) out_port = WEST;
    else if (dst_y > cur_y) out_port = NORTH;
    else if (dst_y < cur_y) out_port = SOUTH;
    else                    out_port = LOCAL;
  end
endmodule

And in VHDL:

-- Representative dimension-order (XY) mesh router next-hop (VHDL).
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity chi_xy_router is
  port (
    tgt_id   : in  std_logic_vector(3 downto 0);
    cur_x    : in  unsigned(1 downto 0);
    cur_y    : in  unsigned(1 downto 0);
    out_port : out std_logic_vector(2 downto 0)
  );
end entity;
 
architecture rtl of chi_xy_router is
  constant LOCAL : std_logic_vector(2 downto 0) := "000";
  constant EAST  : std_logic_vector(2 downto 0) := "001";
  constant WEST  : std_logic_vector(2 downto 0) := "010";
  constant NORTH : std_logic_vector(2 downto 0) := "011";
  constant SOUTH : std_logic_vector(2 downto 0) := "100";
begin
  process (tgt_id, cur_x, cur_y)
    variable dst_x, dst_y : unsigned(1 downto 0);
  begin
    dst_x := unsigned(tgt_id(1 downto 0));
    dst_y := unsigned(tgt_id(3 downto 2));
    if    dst_x > cur_x then out_port <= EAST;
    elsif dst_x < cur_x then out_port <= WEST;
    elsif dst_y > cur_y then out_port <= NORTH;
    elsif dst_y < cur_y then out_port <= SOUTH;
    else                     out_port <= LOCAL;
    end if;
  end process;
end architecture;

All three make one local decision from TgtID and the router's own coordinate, always resolving X before Y. That single rule, applied at every router, produces a deterministic minimal path — and the DebugLab shows the deadlock it does not prevent.

12. Verification View — X is resolved before Y

The invariant that makes dimension-order deadlock-free: whenever the X offset is nonzero, the port is East or West — never North or South. Y is only chosen once X is zero.

// Bind to chi_xy_router.
// If the destination X differs from this router's X, the packet must move in X
// (EAST or WEST) — never in Y. This "X before Y" turn restriction is what keeps
// the turn set acyclic and the fabric free of routing deadlock.
property p_x_before_y;
  @(*) (tgt_id[1:0] != cur_x) |-> (out_port == 3'd1 || out_port == 3'd2);
endproperty
 
// And once X matches, a differing Y moves in Y (NORTH or SOUTH), else LOCAL.
property p_then_y;
  @(*) (tgt_id[1:0] == cur_x && tgt_id[3:2] != cur_y)
       |-> (out_port == 3'd3 || out_port == 3'd4);
endproperty

The system point, beyond the checks:

Two independent guarantees keep a mesh alive, and each has its own mechanism. Routing deadlock — a cycle among paths — is prevented by the turn restriction these properties encode: X before Y makes the turn set acyclic, so packets can never form a circular wait for links. Protocol deadlock — a cycle among message classes — is prevented by separate virtual channels, which the router above does not address. A router can be perfectly dimension-ordered and still deadlock if the classes share a lane. You need both mechanisms; verifying one says nothing about the other.

• What it proves: the router resolves X before Y — the acyclic turn rule, so no routing deadlock.
• What it does not prove: freedom from protocol deadlock — that needs separate VCs per message class (the DebugLab).
• Bug signature: the fabric stops with buffers full, even though every route was legal — a message-class cycle.

13. Testbench — every direction and the local delivery

Drives one router at coordinate (1,1) and checks that each target coordinate selects the right port, X resolved before Y.

module tb_chi_xy_router;
  logic [3:0] tgt_id; logic [1:0] cur_x = 2'd1, cur_y = 2'd1; logic [2:0] out_port;
  int errors = 0;
  localparam LOCAL=3'd0, EAST=3'd1, WEST=3'd2, NORTH=3'd3, SOUTH=3'd4;
 
  chi_xy_router dut (.*);
 
  // Build a TgtID from (x, y): dst_x = bits[1:0], dst_y = bits[3:2].
  function automatic logic [3:0] id(input logic [1:0] x, input logic [1:0] y);
    return {y, x};
  endfunction
 
  task automatic check(input logic [1:0] x, input logic [1:0] y,
                       input logic [2:0] exp, input string name);
    tgt_id = id(x, y); #1;
    if (out_port !== exp) begin errors++; $display("FAIL %s: port=%0d exp=%0d", name, out_port, exp); end
    else $display("PASS %s -> port %0d", name, out_port);
  endtask
 
  initial begin
    check(2'd2, 2'd1, EAST,  "east  (x+ )");
    check(2'd0, 2'd1, WEST,  "west  (x- )");
    check(2'd1, 2'd2, NORTH, "north (y+ )");
    check(2'd1, 2'd0, SOUTH, "south (y- )");
    check(2'd1, 2'd1, LOCAL, "local (arrived)");
    check(2'd2, 2'd2, EAST,  "x before y (both differ -> X first)");
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS east  (x+ ) -> port 1
PASS west  (x- ) -> port 2
PASS north (y+ ) -> port 3
PASS south (y- ) -> port 4
PASS local (arrived) -> port 0
PASS x before y (both differ -> X first) -> port 1
ALL TESTS PASSED

14. DebugLab — two message classes on one virtual channel

shared VC buffer (REQ + RSP together), full:
  slot 0: REQ  (wants to reach HN, HN buffer full)
  slot 1: REQ
  slot 2: RSP  (a completion that would free an outstanding REQ)
  ...
RSP in slot 2 cannot pass the REQs ahead of it
  -> the REQ it would complete never frees
  -> that REQ keeps holding its slot -> nothing moves

15. Common Mistakes

• Merging message classes onto one VC. Assumption: buffers are fungible. Bug: protocol deadlock (the DebugLab). Prevention: one VC per class — REQ, RSP, SNP, DAT.
• Allowing Y-to-X turns. Assumption: any shortest path is fine. Bug: cyclic turn set → routing deadlock. Prevention: dimension-order, X before Y.
• Assuming routing determines liveness. Assumption: a deadlock-free router means a deadlock-free fabric. Bug: protocol deadlock slips through. Prevention: verify VC separation too.
• Source-routing the whole path. Assumption: the sender must compute the route. Bug: rigidity and header bloat. Prevention: per-hop decisions from TgtID.
• Counting one hop as one cycle for latency. Assumption: hops are free. Bug: mis-estimated latency. Prevention: account for per-router pipeline and arbitration.
• Ignoring QoS at routers. Assumption: all packets arbitrate equally. Bug: priority inversion under load. Prevention: honor QoS in router arbitration (Chapter 6.6).

16. Engineering Checklist

• Map each node to a mesh coordinate; route by TgtID only.
• Route per hop — compare target to the router's own coordinate.
• Apply dimension-order: X to zero first, then Y, then Local.
• Give each message class — REQ, RSP, SNP, DAT — its own virtual channel.
• Verify X-before-Y (no routing deadlock) and VC separation (no protocol deadlock).
• Honor QoS in router arbitration.

17. Key Takeaways

• CHI runs over a mesh of routers; each node has an (X, Y) coordinate and every packet routes by TgtID.
• Routing is hop-by-hop — each router forwards one step by comparing the target to its own coordinate.
• Dimension-order (XY) — X before Y — is minimal, deterministic, and routing-deadlock-free because its turn set is acyclic.
• The four channels ride separate virtual channels, so no message class blocks another — this prevents protocol deadlock.
• Routing deadlock and protocol deadlock are distinct; dimension-order cures the first, per-class VCs the second, and you need both.
• Route by TgtID, X then Y, one class per VC; the model here is representative.

18. Quick Revision

Channel routing & topology. CHI runs over a mesh network-on-chip — routers in a grid, each node at an (X, Y) coordinate. A packet routes by its TgtID: every router maps the target to a coordinate, compares it to its own, and forwards one hop. The rule is dimension-order (XY) — resolve X first (East/West), then Y (North/South), then deliver Local. Because packets only turn from X to Y, the turn set is acyclic, so the fabric cannot suffer routing deadlock. Separately, the four channels — REQ, RSP, SNP, DAT — ride four independent virtual channels, so a stalled class cannot block another; this prevents protocol deadlock, a message-class cycle that dimension-order does not address. Two deadlocks, two cures: X-before-Y for routing, per-class VCs for protocol — you need both. Route by TgtID, X then Y, one VC per class. Representative model; Module 7 walks whole transactions, starting with the read.

Coming Next

Chapter 7.1 — The Read Transaction. Module 6 dissected the four channels and how their packets cross the fabric. Module 7 zooms back out to the whole transaction: the ordered exchange of packets that makes one operation happen, end to end. Chapter 7.1 opens with the read — how a ReadShared or ReadUnique flows from request, through any snoops the home issues, to the completion and data that satisfy it, tying together the channels, the cache states, and the routing you now understand into a single, traceable sequence.