Tear Down The Wall: Unified and Efficient Intra-and Inter-Cluster Routing for FPGAs

Routing is one of the most time-consuming phases of the FPGA CAD flow, and its quality of result greatly impacts design speed and whether a successful implementation is achieved with the fixed wiring resources available. Routing is also strongly affected by the FPGA programmable interconnect architecture, making data-driven algorithms crucial to explore new fabrics. The VTR CAD flow has historically split the routing problem into two parts: within the logic cluster and between clusters. This allows a flexible specification of the programmable interconnect of each of these components and also simplifies the routing problem by splitting it into two sub-problems. However, for some architectures, this split can significantly reduce result quality, so in this work, we develop a single-stage router, run-flat, that can simultaneously optimize the intra-cluster and inter-cluster routing. We show that this new router increases the generality of architectures VTR can target and improves the quality of results at the cost of a run time increase. We detail router enhancements that reduce memory by removing non-essential nodes from the routing architecture, reduce run time by accurately ranking partial routing choices with an enhanced lookahead and efficiently resolve resource overuse at choke points with a new net-aware congestion model. Over the VTR benchmarks on an architecture with partial crossbars within the logic clusters, run-flat reduces the minimum channel width by 14% and critical path delay by 2% on average at the cost of 2.7 xthe router run time. On the Titan benchmark suite on a Stratix-IV-like architecture, run-flat reduces wirelength by 6% while taking 1.36 x the router run time.