Crosstalk-driven interconnect optimization by simultaneous gate and wire sizing

Noise, as well as area, delay, and power, is one of the most important conc erns in the design of deep submicrometer integrated circuits. Currently exi sting algorithms do not handle simultaneous switching conditions of signals for noise minimization. In this paper, we model not only physical coupling capacitance, but also simultaneous switching behavior for noise optimizati on. Based on Lagrangian relaxation, we present an algorithm which ran optim ally solve the simultaneous noise, area, delay, and power optimization prob lem by sizing circuit components. Our algorithm, with linear memory require ment and linear runtime, is very effective and efficient. For example, for a circuit of 6144 wires and 3512 gates, our algorithm solves the simultaneo us optimization problem using only 2.1-MB memory and 19.4-min runtime to ac hieve the precision of within 1% error on a SUN Spare Ultra-I workstation.