Gate sizing by Lagrangian relaxation revisited

Jia Wang*, Debasish Das, Hai Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


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.

Original languageEnglish (US)
Article number5075815
Pages (from-to)1071-1084
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number7
StatePublished - Jul 2009


  • Convex programming
  • Gate sizing
  • Lagrangian relaxation
  • Method of feasible directions
  • Network flow

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


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

Cite this