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. A. Rajaram, J. Hu, and R. Mahapatra. Reducing clock skew variability via cross links. In Proceedings of the ACM/IEEE Design Automation Conference, pages 18--23, 2004.
3. A. Rajaram, D. Pan, and J. Hu. Improved algorithms for link based non-tree clock network for skew variability reduction. In Proceedings of the ACM International Symposium on Physical Design, pages 55--62, 2005.
4. D. Lam, C.-K. Koh, Y. Chen, J. Jain, and V. Balakrishnan. Statistical based link insertion for robust clock network design. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pages 588--591, 2005.
5. A. Rajaram and D. Z. Pan. Fast incremental link insertion in clock networks for skew variability reduction. In Proceedings of the IEEE International Symposium on Quality Electronic Design, 2006.
6. G. Venkataraman, N. Jayakumar, J. Hu, P. Li, S. Khatri, A. Rajaram, P. McGuinness, and C. J. Alpert. Practical techniques to reduce skew and its variations in buffered clock networks. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pages 592--596, 2005.
7. A. Rajaram and D. Z. Pan. Variation tolerant buffered clock network with cross links. In Proceedings of the ACM International Symposium on Physical Design, pages 157--164, 2006.
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. J.-L. Tsai, T.-H. Chen, and C. C.-P. Chen. "ε-optimal minimum-delay/area zero-skew clock tree wire-sizing in pseudo-polynomial time. In Proceedings of the ACM International Symposium on Physical Design, pages 166--173, 2003.
11. H. Su and S. S. Sapatnekar. Hybrid structured clock network construction. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pages 333--336, 2001.
12. I.-M. Liu, T.-L. Chou, A. Aziz, and D. F. Wong. Zero-skew clock tree construction by simultaneous routing, wire sizing and buffer insertion. In Proceedings of the ACM International Symposium on Physical Design, pages 33--38, 2000.
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. M. R. Guthaus, D. Sylvester, and R. B. Brown. Clock buffer and wire sizing using sequential programming. In Proceedings of the ACM/IEEE Design Automation Conference, pages 1041--1046, 2006.
15. C. H. Papadimitriou and K. Steiglitz. Combinatorial optimization: algorithms and complexity. Dover Publications, Inc., Mineola, NY, 1998.
16. O. Coudert. Gate sizing for constrained delay/power/area optimization. IEEE Transactions on VLSI Systems, 5(4):465--472, December 1997.
17. V. N. Vapnik. Statistical Learning Theory. Wiley-Interscience Publishers, New York, NY, 1998.
18. T. Joachims. Making large-scale SVM learning practical. Advances in Kernel Methods - Support Vector Learning. MIT-Press, 1998.
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

• Applied computing

  • Arts and humanities

    • Architecture (buildings)

      • Computer-aided design

  • Physical sciences and engineering

    • Engineering

      • Computer-aided design

• Hardware

  • Electronic design automation

    • Logic synthesis

      • Circuit optimization