Placement and Routing

The floorplan has drawn the city limits and dropped the boulders. Now come the two most computationally ferocious steps in all of chip design: put millions of standard cells into the rows (placement), then connect their tens of millions of pins with real wires (routing). Between them they decide whether your chip meets timing — because on a modern process, as the interconnect wall taught, the wires are the delay. Where a cell sits determines how long its wires are, and how long its wires are determines how fast it is. Placement is timing.

Placement: a million cells seek their seats

The placer's objective reads simply: minimise total wirelength, subject to no overlaps, acceptable congestion, and timing. The classic engine behind modern placers is analytic placement: pretend every net is a little spring pulling its pins together, and solve for the cell positions that minimise total quadratic spring energy — a huge but well-behaved optimisation that yields a beautiful, illegal answer: cells piled on top of each other in dense clumps. Then comes the cleanup pipeline:

Spreading / legalization — pull the overlapping clumps apart and snap every cell onto a legal row site, disturbing the analytic answer as little as possible;
Detailed placement — local polish: swap neighbours, slide cells along rows, nudge wirelength and congestion down a few more percent.

A timing-driven placer adds one more force: nets on critical paths get stiffer springs, so timing-critical cells are pulled tightly together while sleepy configuration logic is allowed to sprawl. And throughout, the placer watches the congestion map — a heat map of predicted routing demand versus supply per region. Where demand exceeds supply, the fix is to spread cells apart or lower local utilization: give the wires room before they are drawn.

Routing: two acts and a metal stack

Routing connects every net without two wires ever touching, obeying every design rule, on a chip with tens of millions of nets. No tool attacks that directly; routing runs as two acts:

Global routing — divide the die into coarse tiles; assign each net a corridor of tiles and a rough layer, watching per-tile capacity. Its product is a plan — and an honest congestion report of where the plan is tight.
Detailed routing — within each corridor, choose exact tracks, exact jogs, exact vias (the little vertical connections between adjacent metal layers), delivering geometry that is completely design-rule-clean.

The wires live in a metal stack of some 10–15 layers, and the stack has a shape: lower layers are thin and dense — fine pitch, high resistance, perfect for short local hops between neighbouring cells; upper layers are thick and fast — coarse pitch, low resistance, reserved for long-haul connections, clocks and power. A cross-chip net typically climbs the stack via a ladder of vias, sprints across on thick metal, and climbs back down to its destination pin.

The maze router: a wave that cannot be stopped

The oldest routing algorithm is still the most beautiful. Lee's algorithm (1961) finds a shortest path from a source pin to a target on a grid with obstacles by flooding: label the source's neighbours 1, their neighbours 2, and so on — a breadth-first wavefront that flows around any obstacle like water. The moment the wave touches the target, walk backwards downhill (7, 6, 5, …) to recover a shortest path. If any path exists, the wave finds it, and no shorter one exists. Watch it run:

Modern detailed routers descend from this idea (with A*-style goal direction, line probes, and rip-up-and-reroute negotiation when nets fight over the same tracks), but the guarantee that makes maze routing immortal is Lee's: if a route exists, the flood will find it.

Run the flood yourself

// Lee maze router: BFS wavefront + backtrace on a 9×7 grid with an obstacle. const W = 9, H = 7; const blocked = (x: number, y: number) => x >= 3 && x <= 5 && y >= 2 && y <= 4; const src = { x: 1, y: 3 }, tgt = { x: 7, y: 3 }; const d: number[][] = []; for (let y = 0; y < H; y++) d.push(new Array(W).fill(-1)); d[src.y][src.x] = 0; let frontier = [src]; while (frontier.length > 0 && d[tgt.y][tgt.x] < 0) { const next: { x: number; y: number }[] = []; for (const c of frontier) { for (const [dx, dy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const x = c.x + dx, y = c.y + dy; if (x < 0 || y < 0 || x >= W || y >= H) continue; if (blocked(x, y) || d[y][x] >= 0) continue; d[y][x] = d[c.y][c.x] + 1; next.push({ x, y }); } } frontier = next; } // Backtrace: from the target, step to any neighbour one lower. const path: string[] = []; let cur = { ...tgt }; while (d[cur.y][cur.x] > 0) { path.push(`(${cur.x},${cur.y})`); for (const [dx, dy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const x = cur.x + dx, y = cur.y + dy; if (x >= 0 && y >= 0 && x < W && y < H && d[y][x] === d[cur.y][cur.x] - 1) { cur = { x, y }; break; } } } path.push("(src)"); console.log("Wavefront distances ('##' = obstacle):"); for (let y = H - 1; y >= 0; y--) { console.log( d[y].map((v, x) => (blocked(x, y) ? "##" : v < 0 ? " ." : String(v).padStart(2))).join(" "), ); } console.log(`\nTarget reached at distance ${d[tgt.y][tgt.x]}`); console.log("Backtraced path: " + path.reverse().join(" → "));

Wirelength, quickly estimated

Long before detailed routing, tools score placements with the half-perimeter wirelength (HPWL): for each net, the half-perimeter of the bounding box of its pins — for a two-pin net, simply the Manhattan distance |x_1 - x_2| + |y_1 - y_2|. Summed over all nets it is a remarkably good proxy for final routed length, and it is what the placer's "springs" are really minimising.

placement seats millions of cells to minimise wirelength, congestion and timing — analytic (spring) placement, then legalization, then detailed polish;
routing runs in two acts: global (corridors, layers, congestion) then detailed (exact tracks and vias, design-rule-clean);
the metal stack is tiered: thin, dense lower layers for local hops; thick, fast upper layers for long-haul, clock and power;
maze routing (Lee): a BFS wavefront floods around obstacles and guarantees a shortest path whenever any path exists;
since wires dominate delay, placement is timing — critical cells are pulled together, and congestion is fixed by giving wires room (spread cells, lower utilization).

Because wires are built up, not sideways. After the transistors are formed, the fab alternates: deposit an insulating glass layer, etch trenches, fill them with copper, polish flat, repeat — each repetition one metal layer, each connected to the next by vias. The result, seen edge-on in a microscope, looks like a multi-storey car park stacked over a single floor of transistors. The tiering is deliberate economics: fine-pitch lower layers are expensive to pattern and slow (resistance rises viciously as wires thin — the interconnect wall again), so the stack fattens as it rises, ending in metal thick enough to carry whole amps of supply current. When designers say a net "goes up to M12 for the journey", they mean it exactly: the signal literally rides the express motorway on the top floors.

A junior engineer reports: "Placement converged, and routing completed 99.9% of nets — nearly there!" The senior engineer hears a disaster. With ten million nets, 99.9% leaves ten thousand unrouted — and they are not random stragglers: they are concentrated in exactly the most congested spots, where the router fought hardest and lost. The last 0.1% is not finished by trying harder; it is finished by making room — spreading cells, lowering utilization, sometimes reopening the floorplan. That can perturb timing, which perturbs placement… which is why the pros' rule is: routability is designed in from the floorplan onward, never hoped for at the end. A chip either routes to 100.000% or it does not tape out.