Simulatenous Transistor and Interconnect Sizing Based on General Dominance Property

Jason Cong and Lei He
cong, helei@cs.ucla.edu

In this paper, we study the simultaneous transistor and interconnect sizing (STIS) problem. Our contributions include: (1) We formulated the STIS problem using a distributed RC circuit model which models the waveform-dependent transistor resistances, the distributed nature of the interconnects and the transistor-interconnect interactions. (2) We showed a general dominance property for a large class of posynomial functions (Theorems 1 and 2) and developed efficient algorithms based on recursive local refinement or bundled refinement for optimizing such functions. Although our intended application is to develop optimal algorithms for the STIS problem under a wide range of transistor and interconnect models, it also has direct applications to many other optimization problems in VLSI CAD and other domains. (3) Based on the general dominance property, we developed efficient and optimal algorithms for the STIS problem, which are much more efficient than the mathematical programming based methods such as the convex-programming based transistor-sizing and superior to the sensitivity-based heuristics used in many transistor or interconnect sizing works in terms of both global convergence and optimality. The preliminary experiments for both transistor sizing and simultaneous transistor and interconnect sizing are reported. To our knowledge, this is the first in-depth study of the simultaneous transistor and interconnect sizing problem.