A Clustering Based Fast Clock Schedule Algorithm for Light Clock-Trees

Makoto SAITOH  Masaaki AZUMA  Atsushi TAKAHASHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.12   pp.2756-2763
Publication Date: 2002/12/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Clock Scheduling
semi-synchronous circuit,  clustering,  clock-scheduling,  clock tree,  

Full Text: PDF>>
Buy this Article

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. The registers in each cluster are driven by a buffer and a shorter wire length can be achieved. 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, the clock period achieved in average is about 13% shorter than that achieved by a zero-skew clock tree, and about 4% longer than the theoretical minimum. The wire length and power consumption of a clock tree according to an obtained clock schedule is comparable to these of a zero skew tree.