Explore / Methods & Algorithms / Routing / PathFinder Negotiated Congestion

PathFinder Negotiated Congestion

Routing industry global routing 1995 McMurchie and Ebeling converges in practice principled pricing

The idea

Rip-up and reroute with the economics made explicit. Every routing resource (a wire segment, a grid edge) carries a cost with three factors: its base cost, a present congestion multiplier that grows with how many nets currently occupy it beyond capacity, and a historical congestion term that accumulates a little every iteration the resource stays overused. Each iteration, every net is ripped and re-routed by shortest path (an A*-family search) under current prices, overuse temporarily permitted. Early on, prices are gentle: nets take their ideal paths and pile up. As iterations proceed, contested resources grow expensive; nets with good alternatives peel away voluntarily; the history term ensures chronically contested resources stay pricey even when momentarily free, breaking the oscillations that plague naive rip-up. What remains on a scarce resource is the net that values it most, precisely the negotiation the name promises.

Watch it work: prices doing the planning

Three nets and two routing resources: the preferred gap A, capacity one, and the longer alternative gap B, two tracks wide (rows 2 and 3), capacity two: enough for every net that ends up there to have its own crossing cell. The right panel shows each resource's current price, usage, and overuse. Every decision in the animation is computed from one stated model:

cost(net, gap) = detour(net, gap) + price(gap)
  • detour extra wirelength the net pays to reach that gap, fixed by geometry (derived below)
  • price(gap) price(A) starts at 0 and rises by 2 × overuse after each iteration; gap B is never overused, so price(B) stays 0

Where the detour numbers come from

Both pins of each net sit on a single row, and the wall admits crossings only at gap A (a single track on row 6) and gap B (two tracks, on rows 2 and 3). To cross on a track that is not the net's own row, a net must leave its row to reach the track, cross, and come back. Each row of offset costs one step down and one step back up, so the extra wirelength over the straight, wall-free path is twice the row offset:

detour(net, track) = 2 × |row(net) − row(track)|
  • row(net) the row the net's two pins share (N1: row 5, N2: row 7, N3: row 3)
  • row(track) the row the net crosses the wall on (gap A: row 6; gap B: rows 2 and 3, one net per track)
  • 2 × one departure from the net's row plus one return after crossing

For N1 on row 5, that gives 2 × |5 − 6| = 2 through gap A. Inside gap B, N3 sits level with the row 3 track (2 × |3 − 3| = 0, it crosses without leaving its row) and claims it every iteration, so the track gap B offers N1 is row 2: 2 × |5 − 2| = 6. N3's pair therefore flips relative to N1's: 6 through A, 0 through B. These detours are pure geometry; negotiation never changes them, it only changes the prices added on top. The animation derives the numbers on N1's first decision step: both candidate paths are drawn (chosen path solid, rejected path dashed) with row numbers labeled along the left edge.

Each net independently picks the cheaper gap at the posted price. The captions show every net's arithmetic per iteration; convergence and the winner follow from the numbers.

Pros, cons, and the trade-off

Strengths

  • Principled pricing: present plus historical congestion costs solve the oscillation problem that naive rip-up cannot.
  • Reliable in practice: converges dependably on real FPGA (Field-Programmable Gate Array) and chip workloads.
  • Timing-driven naturally: critical nets simply negotiate harder through cost weighting.
  • Parallelizable: nets route independently within an iteration, which modern multi-core routers exploit.

Weaknesses

  • No convergence theorem: reliability is empirical; adversarial instances can thrash.
  • Iteration cost: hard congestion means many full-netlist passes.
  • Schedule tuning: how fast prices rise governs quality-versus-runtime and is set by hand.
  • Born for fixed fabrics: the cleanest fit is FPGA routing's fixed resource graph; chip adaptations blend it with other methods.

The trade-off

PathFinder turns global coordination into local economics: no planner assigns resources, prices do. Nets with alternatives get priced out of contested wires, and the net that truly needs a resource outbids the rest. It is the intellectual core of congestion-driven routing, twenty-five years on.

Is it actually used today?

The evidence for PathFinder spans FPGA (Field-Programmable Gate Array) compilation, chip global routing, and the field's vocabulary.

  • FPGA (Field-Programmable Gate Array) compilation: VPR (Versatile Place and Route) and the industrial FPGA routers descended from it run PathFinder-family negotiated congestion as the routing algorithm, full stop.
  • Chip global routing: the per-edge overflow costs and history terms inside FastRoute and its commercial peers are PathFinder economics applied to a Steiner-decomposed problem.
  • The vocabulary: when any tool's documentation says "negotiation-based" or "history cost", it is citing this algorithm.

References and further reading