research-article

Gate sizing by Lagrangian relaxation revisited

Authors:

Hai ZhouAuthors Info & Claims

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

Pages 111 - 118

Published: 05 November 2007 Publication History

Abstract

In this paper, we formulate the Generalized Convex Sizing (GCS) problem that unifies and generalizes the sizing problems. We revisit the approach to solve the sizing problem by Lagrangian relaxation, point out several misunderstandings in the previous works, and extend the approach to handle general convex delay functions in the GCS problems. We identify a class of proper GCS problems whose objective functions in the simplified dual problem are differentiable and show many practical sizing problems, including the simultaneous sizing and clock skew optimization problem, are proper. We design an algorithm based on the method of feasible directions to solve proper GCS problems. The algorithm will provide evidences for infeasible GCS problems according to a condition derived by us. Experimental results confirm the efficiency and the effectiveness of our algorithm when the Elmore delay model is used.

References

[1]

J. Fishburn and A. Dunlop, "TILOS: A posynomial programming approach to transistor sizing," in ICCAD, 1985, pp. 326--328.

[2]

S. 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 optimization," IEEE TCAD, vol. 12, pp. 1621--1634, Nov. 1993.

Digital Library

[3]

W. Chuang, S. S. Sapatnekar, and I. N. Hajj, "Timing and area optimization for standard-cell VLSI circuit design," IEEE TCAD, vol. 14, no. 3, pp. 308--320, Mar. 1995.

Digital Library

[4]

C.-P. Chen, C. C. N. Chu, and D. F. Wong, "Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation," IEEE TCAD, vol. 18, no. 7, pp. 1014--1025, July 1999.

Digital Library

[5]

V. Sundararajan, S. S. Sapatnekar, and K. K. Parhi, "Fast and exact transistor sizing based on iterative relaxation," IEEE TCAD, vol. 21, no. 5, pp. 568--581, May 2002.

Digital Library

[6]

H. Tennakoon and C. Sechen, "Gate sizing using Lagrangian relaxation combined with a fast gradient-based pre-processing step," in ICCAD, 2002, pp. 395--402.

Digital Library

[7]

S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004.

Digital Library

[8]

M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming, 3rd ed. Wiley-Interscience, 2006.

[9]

W. C. Elmore, "The transient response of damped linear networks with particular regard to wide-band amplifiers," Journal of Applied Physics, vol. 19, no. 1, pp. 55--63, Jan. 1948.

[10]

K. Kasamsetty, M. Ketkar, and S. S. Sapatnekar, "A new class of convex functions for delay modeling and their application to the transistor sizing problem," IEEE TCAD, vol. 19, no. 7, pp. 779--788, July 2000.

Digital Library

[11]

Faraday Technology Corporation, "UMC 90-nano Libraries," http://freelibrary.faraday-tech.com/, Nov. 2005.

[12]

H. Tennakoon and C. Sechen, "Efficient and accurate gate sizing with piecewise convex delay models," in DAC, 2005, pp. 807--812.

Digital Library

[13]

C. Lin and H. Zhou, "Clock skew scheduling with delay padding for prescribed skew domains," in ASP-DAC, 2007.

[14]

R. T. Rockafellar, "Ordinary convex programs without a duality gap," Journal of Optimization Theory and Applications, vol. 7, no. 3, pp. 143--148, Mar. 1971.

[15]

Andrew Goldberg's network optimization library, http://www.avglab.com/andrew/soft.html.

Cited By

Xie JChen CJones ALi HCoskun AMargala M(2015)Lookup Table Based Discrete Gate Sizing for Delay Minimization with Modified Elmore Delay ModelProceedings of the 25th edition on Great Lakes Symposium on VLSI10.1145/2742060.2742094(361-366)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1145/2742060.2742094
Li LKang PLu YZhou HHu A(2012)An efficient algorithm for library-based cell-type selection in high-performance low-power designsProceedings of the International Conference on Computer-Aided Design10.1145/2429384.2429427(226-232)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2429384.2429427
Shklover GEmanuel BHu JKoh C(2012)Simultaneous clock and data gate sizing algorithm with common global objectiveProceedings of the 2012 ACM international symposium on International Symposium on Physical Design10.1145/2160916.2160948(145-152)Online publication date: 25-Mar-2012
https://dl.acm.org/doi/10.1145/2160916.2160948
Show More Cited By

