Article

Free access

Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation

Authors:

Chung-Ping Chen,

Chris C. N. Chu,

D. F. WongAuthors Info & Claims

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

Pages 617 - 624

https://doi.org/10.1145/288548.289097

Published: 01 November 1998 Publication History

PDF eReader

References

[1]

M. S. Bazaraa, H. D. Sherali, and C. M. Shetty. Nonlinear Programming: Theory and Algorithms. John Wiley & Sons, Inc., second edition, 1993.

Google Scholar

[2]

Chung-Ping Chen, Yao-Wen Chang, and D. E Wong. Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation. In Proc. IEEE ICCAD, pages 405- 408, 1996.

Digital Library

Google Scholar

[3]

Chung-Ping Chen and D. E Wong. A fast algorithm for optimal wire-sizing under Elmore delay model. In Proc. IEEE ISCAS, volume 4, pages 412-415, 1996.

Google Scholar

[4]

Chung-Ping Chen, Hal Zhou, and D. E Wong. Optimal nonuniform wire-sizing under the Elmore delay model. In Proc. IEEE ICCAD, pages 38--43, 1996.

Digital Library

Google Scholar

[5]

Chris C. N. Chu, Chung-Ping Chen, and D. E Wong. Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation. Tech. Rep. TR98-06, UT Austin CS Dept., February 1998.

Digital Library

Google Scholar

[6]

M. A. Cidt. Transistor sizing in CMOS circuits. In Proc. ACM/IEEE DAC, pages 121-124, 1987.

Digital Library

Google Scholar

[7]

Jason Cong and Lei He. An efficient approach to simultaneous transistor and interconnect sizing, in Proc. IEEE ICCAD, pages 181-186, 1996.

Digital Library

Google Scholar

[8]

Jason Cong and Cheng-Kok Koh. Simultaneous driver and wire sizing for performance and power optimization. In Proc. IEEE ICCAD, pages 206--212, 1994.

Digital Library

Google Scholar

[9]

Jason Cong and Kwok-Shing Leung. Optimal wiresizing under the distributed Elmore delay model. IEEE Trans. on CAD, 14(3):321-336, March 1995.

Digital Library

Google Scholar

[10]

R.J. Duffin, E. L. Peterson, and C. Zener. Geometric Programruing - Theor3, and Application. John Wiley & Sons, Inc., NY, 1967.

Google Scholar

[11]

W. C. Elmore. The transient response of damped linear network with particular regard to wideband amplifiers. J. Applied Physics, 19:55-63, 1948.

Crossref

Google Scholar

[12]

J. P. Fishbum and A. E. Dunlop. TILOS: A posynominal programming approach to transistor sizing. In Proc. IE, EE ICCAD, pages 326-328, 1985.

Google Scholar

[13]

M. L. Fisher. An application oriented guide to lagrangian relaxation. Interfaces, 15(2):10-21, March-April 1985.

Digital Library

Google Scholar

[14]

D.G. Luenberger. Linear and Nonlinear Programming. Addison Wesley, second edition, 1984.

Google Scholar

[15]

David E Marple and Abbas El Gamal. Optimal selection of transistor sizes in digital VLSI circuits. In Proc. 1987 Stanford Conf., pages 151-172, 1987.

Google Scholar

[16]

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.

Digital Library

Google Scholar

[17]

N. Menezes, S. Pullela, E Dartu, and L. T. Pileggi. RC interconnect syntheses-a moment fitting approach. In Proc. IEEE ICCAD, pages 418-425, 1994.

Digital Library

Google Scholar

[18]

N. Menezes, S. Pullela, and L. T. Pileggi. Simultaneous gate and interconnect sizing for circuit level delay optimization. In Proc. ACM/IEEE DAC, pages 690--695, 1995.

Digital Library

Google Scholar

[19]

Sachin S. Sapatnekar. RC interconnect optimization under the Elmore delay model. In Proc. A CM/IEEE DAC, pages 387- 391, 1994.

Digital Library

Google Scholar

[20]

Sachin S. Sapatnekar, V. B. Rao, P. M. Vaidya, and S. M. Kang. An exact solution to the transistor sizing problem for CMOS circuits using convex optimizaiton. IEEE Trans. on CAD, 12(1 I): 1621-1634, November 1993.

