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.


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.

1. Introduction

2. Problem Formulation

3. A Graph Steiner Tree Heuristic

4. Path-Folding Heuristic

5. Iterated Dominance Heuristic

6. Experimental Results

7. Acknowledgments