Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation

Abstract

This paper considers simultaneous gate and wire sizing for general VUI circuits under the E[more delay model. JVepresent a fast and met algorithm which can minimize total area subject to mmimurn delay bound. The algorithm can be easily modl~ed to give ~wct algorithms for optimizing several other objectives (e.g. minimizing maximum delay or minimizing total area subject to arrival time specl~cations at all inputs and outputs). No previous algorithm for simultaneous gate and wire sizing can guarantee met solutions for general circuits. Our algorithm is an iterative one with a guarantee on convergence to global Oph.malsolutions. It is based on hgransian relmtion and "one-gatdwire-at-a-time" local optimi~tions, and is mtremely economical and fast. For example, we can optimize a circuit with 27,648 gates and wires in about 36 minutes using under 23 MB metnory on an IBM RS/6000 worhtation.