"-Optimal Minimum-Delay/Area Zero-Skew Clock Tree Wire-Sizing in Pseudo-Polynomial Time

In 21st-Century VLSI design, clocking plays crucial roles for both performance and timing convergence. Due to their non-convex nature, optimal minimum-delay/area zero-skew wire-sizing problems have long been considered intractable. None of the existing approaches can guarantee optimality for general clock trees to the authors ' best knowledge. In this paper, we present an -optimal zero-skew wire-sizing algorithm, ClockTune, which guarantees zero-skew with de-lay and area within distance to the optimal solutions in pseudo-polynomial time. Extensive experimental results show that our algorithm executes very eciently in both runtime and memory usage. For example, ClockTune takes less than two minutes and 35MB memory to size an industrial clock tree with 3101 sink nodes within 2 % to the optimal solution on a 533MHz Pentium III PC. Our algorithm can also be used to achieve useful clock skew to facilitate timing con-vergence and to incrementally adjust clock tree for design convergence and explore delay/power tradeos during de-sign cycles. ClockTune is available on the web [13]. Categories and Subject Descriptor