Optimal spacing and capacitance padding for general clock structures

ABSTRACT

Clock-tuning has been classified as important but tough tasks 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 El-more 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.

REFERENCES

• 1: H. Bakoglu, Circuits, Interconnections, and Packaging for VLSI, Addison-Wesley Pub. Company Inc., 1990.
• 2: Chung-Ping Chen , Yao-Wen Chang , D. F. Wong, Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation, Proceedings of the 33rd annual conference on Design automation, p.405-408, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240596]
• 3: Jae Chung , Chung-Kuan Cheng, Skew sensitivity minimization of buffered clock tree, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.280-283, November 06-10, 1994, San Jose, California, United States
• 4: J. Cong and K.-S. Leung, "Optimal wiresizing under elmore delay model," IEEE TCAD 14(3), pp. 321-336, 1995.
• 5: D. Dobberpuhl and R. Witek, "A 200MHz 64B dualissue CMOS microprocessor," Proc. IEEE ISSCC, pp. 106- 107, 1992.
• 6: W. C. Elmore, "The transient response of damped linear networks with particular regard to wide band amplifiers," J. Applied Physics, 19(1), 1948.
• 7: Michael A. B. Jackson , Arvind Srinivasan , E. S. Kuh, Clock routing for high-performance ICs, Proceedings of the 27th ACM/IEEE conference on Design automation, p.573-579, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123406]
• 8: D. G. Luenberger, Linear and Nonlinear Programming, Addison-Wesley Pub. Company Inc., 1984.
• 9: Noel Menezes , Ross Baldick , Lawrence T. Pileggi, A sequential quadratic programming approach to concurrent gate and wire sizing, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.144-151, November 05-09, 1995, San Jose, California, United States
• 10: Noel Menezes , Satyamurthy Pullela , Florentin Dartu , Lawrence T. Pillage, RC interconnect synthesis—a moment fitting approach, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.418-425, November 06-10, 1994, San Jose, California, United States
• 11: Satyamurthy Pullela , Noel Menezes , Lawrence T. Pillage, Reliable non-zero skew clock trees using wire width optimization, Proceedings of the 30th international conference on Design automation, p.165-170, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164653]
• 12: Sachin S. Sapatnekar, RC interconnect optimization under the Elmore delay model, Proceedings of the 31st annual conference on Design automation, p.387-391, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196430]
• 13: R.-S. Tasy, "Exact zero skew," IEEE TCAD, 1993.
• 14: Neil H. E. Weste , Kamran Eshraghian, Principles of CMOS VLSI design: a systems perspective, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 15: Qing Zhu , Wayne W.-M. Dai , Joe G. Xi, Optimal sizing of high-speed clock networks based on distributed RC and lossy transmission line models, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.628-633, November 07-11, 1993, Santa Clara, California, United States
• 16: L. T. Pillege, and R. A. Rohrer "Asymptotic waveform evaluation for timing analysis", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, April, 1990.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory