Item Details

Print View

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
2012-10-29
Published
University of Virginia, Department of Computer Science, 1994
Published Date
1994
Collection
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less

Availability

Access Online