Item Details

Rectilinear Steiner Trees With Minimum Elmore Delay

Boese, Kenneth; Kahng, Andrew; McCoy, Bernard; Robins, Gabriel
Format
Report
Author
Boese, Kenneth
Kahng, Andrew
McCoy, Bernard
Robins, Gabriel
Abstract
We provide a new theoretical framework for constructing Steiner routing trees with minimum Elmore delay. Earlier work [3, 13] has established Elmore delay as a high fidelity estimate of "physical", i.e., SPICE- computed, signal delay. Previously, however, it was not known how to construct an Elmore delay-optimal Steiner tree. Our main theoretical result is a generalization of Hanan's theorem [1]] which limited the number ofpossible locations ofSteiner nodes in an optimal delay rectilinear Steiner tree. Another theoretical result establishes a new decomposition theorem for constructing optimal-delay Steiner trees. We develop a branch-andbound method, called BB - SORT - C, which ezactly minimizes any linear combination of Elmore sink delays; BB-SORT-C is practical for routing small nets and for delimiting the space of achievable routing solutions with respect to Elmore delay. Note: Abstract extracted from PDF file via OCR
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1994
Published Date
1994
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online