skip to main content
10.1145/1228784.1228908acmconferencesArticle/Chapter ViewAbstractPublication PagesglsvlsiConference Proceedingsconference-collections
Article

An efficient net ordering algorithm for buffer insertion

Published: 11 March 2007 Publication History

Abstract

There are efficient algorithms for net-based buffer insertion but they lead to sub-optimal path delays or unnecessarily large number of buffers due to their lack of global view. This can increase power consumption as well as die area. The ordering of nets for buffer insertion has a crucial impact on the quality of buffering in terms of path delay and the number of used buffers. A good net ordering can extend the local view of any net-based buffer insertion algorithm.In this paper, an efficient O(nlogn) algorithm for net ordering is presented. The net ordering problem is mapped to traditional knapsack problem to obtain an efficient ordering. Experimental results show that our algorithm can meet timing constraints with an 18.8% reduction in the number of buffers on average.

References

[1]
Alpert, C. J., and Devgan, A., Wire segmenting for improved buffer insertion. In Proc. Design Automation Conf., 1997, 588--593.
[2]
Alpert, C. J., Devgan, A, and Quay, S. T., Buffer insertion for noise and delay optimization. In Proc. of Design Automation Conf., 1998, 362--367.
[3]
Cong, J., He, L., Khoo, K.-Y., Koh, C.-K., and Pan, D. Z., Interconnect design for deep submicron ICs. In Proc. Int. Conf. Computer-Aided Design, 1997, 478--485.
[4]
Cong, J. and Pan, D. Z., Interconnect delay estimation models for synthesis and design planning. In Proc. Asia and South Pacific Design Automation Conf., 1999, 97--100.
[5]
ISCAS Benchmarks, http://iwls.org/iwls2005/benchmarks.
[6]
Lillis, J., Cheng, C. K., and Lin, T. T. Y., Optimal wire sizing and buffer insertion for low power and a generalized delay model. In Proc. Design Automation Conf., 1995, 138--143.
[7]
Saxena, P., Menzes, N., Cocchini, P., and D. Kirkpatrick, A., Repeater scaling and its impact on CAD. In IEEE Trans. on Computer-Aided Design, 23, 4 (April 2004), 451--463.
[8]
Semiconductor Industry Association, NationalTechnoogy Roadmap for Semiconductor, 1997.
[9]
Shi, W. and Li, Z., An O(nlogn) time algorithm for optimal buffer insertion. In Proc. Design Automation Conf., 2003, 580--585.
[10]
Sze, C. N., Alpert, Hu, C. J., J., and Shi, W., Path Based Buffer Insertion. In Proc. Design Automation Conf., 2005, 509--514.
[11]
Waghmode, M., Li, Z., and Shi, W., Buffer Insertion in Large Circuits with Constructive Solution Search Techniques. In Proc. Design Automation Conf., 2006, 296--301.
[12]
Van Ginneken, L. P. P. P., Buffer Placement in distributed RC-tree networks for minimal Elmore delay. In Proc. IEEE Int. Symp. on Circuit and Systems, 1990, 865--868.
[13]
Cormen, T. H., Leiserson, C. E., Rivest, R. L., Introduction to Algorithms. MIT Press, 1990.

Index Terms

  1. An efficient net ordering algorithm for buffer insertion

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      GLSVLSI '07: Proceedings of the 17th ACM Great Lakes symposium on VLSI
      March 2007
      626 pages
      ISBN:9781595936059
      DOI:10.1145/1228784
      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: 11 March 2007

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. buffer insertion
      2. buffer usage
      3. net ordering

      Qualifiers

      • Article

      Conference

      GLSVLSI07
      Sponsor:
      GLSVLSI07: Great Lakes Symposium on VLSI 2007
      March 11 - 13, 2007
      Stresa-Lago Maggiore, Italy

      Acceptance Rates

      Overall Acceptance Rate 312 of 1,156 submissions, 27%

      Upcoming Conference

      GLSVLSI '25
      Great Lakes Symposium on VLSI 2025
      June 30 - July 2, 2025
      New Orleans , LA , USA

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • 0
        Total Citations
      • 196
        Total Downloads
      • Downloads (Last 12 months)1
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 27 Jan 2025

      Other Metrics

      Citations

      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