J. Cong et L. He, Theory and algorithm of local-refinement-based optimization with application to device and interconnect sizing, IEEE COMP A, 18(4), 1999, pp. 406-420
Citations number
31
Categorie Soggetti
Eletrical & Eletronics Engineeing
Journal title
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
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.