New Performance-Driven FPGA Routing Algorithms
Michael J. Alexander and Gabriel Robins
Department of Computer Science
University of Virginia
Charlottesville, VA 22903-2442
(Postscript Version), as appeared on pp. 562-567 of
1995 DAC proceedings.
Abstract
Motivated by the goal of increasing the performance of FPGA-based
designs, we propose effective Steiner and arborescence FPGA
routing algorithms. Our graph-based Steiner tree constructions have
provably-good performance bounds and outperform the best known ones in
practice, while our arborescence heuristics produce routing solutions
with optimal source-sink pathlengths at a reasonably low wirelength
penalty. We have incorporated our algorithms into an actual FPGA
router which routed a number of industrial circuits using channel
widths considerably smaller than was previously possible.