Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation
- 1 July 1999
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 18 (7) , 1014-1025
- https://doi.org/10.1109/43.771182
Abstract
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 27648 gates and wires in 11.53 min using under 23 Mbytes memory on a PC with a 333-MHz Pentium II processor.Keywords
This publication has 19 references indexed in Scilit:
- Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Power vs. delay in gate sizing: conflicting objectives?Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Optimal wiresizing under Elmore delay modelIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1995
- RC interconnect optimization under the Elmore delay modelPublished by Association for Computing Machinery (ACM) ,1994
- An exact solution to the transistor sizing problem for CMOS circuits using convex optimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- Transistor size optimization in the tailor layout systemPublished by Association for Computing Machinery (ACM) ,1989
- Transistor sizing in CMOS circuitsPublished by Association for Computing Machinery (ACM) ,1987
- An Applications Oriented Guide to Lagrangian RelaxationInterfaces, 1985
- Short-circuit dissipation of static CMOS circuitry and its impact on the design of buffer circuitsIEEE Journal of Solid-State Circuits, 1984
- The Transient Response of Damped Linear Networks with Particular Regard to Wideband AmplifiersJournal of Applied Physics, 1948