Multilevel optimization of high speed VLSI interconnect networks by decomposition

A multilevel optimization technique is developed for large-scale and hierarchical optimization of high-speed VLSI interconnects modeled by distributed transmission lines. Mathematical programming decomposition is combined with network tearing where the overall network is optimized by a set of parallel suboptimizations. The technique takes advantage of VLSI interconnects in the hierarchy of IC, multichip modules (MCM) and printed circuit board (PCB), and is faster than standard optimization. The convergence property of the technique is derived through Gauss-Seidel relaxation analysis and optimality conditions for the multiple suboptimizations