Layer Assignment and Via Minimization
The idea
A modern stack has ten or more metal layers, each with a preferred direction, a track capacity, and its own electrical character: thin, resistive wires on the bottom layers, thick fast ones on top. A 2D route says where a net goes; layer assignment decides which layer each segment rides, and every change of layer costs a via. The per-net objective:
r(layer)resistance per unit length on the segment's layer; thick top metal is several times lower than the thin bottom layersvthe cost of one via: added resistance, and blocked tracks on both layers it connects- subject to each layer's track capacity per region and its preferred direction
Two classic moves fall out of the same objective. Via minimization assigns consecutive segments to the same layer so staircases merge into long straight runs (the constrained version of this problem is NP (Nondeterministic Polynomial time) hard, but per-net dynamic programming is exact and fast). Promotion moves a timing-critical run to thick top metal, paying a taller via stack for several times less resistance.
The recipe
Step 1 (route in 2D). Run global routing on a single collapsed plane, all metal layers folded into one: every net gets a 2D tree, which is its corridor of GCells with the cell centers connected. Each straight run of the tree will become one or more layer-assigned segments; the tree's turns are where vias may be needed.
Step 2 (assign per net, by dynamic programming). Walk each net's tree; for every segment and every legal layer, keep the cheapest cost of the subtree so far. The best leaf-to-root combination is exact for that net under the current capacities.
Step 3 (respect capacity). Deduct each assignment from its layer's per-region capacity; when a layer fills, later nets price it accordingly, congestion handling again, now in the third dimension.
Watch it work: the same net, three assignments
One net whose 2D geometry never changes; only the layers do. The walkthrough steps through the naive direction-matched assignment segment by segment, totals its vias and resistance, removes vias by allowing short wrong-way runs, promotes the long run to thick metal with the via-stack cost included, and ends on the per-segment decision rule and why dynamic programming solves it. Every via count and resistance figure in the captions is computed from the drawn assignment.
Pros, cons, and the trade-off
Strengths
- Exact per net: dynamic programming over a net's tree finds that net's optimal assignment in linear time.
- Big electrical wins: promoting a long critical run to thick metal is one of the cheapest timing fixes in the flow.
- Fewer vias, better yield: vias are a dominant failure and resistance source; minimizing them helps everything downstream.
- Separable: 2D routing plus layer assignment decomposes a 3D search that would otherwise be far more expensive.
Weaknesses
- Per-net exactness is not global optimality: nets assigned in sequence contend for layer capacity; ordering effects return.
- The 2D bet can lose: a route optimal on the collapsed plane may have no good layer embedding in a crowded stack.
- Capacity abstraction: per-region layer capacities approximate real track and via-rule interactions; errors surface in detailed routing.
The trade-off
Layer assignment is the flow's second act of dimensional information hiding: solve the plan in two dimensions where congestion is visible, then solve the stack per net where electrical cost is visible. The seam costs the same kind of repair iterations as the global-to-detailed seam, and earns the same speed.
Is it actually used today?
The evidence for layer assignment comes from open-source global routers, user-level commercial controls, and the academic lineage.
- Open source: FastRoute in OpenROAD follows the FastRoute 4.0 architecture: 2D routing first, then via-aware layer assignment by per-net dynamic programming.
- Commercial: partly documented, partly inferred. That commercial flows assign layers with resistance-aware promotion of critical nets is documented at the user level (layer-promotion and non-default-rule controls are exposed in every major tool). That the internal engine is 2D routing followed by per-net dynamic programming, as in FastRoute 4.0, is inference from the academic lineage; the vendors do not publish it.
- The lineage: constrained via minimization was formalized in the channel era (Pinter, 1984, and contemporaries); the modern per-net dynamic-programming form is the FastRoute 4.0 (2009) design.