Clock buffer and wire sizing using sequential programming

ABSTRACT

This paper investigates methods for clock skew minimization using buffer and wire sizing. First, a technique that significantly improves solution quality and stability of sequential programming-based buffer/wire sizing is used. Then, a new formulation of clock skew minimization that uses quadratic programming and considers sub-critical skews in addition to the most critical skews is presented. The quality of results are verified to be more robust using Monte Carlo simulations to account for process sensitivity. For the same power budget, the sequential quadratic programming (SQP) method has better expected skew, standard deviation, and overall CPU time on average.

REFERENCES

• 1: Aseem Agarwal , David Blaauw , Vladimir Zolotov, Statistical Clock Skew Analysis Considering Intra-Die Process Variations, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.914, November 09-13, 2003 [doi>10.1109/ICCAD.2003.128]
• 2: C. Albrecht, A. B. Kahng, B. Liu, I. Mandoiu, and A. Zelikovsky. On the skew-bounded minimum buffer routing tree problem. In SASIMI, pages 250--256, 2001.
• 3: Xiaoliang Bai , Chandu Visweswariah , Philip N. Strenski, Uncertainty-aware circuit optimization, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513935]
• 4: K. Boese and A. Kahng. Zero-skew clock routing trees with minimum wirelength. In ASIC Conf., pages 1.1.1--1.1.5, 1992.
• 5: Y. Cao, P. Gupta, A. B. Kahng, D. Sylvester, and J. Yang. Design sensitivities to variability: Extrapolations and assessments in nanometer VLSI. In ASIC/SOC, pages 411--415, September 2002.
• 6: T.-H. Chao , J.-M. Ho , Y.-C. Hsu, Zero skew clock net routing, Proceedings of the 29th ACM/IEEE conference on Design automation, p.518-523, June 08-12, 1992, Anaheim, California, United States
• 7: Chung-Ping Chen , Yao-Ping Chen , D. F. Wong, Optimal wire-sizing formula under the Elmore delay model, Proceedings of the 33rd annual conference on Design automation, p.487-490, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240611]
• 8: Computational infrastructure for operations research. http://www.coin-or.org.
• 9: John P. Fishburn, Clock Skew Optimization, IEEE Transactions on Computers, v.39 n.7, p.945-951, July 1990 [doi>10.1109/12.55696]
• 10: Masanori Hashimoto , Tomonori Yamamoto , Hidetoshi Onodera, Statistical Analysis of Clock Skew Variation in H-Tree Structure, Proceedings of the 6th International Symposium on Quality of Electronic Design, p.402-407, March 21-23, 2005 [doi>10.1109/ISQED.2005.114]
• 11: International technology roadmap on semiconductors. http://public.itrs.net, 2004.
• 12: R. Kay and L. T. Pileggi. EWA: Efficient wiring-sizing algorithm for signal nets and clock nets. IEEE Trans. on CAD, 17(1):40--49, January 1998.
• 13: I. S. Kourtev and E. G. Friedman. A quadratic programming approach to clock skew scheduling for reduced sensitivity to process parameter variations. In ASIC/SOC, pages 210--215, 1999.
• 14: I-Min Liu , Tan-Li Chou , Adnan Aziz , D. F. Wong, Zero-skew clock tree construction by simultaneous routing, wire sizing and buffer insertion, Proceedings of the 2000 international symposium on Physical design, p.33-38, May 2000, San Diego, California, United States [doi>10.1145/332357.332370]
• 15: Bing Lu , Jiang Hu , Gary Ellis , Haihua Su, Process variation aware clock tree routing, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640037]
• 16: José Luis Neves , Eby G. Friedman, Optimal clock skew scheduling tolerant to process variations, Proceedings of the 33rd annual conference on Design automation, p.623-628, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240636]
• 17: J. Nocedal and S. J. Wright. Numerical Optimization. Springer, 1999.
• 18: 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]
• 19: G. E. Tellez and M. Sarrafzadeh. Minimal buffer insertion in clock trees with skew and slew rate constraints. IEEE Trans. on CAD, 16(4):333--342, 1997.
• 20: J.-L. Tsai, T.-H. Chen, and C. C. Chen. Zero skew clock-tree optimization with buffer insertion/sizing and wire sizing. IEEE Trans. on CAD, 23(4):565--573, April 2004.
• 21: Kai Wang , Malgorzata Marek-Sadowska, Buffer sizing for clock power minimization subject to general skew constraints, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996614]

INDEX TERMS

General Terms:
Algorithms, Design

Keywords:
clock tree synthesis, robust design, skew