skip to main content
10.1145/1146909.1146988acmconferencesArticle/Chapter ViewAbstractPublication PagesdacConference Proceedingsconference-collections
Article

Buffer insertion in large circuits with constructive solution search techniques

Published: 24 July 2006 Publication History

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. Sze, C. Alpert, J. Hu and W. Shi, "Path-based buffer insertion," Proc. 2005 DAC, 509--514.
[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]
I-Min Liu, A. Aziz, D.F. Wong and H. Zhou, "An efficient buffer insertion algorithm for large networks based on Lagrangian relaxation," ICCD 1999, 210--215.
[6]
I.-M. Liu, A. Aziz, and D. F. Wong, "Meeting delay constraints in DSM by minimal repeater insertion," Proc. of DATE, 436--441, 2000.
[7]
R. Chen and H. Zhou, "Efficient Algorithms for Buffer Insertion in General Circuits Based on Network Flow," ICCAD 2005, 509--514.
[8]
C. J. Alpert and A. Devgan. "Wire segmenting for improved buffer insertion," Proc. 1997 DAC, 588--593.
[9]
W. Shi, Z. Li and C.J. Alpert, "Complexity analysis and speedup techniques for optimal buffer insertion with minimum cost," Proc. 2004 ASPDAC, 609--614.
[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]
Y. Jiang, S. Sapatnekar, C. Bamji and J. Kim, "Interleaving buffer insertion and transistor sizing into a single optimization", IEEE Transactions on VLSI Systems, 6(4):625--633, Dec. 1998.
[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.

Cited By

View all
  • (2012)Guiding a physical design closure system to produce easier-to-route designs with more predictable timingProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228442(465-470)Online publication date: 3-Jun-2012
  • (2012)A semi-formal min-cost buffer insertion technique considering multi-mode multi-corner timing constraints17th Asia and South Pacific Design Automation Conference10.1109/ASPDAC.2012.6165005(505-510)Online publication date: Jan-2012
  • (2008)Circuit-wise buffer insertion and gate sizing algorithm with scalabilityProceedings of the 45th annual Design Automation Conference10.1145/1391469.1391652(708-713)Online publication date: 8-Jun-2008
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
DAC '06: Proceedings of the 43rd annual Design Automation Conference
July 2006
1166 pages
ISBN:1595933816
DOI:10.1145/1146909
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. buffer insertion
  2. cost optimization
  3. interconnect synthesis
  4. physical design

Qualifiers

  • Article

Conference

DAC06
Sponsor:
DAC06: The 43rd Annual Design Automation Conference 2006
July 24 - 28, 2006
CA, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25
62nd ACM/IEEE Design Automation Conference
June 22 - 26, 2025
San Francisco , CA , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2012)Guiding a physical design closure system to produce easier-to-route designs with more predictable timingProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228442(465-470)Online publication date: 3-Jun-2012
  • (2012)A semi-formal min-cost buffer insertion technique considering multi-mode multi-corner timing constraints17th Asia and South Pacific Design Automation Conference10.1109/ASPDAC.2012.6165005(505-510)Online publication date: Jan-2012
  • (2008)Circuit-wise buffer insertion and gate sizing algorithm with scalabilityProceedings of the 45th annual Design Automation Conference10.1145/1391469.1391652(708-713)Online publication date: 8-Jun-2008
  • (2008)A practical repeater insertion flowProceedings of the 18th ACM Great Lakes symposium on VLSI10.1145/1366110.1366174(261-266)Online publication date: 4-May-2008
  • (2007)Fast min-cost buffer insertion under process variationsProceedings of the 44th annual Design Automation Conference10.1145/1278480.1278567(338-343)Online publication date: 4-Jun-2007
  • (2007)An efficient net ordering algorithm for buffer insertionProceedings of the 17th ACM Great Lakes symposium on VLSI10.1145/1228784.1228908(521-524)Online publication date: 11-Mar-2007
  • (2007)An Efficient Analytical Approach to Path-Based Buffer InsertionProceedings of the IEEE Computer Society Annual Symposium on VLSI10.1109/ISVLSI.2007.23(219-224)Online publication date: 9-Mar-2007

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media