Rectilinear Steiner Trees with Minimum Elmore Delay

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

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).