← back to legend
Physical / electrical concepts

Negotiated congestion (PathFinder)

1995 method from FPGA routing: let nets overlap at first, then make crowded spots more expensive each round until everyone negotiates their own space. Its "history cost" works like ant pheromone.

How it looks

Drawing: a routing grid, not a part of CORE3588
AABB
A drawing on a routing grid, computed with the PathFinder rule for this card. After 2 rounds the two nets no longer share any square: net B moved to a side gap because the squares both had used (shaded) became expensive.

How it works

AABB+1+1+1two nets, three gaps in a wall of parts. The middle gap is shortest for bothround 1: 3 squares used by both nets (circled): not legal yetshared squares get a surcharge that stays (history cost)round 2: no square is shared. Legal

Where it fits

PathFinder came from routing FPGAs in 1995 and is behind the strongest modern PCB routers. It is one way to do dial 2 of the three dials (negotiation (routing)); the alternatives are net ordering and rip-up and reroute.

Each round is just the normal search (A*) with a cost function whose crowding price rises round by round.

← back to legend