Buffer insertion in large circuits with constructive solution search techniques

ABSTRACT

Most existing buffer insertion algorithms, such as van Ginneken's algorithm, consider only individual nets. As a result, these algorithms tend to over buffer when applied to combinational circuits, since it is difficult to decide how many buffers to insert in each net. Recently, Sze, et al. [1] proposed a path-based algorithm for buffer insertion in combinational circuits. However their algorithm is inefficient for large circuits when there are many critical paths.In this paper, we present a new buffer insertion algorithm for combinational circuits such that the timing requirements are met and the buffer cost is minimized. Our algorithm iteratively inserts buffers in the circuit to improve the circuit delay. The core of this algorithm is simple but effective technique that guides the search for a good buffering solution. Experimental results on ISCAS85 circuits show that our new algorithm on average uses 36% less buffers and runs 3 times faster than Sze's algorithm.

REFERENCES

• 1: C. N. Sze , Charles J. Alpert , Jiang Hu , Weiping Shi, Path based buffer insertion, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065711]
• 2: L. P. P. P. van Ginneken, "Buffer placement in distributed RC-tree network for minimal Elmore delay," Proc. 1990 ISCAS, 865--868.
• 3: 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.
• 4: J. Lillis, C. K. Cheng and T.-T. Y. Lin, "Optimal wire sizing and buffer insertion for low power and a generalized delay model," IEEE Trans. Solid-State Circuits, 31(3), 437--447, 1996.
• 5: An Efficient Buffer Insertion Algorithm for Large Networks Based on Lagrangian Relaxation, Proceedings of the 1999 IEEE International Conference on Computer Design, p.210, October 10-13, 1999
• 6: 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]
• 7: Ruiming Chen , Hai Zhou, Efficient algorithms for buffer insertion in general circuits based on network flow, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.322-326, November 06-10, 2005, San Jose, CA
• 8: 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]
• 9: Weiping Shi , Zhuo Li , Charles J. Alpert, Complexity analysis and speedup techniques for optimal buffer insertion with minimum cost, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.609-614, January 27-30, 2004, Yokohama, Japan
• 10: Y. Zhang, Q. Zhou, X. Hong and Y. Cai, "Path-based timing optimization by buffer insertion with accurate delay model", Proc. 5th International Conference on ASIC, Vol.1:89--92, Oct. 2003.
• 11: 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]
• 12: K. S.Lowe and P. G. Gulak, "A joint gate sizing and buffer insertion method for optimizing delay and power in CMOS and BiCMOS combinational logic", IEEE Trans. on CAD, 17(5):419--434,May 1998.

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, cost optimization, interconnect synthesis, physical design