MATCHING-BASED METHODS FOR HIGH-PERFORMANCE CLOCK ROUTING

Minimizing clock skew is important in the design of high performance V LSI systems. We present a general clock routing scheme that achieves v ery small clock skews while still using a reasonable amount of wirelen gth. Our routing solution is based on the construction of a binary tre e using geometric matching. For cell-based designs, the total wireleng th 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 b ounded by O(square-root l1l2 . square-root n) for n terminals arbitrar ily distributed in the l1 x l2 grid. The bottom-up construction readil y extends to general cell layouts, where it also achieves essentially zero clock skew within reasonably bounded total wirelength. We have te sted our algorithms on numerous random examples and also on layouts of industrial benchmark circuits. The results are promising: our clock r outing yields near-zero average clock skew while using total wirelengt h competitive with previously known methods.