A STOCHASTIC ALGORITHM FOR HIGH-SPEED CAPACITANCE EXTRACTION IN INTEGRATED-CIRCUITS

We present the theory of a novel stochastic algorithm for high-speed capacitance extraction in complex integrated circuits. The algorithm is most closely related to a statistical procedure for solving Laplace's equation known as the floating random-walk method. Overall computational efficiency stems from various factors: suitability to rectilinear geometries, statistical-error cancellation, selective integration over Gaussian surfaces and direct capacitance-matrix evaluation. Our analysis begins with Laplace's equation for a scalable square domain, subject to arbitrary Dirichlet conditions. A boundary-integral solution is then found, from which are obtained integrals for electric potential and electric field at the domain center. An electrode-capacitance integral is next derived. This integral is expanded as an infinite sum, and probability rules that statistically evaluate the sum are deduced. These rules define the algorithm. Three sources of numerical error associated with the algorithm have been identified. They are series-truncation error, space-discretization error and statistical error. All these errors can be adequately controlled through proper adjustment of algorithm parameters.