PathFinder

TLDR

Routing FPGAs is difficult due to scarce routing resources, which can cause slow implementations or routing failures. The paper introduces PathFinder, a router that balances performance and routability. PathFinder iteratively negotiates routing resources, ensuring all signals are routed while giving critical signals priority, and uses a directed‑graph model that adapts to various FPGA architectures. On Triptych, PathFinder’s critical path delay is only 4.5 % higher than optimum, and on Xilinx 3000 it achieves higher completion rates and 11 % faster implementations than commercial tools.

Abstract

Routing FPGAs is a challenging problem because of the relative scarcity of routing resources, both wires and connection points. This can lead either to slow implementations caused by long wiring paths that avoid congestion or a failure to route all signals. This paper presents PathFinder, a router that balances the goals of performance and routability. PathFinder uses an iterative algorithm that converges to a solution in which all signals are routed while achieving close to the optimal performance allowed by the placement. Routability is achieved by forcing signals to negotiate for a resource and thereby determine which signal needs the resource most. Delay is minimized by allowing the more critical signals a greater say in this negotiation. Because PathFinder requires only a directed graph to describe the architecture of routing resources, it adapts readily to a wide variety of FPGA architectures such as Triptych, Xilinx 3000 and mesh-connected arrays of FPGAs. The results of routing ISCAS benchmarks on the Triptych FPGA architecture show an average increase of only 4.5% in critical path delay over the optimum delay for a placement. Routes of ISCAS benchmarks on the Xilinx 3000 architecture show a greater completion rate than commercial tools, as well as 11% faster implementations.