10/01/1993 09:00 AM
Computer Engineering
The timing-driven routing of a critical net can be implemented as a delay-bounded minimum Steiner tree. This routing tree has the path delays always limited no larger than a delay bound D, while the total wire length is minimized. The delay bound is usually specified at the system/logic design stage. The routing maintains this delay bound to guarantee the correct timing of the finally implemented system in physical layout. We propose a new algorithm of constructing delay bounded minimum Steiner tree. This algorithm is designed based on the observation that this tree can be obtained based on the trade-off between two other special types of Steiner tree: (1) minimum Steiner tree and (2) minimum path delay Steiner tree, by taking into account of a delay bound D. We also proposed a new algorithm of constructing the minimum delay Steiner tree. During the tree growing, the Elmore delay is incremently updated in constant time. These novel Steiner tree algorithms have been applied on a clock routing scheme for multi-chip modules based on area pad interconnections.