Gate sizing by Lagrangian relaxation revisited
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

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 ...
Gate sizing by Lagrangian relaxation revisited

In this paper, we formulate the generalized convex sizing (GCS) problem that unifies the sizing problems and applies to sequential circuits with clock-skew optimization. We revisit the approach to solve the sizing problem by Lagrangian relaxation, point ...
A Lagrangian---DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems

We propose an efficient computational method for linearly constrained quadratic optimization problems (QOPs) with complementarity constraints based on their Lagrangian and doubly nonnegative (DNN) relaxation and first-order algorithms. The simplified ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

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

November 2007

933 pages

ISBN:1424413826

General Chair:
Georges Gielen
ESAT-MICAS, Katholieke Univ. Leuven, Leuven, Belgium

Sponsors

CEDA: Council on Electronic Design Automation
SIGDA: ACM Special Interest Group on Design Automation
IEEE CASS/CANDE
IEEE-CS\DATC: IEEE Computer Society

Publisher

IEEE Press

Publication History

Published: 05 November 2007

Check for updates

Qualifiers

Research-article

Conference

ICCAD07

Sponsor:

CEDA
SIGDA
IEEE-CS\DATC

ICCAD07: The International Conference on Computer-Aided Design 2007

November 5 - 8, 2007

California, San Jose

Acceptance Rates

ICCAD '07 Paper Acceptance Rate 139 of 510 submissions, 27%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
182
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xie JChen CJones ALi HCoskun AMargala M(2015)Lookup Table Based Discrete Gate Sizing for Delay Minimization with Modified Elmore Delay ModelProceedings of the 25th edition on Great Lakes Symposium on VLSI10.1145/2742060.2742094(361-366)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1145/2742060.2742094
Li LKang PLu YZhou HHu A(2012)An efficient algorithm for library-based cell-type selection in high-performance low-power designsProceedings of the International Conference on Computer-Aided Design10.1145/2429384.2429427(226-232)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2429384.2429427
Shklover GEmanuel BHu JKoh C(2012)Simultaneous clock and data gate sizing algorithm with common global objectiveProceedings of the 2012 ACM international symposium on International Symposium on Physical Design10.1145/2160916.2160948(145-152)Online publication date: 25-Mar-2012
https://dl.acm.org/doi/10.1145/2160916.2160948
Li LSun JLu YZhou HZeng X(2011)Low power discrete voltage assignment under clock skew schedulingProceedings of the 16th Asia and South Pacific Design Automation Conference10.5555/1950815.1950920(515-520)Online publication date: 25-Jan-2011
https://dl.acm.org/doi/10.5555/1950815.1950920
Huang YHu JShi WChang YHu J(2011)Lagrangian relaxation for gate implementation selectionProceedings of the 2011 international symposium on Physical design10.1145/1960397.1960436(167-174)Online publication date: 27-Mar-2011
https://dl.acm.org/doi/10.1145/1960397.1960436
Held SBenini LDe Micheli GAl-Hashimi BMueller W(2009)Gate sizing for large cell-based designsProceedings of the Conference on Design, Automation and Test in Europe10.5555/1874620.1874823(827-832)Online publication date: 20-Apr-2009
https://dl.acm.org/doi/10.5555/1874620.1874823
Lu YZhou HShang LZeng X(2009)Multicore parallel min-cost flow algorithm for CAD applicationsProceedings of the 46th Annual Design Automation Conference10.1145/1629911.1630124(832-837)Online publication date: 26-Jul-2009
https://dl.acm.org/doi/10.1145/1629911.1630124
Wu TDavoodi A(2009)PaRSIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2009.202868228:11(1666-1678)Online publication date: 1-Nov-2009
https://dl.acm.org/doi/10.1109/TCAD.2009.2028682
Wang JDas DZhou H(2009)Gate sizing by Lagrangian relaxation revisitedIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2009.201887228:7(1071-1084)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1109/TCAD.2009.2018872

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten