[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.5555/266388.266564acmconferencesArticle/Chapter ViewAbstractPublication PagesiccadConference Proceedingsconference-collections
Article
Free access

A new approach to simultaneous buffer insertion and wire sizing

Published: 13 November 1997 Publication History

Abstract

In this paper, we present a completely new approach to the problem of delay minimization by simultaneous buffer insertion and wire sizing for a wire. We show that the problem can be formulated as a convex quadratic program, which is known to be solvable in polynomial time. Nevertheless, we explore some special properties of our problem and derive an optimal and very efficient algorithm to solve the resulting program. Given m buffers and a set of n discrete choices of wire width, the running time of our algorithm is O(mn^2) and is independent of the wire length in practice. For example, an instance of 100 buffers and 100 choices of wire width can be solved in 3 seconds. Besides, our formulation is so versatile that it is easy to consider other objectives like wire area or power dissipation, or to add constraints to the solution. Also, wire capacitance lookup tables, or very general wire capacitance models which can capture area capacitance, fringing capacitance, coupling capacitance, etc. can be used.

References

[1]
Chung-Ping Chen, Yao-Wen Chang, and D. F. Wong. Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation. In Proc. IEEE ICCAD, pages 405-408, 1996.
[2]
Chung-Ping Chen, Yao-Ping Chen, and D. F. Wong. Optimal wire-sizing formula under the Elmore delay model. In Proc. A CM/IEEE DA 6+, pages 487-490, 1996.
[3]
Chung-Ping Chen and D. F. Wong. A fast algorithm for optimal wire-sizing under Elmore delay model. In Proc. IEEE ISCAS, volume 4, pages 412-415, 1996.
[4]
Chung-Ping Chen and D. F. Wong. Optimal wire-sizing function with fringing capacitance consideration. In Proc. A CM/IEEE DA C, 1997.
[5]
Chung-Ping Chen, Hai Zhou, and D. F. Wong. Optimal non-uniform wire-sizing under the Elmore delay model. In Proc. IEEE ICCAD, pages 38-43, 1996.
[6]
Chris C. N. Chu and D. F. Wong. Closed form solution to simultaneous buffer insertion/sizing and wire sizing. In Proc. Intl. Syrup. on Physical Design, pages 192-197, 1997.
[7]
Jason Cong and Lei He. An efficient approach to simultaneous transistor and interconnect sizing. In Proc. IEEE ICCAD, pages 181-186, 1996.
[8]
Jason Cong and Lei He. Optimal wiresizing for interconnects with multiple sources. A CM Trans. Design Automation of Electronic Systems, 1(4), October 1996.
[9]
Jason Cong, Lei He, Cheng-Kok Koh, and Patrick H. Madden. Performance optimization of VLSI interconnect layout. INTEGRATION, the VLSI Journal, 21:1- 94, 1996.
[10]
Jason Cong and Cheng-Kok Koh. Simultaneous buffer and wire sizing for performance and power optimization. In Proc. Intl. Syrup. on Low Power Electronics and Design, pages 271-276, August 1996.
[11]
Jason Cong and Kwok Shing Leung. Optimal wiresizing under the distributed Elmore delay model. IEEE Trans. on CAD, 14(3):321-336, March 1995.
[12]
Jim DeTar. Advances outpace SIA roadmap (Semiconductor Industry Association alters projections) (Industry Trend or Event). Electronic News, 42(2147):1, December 16 1996.
[13]
W. C. Elmore. The transient response of damped linear network with particular regard to wideband amplifiers. J. Applied Physics, 19:55-63, 1948.
[14]
J. P. Fishburn. Shaping a VLSI wire to minimize Elmore delay. In Proc. European Design and Test Conference, 1997.
[15]
J. P. Fishburn and C. A. Schevon. Shaping a distributed- RC line to minimize Elmore delay. IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, 42(12):1020-1022, December 1995.
[16]
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, NY, 1979.
[17]
M. K. Kozlov, S. P. Tarasov, and L. G. Khachiyan. Polynomial solvability of convex quadratic programming. Soviet Mathematics Doklady, 20:1108-1111, 1979.
[18]
John Lillis, Chung-Kuan Cheng, and Ting-Ting Y. Lin. Optimal wire sizing and buffer insertion for low power and a generalized delay model. IEEE Journal of Solid State Circuits, 31(3):437-447, March 1996.
[19]
D. G. Luenberger. Linear and Nonlinear Programming. Addison Wesley, second edition, 1984.
[20]
N. Menezes, R. Baldick, and L. T. Pileggi. A sequential quadratic programming approach to concurrent gate and wire sizing. In Proc. IEEE ICCAD, pages 144-151, 1995.
[21]
Sachin S. Sapatnekar. RC interconnect optimization under the Elmore delay model. In Proc. A CM~IEEE DA C, pages 387-391, 1994.
[22]
L. P. P. P. van Ginneken. Buffer placement in distributed RC-tree networks for minimal Elmore delay. In Proc. Intl. Syrup. on Circuits and Systems, pages 865-868, 1990.
[23]
Qing Zhu, Wayne W.-M. Dai, and Joe G. Xi. Optimal sizing of high-speed clock networks based on distributed RC and lossy transmission line models. In Proc. IEEE ICCAD, pages 628-633, 1993.

Cited By

View all
  • (2019)Buffer insertion for delay minimization in RLC interconnects using cuckoo optimization algorithmAnalog Integrated Circuits and Signal Processing10.1007/s10470-018-1318-y99:1(111-121)Online publication date: 1-Apr-2019
  • (2017)A CPS framework based perturbation constrained buffer planning approach in VLSI designJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.11.013103:C(3-10)Online publication date: 1-May-2017
  • (2005)RIPProceedings of the conference on Design, Automation and Test in Europe - Volume 210.1109/DATE.2005.262(1330-1335)Online publication date: 7-Mar-2005
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
ICCAD '97: Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design
November 1997
769 pages
ISBN:0818682000

Sponsors

Publisher

IEEE Computer Society

United States

Publication History

Published: 13 November 1997

Check for updates

Author Tags

  1. buffer insertion
  2. convex quadratic programming
  3. interconnect area minimization
  4. interconnect delay minimization
  5. wire sizing

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)28
  • Downloads (Last 6 weeks)5
