Gate sizing by Lagrangian relaxation revisited

Jia Wang*, Debasish Das, Hai Zhou

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations


In this paper, we formulate the Generalized Convex Sizing (GCS) problem that unities 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.

Original languageEnglish (US)
Title of host publication2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD
Number of pages8
StatePublished - 2007
Event2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD - San Jose, CA, United States
Duration: Nov 4 2007Nov 8 2007

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)1092-3152


Other2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD
Country/TerritoryUnited States
CitySan Jose, CA

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Gate sizing by Lagrangian relaxation revisited'. Together they form a unique fingerprint.

Cite this