Matching-based methods for high-performance clock routing
Authors:
- A.B. KahngAKA.B. Kahng
- G. RobinsGRG. Robins
- 1 January 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 12 (8) , 1157-1169
Abstract
The authors point out that minimizing clock skew is important in the design of high-performance VLSI systems. A general clock routing scheme that achieves extremely small clock skews while still using a reasonable amount of wirelength is presented. The routing solution is based on the construction of a binary tree using geometric matching. For cell-based designs, the total wirelength of the clock routing tree is on average within a constant factor of the wirelength in an optimal Steiner tree, and in the worst case is bounded by O(√l 1l2×1√n) for n terminals arbitrarily distributed in the l1×l2 grid. The bottom-up construction readily extends to general cell layouts, where it also achieves essentially zero clock skew within reasonably bounded total wirelength. The algorithms have been tested on numerous random examples and also on layouts of industrial benchmark circuits. The results are very promising: the clock routing yields near-zero average clock skew while using total wirelength competitive with that used by previously known methodsKeywords
This publication has 19 references indexed in Scilit:
- High-performance clock routing based on recursive geometric matching1991
- Clock skew optimizationIEEE Transactions on Computers, 1990
- Geometry helps in matching1988
- Asynchronous and Clocked Control Structures for VSLI Based Interconnection NetworksIEEE Transactions on Computers, 1983
- The Travelling Salesman Problem and Minimum Matching in the Unit SquareSIAM Journal on Computing, 1983
- Divide and Conquer Heuristics for Minimum Weighted Euclidean MatchingSIAM Journal on Computing, 1983
- Synchronizing Large Systolic Arrays1982
- The Rectilinear Steiner Tree Problem is $NP$-CompleteSIAM Journal on Applied Mathematics, 1977
- An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on GraphsJournal of the ACM, 1976
- The Transient Response of Damped Linear Networks with Particular Regard to Wideband AmplifiersJournal of Applied Physics, 1948