Google Scholar

Cited By

View all

Zhang GLi BHuang XYin XZhuo CHashimoto MSchlichtmann U(2022)VirtualSync+: Timing Optimization With Virtual SynchronizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.315343341:12(5526-5540)Online publication date: Dec-2022
https://doi.org/10.1109/TCAD.2022.3153433
Zhang GLi BHashimoto MSchlichtmann U(2018)VirtualsyncProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3196135(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1145/3195970.3196135
Wu GChu C(2017)Two Approaches for Timing-Driven Placement by Lagrangian RelaxationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.269794736:12(2093-2105)Online publication date: Dec-2017
https://doi.org/10.1109/TCAD.2017.2697947
Show More Cited By

Index Terms

Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation

Recommendations

Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation

This paper considers simultaneous gate and wire sizing for general very large scale integrated (VLSI) circuits under the Elmore delay model. We present a fast and exact algorithm which can minimize total area subject to maximum delay bound. The ...
Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization

Optimization problems whose objective function and constraints are quadratic polynomials are called quadratically constrained quadratic programs (QCQPs). QCQPs are NP-hard in general and are important in optimization theory and practice. There have been ...
Fast and Exact Simultaneous Gate and Wire Sizing by Lagrangian Relaxation

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

November 1998

704 pages

ISBN:1581130082

DOI:10.1145/288548

Chairman:
Hiroto Yasuura
Kyushu Univ., Fukuoka, Japan

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICCAD '98

Sponsor:

IEEE-EDS
SIGDA
IEEE-CAS
IEEE-CS

ICCAD '98: International Conference on Computer-Aided Design - 1998

November 8 - 12, 1998

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

71
Total Citations
View Citations
714
Total Downloads

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

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang GLi BHuang XYin XZhuo CHashimoto MSchlichtmann U(2022)VirtualSync+: Timing Optimization With Virtual SynchronizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.315343341:12(5526-5540)Online publication date: Dec-2022
https://doi.org/10.1109/TCAD.2022.3153433
Zhang GLi BHashimoto MSchlichtmann U(2018)VirtualsyncProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3196135(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1145/3195970.3196135
Wu GChu C(2017)Two Approaches for Timing-Driven Placement by Lagrangian RelaxationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.269794736:12(2093-2105)Online publication date: Dec-2017
https://doi.org/10.1109/TCAD.2017.2697947
Wu GChu CFanucci LTeich J(2016)Simultaneous slack matching, gate sizing and repeater insertion for asynchronous circuitsProceedings of the 2016 Conference on Design, Automation & Test in Europe10.5555/2971808.2972051(1042-1047)Online publication date: 14-Mar-2016
https://dl.acm.org/doi/10.5555/2971808.2972051
Roy SLiu DSingh JUm JPan D(2016)OSFAIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2016.252343935:10(1618-1629)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1109/TCAD.2016.2523439
Sundararajan V(2016)Gate SizingEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_159(811-814)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_159
Roy SLiu DUm JPan D(2015)OSFAProceedings of the 52nd Annual Design Automation Conference10.1145/2744769.2744885(1-6)Online publication date: 7-Jun-2015
https://dl.acm.org/doi/10.1145/2744769.2744885
Wu GSharma AChu C(2015)Gate Sizing and Vth Assignment for Asynchronous Circuits Using Lagrangian Relaxation2015 21st IEEE International Symposium on Asynchronous Circuits and Systems10.1109/ASYNC.2015.17(53-60)Online publication date: May-2015
https://doi.org/10.1109/ASYNC.2015.17
Sundararajan V(2015)Gate SizingEncyclopedia of Algorithms10.1007/978-3-642-27848-8_159-2(1-4)Online publication date: 25-Jun-2015
https://doi.org/10.1007/978-3-642-27848-8_159-2
Wu GLin THuang HChu CBeerel PChang Y(2014)Asynchronous circuit placement by lagrangian relaxationProceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design10.5555/2691365.2691496(641-646)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.5555/2691365.2691496
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

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

Cited By

Index Terms

Recommendations

Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation

Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization

Fast and Exact Simultaneous Gate and Wire Sizing by Lagrangian Relaxation