Theory and Algorithm of Local-Refinement Based Optimization with Application to Transistor and Interconnect Sizing

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

In this paper, we formulate a new class of optimization problem, named the general CH-posynomial program, and reveal the general dominance property. We propose an efficient algorithm based on the extended local refinement operation to compute lower and upper bounds of the exact solution to the general CH-posynomial program. We apply the algorithm to solve the simultaneous transistor and interconnect sizing (STIS) problem under the table-based device model, and the global interconnect sizing and spacing (GISS) problem with consideration of the crosstalk capacitance. Experiment results show that our algorithm can handle many device and interconnect modeling issues in deep submicron designs and is very efficient.