Discrete buffer and wire sizing for link-based non-tree clock networks

ABSTRACT

Clock network is a vulnerable victim of variations as well as a main power consumer in many integrated circuits. Recently, link-based non-tree clock network attracts people's attention due to its appealing tradeoff between variation tolerance and power overhead. In this work, we investigate how to optimize such clock networks through buffer and wire sizing. A two-stage hybrid optimization approach is proposed. It considers the realistic constraint of discrete buffer/wire sizes and is based on accurate delay models. In order to provide reliable and efficient guidance for the optimization, we suggest to apply SVM (Support Vector Machine) based machine learning as a surrogate for expensive circuit-level simulation. Experimental results on benchmark circuits show that our sizing method can reduce clock skew by 43% on average with very small increase on power dissipation

REFERENCES

• 1: P. J. Restle, T. G. McNamara, D. A. Webber, P. J. Camporese, K. F. Eng, K. A. Jenkins, D. H. Allen, M. J. Rohn, M. P. Quaranta, D. W. Boerstler, C. J. Alpert, C. A. Carter, R. N. Bailey, J. G. Petrovick, B. L. Krauter, and B. D. McCredie. A clock distribution network for microprocessors. IEEE Journal of Solid-State Circuits, 36(5):792--799, May 2001.
• 2: Anand Rajaram , Jiang Hu , Rabi Mahapatra, Reducing clock skew variability via cross links, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996574]
• 3: Anand Rajaram , David Z. Pan , Jiang Hu, Improved algorithms for link-based non-tree clock networks for skew variability reduction, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055150]
• 4: W.-C. D. Lam , J. Jam , C.-K. Koh , V. Balakrishnan , Y. Chen, Statistical based link insertion for robust clock network design, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.588-591, November 06-10, 2005, San Jose, CA
• 5: Anand Rajaram , David Z. Pan, Fast Incremental Link Insertion in Clock Networks for Skew Variability Reduction, Proceedings of the 7th International Symposium on Quality Electronic Design, p.79-84, March 27-29, 2006 [doi>10.1109/ISQED.2006.66]
• 6: G. Venkataraman , N. Jayakumar , J. Hu , P. Li , Sunil Khatri , Anand Rajaram , P. McGuinness , C. Alpert, Practical techniques to reduce skew and its variations in buffered clock networks, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.592-596, November 06-10, 2005, San Jose, CA
• 7: Anand Rajaram , David Z. Pan, Variation tolerant buffered clock network synthesis with cross links, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123038]
• 8: S. Pullela, N. Menezes, J. Omar, and L. T. Pillage. Skew and delay optimization for reliable buffered clock trees. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pages 556--562, 1993.
• 9: S. Pullela, N. Menezes, and L. T. Pileggi. Moment-sensitivity-based wire sizing for skew reduction in on-chip clock nets. IEEE Transactions on Computer-Aided Design, 16(2):210--215, February 1997.
• 10: Jeng-Liang Tsai , Tsung-Hao Chen , Charlie Chung-Ping Chen, Optimal minimum-delay/area zero-skew clock tree wire-sizing in pseudo-polynomial time, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640036]
• 11: Haihua Su , Sachin S. Sapatnekar, Hybrid structured clock network construction, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 12: 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]
• 13: K. Wang, Y. Ran, H. Jiang, and M. Marek-Sadowska. General skew constrained clock network sizing based on sequential linear programming. IEEE Transactions on Computer-Aided Design, 24(5):773--782, May 2005.
• 14: Matthew R. Guthaus , Dennis Sylvester , Richard B. Brown, Clock buffer and wire sizing using sequential programming, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147171]
• 15: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 16: Olivier Coudert, Gate sizing for constrained delay/power/area optimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.4, p.465-472, Dec. 1997 [doi>10.1109/92.645073 ]
• 17: V. N. Vapnik. Statistical Learning Theory. Wiley-Interscience Publishers, New York, NY, 1998.
• 18: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 19: B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2):291--307, February 1970.
• 20: CPMO-constrained placement by multilevel optimization. http://ballade.cs.ucla.edu/cpmo/. Computer Science Department, UCLA.
• 21: E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, and A. L. Sangiovanni-Vincentelli. SIS: a system for sequential circuit synthesis. Memorandum no. M92/41, ERL, University of California, Berkeley, May 1992.
• 22: Y. Cao, T. Sato, D. Sylvester, M. Orshansky and C. Hu. New paradigm of predictive MOSFET and interconnect modeling for early circuit simulation. IEEE Custom Integrated Circuit Conference, pages 201--204, 2000.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Performance

Keywords:
buffer, clock, non-tree, svm, wire