Matching-Based Methods for High-Performance
Jason Cong, Andrew B. Kahng, Gabriel Robins · 1993
Minimizing clock skew is important in the design of high performance VLSI systems. We present a general clock routing scheme that achieves very small clock skews while still using a reasonable amount of wirelength. Our routing solution is based on the construction of a binary tree using geometric matching. For cell-based designs, the total wirelength of our 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(a . &) for n terminals arbitrarily distrib- uted in the 1, X 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. We have tested our algorithms on numerous random examples and also on layouts of industrial benchmark circuits. The re- sults are promising: our clock routing yields near-zero average clock skew while using total wirelength competitive with pre- viously known methods.