A Fast Quasi-Multiple Medium Algorithm for 3-D Interconnect Capacitance Calculation

摘要

In the deep-submicron VLSI circuits, fast and accurate computation of the parasitic interconnect capacitance is very significant for design of the circuits with high performance, and is becoming an important and difficult task in the numerical computation. In the extraction of the capacitance, the direct boundary element method (BEM) is used for solving the Laplacian's equation with mixed Dirichlet and Neumann boundary conditions. In the paper, the localization of the direct BEM is analyzed and a fast quasi-multiple medium (QMM) algorithm based on it is presented in detail. A primary analysis of the computational complexity for a simplified model problem is given and it is concluded with a nearly linear relationship of N, where N is the number of the boundary elements. Numerical results can match the theoretical analysis well.