Reflects downloads up to 11 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2019)Buffer insertion for delay minimization in RLC interconnects using cuckoo optimization algorithmAnalog Integrated Circuits and Signal Processing10.1007/s10470-018-1318-y99:1(111-121)Online publication date: 1-Apr-2019
  • (2017)A CPS framework based perturbation constrained buffer planning approach in VLSI designJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.11.013103:C(3-10)Online publication date: 1-May-2017
  • (2005)RIPProceedings of the conference on Design, Automation and Test in Europe - Volume 210.1109/DATE.2005.262(1330-1335)Online publication date: 7-Mar-2005
  • (2003)Buffer delay change in the presence of power and ground noiseIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2003.81231011:3(461-473)Online publication date: 1-Jun-2003
  • (2002)Maze Routing with Buffer Insertion under Transition Time ConstraintsProceedings of the conference on Design, automation and test in Europe10.5555/882452.874545Online publication date: 4-Mar-2002
  • (2002)Timing-driven routing for FPGAs based on Lagrangian relaxationProceedings of the 2002 international symposium on Physical design10.1145/505388.505431(176-181)Online publication date: 7-Apr-2002
  • (2001)A graph based algorithm for optimal buffer insertion under accurate delay modelsProceedings of the conference on Design, automation and test in Europe10.5555/367072.367382(535-539)Online publication date: 13-Mar-2001
  • (2001)A fast and accurate delay estimation method for buffered interconnectsProceedings of the 2001 Asia and South Pacific Design Automation Conference10.1145/370155.370526(533-538)Online publication date: 30-Jan-2001
  • (2000)Meeting delay constraints in DSM by minimal repeater insertionProceedings of the conference on Design, automation and test in Europe10.1145/343647.343814(436-440)Online publication date: 1-Jan-2000
  • (2000)A fast algorithm for context-aware buffer insertionProceedings of the 37th Annual Design Automation Conference10.1145/337292.337496(368-373)Online publication date: 1-Jun-2000
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media