page 1  (38 pages)
2to next section

An Iterative Approach for Delay-Bounded
Minimum Steiner Tree Construction

Qing Zhu Mehrdad Parsa Wayne W.M. Dai

Board of Studies in Computer Engineering
University of California, Santa Cruz, CA 95064
qingz, courant, dai@cse.ucsc.edu
UCSC-CRL-94-39, Oct. 1994

Abstract

This paper presents a delay-bounded minimum Steiner tree algorithm. The delay bounds, given as inputs to the algorithm, can be different for each individual sourcesink connection. The approach is based on feasible search optimization that satisfies the delay bounds first, then improves the routing tree for the cost minimization. Iterative cut-and-link tree transformation constrained by delay bounds provides an efficient technique to reduce the cost. Once reasonable delay bounds are set, this algorithm constructs Steiner trees with the correct timing, and by experiments the costs are always less than the trees obtained by a well-known, provably near-optimal Steiner-tree heuristic within the factor 2(1 ? 1j Sj ) of the optimal Steiner tree for jSj sinks. In order to satisfy given delay bounds, we also propose a new algorithm to construct a maximaldelay-slack tree based on the global information of sink delay slacks. The use of our algorithm is especially attractive for deep-submicron VLSI layout or MCM substrate layout where the interconnect resistance is comparable to the driver on-resistance, when the minimal delay tree may have an unacceptably high cost while the traditional minimum Steiner tree fails the delay requirements.

Steiner tree, minimum Steiner tree, delay-bounded minimum Steiner tree, routing, delay-bounded routing, layout, timing-driven layout, shortest path, feasible search optimization