skip to main content
10.1145/1120725.1120733acmconferencesArticle/Chapter ViewAbstractPublication PagesaspdacConference Proceedingsconference-collections
Article

Making fast buffer insertion even faster via approximation techniques

Published: 18 January 2005 Publication History

Abstract

As technology scales to 0.13 micron and below, designs are requiring buffers to be inserted on interconnects of even moderate length for both critical paths and fixing electrical violations. Consequently, buffer insertion is needed on tens of thousands of nets during physical synthesis optimization. Even the fast implementation of van Ginneken's algorithm requires several hours to perform this task. This work seeks to speed up the van Ginneken style algorithms by an order of magnitude while achieving similar results. To this end, we present three approximation techniques in order to speed up the algorithm: (1) aggressive pre-buffer slack pruning, (2) squeeze pruning, and (3) library lookup. Experimental results from industrial designs show that using these techniques together yields solutions in 9 to 25 times faster than van Ginneken style algorithms, while only sacrificing less than 3% delay penalty.

References

[1]
P. Saxena, N. Menezes, P. Cocchini, and D. A. Kirkpatrick, "Repeater scaling and its impact on cad," IEEE Trans. CAD, vol. 23, no. 4, pp. 451--463, 2004.
[2]
P. J. Osler, "Placement driven synthesis case studies on two sets of two chips: Hierarchical and flat," in ISPD, 2004, pp. 190--197.
[3]
L. P. P. P. van Ginneken, "Buffer placement in distributed RC-tree network for minimal elmore delay," in ISCAS, 1990, pp. 865--868.
[4]
W. Shi and Z. Li, "A Fast Algorithm for Fast Buffer Insertion," IEEE Trans. CAD, to appear.
[5]
W. Shi and Z. Li, "An O(nlogn) time algorithm for optimal buffer insertion," in DAC, 2003, pp. 580--585.
[6]
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, vol. 31, no. 3, pp. 437--447, 1996.
[7]
C. J. Alpert, A. Devgan, and S. T. Quay, "Buffer insertion with accurate gate and interconnect delay computation," in DAC, 1999, pp. 479--484.
[8]
C.-P. Chen and N. Menezes, "Noise-aware repeater insertion and wire sizing for on-chip interconnect using hierarchical moment matching," in DAC, 1999, pp. 502--506.
[9]
T. Okamoto and J. Cong, "Buffered steiner tree construction with wire sizing for interconnect layout optimization," in ICCAD, 1996, pp. 44--49.
[10]
M. Hrkic and J. Lillis, "S-tree: a technique for buffered routing tree synthesis," in DAC, 2002, pp. 578--583.
[11]
M. Hrkic and J. Lillis, "Buffer tree synthesis with consideration of temporal locality, sink polarity requirements, solution cost and blockages," in ISPD, 2002, pp. 98--103.
[12]
J. Hu, C. J. Alpert, S. T. Quay and G. Gandham, "Buffer insertion with adaptive blokage avoidance," IEEE Trans. CAD, vol. 22, no. 4, pp. 492--498, 2003.
[13]
C. J. Alpert, A. Devgan, and S. T. Quay, "Buffer insertion for noise and delay optimization," in DAC, 1998, pp. 362--367.
[14]
W. Shi, Z. Li, and C. J. Alpert, "Complexity analysis and speedup techniques for optimal buffer insertion with minimum cost," in ASPDAC, 2004, pp. 609--614.
[15]
C. J. Alpert, R. G. Gandham, J. L. Neves, and S. T. Quay, "Buffer library selection," in ICCD, 2000, pp. 221--226.

Cited By

View all
  • (2023)BufFormerProceedings of the 28th Asia and South Pacific Design Automation Conference10.1145/3566097.3567900(264-270)Online publication date: 16-Jan-2023
  • (2012)Progress and challenges in VLSI placement researchProceedings of the International Conference on Computer-Aided Design10.1145/2429384.2429441(275-282)Online publication date: 5-Nov-2012
  • (2012)Physically-Driven Logic RestructuringMulti-Objective Optimization in Physical Synthesis of Integrated Circuits10.1007/978-1-4614-1356-1_6(83-103)Online publication date: 8-Aug-2012
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation Conference
January 2005
1495 pages
ISBN:0780387376
DOI:10.1145/1120725
  • General Chair:
  • Ting-Ao Tang
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: 18 January 2005

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

ASPDAC05
Sponsor:

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2023)BufFormerProceedings of the 28th Asia and South Pacific Design Automation Conference10.1145/3566097.3567900(264-270)Online publication date: 16-Jan-2023
  • (2012)Progress and challenges in VLSI placement researchProceedings of the International Conference on Computer-Aided Design10.1145/2429384.2429441(275-282)Online publication date: 5-Nov-2012
  • (2012)Physically-Driven Logic RestructuringMulti-Objective Optimization in Physical Synthesis of Integrated Circuits10.1007/978-1-4614-1356-1_6(83-103)Online publication date: 8-Aug-2012
  • (2011)Shedding physical synthesis area bloatVLSI Design10.1155/2011/5030252011(1-10)Online publication date: 1-Jan-2011
  • (2010)Ultra-fast interconnect driven cell cloning for minimizing critical path delayProceedings of the 19th international symposium on Physical design10.1145/1735023.1735047(75-82)Online publication date: 14-Mar-2010
  • (2008)Fast interconnect synthesis with layer assignmentProceedings of the 2008 international symposium on Physical design10.1145/1353629.1353648(71-77)Online publication date: 13-Apr-2008
  • (2008)Blockage and voltage island-aware dual-vdd buffered tree construction under fixed buffer locationsProceedings of the 2008 international symposium on Physical design10.1145/1353629.1353636(23-30)Online publication date: 13-Apr-2008
  • (2008)Multi-scenario buffer insertion in multi-core processor designsProceedings of the 2008 international symposium on Physical design10.1145/1353629.1353635(15-22)Online publication date: 13-Apr-2008
  • (2007)Fast dual-vdd buffering based on interconnect prediction and samplingProceedings of the 2007 international workshop on System level interconnect prediction10.1145/1231956.1231976(95-102)Online publication date: 17-Mar-2007
  • (2006)Information theoretic approach to address delay and reliability in long on-chip interconnectsProceedings of the 2006 IEEE/ACM international conference on Computer-aided design10.1145/1233501.1233563(310-314)Online publication date: 5-Nov-2006
  • Show More Cited By

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