Rectilinear Steiner Trees and FLUTE
The idea
Connect n pins with rectilinear wire of minimum total length. The optimum may add Steiner points: junctions at none of the pins (a plus-sign junction joining four pins beats any pin-to-pin chaining). Hanan's theorem restricts the candidates to the grid of the pins' x and y coordinates; exact optimization is still NP-hard (Non-deterministic Polynomial hard), with the exact solver GeoSteiner practical into the tens of pins.
FLUTE's move
Real netlists are dominated by low-degree nets, and FLUTE (Fast LookUp Table Estimation) exploits exactly that. For every pin count up to nine, all positional orderings of pins fall into finitely many groups; FLUTE precomputes, per group, the small set of potentially optimal tree topologies as wirelength vectors. At runtime: sort the pins, look up the group, evaluate a handful of vectors, emit the best tree, microseconds per net, optimal for up to nine pins and near-optimal beyond via recursive net breaking.
The recipe
Step 1 (canonicalize). Sort the net's pins and reduce their coordinates to the position sequence that captures only their relative order: nets with the same relative order share the same optimal tree shapes, whatever their absolute coordinates.
Step 2 (look up). Use the position sequence to index the precomputed table, which stores, for every relative order up to 9 pins, the handful of potentially-optimal tree topologies as wirelength formulas in the pin coordinates.
Step 3 (evaluate and pick). Evaluate each candidate formula with the actual coordinates and keep the cheapest: an exact RSMT (Rectilinear Steiner Minimal Tree) for up to 9 pins, in microseconds, with the NP (Nondeterministic Polynomial time) hard search computed in advance when the table was built.
Step 4 (break big nets). For more than 9 pins, split the net into overlapping groups of at most 9, solve each by lookup, and merge: near-optimal in practice.
Where the choice comes from: the table
The table below is an illustrative mock of FLUTE's stored data for the four-pin configuration used in the walkthrough (pins at (7,1), (2,5), (12,5), (7,9)). Sorting the coordinates gives x = (2, 7, 7, 12) and y = (1, 5, 5, 9); the positional ordering of the pins selects a group, and the group stores a small set of candidate topologies as wirelength formulas over sorted-coordinate differences. At runtime each formula is evaluated and the minimum is selected.
| Candidate topology | Stored wirelength formula | Evaluated here | |
|---|---|---|---|
| Pin-to-pin chain, no junction | (x4 − x1) + 2(y2 − y1) + (y4 − y1) | 26 | |
| Trunk along y1 with three stubs | (x4 − x1) + (y2 − y1) + (y3 − y1) + (y4 − y1) | 26 | |
| Cross junction at (x2, y2) | (x4 − x1) + (y4 − y1) | 18 | selected |
The real table differs only in scale and encoding: all potentially optimal topologies per group are precomputed (there are finitely many for each degree up to nine), stored as coefficient vectors, and evaluated in a few additions per candidate. The choice of tree is therefore a table lookup plus a minimum, not a search.
This resolves the apparent conflict with NP-hardness (Non-deterministic Polynomial hardness). Hardness is a statement about growth with pin count; for any fixed degree the problem is finite, and the table construction solves it exhaustively once, offline. Nets of degree nine or below therefore receive the exact optimum at runtime; approximation enters only through net breaking for higher-degree nets.
Watch it work: why junctions win
Four pins, one net. Watch the Hanan grid appear, the best pin-to-pin spanning tree get measured, and one Steiner junction beat it by 30 percent.
Different pins, different trees
The gallery below computes every tree it shows. Two five-pin configurations receive different optimal topologies because their positional orderings select different table groups; an eight-pin net is solved by net breaking; and a final frame places a macro on the plane to show the division of labor: the table's topology is obstacle-blind, and the router re-embeds blocked segments around the obstacle, paying measured extra length.
Pros, cons, and the trade-off
Strengths
- Effectively free: microseconds per net; wirelength-optimal through nine pins, near-optimal beyond.
- The enabling primitive: global routing, placement wirelength estimation, and congestion maps all stand on cheap Steiner trees.
- Deterministic and simple to integrate: a lookup and a few comparisons; no search, no tuning.
- Theory-backed: Hanan's grid limits the candidates, and Hwang's bound guarantees even a plain spanning tree is within 50 percent of optimal (a few percent in practice).
Weaknesses
- Degree ceiling: past nine pins the table ends; recursive net breaking is good but no longer near-exact.
- Pure wirelength objective: timing-critical nets want shallow or buffered topologies, which need different constructions.
- Congestion-blind: topologies are chosen before routing knows where the crowds are; routers must bend or rebuild the tree afterward.
- Rectilinear only: diagonal-capable technologies need other techniques.
The trade-off
Decompose-then-route is an approximation everybody accepts: fix a near-optimal tree topology cheaply, then route its two-pin edges with the maze router. FLUTE made the first half so cheap that the approximation became the universal architecture.
Is it actually used today?
The evidence for Steiner-tree construction spans every stage of the physical-design flow, open source and commercial.
- Global routing: FastRoute inside OpenROAD decomposes every multi-pin net through FLUTE-style Steiner topologies before routing segments; commercial global routers do the equivalent.
- Placement and estimation: placers and congestion estimators call Steiner evaluators millions of times per run; FLUTE's cost profile is what makes that affordable.
- Research baselines: GeoSteiner remains the exact-optimum reference against which heuristic trees are scored.