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

An O(mn) time algorithm for optimal buffer insertion of nets with m sinks

Published: 24 January 2006 Publication History

Abstract

Buffer insertion is an effective technique to reduce interconnect delay. In this paper, we give a simple O(mn) time algorithm for optimal buffer insertion, where m is the number of sinks and n is the number of buffer positions. This is the first linear time buffer insertion algorithm for nets with constant number of sinks. When m is small, it is a significant improvement over our recent O(n log2 n) time algorithm, and the O(n2) time algorithm of van Ginneken. For b buffer types, the new algorithm runs in O(b2n + bmn) time, an improvement of our recent O(bn2) algorithm. The improvement is made possible by a clever bookkeeping method and an innovative linked list data structure that can perform addition of a wire, and addition of a buffer in amortized O(1) time. On industrial test cases, the new algorithm is faster than previous best algorithms by an order of magnitude.

References

[1]
P. Saxena, N. Menezes, P. Cocchini, and D. A. Kirkpatrick, "Repeater scaling and its impact on CAD," IEEE Trans. Computer-Aided Design, vol. 23, no. 4, pp. 451--463, 2004.
[2]
L. P. P. P. van Ginneken, "Buffer placement in distributed RC-tree network for minimal Elmore delay," in Proc. IEEE Int. Symp. Circuits Syst. 1990, pp. 865--868.
[3]
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 J. Solid-State Circuits, vol. 31, no. 3, pp. 437--447, 1996.
[4]
W. Shi and Z. Li, "A fast algorithm for opitmal buffer insertion," IEEE Trans. Computer-Aided Design, vol. 24, no. 6, pp. 879--891, 2005.
[5]
Z. Li and W. Shi, "An O(bn2) time algorithm for buffer insertion with b buffer types," in Proc. Design, Automation and Test in Europe 2005, pp. 1324--1329.
[6]
R. Chen and H. Zhou, "A flexible data structure for efficient buffer insertion," in Proc. IEEE Int. Conf. Computer Design 2004, pp. 216--221.
[7]
T. Okamoto and J. Cong, "Buffered steiner tree construction with wire sizing for interconnect layout optimization," in Proc. IEEE/ACM Int. Conf. Computer-Aided Design 1996, pp. 44--49.
[8]
M. Hrkic and J. Lillis, "S-tree: a technique for buffered routing tree synthesis," in Proc. ACM/IEEE Design Automation Conf. 2002, pp. 578--583.
[9]
C. J. Alpert, A. Devgan, and S. T. Quay, "Buffer insertion for noise and delay optimization," in Proc. ACM/IEEE Design Automation Conf. 1998, pp. 362--367.
[10]
W. Shi, Z. Li, and C. J. Alpert, "Complexity analysis and speedup techniques for optimal buffer insertion with minimum cost," in Proc. Asia South Pacific Design Automation Conf. 2004, pp. 609--614.
[11]
S. Dhar and M. A. Franklin, "Optimum buffer circuits for driving long uniform lines," IEEE J. Solid-State Circuits, vol. 26, no. 1, pp. 32--40, 1991.
[12]
C. C. N. Chu and D. F. Wong, "A quadratic programming approach to simultaneous buffer insertion/sizing and wire sizing," IEEE Trans. Computer-Aided Design, vol. 18, no. 6, pp. 787--798, 1999.
[13]
Z. Li, C. N. Sze, C. J. Alpert, J. Hu and W. Shi, "Making fast buffer insertion even faster via approximation techniques," in Proc. Asia South Pacific Design Automation Conf., 2005, pp. 13--18.

Cited By

View all
  • (2015)Obstacle-Avoiding and Slew-Constrained Clock Tree Synthesis With Efficient Buffer InsertionIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2014.230017423:1(142-155)Online publication date: Jan-2015
  • (2014)Net-by-Net Wire OptimizationMulti-Net Optimization of VLSI Interconnect10.1007/978-1-4614-0821-5_5(43-61)Online publication date: 16-Oct-2014
  • (2012)ECO timing optimization with negotiation-based re-routing and logic re-structuring using spare cells17th Asia and South Pacific Design Automation Conference10.1109/ASPDAC.2012.6165006(511-516)Online publication date: Jan-2012
  • Show More Cited By

Index Terms

  1. An O(mn) time algorithm for optimal buffer insertion of nets with m sinks

        Recommendations

        Comments

        Information & Contributors

        Information

        Published In

        cover image ACM Conferences
        ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference
        January 2006
        998 pages
        ISBN:0780394518

        Sponsors

        • IEEE Circuits and Systems Society
        • SIGDA: ACM Special Interest Group on Design Automation
        • IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
        • IPSJ SIG-SLDM: Information Processing Society of Japan, SIG System LSI Design Methodology

        Publisher

        IEEE Press

        Publication History

        Published: 24 January 2006

        Permissions

        Request permissions for this article.

        Check for updates

        Qualifiers

        • Article

        Acceptance Rates

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

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

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

        Other Metrics

        Citations

        Cited By

        View all
        • (2015)Obstacle-Avoiding and Slew-Constrained Clock Tree Synthesis With Efficient Buffer InsertionIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2014.230017423:1(142-155)Online publication date: Jan-2015
        • (2014)Net-by-Net Wire OptimizationMulti-Net Optimization of VLSI Interconnect10.1007/978-1-4614-0821-5_5(43-61)Online publication date: 16-Oct-2014
        • (2012)ECO timing optimization with negotiation-based re-routing and logic re-structuring using spare cells17th Asia and South Pacific Design Automation Conference10.1109/ASPDAC.2012.6165006(511-516)Online publication date: Jan-2012
        • (2011)Obstacle-avoiding and slew-constrained buffered clock tree synthesis for skew optimizationProceedings of the 21st edition of the great lakes symposium on Great lakes symposium on VLSI10.1145/1973009.1973049(199-204)Online publication date: 2-May-2011
        • (2010)Variability aware low-power delay optimal buffer insertion for global interconnectsIEEE Transactions on Circuits and Systems Part I: Regular Papers10.1109/TCSI.2010.207379057:12(3055-3063)Online publication date: 1-Dec-2010
        • (2009)Fast buffering for optimizing worst slack and resource consumption in repeater treesProceedings of the 2009 international symposium on Physical design10.1145/1514932.1514942(43-50)Online publication date: 29-Mar-2009
        • (2009)X-architecture clock tree construction associated with buffer insertion and sizing2009 1st Asia Symposium on Quality Electronic Design10.1109/ASQED.2009.5206248(298-303)Online publication date: Jul-2009
        • (2008)Buffer and wire-size optimization under higher order RLC model for interconnect design2008 International Conference on Microwave and Millimeter Wave Technology10.1109/ICMMT.2008.4540426(463-466)Online publication date: Apr-2008
        • (2007)ECO timing optimization using spare cellsProceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326183(530-535)Online publication date: 5-Nov-2007
        • (2007)Performance-Driven Routing Tree Construction with Buffer Insertion, Wire Sizing under RLC Delay Model2007 International Conference on Mechatronics and Automation10.1109/ICMA.2007.4304112(3418-3423)Online publication date: Aug-2007
        • 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