Potter: A Parallel Overlap-Tolerant Router for UltraScale FPGAs

Routing is a time-consuming stage in FPGA compilation, and various parallel approaches have been proposed to accelerate it by concurrently routing non-overlapping nets. However, the requirement for non-overlapping nets limits the potential for large-scale parallelism, primarily due to two factors: (1) large circuits inherently contain many nets with overlapping bounding boxes, and (2) in modern FPGAs, such as Xilinx UltraScale FPGAs, a net with a large bounding box often has high occupancy but low utilization of the routing resources. To overcome these limitations, we present Potter, a novel parallel overlap-tolerant router designed to maximize parallelism. Our approach employs recursive partitioning to divide nets into balanced partitions with minimized overlap and allows for routing these partitions in parallel. Additionally, we propose an innovative mechanism for updating the congestion factors to enhance PathFinder in handling routing resource overflows. Evaluations on the FPGA 2024 contest benchmarks demonstrate that Potter achieves significant performance improvements, with average speedups of 12× and 8× compared to RWRoute and Vivado, respectively, while also reducing wire lengths by 4% and 45%. Notably, in some congested benchmarks, Potter exhibits a substantial 30× speedup over RWRoute.