Rectilinear Steiner Trees with Minimum Elmore Delay

Report
Authors:Boese, Kenneth, Department of Computer ScienceUniversity of Virginia Kahng, Andrew, Department of Computer ScienceUniversity of Virginia McCoy, Bernard, Department of Computer ScienceUniversity of Virginia Robins, Gabriel, Department of Computer ScienceUniversity of Virginia
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

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

Boese, Kenneth, Andrew Kahng, Bernard McCoy, and Gabriel Robins. "Rectilinear Steiner Trees with Minimum Elmore Delay." University of Virginia Dept. of Computer Science Tech Report (1994).

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