Field-Programmable Gate Arrays (FPGAs) are flexible and reusable high-density circuits that can be (re)configured by the designer, enabling the VLSI design/validation/simulation cycle to be performed more quickly and cheaply [19]. The flexibility provided by FPGAs incurs a substantial performance penalty due to signal delay through the programmable routing resources, and this is currently a primary concern of FPGA designers and users [16]. In order to increase FPGA performance, partitioning and technology mapping have been used to minimize the length of critical paths [3]. On the other hand, less attention has been focused on the actual routing, which is surprising since circuit performance is limited by routing delays, rather than by combinational logic delays [11].
Routing affects the performance of FPGA-based systems in two major ways. First, a typical design must be partitioned and mapped onto several FPGAs. Because FPGA size is fixed, the ability to pack larger partitions onto a single FPGA can reduce the total number of partitions (and hence FPGAs) required to implement the design. The feasibility of implementing a piece of the design on a single FPGA is often limited by routing-resource availability; this motivates Steiner routing constructions which minimize use of routing resources.
Second, since FPGA resource utilization typically does not exceed 80%, considerable flexibility remains onboard the FPGA for optimizing the routing. For example, we could reduce signal propagation delay through critical paths by using the most direct interconnections (i.e., shortest paths), where a secondary criterion is to minimize wirelength in order to reduce capacitance and conserve routing resources. This motivates Steiner arborescence constructions (i.e., shortest-paths trees having minimum wirelength) for critical-net routing.
Our first contribution is a class of algorithms for non-critical-net routing which can outperform the best known graph Steiner tree heuristics, i.e., those of Kou, Markowsky and Berman [12], and of Zelikovsky [20]. Our graph Steiner construction is based on an iterative template that uses any given Steiner tree heuristic H by greedily selecting Steiner nodes that induce maximum wirelength savings with respect to H. The theoretical performance bound is guaranteed to be no worse than that of H, and in practice the construction will tend to outperform H.
Our second contribution is a pair of arborescence-based constructions for critical-net routing. Given an arbitrary weighted routing graph, our arborescence algorithms produce a Steiner tree where all source-sink paths are shortest-possible, and where total wirelength is optimized as a secondary objective. Our first graph Steiner arborescence heuristic is based on a path-folding strategy that overlaps and merges shortest paths in order to reduce the overall wirelength. Our second heuristic iteratively selects Steiner nodes which improve the total wirelength.
We have incorporated our algorithms into an actual FPGA router and successfully routed industry benchmark circuits using considerably smaller channel width than previous routers. Our routing benchmarks are currently the best among all published results. The total wirelength used by our arborescence constructions in unit-weighted grid graphs is on par with the best graph Steiner tree heuristics. This is interesting, since our arborescence solutions have optimal source-sink pathlengths, while Steiner tree heuristics are designed to only optimize wirelength.