Cited By
View all- Zhang HWong MChao KDeng LNam GSaxena P(2009)Wire shaping is practicalProceedings of the 2009 international symposium on Physical design10.1145/1514932.1514961(131-138)Online publication date: 29-Mar-2009
An efficient algorithm for statistical circuit optimization using Lagrangian relaxation
Authors: 
I-Jye Lin, Yao-Wen ChangAuthors Info & Claims
I-Jye Lin, Yao-Wen ChangAuthors Info & ClaimsPages 119 - 124
Abstract
Due to the technology scaling down, process variation has become a crucial challenge on both interconnect delay and reliability. To handle the process variation, statistical optimization has emerged as a popular technique for yield improvement. As a relatively new technique, second-order conic programming (SOCP) has recently attracted very much attention in the literature for statistical circuit optimization. However, we observe significant limitations of SOCP in its flexibility, accuracy, and scalability for statistical circuit optimization, especially when interconnects are considered. We thus present in this paper an effective and efficient alternative for multi-constrained statistical circuit optimization by both gate and wire sizing using Lagrangian relaxation (LR). Compared with SOCP, experimental results show that our LR-based algorithm can achieve much better solution quality by reducing 21% area and obtain 560X speed-up over SOCP.
References
[1]
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.
[2]
K. Banerjee, M. Pedram, and H. Ajami, "Analysis and Optimization of Thermal Issues in High-performance VLSI," Proc. ISPD, pp. 230--237, Apr. 2001.
[3]
J. R. Black, "Electromigration-a Brief Survey and Some Recent Results," IEEE Trans. Electron Devices, pp. 338--347, 1969.
[4]
S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge, 2004.
[5]
J. Chern, J. Huang, L. Arledge, P. Li, and P. Yang, "Multilevel Metal Capacitance Models for CAD Design Synthesis Systems," IEEE Electron Devices Letters, pp. 32--34, Jan. 1992.
[6]
C.-P. Chen, C. C. N. Chu, and D. F. Wong, "Fast and Exact Simultaneous Gate and Wire Sizing by Lagrangian Relaxation," Proc. ICCAD, pp. 617--624, Nov. 1998.
[7]
S. H. Choi, B. C. Paul and K. Roy, "Novel Sizing Algorithm for Yield Improvement under Process Variarion in Nanometer Technology," Proc. DAC, pp. 454--459, Jun. 2004.
[8]
F. S. Hillier and G. J. Lieberman, Introduction to Operations Research, 5th ed., McGraw Hill, 1990.
[9]
H.-R. Jiang, J.-Y. Jou, and Y.-W. Chang, "Noise-constrained Performance Optimization by Simultaneous Gate and Wire Sizing based on Lagrangian Relaxation," Proc. DAC, pp. 90--95, Jun. 1999.
[10]
I-J. Lin, T.-Y. Ling, and Y.-W. Chang, "Statistical Circuit Optimization Considering Device and Interconnect Process Variations, " Proc. SLIP, pp. 47--54, Mar. 2007.
[11]
Y. Liu, S. Nassif, L. Pileggi, and A. J. Strojwas, "Impact of Interconnect Variations on the Clock Skew of a Gigahertz Microprocessor," Proc. DAC., pp. 168--171, Jun. 2000.
[12]
M. Mani and M. Orshansky, "A New Statistical Optimization Algorithm for Gate Sizing," Proc. ICCD, pp. 272--277, Sep. 2004.
[13]
M. Mani, A. Devgan, and M. Orshansky, "An Efficient Algorithm for Statistical Minimization of Total Power under Timing Yield Constraints," Proc. DAC, pp. 309--314, Jun. 2005.
[14]
M. Mani, A. K. Singh, and M. Orshansky "Joint Design-Time and Post-Silicon Minimization of Parametric Yield Loss using Adjustable Robust Optimization," Proc. ICCAD, pp. 19--26, Nov. 2006.
[15]
MOSEK tool http://www.mosek.com/documentation.htm#manuals
[16]
A. Srivastava, D. Sylvester, and D. Blaauw, Statistical Analysis and Optimization for VLSI: Timing and Power, Michigan, 2005.
[17]
C. Visweswariah, "Statistical Analysis and Optimization in the Presence of Gate and Interconnect Delay Variations," Proc. SLIP, pp. 37, Mar. 2006.
[18]
W. L. Winston, Operations Research: Applications and Algorithms, Thomson, 1994.
- An efficient algorithm for statistical circuit optimization using Lagrangian relaxation
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 ...
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 ...
On Lagrangian Relaxation of Quadratic Matrix Constraints
Quadratically constrained quadratic programs (QQPs) play an important modeling role for many diverse problems. These problems are in general NP hard and numerically intractable. Lagrangian relaxations often provide good approximate solutions to these ...
Comments
Information & Contributors
Information
Published In
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
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 153Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 07 Mar 2025
Other Metrics
Citations
Cited By
View all- Zhang HWong MChao KDeng LNam GSaxena P(2009)Wire shaping is practicalProceedings of the 2009 international symposium on Physical design10.1145/1514932.1514961(131-138)Online publication date: 29-Mar-2009
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in