Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation

Chung Ping Chen, C. C. N. Chu, D. F. Wong

Research output: Contribution to journalJournal articlepeer-review

154 Citations (Scopus)


This paper considers simultaneous gate and wire sizing for general very large scale integrated (VLSI) circuits under the Elmore delay model. We present a fast and exact algorithm which can minimize total area subject to maximum delay bound. The algorithm can be easily modified to give exact algorithms for optimizing several other objectives (e.g., minimizing maximum delay or minimizing total area subject to arrival time specifications at all inputs and outputs). No previous algorithm for simultaneous gate and wire sizing can guarantee exact solutions for general circuits. Our algorithm is an iterative one with a guarantee on convergence to global optimal solutions. It is based on Lagrangian relaxation and 'one-gate/wire-at-a-time' greedy optimizations, and is extremely economical and fast. For example, we can optimize a circuit with 27 648 gates and wires in 11.53 min using under 23 Mbytes memory on a PC with a 333-MHz Pentium II processor.

Original languageEnglish
Pages (from-to)1014-1025
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number7
Publication statusPublished - Jul 1999

Scopus Subject Areas

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


Dive into the research topics of 'Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation'. Together they form a unique fingerprint.

Cite this