Path based buffer insertion

ABSTRACT

Along with the progress of VLSI technology, buffer insertion plays an increasingly critical role on affecting circuit design and performance. Traditional buffer insertion algorithms are mostly net based and therefore often result in sub-optimal delay or unnecessary buffer expense due to the lack of global view. In this paper, we propose a novel path based buffer insertion scheme which can overcome the weakness of the net based approaches. We also discuss some potential difficulties of the path based buffer insertion approach and propose solutions to them. A fast estimation on buffered delay is employed to improve the solution quality. Gate sizing is also considered at the same time. Experimental results show that our method can efficiently reduce buffer/gate cost significantly (by 71% on average) when compared to traditional net based approaches. To the best of our knowledge, this is the first work on path based buffer insertion and simultaneous gate sizing.

REFERENCES

• 1: C. J. Alpert, C. Chu, G. Gandham, M. Hrkic, J. Hu, C. Kashyap, and S. T. Quay. Simultaneous driver sizing and buffer insertion using delay penalty estimation technique. IEEE Trans. on CAD, 23(1):136--141, January 2004.
• 2: 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]
• 3: 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]
• 4: Charles J. Alpert , Anirudh Devgan , Stephen T. Quay, Buffer insertion with accurate gate and interconnect delay computation, Proceedings of the 36th ACM/IEEE conference on Design automation, p.479-484, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309983]
• 5: Charles J. Alpert , Miloš Hrkić , Jiang Hu , Stephen T. Quay, Fast and flexible buffer trees that navigate the physical layout environment, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996575]
• 6: C. J. Alpert , Jiang Hu , S. S. Sapatnekar , C. N. Sze, Accurate estimation of global buffer delay within a floorplan, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.706-711, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382667]
• 7: H. B. Bakoglu. Circuits, interconnections and packaging for VLSI. Addison-Wesley, Reading, MA, 1990.
• 8: C. C. N. Chu and D. F. Wong. A quadratic programming approach to simultaneous buffer insertion/sizing and wire sizing. IEEE Trans. on CAD, 18(6):787--798, June 1999.
• 9: 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]
• 10: J. A. Davis, R. Venkatesan, A. Kaloyeros, M. Beylansky, S. J. Souri, K. Banerjee, K. C. Saraswat, A. Rahman, R. Reif, and J. D. Meindl. Interconnect limits on gigascale integration (GSI) in the 21st century. Proc. of IEEE, 89(3):305--324, March 2001.
• 11: S. Dhar and M. A. Franklin. Optimum buffer circuits for driving long uniform lines. IEEE Journal of Solid-State Circuits, 26(1):32--38, January 1991.
• 12: L. P. P P. van Ginneken. Buffer placement in distributed RC-tree networks for minimal Elmore delay. In Proc. of ISCAS, pages 865--868, 1990.
• 13: C. V. Kashyap, C. J. Alpert, F. Liu, and A. Devgan. Closed-form expressions for extending step delay and slew metrics to ramp inputs for RC trees IEEE Trans. on CAD, 23(4):509--516, April 2004.
• 14: Yanbin Jiang , Sachin S. Sapatnekar , Cyrus Bamji , Juho Kim, Interleaving buffer insertion and transistor sizing into a single optimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.6 n.4, p.625-633, Dec. 1998 [doi>10.1109/92.736136]
• 15: Yun-Cheng Ju , Resve A. Saleh, Incremental techniques for the identification of statically sensitizable critical paths, Proceedings of the 28th conference on ACM/IEEE design automation, p.541-546, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127729]
• 16: Zhuo Li , C. N. Sze , Charles J. Alpert , Jiang Hu , Weiping Shi, Making fast buffer insertion even faster via approximation techniques, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120733]
• 17: John Patrick Lillis , Chung-Kuan Cheng, Algorithms for performance-driven design of integrated circuits, 1996
• 18: J. Lillis, C. K. Cheng, and T. Y. Lin. Optimal wire sizing and buffer insertion for low power and a generalized delay model. IEEE Journal of Solid-State Circuits, 31(3):437--447, March 1996.
• 19: I-Min Liu , Adnan Aziz , D. F. Wong, Meeting delay constraints in DSM by minimal repeater insertion, Proceedings of the conference on Design, automation and test in Europe, p.436-440, March 27-30, 2000, Paris, France [doi>10.1145/343647.343814]
• 20: I.-M. Liu, A. Aziz, D. F. Wong, and H. Zhou. An efficient buffer insertion algorithm for large networks based on Lagrangian relaxation. In Proc. of ICCD, pages 614--621, 1999.
• 21: Sachin Sapatnekar, Timing, Springer-Verlag New York, Inc., Secaucus, NJ, 2004
• 22: P. Saxena, N. Menezes, P. Cocchini, and D. A. Kirkpatrick. Repeater scaling and its impact on CAD. IEEE Trans. on CAD, 23(4):451--463, April 2004.
• 23: Weiping Shi , Zhuo Li, An O(nlogn) time algorithm for optimal buffer insertion, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775980]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

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

General Terms:
Algorithms, Design, Performance

Keywords:
buffer insertion, global routing, interconnect synthesis, layout, physical design, power minimization