XY routing moves a packet fully along X, then fully along Y. The path is deterministic: source (0,0) to destination (3,3) always takes 6 hops, 3 east then 3 north.
Determinism concentrates load. Aligned bursts under dimension-order routing share the same corridor links, which is why hotspot corridors appear mainly under this routing plus synchronized senders.
A packet makes at most one turn per trip: it travels X first, turns once from X to Y, and continues along Y. Pairs sharing a row or column make no turn at all. The four Y-to-X turns never happen, so the channel dependency graph has no cycle.
Dally and Seitz proved the rule behind this: a routing function is deadlock-free when its channel dependency graph is acyclic. Forbidding half the turns is the cheapest way to keep it acyclic on a mesh.
Turn | XY allows | Why it matters |
|---|---|---|
East to north, east to south | Yes | X-to-Y turns complete every XY path |
West to north, west to south | Yes | X-to-Y turns complete every XY path |
North to east, south to east | No | Y-to-X turns would close dependency cycles |
North to west, south to west | No | Y-to-X turns would close dependency cycles |
Routing deadlock is a cycle inside one message class: packets wait on channels that wait back on them. Routing restrictions or escape virtual channels break the cycle.
Protocol deadlock spans message classes: requests cannot sink because the request queue is full of packets waiting for responses, while responses cannot be injected because their path is blocked. Separate request, response and snoop networks fix it; adding virtual channels inside one class does not.
The model below computes XY hop count from coordinates, and the testbench walks every pair step by step as an independent reference.
module xy_hops (
input logic [1:0] sx,
input logic [1:0] sy,
input logic [1:0] dx,
input logic [1:0] dy,
output logic [3:0] hops
);
logic [1:0] xlegs;
logic [1:0] ylegs;
assign xlegs = (sx >= dx) ? (sx - dx) : (dx - sx);
assign ylegs = (sy >= dy) ? (sy - dy) : (dy - sy);
assign hops = {2'b00, xlegs} + {2'b00, ylegs};
endmodule
Protocol deadlock: requests wait on responses while sharing one network. Separate request and response networks fix it; more virtual channels in the shared class do not.
Mean 2.5 hops: 640 divided by 256. Self-pairs contribute 0 hops each and are included; excluding them gives 640 over 240, or about 2.67.