Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation

This paper considers simultaneous gate and wire sizing for general ver,y la rge scale integrated (VLSI) circuits under the Elmore delay-model. We prese nt a fast and exact algorithm which can minimize total area subject to maxi mum delay bound. The algorithm can be easily modified to give exact algorit hms for optimizing several other objectives (e,g,, minimizing maximum delay or minimizing total area subject to arrival time specifications at all inp uts and outputs). No pre,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 solutio ns. It is based on Lagrangian relaxation and "one-gate/wire-at-a-time" gree dy optimizations, and is extremely economical and fast. For example, we can optimize a circuit Kith 27 648 gates and wires in 11.53 min using under 23 Mbytes memory on a PC with a 333-MHz Pentium II processor.