| Aspects of clock distribution in VLSI circuits, including skew, phase delay and edge rate, strongly limit the achievable level of system performance. Clock distribution can account for a significant portion of wiring area and power dissipation, and is closely coupled to signal integrity and reliability issues. In this thesis, we address several important interconnect design problems related to lock distribution in high-performance synchronous systems.; First, we study the planar-embeddable zero-skew clock routing problem. We propose the Linear-Planar-DME method, which guarantees an optimal planar zero-skew clock (ZST) under pathlength delay. The subsequent Elmore-Planar-DME method uses the Linear-Planar-DME connection topology in constructing a low-cost ZST according to the Elmore delay model. The total wirelengths of these planar ZST solutions are comparable to those of best previous non-planar solutions.; Second, we study the minimum-cost bounded-skew routing tree problem. For a fixed tree topology, we first propose the Extended DME (Ex-DME) algorithm, which extends the DME algorithm to construct a bounded-skew tree (BST) two phases: (i) a bottom-up phase to construct a binary tree of so-called merging regions which represent the loci of possible embedding points of the internal nodes, and (ii) a top-down phase to determine the exact locations of the internal nodes.; For arbitrary topology, we propose the Extended Greedy-DME (ExG-DME) algorithm, which combines merging region computation with the topology approach of the the Greedy-DME algorithm (Eda93a). A key distinction is that ExG-DME allows merging at non-root nodes whereas Greedy-DME always merges two subtrees at their roots. For single-layer (planar) embedding under pathlength delay, we propose the Extended Planar-DME (ExP-DME) algorithm which simply uses Linear-Planar-DME to recursively partition the sink set until each sink cluster has radius less than B, then constructs a planar radius-bounded tree over each cluster.; Finally, we explores directions in which traditional formulations can be extended so that the resulting algorithms are more useful in production design environments. Specifically, the following issues are addressed: (i) clock routing for varying layer parasitics and non-zero via parasitics; (ii) obstacle-avoidance clock routing; and (iii) hierarchical buffered clock tree synthesis. |
