Gate Sizing by Lagrangian Relaxation Revisited
Authors:
- Jia WangJWJia Wang
- Debasish DasDDDebasish Das
- Hai ZhouHZHai Zhou
- 16 June 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 28 (7) , 1071-1084
Abstract
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 out several misunderstandings in the previous paper, 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 transform the simultaneous sizing and clock-skew optimization problem into a proper GCS problem. We design an algorithm based on the method of feasible directions and min-cost network flow 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.Keywords
This publication has 20 references indexed in Scilit:
- Gate sizing by lagrangian relaxation revisited2007
- Gate sizing for cell library-based designsProceedings of the 39th conference on Design automation - DAC '02, 2007
- Fast and effective gate-sizing with multiple-V/sub t/ assignment using generalized Lagrangian relaxation2005
- Efficient and accurate gate sizing with piecewise convex delay models2005
- A new class of convex functions for delay modeling and its application to the transistor sizing problem [CMOS gates]IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000
- Speeding up pipelined circuits through a combination of gate sizing and clock skew optimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998
- Gate sizing for constrained delay/power/area optimizationIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1997
- Timing and area optimization for standard-cell VLSI circuit designIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1995
- An exact solution to the transistor sizing problem for CMOS circuits using convex optimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- The Transient Response of Damped Linear Networks with Particular Regard to Wideband AmplifiersJournal of Applied Physics, 1948