Explore / Methods & Algorithms / Routing / Pin Access Analysis

Pin Access Analysis

Routing industry detailed routing 2010s TritonRoute (Kahng, Wang, Xu); commercial routers the dominant failure at 7 nm and below

The idea

At advanced nodes the hardest part of a route is often its last few tracks. Cell pins on M1 are slivers one track wide, on-track positions are few, and a via onto the pin must satisfy enclosure, spacing, and end-of-line rules against every neighbouring shape in the cell. A maze search that discovers this at the pin, after expanding thousands of cells, has wasted the expansion and may still find no legal landing. Pin access analysis moves the problem in front of the search:

access(pin) = { (track, via pattern) : the via is legal under the full rule deck }

track a routing track on the layer above the pin that crosses the pin shape
via pattern a specific via geometry (cut, enclosures) placed at that crossing
legal passes enclosure, spacing to every neighbouring shape, and end-of-line rules; checked against real geometry, not a capacity abstraction

The set is computed once per pin, before routing, and the router then targets the set instead of the pin shape. A pin whose set is empty is reported as unroutable before a single net is searched, at the point where moving or flipping the cell is still cheap.

The recipe

Step 1 (enumerate). For each pin, list every candidate access point: each track on the layer above that crosses the pin shape, combined with each allowed via pattern.

Step 2 (check rules). Test each candidate against the deck: via enclosure by the pin metal, spacing to neighbouring pins and blockages, end-of-line and minimum-area rules. Discard failures.

Step 3 (record). Store the survivors as the pin's access-point set, with a preference order (on-track over off-track, fewer vias over more). Report pins with empty sets.

Step 4 (route to the set). During detailed routing, the search for a net terminates at any recorded access point of its pin, committing that point's via pattern. Enclosure and spacing at the pin need not be reasoned about in the search: the point is legal by construction.

Watch it work: one pin, seven candidates

A standard cell with a one-track-wide pin, a neighbouring pin, and an M1 blockage. The walkthrough enumerates the candidates on the M2 tracks, applies enclosure and spacing, records the survivors, routes to one, and ends on the empty-set failure that this pass exists to catch.

Pros, cons, and the trade-off

Strengths

Precomputed legality: the expensive rule checking at pins runs once, before the search, the same economics as FLUTE (Fast Lookup Table Estimation)'s lookup table.
Early failure reporting: an unreachable pin is known before routing, when the fix (move, flip, swap pin, change cell) is cheap.
Cleaner convergence: routes that end at pre-checked points do not generate the pin-area violation churn that dominates rip-up iterations at advanced nodes.

Weaknesses

Context blindness: access points are checked against the cell's own geometry; a neighbouring cell's routing can still invalidate one, so some checking recurs in the search.
Combinatorial at scale: pins times tracks times via patterns is large; production implementations prune aggressively and cache per cell type.
Library dependence: a poorly designed cell library has pins with tiny access sets no router can fix; the pass exposes the problem but cannot solve it.

The trade-off

Pin access analysis is the acknowledgement that, at advanced nodes, the search space's boundary is harder than its interior. It buys the search legal endpoints at the cost of a preprocessing pass and some duplicated checking, and it moves the field's most common failure from a late surprise to an early report.

Is it actually used today?

The evidence for pin access analysis comes from open-source detailed routers, the routing literature, and the failure statistics engineers meet at advanced nodes.

Open source: TritonRoute, OpenROAD's detailed router, runs an explicit pin-access stage that enumerates and rule-checks access points per pin before its search iterations; the stage is documented in the TritonRoute papers.
Commercial: partly documented, partly inferred. Commercial detailed routers report pin-access failures and expose pin-access options at the user level; that they precompute access-point sets in the same way is inference from the academic lineage.
The failure statistics: at 7 nm and below, pin access and via-rule violations, not congestion, dominate detailed routing DRC (Design Rule Check) reports, which is why the pass exists.