New Graph Arborescence and Steiner Constructions for High-Performance FPGA Routing

Report
Authors:Alexander, Michael, Department of Computer ScienceUniversity of Virginia Robins, Gabriel, Department of Computer ScienceUniversity of Virginia
Abstract:

The flexibility and reusability of field-programmable gate arrays (FPGAs) enable significant speed and cost savings in the VLSI design/validation/simulation cycle. However, this is achieved at a substantial performance penalty due to signal delays through the programmable interconnect. This motivates a critical-net routing objective which seeks to minimize source-sink signal propagation delays; we formulate this objective as a graph Steiner arborescence (i.e., shortest-path tree with minimum wirelength) problem and propose an effective heuristic which produces routing trees with optimal source-sink pathlengths, and having wirelength on par with the best existing graph Steiner tree heuristics. Our second contribution is a new class of greedy Steiner tree constructions in weighted graphs, based on an iterated application of an arbitrary given graph Steiner heuristic; this construction significantly outperforms the best known graph Steiner tree heuristics of Kou, Markowsky and Berman, and of Zelikovsky. We incorporated our algorithms into an actual router, enabling the complete routing of several industrial designs while requiring a reduced maximum channel width. All of our methods are directly applicable to other graph-based routing regimes, such as building-block design, routing in the presence of obstacles, etc., as well as in non-CAD areas such as multicasting in communication networks.

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Alexander, Michael, and Gabriel Robins. "New Graph Arborescence and Steiner Constructions for High-Performance FPGA Routing." University of Virginia Dept. of Computer Science Tech Report (1994).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1994