Fast Timing-Model Independent Buffered Clock-Tree Synthesis

In high-performance synchronous chip design, a buffered clock tree with small clock skew is essential for improving clocking speed. Due to the insufficient accuracy of timing models for modern chip design, embedding simulation into a clock-tree synthesis flow becomes inevitable. Consequently, the running time for clock-tree synthesis becomes prohibitively huge as the complexity of chip designs grows rapidly. To construct a buffered clock tree efficiently, we propose an efficient timing-model independent approach to perform skew minimization by structural optimization. To achieve the goal, a novel clock-tree structure, called symmetrical structure, is presented. At each level of a symmetrical clock tree, the number of branches, the wirelength, and the inserted buffers are almost the same. It is natural that the clock skew could be minimized if the configurations of all paths from the clock source to sinks are similar. By symmetrically constructing a clock tree, the clock skew can be minimized without referring to simulation information. Experimental results show that our approach can not only efficiently construct a buffered clock tree but also effectively minimize clock skew with marginal wiring overheads. Based on a set of commonly used IBM benchmarks, e.g., a state-of-the-art work without (with) ngspice simulation results in averagely 10.04X (3.44X) clock skew and requires 163X (61906X) running time over our approach.

I. Introduction

Skew-Minimized Buffered Clock-Tree Synthesis (BCTS) plays an important role in high-performance very large-scale integration (VLSI) designs for synchronous circuits. Due to the insufficient accuracy of existing timing models for modern chip design, embedding simulation process into a clock-tree synthesis flow becomes inevitable [9]. Consequently, the running time for clock-tree synthesis becomes prohibitively huge as the complexity of chip designs grows rapidly. Therefore, it is desirable to develop an efficient mechanism for the synthesis of large-scale clock trees.