Stochastic integral equation solver for efficient variation-aware interconnect extraction

ABSTRACT

In this paper we present an efficient algorithm for extracting the complete statistical distribution of the input impedance of interconnect structures in the presence of a large number of random geometrical variations. The main contribution in this paper is the development of a new algorithm, which combines both Neumann expansion and Hermite expansion, to accurately and efficiently solve stochastic linear system of equations. The second contribution is a new theorem to efficiently obtain the coefficients of the Hermite expansion while computing only low order integrals. We establish the accuracy of the proposed algorithm by solving stochastic linear systems resulting from the discretization of the stochastic volume integral equation and comparing our results to those obtained from other techniques available in the literature, such as Monte Carlo and stochastic finite element analysis. We further prove the computational efficiency of our algorithm by solving large problems that are not solvable using the current state of the art.

REFERENCES

• 1: Zhenhai Zhu , J. White , A. Demir, A stochastic integral equation method for modeling the rough surface effect on interconnect capacitance, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.887-891, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382699]
• 2: Hengliang Zhu , Xuan Zeng , Wei Cai , Jintao Xue , Dian Zhou, A sparse grid based spectral stochastic collocation method for variations-aware capacitance extraction of interconnects under nanometer process technology, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 3: T. Moselhy and L. Daniel, "Stochastic High Order Basis Functions for Volume Integral Equation with Surface Roughness," EPEP 2007.
• 4: Zhenhai Zhu , J. White, FastSies: a fast stochastic integral equation solver for modeling the rough surface effect, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.675-682, November 06-10, 2005, San Jose, CA
• 5: Dongbin Xiu , Jan S. Hesthaven, High-Order Collocation Methods for Differential Equations with Random Inputs, SIAM Journal on Scientific Computing, v.27 n.3, p.1118-1139, 2005 [doi>10.1137/040615201]
• 6: Roger G. Ghanem , Pol D. Spanos, Stochastic finite elements: a spectral approach, Springer-Verlag New York, Inc., New York, NY, 1991
• 7: M. Kamon, N. Marques and J. White "Generating compact guaranteed passive reduced-order models for 3-D RLC interconnects" IEEE Trans. on Advanced Packaging, Vol.27, Nov. 2004.
• 8: M. Loeve, Probability Theory, Spring-Verlag, 1977.
• 9: Dongbin Xiu , George Em Karniadakis, The Wiener--Askey Polynomial Chaos for Stochastic Differential Equations, SIAM Journal on Scientific Computing, v.24 n.2, p.619-644, 2002 [doi>10.1137/S1064827501387826]
• 10: T. Gerstner and M. Griebel, "Numerical Integration using Sparse Grids" Numerical Algorithms, 1998.
• 11: D. W. Bolton, "The Multinomial Theorem" The Mathematical Gazette, December 1968.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.9 Integral Equations

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design, Theory

Keywords:
Neumann expansion, polynomial chaos expansion, stochastic field solvers, surface roughness, variation-aware extraction