PathSteiner: Improving PathFinder with Quasi-Optimal Steiner-Tree Initialization

FPGA routing has been studied for a few decades due to its critical role in determining both the quality of results and compilation time. Recent work has shown that constructing more resource-efficient routing trees can improve both runtime and wirelength. Yet, the proposed approach of constructing multiple routing trees per net via random sink orderings—within the PathFinder routing paradigm—and selecting the best candidate becomes increasingly impractical as net fanout grows. This limitation arises because the space of possible sink orderings grows super-exponentially, allowing only a small fraction of it to be explored in practice. Moreover, even exhaustive enumeration of all sink permutations for low-fanout nets does not necessarily yield an optimal routing tree. To address these limitations, we initialize routing with quasi-optimal rectilinear Steiner trees to better cover the solution space across net fanouts. Our results show that, because these trees are only weakly congestion-aware, the final routed wirelength gains are real but fall short of the wirelength advantage implied by the seeded trees. How much of the gain remains depends on how effectively PathFinder resolves congestion while staying close to the seed. We report an average 6% improvement in wirelength, along with an 8× reduction in runtime on the most congested benchmark, which otherwise takes more than half a day to route.