PathFinder Routing: Why Congestion Makes It Fail

Field programmable gate arrays present a routing problem that is unusually unforgiving. The device contains a fixed fabric of wires and programmable switches, the placement of logic blocks is decided before routing begins, and the connections that must be made are not known until the design is compiled. Routing therefore has to be solved as a resource allocation problem, and the algorithm that solves it has been the same for more than two decades in most tool chains.

That algorithm, known as PathFinder, routes each multi terminal net as a tree through the available interconnect, using a cost function that penalises both the length of the path and the use of resources that are already occupied by other nets. It is robust enough to have become a default, and it has known limitations that become visible when a design is large and the fabric is nearly full.

What Routing Has to Satisfy

Three requirements compete. Connections must not overlap, since two nets cannot occupy the same wire or switch resource. Delay must be bounded, because a path that is electrically connected but far too long will fail timing. And routing resources are finite, so the algorithm has to trade longer paths against congestion rather than optimising either alone.

PathFinder addresses this by treating each net as a tree that reaches all of its terminals, and by iteratively ripping up and re-routing connections whose cost is too high. The cost of using a resource includes a congestion term that rises as more nets compete for the same wire, so a net will accept a longer path to avoid a crowded region in later iterations. This negotiated congestion mechanism is what allows the algorithm to converge on a solution that respects both length and capacity, and it is the reason the approach has remained in use for so long.

How Negotiated Congestion Works

The process is iterative and gradually more selective. In early iterations the congestion penalty is small, so nets are allowed to share resources, and the algorithm concentrates on finding any connection at all. As iterations proceed, the penalty for sharing a resource increases, and nets are pushed apart onto their own paths. A net that was routed through a crowded region in the first pass migrates out of it in a later one, and the design converges towards an assignment in which every connection is unique.

Convergence depends on the growth rate of the penalty and on the order in which nets are processed, and it is not guaranteed. For designs well inside the capacity of the device, the process usually finishes quickly and the result is close to optimal. For designs that approach the resource limit, the iteration count rises, runtime increases sharply, and the outcome becomes sensitive to decisions that were never part of the design intent.

Three Known Weaknesses

Recent research into PathFinder routing behaviour has identified a set of limitations that appear when designs become large and congested. The first is that the routing tree produced for a net is sometimes larger than necessary. The algorithm can spread branches defensively, occupying more interconnect than the connection requires, which consumes resources that other nets then have to route around. The tree is valid, but it increases resource congestion for the design as a whole.

The second is sensitivity to order. When branches are added to a net, the sequence in which they are processed affects the outcome, so two runs that differ only in this order can produce different results, one succeeding and one failing. In small cases that should be routable, the algorithm can behave counterintuitively, which means the difference between a routed design and an unrouted one may depend on a decision that is invisible to the user.

The third is fragility in dense regions. Where resources are nearly exhausted, the algorithm can report a design as unroutable even though a valid solution exists. The practical consequence is familiar to anyone who has worked close to the capacity of a device: rather than accepting the limit, designers respond by selecting a larger FPGA, re-arranging the floorplan, or dropping part of the connectivity, none of which addresses the underlying allocation problem.

What a Designer Can Control

PathFinder itself is not accessible, but the conditions it operates under are. Placement is the most powerful lever, because routing difficulty follows from where logic blocks and memories end up. Spreading high fanout nets across the device, keeping related modules together, and avoiding a placement that funnels many connections through one region all reduce the congestion the router has to resolve.

Interface placement deserves particular attention. Pins and transceivers should be assigned so that the traffic they generate does not have to cross the whole fabric, and memory controllers should face the banks they serve. The routing and escape practices that apply to dense boards are described in escape routing and fanout, and the constraint thinking behind them is the same as for high density interconnect design. Making routing failure a review item, checked with the same discipline as the PCBA development process, keeps the problem visible before it becomes a schedule risk.

When a design will not route, the useful question is whether the device is genuinely full or whether the tool has reached one of its known limits. Raising the routing effort, changing the seed, or relaxing a non-critical timing target can sometimes resolve a case that appears impossible. Where those fail, moving to a larger device is honest, but it is worth documenting why, because timing closure on the next design depends on knowing which resource was actually exhausted.

Reading a Routing Failure Report

When routing fails, the report usually identifies the nets that could not be completed and the resources they were competing for. That information should be read as a congestion map rather than as a list of problems. Nets that fail together are usually passing through the same region, and the region rather than the nets is the real subject of the investigation. Plotting the failures on the floorplan turns an abstract message into a geographic problem that placement can address.

It is also worth separating two cases that look identical in the log. A design that fails because a small number of nets are in an impossible position can often be fixed by moving the logic that drives them, or by adding a pipeline register that shortens the paths. A design that fails because the fabric is genuinely full will fail again after any local change, and the honest response is to reduce the logic or select a larger device. Distinguishing the two early avoids a long sequence of ineffective attempts.

FAQ

Does a router failure mean the design cannot be built? Not necessarily. It means the algorithm did not find a solution under the constraints it was given. Changing placement, effort level or a timing target can change the outcome.

Why does the same design route on one run and fail on another? Because branch insertion order and the negotiation path affect the result. The algorithm is deterministic for a given input, but small changes upstream can lead it to a different solution.

Is a larger device the only answer to congestion? No. Reducing fanout, improving placement and reassigning interface pins often recover enough capacity that a device change becomes unnecessary.