Clustering based fast clock scheduling for light clock-tree

We introduce a clock schedule algorithm to obtain a clock schedule that achieves a shorter clock period and that can be realized by a light clock tree. A shorter clock period can be achieved by controlling the clock input timing of each register but the required wire length and power consumption of a clock tree tends to be large if clock input timings are determined without considering the locations of registers. To overcome the drawback, our algorithm constructs a cluster that consists of registers with the same clock input timing located in a close area. In our algorithm, first registers are partitioned into clusters by their locations, and clusters are modified to improve the clock period while maintaining the radius of each cluster small. In our experiments for an industrial data of 888 registers, the clock period achieved is 27% shorter than that achieved by a zero-skew clock tree, and 1% longer than the theoretical minimum. The computational time is about 24.9 seconds and the wire length and power consumption of the clock tree is comparable to those of a zero skew tree