How a production router works, in flow order: the two-pass architecture, the global pass that plans corridors, the detailed pass that lays exact wires, the rip-up loop both converge on, and the sign-off repairs that follow. The foundations and history sit at the bottom, and the classic search kernels run live in the maze lab.
Read this first. Production routing is a coarse capacity-planning pass followed by an exact track-level pass; every algorithm below belongs to one of them or spans both.
The die coarsened into GCells, every net a tree, every tree a corridor priced against congestion. This pass decides where wires go, which layers they ride, and which regions are in trouble, long before any track exists.
The minimum-wirelength tree connecting a multi-pin net may add junction points that are not pins. Exact is NP-hard (Non-deterministic Polynomial hard); FLUTE's lookup tables made near-optimal trees effectively free.
Route most nets from a tiny library of fixed shapes, L and Z patterns priced against the congestion map, and fall back to maze search only for the few nets no pattern fits. The reason global routing is fast.
Let every net route through congestion at first, but make each resource's price grow with present and historical overuse; nets with alternatives get priced out, and the net that truly needs a resource outbids the rest.
Decide which metal layer each route segment rides: merge staircases to cut via count, promote critical runs to thick low-resistance metal, and respect per-layer capacity and preferred direction.
Not a new search: the same negotiation with a cost function that carries timing slack and coupling. Critical nets are weighted to win contested resources, and coupling terms, spacing, and shielding keep aggressors away from them.
Write global routing down as an integer linear program: one binary variable per candidate path, capacity constraints per edge, provable optimality per instance. Intractable at full scale, indispensable as a gold standard.
Make the router data-parallel: relax whole wavefront rings at once on a GPU (Graphics Processing Unit) and route batches of non-overlapping nets in the same pass. Wins the recent academic contests; not yet the production path.
Learned congestion prediction, net ordering, and cost tuning: an active literature, and a negative result so far: unlike placement, no learned component ships inside a production router's search.
Inside each corridor, real tracks, real vias, and the full design-rule deck. Bulk assignment first, point-to-point search for the rest, and a gridless escape hatch for what the track lattice cannot express.
Best-first search ordered by cost-so-far plus an admissible estimate of cost-to-go. The skeleton production routers actually use, because the cost can price vias, bends, and congestion, not just distance.
Between global and detailed routing: bulk-place each net's long straight segments onto physical tracks by interval packing, so the expensive point-to-point search only handles short connections and repairs.
Before any search, enumerate every legal via position on every cell pin under the full rule deck, so the detailed router targets pre-checked access points instead of discovering, deep in a maze expansion, that a pin cannot be reached.
Drop the track lattice: store the layout as geometric shapes and search corner points, so wires can sit at any coordinate. Slower than gridded search, but the only model that fits off-grid pins, analog constraints, and non-uniform widths.
Two ways the manufacturing process constrains routing: named rule sets that give chosen nets wider wires and spacing, and at sub-lithographic pitches, multi-patterning constraints that turn a metal layer into a mask-coloring problem the router must keep solvable.
Route a group of nets as one structured object: a single trunk topology replicated on adjacent tracks with bit order preserved, and, where skew matters, serpentine length matching. Memory interfaces and datapaths depend on it.
Both passes converge the same way: route everything, find the conflicts, tear out and re-route until the count reaches zero. This is the iteration a PD (Physical Design) engineer watches in the log.
Checks that run on the finished routing and the repairs that clear them. Not searches, but algorithms every tape-out runs, and the physics is manufacturing rather than operation.
Everything above is what production routers do. This section is where it came from: the maze-search kernels A* (A-star) descends from (all live in the maze lab), the line-search routers of the memory-starved era, and the channel routers built when wires could not cross the cell rows. Read for lineage and interviews, not for the flow.
Breadth-first wavefront expansion: rings radiate from the source until one touches the target, then the path traces back. The founding algorithm of the field.
Order the search by detour number, how many moves a path has spent walking away from the target; minimal detours still means shortest path, found with far fewer cells settled.
Sprint greedily straight toward the target; when stuck, fall back to a Lee-style escape wave just long enough to get closer, then sprint again. Roughly 10-50x faster than Lee in its day, minus the shortest-path guarantee.
Shoot probe lines from both pins; from every point of every probe, shoot perpendiculars next iteration; when source and target families intersect, join. Complete like Lee, far lighter on memory.
Line search that probes only from carefully chosen escape points past each blocking obstacle rather than from every point: faster and leaner than Mikami-Tabuchi, but completeness is sacrificed.
Sort net segments by left endpoint and pack them greedily into tracks like interval scheduling, respecting vertical constraints; dogleg splitting breaks the cycles. The classic of the channel-routing era.
Add 45-degree wiring layers and cut wirelength about 20 percent: the geometry worked, the arithmetic was real, and manufacturing plus the ecosystem killed it anyway. The catalog's example of a research direction that was not adopted.