A fast algorithm for optimal wire-sizing under Elmore delay model

Author

Chen, Chung-Ping ; Wang, Dong

Author_Institution

Dept. of Comput. Sci., Texas Univ., Austin, TX, USA

Volume

4

fYear

1996

Firstpage

412

Abstract

We present a fast algorithm for continuous wire-sizing under the distributed Elmore delay model. Our algorithm GWSA-C, an extension of the GWSA algorithm (for discrete wire-sizing), is an iterative algorithm with guaranteed convergence to optimal wire-sizing solutions. When specialized to discrete wire-sizing problems, GWSA-C is an improved implementation of GWSB, both in terms of runtime and memory usage. GWSA-C is extremely fast even on very large problems. For example, we can solve a 1,000,000 wire-segment problem in less than 3 minutes runtime on an IBM RS/6000 workstation

Keywords

circuit layout CAD; circuit optimisation; convergence of numerical methods; delays; integrated circuit layout; iterative methods; network routing; GWSA-C algorithm; IBM RS/6000 workstation; discrete wire-sizing problems; distributed Elmore delay model; fast algorithm; guaranteed convergence; interconnect delay; iterative algorithm; optimal wire-sizing; wire sizing optimization; wire-segment problem; Algorithm design and analysis; Circuit optimization; Clocks; Delay; Distributed computing; Fabrication; Greedy algorithms; Iterative algorithms; Runtime; Wire;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1996. ISCAS '96., Connecting the World., 1996 IEEE International Symposium on

Conference_Location

Atlanta, GA

Print_ISBN

0-7803-3073-0

Type

conf

DOI

10.1109/ISCAS.1996.541989

Filename

541989