Published Articles >> Table of Contents >> Abstract

Fifth Great Lakes Symposium on VLSI (GLSVLSI'95)   p. 198
Fast algorithm for performance-oriented Steiner routing
M. Borah, Dept. of Comput. Sci. & Eng., Pennsylvania State Univ., University Park, PA, USA
R.M. Owens, Dept. of Comput. Sci. & Eng., Pennsylvania State Univ., University Park, PA, USA
M.J. Irwin, Dept. of Comput. Sci. & Eng., Pennsylvania State Univ., University Park, PA, USA

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/GLSV.1995.516052
Send link to a friend

Abstract
We present a routing algorithm which minimizes the Elmore delay to the identified critical sinks while producing routes comparable to the best previously existing Steiner router. Since performance oriented layout generators employ iterative techniques that require a large number of calls to the routing algorithm for layout evaluation, a fast algorithm for routing is desirable. Our algorithm has a fast (O(n/sup 2/), where n is the number of points) and practical implementation using simple data structures and techniques. Comparisons with other existing algorithms are presented along with results from a performance driven layout generator using our routing algorithm.
Back to Top Additional Information
Index Terms- network routing; integrated circuit layout; VLSI; circuit layout CAD; iterative methods; data structures; computational complexity; delays; performance-oriented Steiner routing; fast routing algorithm; Elmore delay minimisation; layout generators; iterative techniques; data structures Citation:  M. Borah, R.M. Owens, M.J. Irwin, "Fast algorithm for performance-oriented Steiner routing," glsvlsi, p. 198,  Fifth Great Lakes Symposium on VLSI (GLSVLSI'95),  1995