An efficient surface-based low-power buffer insertion algorithm

ABSTRACT

Buffer insertion is an important technique used to achieve timing closure in high performance VLSI designs. As the number of buffers in ASIC designs has increased with process scaling, the power con-sumption of buffers has become a critical concern. In this paper, we present an efficient algorithm that performs van Ginneken style buffer insertion on RC trees and minimizes the total power con-sumption under a given delay constraint. Our algorithm is based on a formulation that uses a buffer library consisting of continuous buffer sizes. We construct solution candidates in the form of surfaces in the 3-D delay, capacitance and power (DCP) space and show the mecha-nisms to propagate and merge them in the interconnect tree. Instead of a single minimal power solution, the algorithm produces an entire DCP surface from which a suitable solution point can be selected. We also present a post-processing step where buffers with continu-ous (non-standard) sizes are snapped to discrete size values corre-sponding to the buffers in a given library. The proposed algorithm has a worst-case runtime complexity that is polynomial (quadratic) in the number of possible buffer locations. We implemented and tested our proposed algorithm on a number of large benchmark nets and observed that our method produces a speedup in runtime of 5-6X in comparison with previous power aware buffer insertion methods.

REFERENCES

• 1: Ralph H. J. M. Otten , Robert K. Brayton, Planning for performance, Proceedings of the 35th annual conference on Design automation, p.122-127, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277071]
• 2: L. P. P. P. van Ginneken, "Buffer placement in distributed RC-tree networks for minimal elmore delay", ISCAS 1990.
• 3: Charles Alpert , Anirudh Devgan, Wire segmenting for improved buffer insertion, Proceedings of the 34th annual conference on Design automation, p.588-593, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266291]
• 4: Charles J. Alpert , Anirudh Devgan , Stephen T. Quay, Buffer insertion for noise and delay optimization, Proceedings of the 35th annual conference on Design automation, p.362-367, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277145]
• 5: C. Chu, D. F. Wong, "A quadratic programming approach to simultaneous buffer insertion/sizing and wire sizing", IEEE Trans. on CAD, 18(6), 1999.
• 6: C.-P. Chen, C. Chu, D. F. Wong, "Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation", IEEE Trans. on CAD, 18(7), 1999.
• 7: J.-L. Tsai, T.-H. Chen, C.-P. Chen, "Zero skew clock-tree optimization with buffer insertion/sizing and wire sizing", IEEE Trans. on CAD, 23(4), 2004.
• 8: C. J. Alpert, C. Chu, G. Gandham, M. Hrkic, J. Hu, C. Kashyap, S. Quay, "Simultaneous driver sizing and buffer insertion using a delay penalty estimation technique", IEEE Trans. on CAD, 23(1), 2004.
• 9: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin, Simultaneous Routing and Buffer Insertion for High Performance Interconnect, Proceedings of the 6th Great Lakes Symposium on VLSI, p.148, March 22-23, 1996
• 10: H. Zhou, D. F. Wong, I. Liu, A. Aziz,"Simultaneous routing and buffer insertion with restrictions on buffer locations", IEEE Trans. on CAD, 19(7), 2000.
• 11: Sampath Dechu , Zion Cien Shen , Chris C. N. Chu, An efficient routing tree construction algorithm with buffer insertion, wire sizing and obstacle considerations, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.361-366, January 27-30, 2004, Yokohama, Japan
• 12: Ruiming Li , Dian Zhou , Jin Liu , Xuan Zeng, Power-Optimal Simultaneous Buffer Insertion/Sizing and Wire Sizing, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.581, November 09-13, 2003 [doi>10.1109/ICCAD.2003.116]
• 13: Ashok K. Murugavel , N. Ranganathan, Gate Sizing and Buffer Insertion using Economic Models for Power Optimization, Proceedings of the 17th International Conference on VLSI Design, p.195, January 05-09, 2004
• 14: S. Weiping, L. Zhuo, "An O(nlogn) time algorithm for optimal buffer insertion", DAC 2003.
• 15: P. Saxena, N. Menezes, P. Cocchini, D. Kirkpatrick, "Repeater scaling and its impact on CAD", IEEE Trans. on CAD, 23(4), 2004.
• 16: Kerry Bernstein , Ching-Te Chuang , Rajiv Joshi , Ruchir Puri, Design and CAD Challenges in sub-90nm CMOS Technologies, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.129, November 09-13, 2003 [doi>10.1109/ICCAD.2003.54]
• 17: Prashant Saxena , Noel Menezes , Pasquale Cocchini , Desmond A. Kirkpatrick, The scaling challenge: can correct-by-construction design help?, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640014]
• 18: Siva Narendra , Vivek De , Dimitri Antoniadis , Anantha Chandrakasan , Shekhar Borkar, Scaling of stack effect and its application for leakage reduction, Proceedings of the 2001 international symposium on Low power electronics and design, p.195-200, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383132]
• 19: J. Lillis, C.-K. Cheng, T. Y. Lin, "Optimal wire sizing and buffer insertion for low power and a generalized delay model", JSSC, 31(3), 1996.
• 20: Jatan C. Shah , Sachin S. Sapatnekar, Wiresizing with Buffer Placement and Sizing for Power-Delay Tradeoffs, Proceedings of the 9th International Conference on VLSI Design: VLSI in Mobile Communication, p.346, January 03-06, 1996
• 21: J. Fishburn, C. Schevon, "Shaping a distributed RC line to minimize Elmore delay", IEEE Trans. on Circuits and Systems, 42(12), 1995.
• 22: Chris Chu , D. F. Wong, Closed form solutions to simultaneous buffer insertion/sizing and wire sizing, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.3, p.343-371, July 2001 [doi>10.1145/383251.383256]
• 23: Joel Grodstein , Eric Lehman , Heather Harkness , Bill Grundmann , Yosinatori Watanabe, A delay model for logic synthesis of continuously-sized networks, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.458-462, November 05-09, 1995, San Jose, California, United States
• 24: Wei Chen , Cheng Ta Hsieh , Massoud Pedram, Simultaneous gate sizing and fanout optimization, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 25: W. C. Elmore, "The transient response of a damped linear network with particular regard to wideband amplifiers", J. Applied Physics, 19, 1948.
• 26: Frederik Beeftink , Prabhakar Kudva , David Kung , Leon Stok, Gate-size selection for standard cell libraries, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.545-550, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289084]
• 27: R. Haddad, L. P. P. P. van Ginneken, N. Shenoy, "Discrete drive selection for continuous sizing", ICCD 1997.
• 28: David S. Kung, A fast fanout optimization algorithm for near-continuous buffer libraries, Proceedings of the 35th annual conference on Design automation, p.352-355, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277143]
• 29: Wei Chen , Cheng Ta Hsieh , Massoud Pedram, Simultaneous gate sizing and fanout optimization, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 30: GNU Scientific Library (GSL), http://www.gnu.org/software/gsl/.
• 31: C. J. Alpert, M. Hrkic, J. Hu, A. B. Kahng, J. Lillis, B. Liu, S. T. Quay, S. S. Sapatnekar, A. J. Sullivan, P. Villarrubia, "Buffered Steiner trees for difficult instances", IEEE Trans. on CAD, 21(1), 2002.
• 32: http://dropzone.tamu.edu/~cnsze/GSRC/ctree.html
• 33: International Technology Roadmap for Semiconductors (ITRS), 2001.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

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

General Terms:
Algorithms, Design

Keywords:
buffer insertion, low-power design, physical synthesis