In a 4×4 mesh, a packet from the bottom-left corner to the top-right corner has twenty different shortest paths. A router at each hop must pick an output. Pick cleverly, around congestion, and the network runs faster on average. Pick cleverly without care, and four packets can each wait for a link another one holds, and the network stops.
How should a packet choose its path, and how does that choice affect deadlock?
The obvious goal is the best path for each packet: shortest, and avoiding busy links. That is adaptive routing, and it does balance load. But packets that can turn in any direction can form a cycle: each holds a buffer on one link and waits for the next link, held by the next packet, all the way round (Part 9). Routing is not only a performance choice; it decides whether cycles of waiting are possible at all.
Kind | Path | Strength | Weakness |
|---|---|---|---|
Deterministic (for example XY) | Fixed by source and destination | Simple; in-order delivery per pair; easy deadlock argument | Cannot avoid congested links |
Adaptive | Chosen hop by hop from allowed outputs, using congestion | Balances load, tolerates faults | Packets can arrive out of order; needs a deadlock argument (turn restrictions or escape channels) |
A second axis is who decides: source routing (the source writes the whole path into the packet header) or distributed routing (each router computes the next hop from the destination). Most on-chip networks use distributed, deterministic routing.
Dimension-order routing in a 2-D mesh, XY routing, moves a packet along X until it reaches the destination's column, then along Y. That is all.
A deadlock needs a cycle of packets, each waiting for a link held by the next. A cycle in a mesh must turn at least once from Y back to X (to go round a loop you must eventually come back in the X direction). XY routing forbids every Y-to-X turn: once a packet starts moving in Y, it never moves in X again. So no cycle can form, and the network cannot deadlock through routing, without needing any extra virtual channels.
The turn model generalises the argument: forbid just enough turns to break every cycle, and adaptive routing within the remaining turns stays deadlock-free. Escape channels go the other way: let packets route adaptively on some virtual channels, but always keep one channel where they follow a deadlock-free route, so they can never be stuck for ever.
Where | Routing |
|---|---|
On-chip meshes | Mostly XY (dimension-order) routing: deterministic, simple, deadlock-free, in-order between each pair. |
Rings | Shortest direction, with an extra virtual channel (a dateline) to break the ring's cycle (lesson 9.6). |
Large off-chip networks | Often adaptive, with escape virtual channels or turn restrictions for deadlock freedom. |
A mesh (illustrative) added a small adaptive tweak to XY routing: a packet blocked on its X link could take a Y link and come back to X later, to route around a hot spot. Under heavy traffic the network froze: four packets in a square each held one link and waited for the next. The tweak had re-allowed Y-to-X turns, restoring the cycles XY routing exists to prevent. Removing it (or adding an escape channel with pure XY) fixed the hang.
Along X from column 1 to column 3 (two hops) in row 3, then along Y from row 3 to row 0 (three hops).
They may take different paths with different congestion, so the later packet can take a faster path.
Routing is deterministic (fixed path) or adaptive (chosen around congestion), decided at the source or at each router.
XY routing never turns from Y back to X, so no cycle of link dependencies, and no routing deadlock, can form.
Adaptive routing needs turn restrictions or escape channels to stay deadlock-free, and may reorder packets.