Researchers at EPFL, AMD, and the University of Novi Sad have revealed a subtle but consequential weakness in PathFinder, a long-standing algorithm used to route circuits on field-programmable gate arrays (FPGAs), tells Tech Xplore. These chips are prized for flexibility, but their routing software must connect vast numbers of components without conflicts. PathFinder has been the industry standard since the 1990s, yet modern, large-scale designs sometimes render it incapable, labeling routable designs “unroutable.”
The team’s insight came from dissecting small but challenging routing problems extracted from real FPGA designs. They discovered that PathFinder’s failures often stem not from circuit complexity, but from the order in which it adds branches to routing trees. In effect, the algorithm sometimes builds unnecessarily large trees, increasing overlap risk and conflict, simply because it committed earlier decisions in an unlucky sequence.
To test their hypothesis, the researchers developed a framework that isolates “hard” subproblems and lets them observe PathFinder’s behavior in controlled settings. By permuting the branch-addition order and selecting the version that yields the smallest tree, they achieved much better routing success. This simple fix suggests the root issue was hidden all along: not that PathFinder was fundamentally broken, but that its heuristics were brittle when scaled.
The significance is twofold. First, it sheds light on why well-designed circuits sometimes fail to route on FPGAs using PathFinder, a mystery that has puzzled engineers for years. Second, it offers a path forward: a more intelligent ordering strategy could unlock better performance without reinventing the entire algorithm.
Moving ahead, the researchers plan to scale their solution, explore variants that work on larger designs, and integrate fixes into production FPGA tools. If successful, this work could impact how millions of reconfigurable chips are programmed, effectively breathing new life into a venerable algorithm.