11/01/1994 09:00 AM
Computer Engineering
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 source-sink 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-1/|S|) of the optimal Steiner tree for |S| sinks. In order to satisfy given delay bounds, we also propose a new algorithm to construct a maximal-delay-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.
