Article

Free access

Buffered Steiner tree construction with wire sizing for interconnect layout optimization

Authors:

Takumi Okamoto,

Jason CongAuthors Info & Claims

ICCAD '96: Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design

Pages 44 - 49

Published: 01 January 1997 Publication History

Abstract

This paper presents an efficient algorithm for buffered Steiner tree construction with wire sizing. Given a source and n sinks of a signal net, with given positions and a required arrival time associated with each sink, the algorithm finds a Steiner tree with buffer insertion and wire sizing so that the required arrival time (or timing slack) at the source is maximized. The unique contribution of our algorithm is that it performs Steiner tree construction, buffer insertion, and wire sizing simultaneously with consideration of both critical delay and total capacitance minimization by combining the performance-driven A-tree construction and dynamic programming based buffer insertion and wire sizing, while tree construction and the other delay minimization techniques were carried out independently in the past. Experimental results show the effectiveness of our approach.

References

[1]

C. L. Barman, J. L. Carter, and K. F. Day, "The fanout problem: From theory to practice," Advanced Research in VL SI: Proc. 1989 Decennial CaItech Co@, pp.69-99, 1989.

Digital Library

[2]

J. Cong and C.-K. Koh, "Simultaneous Driver and Wire Sizing for Performance and Power Optimization," IEEE Trans. V LSI, 2(4), pp.408-423, Dec. 1994.

Digital Library

[3]

J. Cong and K. S. Leung, "Optimal Wiresizing Under the Distributed Elmore Delay Model," IEEE Trans. Computer- Aided Design, 14(3), pp.321-336, Mar. 1995.

Digital Library

[4]

J. Cong, K. S. Leung, and D. Zhou, "Performance-Driven Interconnect Design Based on Distributed RC Delay Mode," Proc. A CM/IEEE Design Automation Conf., 1993, pp.606- 611.

Digital Library

[5]

W. C. Elmore, "The Transient Response of Damped Linear Network with Particular Regard to Wideband Amplifier," J. Applied Physics, 19, pp. 55-63, 1948.

[6]

L.P.P.P. van Ginneken, "Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay," Proc. IEEE Int. Symp. Circuits Syst., 1990, pp.865-868.

[7]

T. D. Hodes, B. A. McCoy, and G. Robins, "Dynamically- Wiresized Elmore-Based Routing Constructions," Proc. IEEE Int. Syrup. Circuits Syst., 1994, pp.463-466.

[8]

A. B. Kahng and G. Robins, On Optimal Interconnection for VLSI, Kluwer Academic Publishers, 1995.

[9]

L. N. Kannan, P. R. Suaris, and H. G. Fang, "A Methodology and Algorithms for Post-Placement Delay Optimization," Proc. A CM/IEEE Design Automation Conf., 1994, pp.32%332.

Digital Library

[10]

J. Lillis, C. K. Cheng, and T. T. Lin, "Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model," Proc. IEEE Int. Conf. Computer-Aided Design, 1995, pp.138-143.

Digital Library

[11]

J. Lillis, C. K. Cheng, and T. T. Lin, "Simultaneous Routing and Buffer Insertion for High Performance Interconnect," Proc. the Sixth Great Lakes Symp. on VLSL 1996

Digital Library

[12]

J. Lillis, C. K. Cheng, T. T. Lin, and C. Y. Ho, "New Performance Driven Routing Techniques with Explicit Area/Delay Tradeoff and Simultaneous Wire Sizing," Proc. A CM//IEEE Design Automation Conf., 1996, pp. 395-400.

Digital Library

[13]

N. Menezes, R. Baldick, and L. T. Pileggi, "A Sequential Quadratic Programming Approach to Concurrent Gate and Wire Sizing," Proc. IEEE Int. Conf. Computer-Aided Design, 1995, pp.144-151.

Digital Library

[14]

T. Okamoto and J. Cong, "Interconnect Layout Optimization by Simultaneous Steiner Tree Construction and Buffer Insertion," Proc. Fifth A CM/SIGDA Physical Design Workshop, 1996, pp.1-6.

[15]

S. K. Rao, P. Sadayappan, F. K. Hwang, and P. W. Shor, "The Rectilinear Steiner Arborescence Problem," A Igorithmica 7, pp.277-288, 1992.

[16]

J. Rubinstein, P. Penfield, and M. A. Horowitz, "Signal Delay in RC Tree Networks," IEEE Trans. Computer-Aided Design, 2(3), pp.202-211, 1983.

Digital Library

[17]

S. S. Sapatnekar, "RC Interconnect Optimization under the Elmore Delay Model," Proc. A CM/IEEE Design A utomation Conf., 1994, pp. 387-391.

Digital Library

[18]

K. J. Singh and A. Sangiovanni-Vincentelli, "A Heuristic AI- gorithm for the Fanout Problem," Proc. A CM/IEEE Design Automation Conf., 1990, pp.357-360.

Digital Library

[19]

H. J. Touati, C. W. Moon, R. K. Brayton, and A. Wang, "Performance Oriented Technology Mapping," Proc. sixth MIT VLSI Conf., pp.79-97, 1990.

Digital Library

[20]

H. Vaishnav and M. Pedram, "Routability-Driven Fanout Optimization," Proc. A CM/IEEE Design Automation Conf., 1993, pp.230-235.

Digital Library

[21]

T. Xue, and E. S. Kuh, "Post Routing Performance Optimization via Multi-Link Insertion and Non-Uniform Wiresizing," Proc. IEEE Int. Conf. Computer-Aided Design, 1995, pp. 575-580.

Digital Library

