A Fast and Near-Optimal Clustering Algorithm for Low-Power Clock Tree Synthesis

Clocks are known to be major source of power consumption in digital circuits. In this paper, we propose a clustering algorithm for the minimization of power in a local clock tree. Given a set of sequentials and their locations, clustering is performed to determine the clock buffers that are required to synchronize the sequentials, where a cluster implies that a clock buffer drives all the sequentials in the cluster. The results produced by the algorithm are often within 1.3 × of the lower bound and have 32% lower costs, on average, than those due to an approximation algorithm with 2.5 × faster runtimes. Compared to competitive heuristic from a vendor tool, the results due to the algorithm on several blocks in microprocessor designs in advanced nanometer technologies show 14% reduction, on average, in clock tree power while meeting skew or slew constraints. The algorithm has been employed for clock tree synthesis for several microprocessor designs across process generations due to consistently significant clock tree power savings over the results due to competitive alternatives.