A quadratic programming approach to simultaneous buffer insertion/sizing and wire sizing
Authors:
- D.F. WongDWD.F. Wong
- 1 June 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 (6) , 787-798
Abstract
In this paper, we present a completely new approach to the problem of delay minimization by simultaneous buffer insertion and wire sizing for a wire. We show that the problem can be formulated as a convex quadratic program, which is known to be solvable in polynomial time. Nevertheless, we explore some special properties of our problem and derive an optimal and very efficient algorithm, modified active set method (MASM), to solve the resulting program. Given m buffers and a set of m discrete choices of wire width, the running time of our algorithm is O(mn2) and is independent of the wire length in practice. For example, an instance of 100 buffers and 100 choices of wire width can be solved in 0.92 s. In addition, we extend MASM to consider simultaneous buffer insertion, buffer sizing, and wire sizing. The resulting algorithm MASM-BS is again optimal and very efficient. For example, with six choices of buffer size and 10 choices of wire width, the optimal solution for a 15000 μm long wire can be found in 0.05 s. Besides, our formulation is so versatile that it is easy to consider other objectives like wire area or power dissipation, or to add constraints to the solution. Also, wire capacitance lookup tables, or very general wire capacitance models which can capture area capacitance, fringing capacitance, coupling capacitance, etc. can be usedKeywords
This publication has 13 references indexed in Scilit:
- Closed form solution to simultaneous buffer insertion/sizing and wire sizing1997
- Interconnect design for deep submicron ICs1997
- Performance optimization of VLSI interconnect layoutIntegration, 1996
- Optimal wire sizing and buffer insertion for low power and a generalized delay modelIEEE Journal of Solid-State Circuits, 1996
- A fast algorithm for optimal wire-sizing under Elmore delay model1996
- Shaping a distributed-RC line to minimize Elmore delayIEEE Transactions on Circuits and Systems I: Regular Papers, 1995
- Optimum buffer circuits for driving long uniform linesIEEE Journal of Solid-State Circuits, 1991
- CMOS Circuit Speed and Buffer OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Comments on "An optimized output stage for MOS integrated circuits" [with reply]IEEE Journal of Solid-State Circuits, 1975
- The Transient Response of Damped Linear Networks with Particular Regard to Wideband AmplifiersJournal of Applied Physics, 1948