Bounded-skew clock and Steiner routing
Authors:
Open Access
- 1 July 1998
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Design Automation of Electronic Systems
- Vol. 3 (3) , 341-388
Abstract
We study the minimum-cost bounded-skew routing tree problem under the pathlength (linear) and Elmore delay models. This problem captures several engineering tradeoffs in the design of routing topologies with controlled skew. Our bounded-skew routing algorithm, called the BST/DME algorithm, extends the DME algorithm for exact zero-skew trees via the concept of a merging region . For a prescribed topology , BST/DME constructs a bounded-skew tree (BST) in two phases: (i) a bottom-up phase to construct a binary tree of 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. We present two approaches to construct the merging regions: (i) the Boundary Merging and Embedding (BME) method which utilizes merging points that are restricted to the boundaries of merging regions, and (ii) the Interior Merging and Embedding (IME) algorithm which employs a sampling strategy and a dynamic programming-based selection technique to consider merging points that are interior to, as well as on the boundary of, the merging regions. When the topology is not prescribed, we propose a new Greedy -BST/DME algorithm which combines the merging region computation with topology generation. The Greedy-BST/DME algorithm very closely matches the best known heuristics for the zero-skew case and for the unbounded-skew case (i.e., the Steiner minimal tree problem). Experimental results show that our BST algorithms can produce a set of routing solutions with smooth skew and wire length tradeoffs.Keywords
This publication has 11 references indexed in Scilit:
- Practical Bounded-Skew Clock RoutingJournal of Signal Processing Systems, 1997
- Performance optimization of VLSI interconnect layoutIntegration, 1996
- Post-processing of clock trees via wiresizing and buffering for robust designIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996
- Planar-DME: a single-layer zero-skew clock tree routerIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996
- Optimal wiresizing under Elmore delay modelIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1995
- On Optimal Interconnections for VLSI1995
- Near-optimal critical sink routing tree constructionsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1995
- Simultaneous driver and wire sizing for performance and power optimizationIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1994
- An exact zero-skew clock routing algorithmIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- The Transient Response of Damped Linear Networks with Particular Regard to Wideband AmplifiersJournal of Applied Physics, 1948