Rip-Up and Reroute
The idea
Nets are routed one at a time, and each committed route becomes an obstacle for the nets after it. The outcome therefore depends on routing order, and selecting an optimal order is intractable: the joint routing problem is NP-hard (Non-deterministic Polynomial hard). Rip-up and reroute replaces order selection with iterative repair.
Step 1: Route. Route every net sequentially, accepting failures and over-capacity resources rather than stopping.
Step 2: Select victims. Identify nets to remove: failed nets, nets through over-capacity regions, or nets whose removal unblocks another.
Step 3: Rip up. Delete the victims' routes; their resources return to the pool.
Step 4: Reprice. Update costs so contested resources appear expensive and freed space appears available. The pricing rule is the main design variable; PathFinder's present-plus-history scheme is its principled form.
Step 5: Reroute. Route the victims again under the new costs, possibly in a new order. Return to Step 2 until no violations remain or an iteration limit is reached.
How victims are identified
Blockers are not deduced in advance; they are observed or discovered:
- Overflow bookkeeping: every resource tracks occupancy versus capacity, so over-capacity resources and the nets occupying them are read directly from tables.
- Probe routing: a failed net is searched again with committed nets penalized instead of forbidden. The minimum-penalty path it finds crosses specific committed nets, and those are, by construction, the nets whose removal unblocks it along its best corridor. The failed net's own search produces the victim list.
- Violation ownership: in detailed routing, each DRC (Design Rule Check) violation involves shapes owned by specific nets; those nets, plus neighbors within a window around the violation, are selected.
- Or no selection at all: PathFinder rips every net every iteration and lets pricing resolve contention, removing the question entirely.
Watch it work: commit, regret, repair
Two nets contend for one preferred gap. The frames follow one full repair cycle: the initial order commits the gap to the wrong net, the rip-up returns it to the pool, and the reroute produces the better allocation, with total wirelength measured before and after.
Convergence behavior
No convergence or optimality guarantee exists; the loop is a heuristic. Two nets can evict each other indefinitely unless the pricing carries memory, so history terms (costs that accumulate on repeatedly contested resources) are the standard remedy, with iteration limits as the backstop. Variants differ in victim selection (worst overflow first, history-weighted, conflict-graph-guided) and in granularity (single nets versus whole regions). With history-bearing costs, the loop converges quickly on production designs; instances that thrash exist but are rare in practice.
Pros, cons, and the trade-off
Strengths
- Universal: composes with any router, cost scheme, or technology; it is a control loop with no assumptions about the search inside it.
- Anytime behavior: every iteration ends with a complete routing; the loop can stop whenever the result is acceptable.
- Simple to construct: victim selection plus re-invocation of an existing router.
- Empirically reliable: with history-bearing costs it converges quickly on production designs.
Weaknesses
- No guarantees: neither convergence nor solution quality is provable in general.
- Oscillation risk: mutual eviction cycles require history costs or iteration limits to break.
- Heuristic victim selection: the choice of what to rip is unprincipled, and poor choices waste iterations.
- Can mask upstream problems: a placement that should be repaired is sometimes routed around instead, at a wirelength and runtime cost.
The trade-off
Sequential routing commits resources in an order that cannot be chosen optimally in advance. Rip-up and reroute replaces order selection with iteration: commit cheaply, measure the resulting contention, reprice, and re-commit. Guarantees are surrendered; in exchange, the loop reaches allocations that no computable single-pass order would find, and it does so on every production design routed today.
Is it actually used today?
The evidence for rip-up-and-reroute comes from router architecture documentation, open source and commercial.
- Detailed routing: TritonRoute's convergence is a rip-up-and-reroute loop driven by DRC (Design Rule Check) violation counts, iterated until clean; commercial detailed routers share the structure.
- Global routing: overflow-driven rip-up under rising congestion costs is the core of FastRoute and its peers.
- Observable: the per-iteration violation and overflow counts in any routing log are this loop's progress metric.