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.