[22]

D. Zhou, F. P. Preparata, and S. M. Kang, "Interconnection Delay in Very High-Speed VLSI," IEEE Trans. Circuits Syst., 38(7), pp.779-790, July 1991.

Cited By

Kim JKim T(2017)Adjustable Delay Buffer Allocation under Useful Clock Skew SchedulingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2016.259721336:4(641-654)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TCAD.2016.2597213
Kim JJoo DKim T(2016)Optimal utilization of adjustable delay clock buffers for timing correction in designs with multiple power modesIntegration, the VLSI Journal10.1016/j.vlsi.2015.08.00552:C(91-101)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.vlsi.2015.08.005
Siozios KSoudris DHübner M(2014)A Framework for Supporting Adaptive Fault-Tolerant SolutionsACM Transactions on Embedded Computing Systems10.1145/262947313:5s(1-22)Online publication date: 15-Dec-2014
https://dl.acm.org/doi/10.1145/2629473
Show More Cited By

Index Terms

Buffered Steiner tree construction with wire sizing for interconnect layout optimization
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Partitioning and floorplanning
  2. Very large scale integration design
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Trees

Recommendations

Closed form solutions to simultaneous buffer insertion/sizing and wire sizing

In this paper, we consider the delay minimization problem of an interconnect wire by simultaneously considering buffer insertion, buffer sizing and wire sizing. We consider three cases, namely using no buffer (i.e., wire sizing alone), using a given ...
An efficient routing tree construction algorithm with buffer insertion, wire sizing, and obstacle considerations

In this paper, we propose a fast algorithm to construct a performance-driven routing tree with simultaneous buffer insertion and wire sizing in the presence of wire and buffer obstacles. Recently, several algorithms have been published addressing the ...
Power-optimal simultaneous buffer insertion/sizing and wire sizing for two-pin nets

This paper studies the problems of optimizing power dissipation for simultaneous buffer insertion/sizing and uniform wire sizing (BISUWS), and simultaneous buffer insertion/sizing and tapered wire sizing (BISTWS). For BISUWS, we analyze the optimal ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '96: Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design

January 1997

703 pages

ISBN:0818675977

Chairmen:
Rob A. Rutenbar
Carnegie Mellon Univ., Pittsburgh, PA
,
Ralph H. J. M. Otten
Delft Univ. of Technology, Delft, The Netherlands

Copyright © Copyright (c) 1996 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CAS: Circuits & Systems
IEEE-CS: Computer Society

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 January 1997

Check for updates

Author Tags

Qualifiers

Article

Conference

ICCAD '96

Sponsor:

SIGDA
IEEE-CAS
IEEE-CS

ICCAD '96: International Conference on Computer Aided Design

November 10 - 14, 1996

California, San Jose, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
931
Total Downloads

Downloads (Last 12 months)464
Downloads (Last 6 weeks)25

Reflects downloads up to 07 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kim JKim T(2017)Adjustable Delay Buffer Allocation under Useful Clock Skew SchedulingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2016.259721336:4(641-654)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TCAD.2016.2597213
Kim JJoo DKim T(2016)Optimal utilization of adjustable delay clock buffers for timing correction in designs with multiple power modesIntegration, the VLSI Journal10.1016/j.vlsi.2015.08.00552:C(91-101)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.vlsi.2015.08.005
Siozios KSoudris DHübner M(2014)A Framework for Supporting Adaptive Fault-Tolerant SolutionsACM Transactions on Embedded Computing Systems10.1145/262947313:5s(1-22)Online publication date: 15-Dec-2014
https://dl.acm.org/doi/10.1145/2629473
Kim JJoo DKim T(2013)An optimal algorithm of adjustable delay buffer insertion for solving clock skew variation problemProceedings of the 50th Annual Design Automation Conference10.1145/2463209.2488845(1-6)Online publication date: 29-May-2013
https://dl.acm.org/doi/10.1145/2463209.2488845
Lim KKim T(2011)An optimal algorithm for allocation, placement, and delay assignment of adjustable delay buffers for clock skew minimization in multi-voltage mode designsProceedings of the 16th Asia and South Pacific Design Automation Conference10.5555/1950815.1950918(503-508)Online publication date: 25-Jan-2011
https://dl.acm.org/doi/10.5555/1950815.1950918
Su YHon WYang CChang SChang YRoychowdhury J(2009)Value assignment of Adjustable Delay Buffers for clock skew minimization in multi-voltage mode designsProceedings of the 2009 International Conference on Computer-Aided Design10.1145/1687399.1687500(535-538)Online publication date: 2-Nov-2009
https://dl.acm.org/doi/10.1145/1687399.1687500
Ryzhenko NVenger ONarayanan VYan ZMacii EBhanja S(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
https://dl.acm.org/doi/10.1145/1366110.1366174
Bañeres DCortadella JKishinevsky MLauwereins RMadsen J(2007)Layout-aware gate duplication and buffer insertionProceedings of the conference on Design, automation and test in Europe10.5555/1266366.1266664(1367-1372)Online publication date: 16-Apr-2007
https://dl.acm.org/doi/10.5555/1266366.1266664
Hu YTam KJing THe LKennings AMandoiu I(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
https://dl.acm.org/doi/10.1145/1231956.1231976
Bartoschek CHeld SRautenbach DVygen JScheffer L(2006)Efficient generation of short and fast repeater tree topologiesProceedings of the 2006 international symposium on Physical design10.1145/1123008.1123032(120-127)Online publication date: 9-Apr-2006
https://dl.acm.org/doi/10.1145/1123008.1123032
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents