Theory and algorithm of local-refinement-based optimization with application to device and interconnect sizing

In this paper we formulate three classes of optimization problems: the simp le, monotonically constrained, and bounded Gong-He (CH)-programs. We reveal the dominance property under the local refinement (LR) operation for the s imple CH-program, as well as the general dominance property under the pseud o-LR operation for the monotonically constrained CH-program and the extende d-la operation for the bounded CH-program. These properties enable a very e fficient polynomial-time algorithm, using different types of LR operations to compute tight lower and upper bounds of the exact solution to any CH-pro gram, We show that the algorithm is capable of solving many ragout optimiza tion problems in deep submicron iterative circuit and/or high-performance m ultichip module (MCM) and printed circuit board (PCB) designs, In particula r, we apply the algorithm to the simultaneous transistor and interconnect s izing problem, and to the global interconnect sizing and spacing problem co nsidering the coupling capacitance for multiple nets, We use tables precomp uted from SPICE simulations and numerical capacitance extractions to model device delay and interconnect capacitance, so that our device and interconn ect models are much more accurate than many used in previous interconnect o ptimization algorithms. Experiments show that the bound-computation algorit hm can efficiently handle such complex models, and obtain solutions close t o the global optimum in most cases. We believe that the CH-program formulat ions and the bound-computation algorithm can also be applied to other optim ization problems in the computer-aided design field.