Optimal spacing and capacitance padding for general clock structures

Clock-tuning has been classified as an important but tough task due to the non-convex nature caused by the skew requirements. As a result, all existing mathematical programming approaches are often trapped at local minimum and have no guarantee of obtaining global optimal solution. In this paper, we present optimal clock tuning algorithms which effectively apply capacitance-padding to reduce clock skew, power, and delay for general clock topologies. Capacitance-padding can be achieved by wire-spacing, wire-splitting, wire-padding and transistor-padding. We show that under the Elmore delay model, capacitance-padding can be formulated as a linear programming problem and solved with great efficiency. Capacitance-padding can also be used as a post processing step for any non zero-skew clock tree or mesh structure to achieve timing closure. Experiment results on several practical industry examples show that our algorithms are extremely efficient. Problems with over 6000 variables can be optimally tuned within 1 minute on a PC with 500-MHZ Intel Pentium III processor