Pattern Routing
The idea
A maze or A* (A-star) search earns its cost when the route is hard, but most nets are not hard: on a mostly open die, the best route between two pins is almost always a straight line, a single-bend L, or a two-bend Z. Pattern routing takes that observation literally. Instead of searching the grid, it enumerates a fixed library of candidate shapes between the pins, prices each against the current congestion map, and commits the cheapest:
wirelengthcells the shape occupies; every 1-bend and 2-bend candidate between two pins has the same, minimal wirelengthprice(cell)congestion penalty from nets already routed, the same negotiated prices the PathFinder family maintains
Because every candidate already has minimal wirelength, the congestion penalties alone separate them: the pattern that threads between crowded regions wins.
The recipe
Step 1 (enumerate). Generate the candidates: the two L shapes (one bend, at either corner of the pins' bounding box) and the Z shapes (two bends, one per intermediate column or row).
Step 2 (price). Evaluate each candidate's cost with the equation above: a walk over its cells, no queue and no wavefront. The work per candidate is constant in the region's size.
Step 3 (commit or escalate). Commit the cheapest candidate and add its usage to the congestion map. If every candidate is blocked or exceeds a congestion threshold, hand the net to a real maze or A* (A-star) search: patterns for the bulk, search for the few.
Watch it work: pricing the shape library
One net, a congestion map from earlier nets (red cells, +2 each), and the candidate library priced one family per step: the two Ls, then the Zs, then the commit. Every cost in the captions is computed from the map.
Pros, cons, and the trade-off
Strengths
- Speed: constant work per net for the vast majority of nets; the reason global routers finish in minutes, not days.
- Predictability: a pattern's shape is known before routing, so wirelength and timing estimates made at placement hold.
- Composes with negotiation: pattern costs read the same congestion prices rip-up iterations maintain, so the two machineries share one currency.
- Trivially parallel: nets price their candidates independently.
Weaknesses
- Blind outside its library: a net whose best route needs three bends is invisible to the pattern set; only the fallback saves it.
- Fallback cliff: in dense regions the fallback rate climbs and the speed advantage erodes.
- Quality ceiling: committing shapes net by net can lock in congestion that a global view would have avoided; rip-up iterations must repair it.
The trade-off
Pattern routing bets that routing cost is concentrated in a small fraction of nets, and wins the bet on real designs: the easy majority is dispatched by arithmetic, and the full price of search is paid only where search earns it. It is the scheduling insight of the two-pass flow applied one level down.
Is it actually used today?
The evidence for pattern routing comes from open-source global routers, commercial architecture and patents, and the academic lineage.
- Open source: FastRoute, the global router inside OpenROAD, routes nets by L and Z patterns with congestion-priced selection, escalating to monotonic and maze routing only under congestion.
- Commercial: inferred, not verified. The global routers in Innovus, Fusion Compiler, and Aprisa do not publish their internals; what is public is that they run congestion-driven, negotiation-style global routing with cheap early passes and expensive escalation, and that vendor patents describe pattern-based candidate routing. That the fast early pass is literally L and Z enumeration is a reasonable inference from the architecture and the academic lineage, not a documented fact.
- The lineage: Kastner, Bozorgzadeh, and Sarrafzadeh's pattern-routing work (2000) framed the predictability argument; FastRoute (2006 onward) made the pattern-first pyramid the standard architecture.