Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation

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

Research output: Contribution to journalConference article

Abstract

This paper considers simultaneous gate and wire sizing for general 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' local optimizations, and is extremely economical and fast. For example, we can optimize a circuit with 27,648 gates and wires in about 36 minutes using under 23 MB memory on an IBM RS/6000 workstation.

Original languageEnglish (US)
Pages (from-to)617-624
Number of pages8
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
DOIs
StatePublished - 1998
Externally publishedYes
EventProceedings of the 1998 IEEE/ACM International Conference on Computer-Aided Design, ICCAD - San Jose, CA, USA
Duration: Nov 8 1998Nov 12 1998

ASJC Scopus subject areas

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

Fingerprint 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