Networks on Chip

The crossbar served us well — every master a private path to every slave — but its cost grows as N^2. At eight masters it's a bargain; at sixty-four cores, a memory controller per edge, and a swarm of accelerators, the crossbar is a wiring catastrophe that no floorplan can absorb. The interconnection-networks toolbox offers the escape, and it is the same one the telephone system and the Internet found: stop building a wire per conversation. Packetise. Put a small router at each grid point, give every block a local doorstep, and let messages find their own way, a hop at a time. The SoC grows a postal service — and like any postal service, its character is set by three choices: how letters are cut up, which route they take, and what stops the whole system jamming.

Flits: cutting the letter into beads

A message (a cache line, a DMA burst) becomes a packet; the packet is chopped into flits (flow-control digits) — the unit a router buffers and forwards, typically one link-width each:

Routers forward flits in wormhole style: the head moves on as soon as the next link is free, and the packet stretches out like a worm across several routers at once — the head three hops ahead while the tail is still leaving home. Buffering is per-flit, not per-packet, so router storage stays tiny; the price is that a blocked head leaves its body parked across the network, holding a chain of links. Remember that price — it is where deadlock will come from.

The mesh, and routing by dimension

Topologies abound — rings, tori, fat trees — but the workhorse of SoCs is the 2-D mesh: routers at grid points, links to the four neighbours, a block (core, cache slice, memory controller) at each router's doorstep. It is the shape that loves silicon back: planar, short equal wires, and it grows by tiling.

Routing rule number one is almost embarrassingly simple. XY dimension-ordered routing: first travel along x until your column is correct, then along y to the destination. Deterministic, needs no tables — just two comparators — and it crosses exactly |x_1-x_2| + |y_1-y_2| links, a shortest path. But its deep virtue is subtler: XY is deadlock-free by construction. A deadlock needs a cycle of packets each waiting for a link the next one holds. Any such cycle in a mesh must somewhere turn from travelling in y back into travelling in x — and XY simply never makes that turn. Once you've turned onto your column, you never leave it. No y-to-x turns, no cyclic channel dependency, no deadlock — a proof you can draw on a napkin.

See it on the grid

Step through the three headline ideas on one 4×4 mesh:

Virtual channels: more lanes, same road

A virtual channel (VC) is an extra set of flit buffers sharing one physical link — several queues multiplexed onto the same wires, like turning a one-lane road into a motorway without widening the tarmac. VCs earn their area three times over:

What does a message cost?

The back-of-napkin latency model has two terms — distance and length. The head pays per hop; the rest of the packet follows in pipeline:

T \;\approx\; \underbrace{H \cdot t_{\text{hop}}}_{\text{head walks }H\text{ hops}} \;+\; \underbrace{L / b}_{\text{serialisation: } L \text{ flits at } b \text{ per cycle}}

with H = |x_1-x_2|+|y_1-y_2| on a mesh and t_{\text{hop}} the router-plus-link pipeline delay (a few cycles). Short packets are dominated by distance; long bursts by serialisation — which is why a cache-line read cares about hop count while a DMA stream cares about link width. For whole-chip capacity, the standard yardstick is bisection bandwidth: cut the chip in half and sum the bandwidth of the severed links. A k \times k mesh cut down the middle severs k links — so doubling the mesh's side length doubles bisection bandwidth but quadruples the cores contending for it. That mismatch is the eternal argument for keeping traffic local.

Route a batch, find the hot links

Here is XY routing as ten lines of code, plus an occupancy counter per link. A seeded batch of packets crosses a 4×4 mesh; watch where XY piles them up:

// XY routing on a 4x4 mesh, counting how many packets use each link. const N = 4; let seed = 77; const rand = () => { seed = (seed * 1664525 + 1013904223) % 4294967296; return seed / 4294967296; }; const cell = () => [Math.floor(rand() * N), Math.floor(rand() * N)]; const load = new Map<string, number>(); // directed link -> packets carried const use = (a: string, b: string) => { const k = `${a}->${b}`; load.set(k, (load.get(k) || 0) + 1); }; function routeXY(sx: number, sy: number, dx: number, dy: number): number { let x = sx, y = sy, hops = 0; while (x !== dx) { const nx = x + Math.sign(dx - x); use(`(${x},${y})`, `(${nx},${y})`); x = nx; hops++; } while (y !== dy) { const ny = y + Math.sign(dy - y); use(`(${x},${y})`, `(${x},${ny})`); y = ny; hops++; } return hops; // always |dx-sx| + |dy-sy| } console.log("pkt src -> dst hops"); for (let p = 0; p < 10; p++) { const [sx, sy] = cell(); let [dx, dy] = cell(); if (sx === dx && sy === dy) dx = (dx + 1) % N; // no packets to yourself const h = routeXY(sx, sy, dx, dy); console.log(` ${p} (${sx},${sy}) -> (${dx},${dy}) ${h}`); } const busy = [...load.entries()].sort((a, b) => b[1] - a[1]); console.log("\ncontention map - busiest links:"); for (const [link, n] of busy.slice(0, 5)) console.log(` ${link} carried ${n} packets`); console.log(`\n${load.size} links used; max load ${busy[0][1]}.`); console.log("XY funnels every packet's column-turn through one router per (column,row) pair -"); console.log("deterministic and deadlock-free, but hotspots are the price of never turning y-to-x.");

Increase the packet count to 40 and rerun: the maximum link load climbs much faster than the average — deterministic routing concentrates traffic. That observation is exactly what tempts designers toward adaptive routing… and straight into the vignette below.

Almost — and the differences are as instructive as the likeness. Like the Internet, a NoC has routers, packets, addresses and multi-hop paths; the mental furniture transfers one-for-one. Unlike the Internet, a NoC never drops a packet: flow control is credit-based — a router only sends a flit when the neighbour has advertised a free buffer — so congestion propagates as polite backpressure rather than loss and retransmission. There is no TCP, no routing protocol chatter, no misbehaving stranger's traffic: every router was designed by the same team and verified against the same spec, which is why hop latencies are measured in cycles, not milliseconds. GPUs run one of the industry's densest examples as their internal glue — dozens of cores on one side, a comb of memory-controller channels on the other, and a NoC in between carrying terabytes per second. The postal service metaphor runs deep: the Internet is the international mail, and the NoC is the pneumatic tube system inside one very well-run building.

After seeing XY's hotspots, the obvious "improvement" writes itself: let each router steer around congestion — go Y first when X is busy, X first otherwise. Ship it, and the chip runs beautifully for hours… then freezes solid, whole quadrants of the mesh waiting on each other, no error, no timeout, no recovery. By allowing both turn orders you have re-created exactly the cyclic channel dependencies that XY's missing turns made impossible — the four-packet cycle from the figure above, now legal again. The lesson generalises far beyond routing: deadlock freedom is a proof obligation, not a vibe. Every adaptive scheme that works — turn-model routing (forbid a carefully chosen subset of turns), Duato's protocol (adaptive lanes backed by an ordered escape VC that is always cycle-free) — comes with a theorem attached showing the channel-dependency graph is acyclic. If you cannot draw that graph for your clever new router and show it has no cycles, you have not designed a router; you have designed an intermittent, unreproducible field failure.