A fast method of moments solver for efficient parameter extraction of MCMs

ABSTRACT

The Method of Moments (MoM) is often effectively used inthe extraction of passive components in modeling integratedcircuits and MCM packaging. MoM extraction, however,involves solving a dense system of linear equations, and using direct factorization methods can be prohibitive for large problems. In this paper, we present a Fast Method of Moments Solver (FMMS) for the rapid solution of such linear systems. Our algorithm exploits the fact that the integral equation kernels are locally "smooth" and can be dramatically compressed via the singular value decomposition(SVD). This greatly speeds up the matrix-vector products ina Krylov-subspace iterative algorithm (e.g., GMRES). Wedemonstrate the efficiency and exibility of our scheme forthe modeling of embedded inductors in MCM-D. Results arepresented to show that the method isaccurate and can betwo orders of magnitude faster than Gaussian eliminationand one order of magnitude faster than standard iterative schemes.

REFERENCES

• 1: Germund Dahlquist , Ake Bjorck, Numerical Methods, Dover Publications, Incorporated, 2003
• 2: L. Greengard , V. Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics, v.73 n.2, p.325-348, December 1, 1987 [doi>10.1016/0021-9991(87)90140-9]
• 3: Roger F. Harrington, Field Computation by Moment Methods, Wiley-IEEE Press, 1993
• 4: M. Kamon, M.J. Tsuk, J. White. Fasthenry: A Multipole Accelerated 3-D Inductance Extraction Program. IEEE Transactions on Microwave theory and techniques., Vol 42(9):1750-1758, 1994.
• 5: Sharad Kapur, High-order quadratures for singular functions and their applications to the evaluation of Fourier and Hankel transforms, Yale University, New Haven, CT, 1996
• 6: K. Nabors , F. T. Korsmeyer , F. T. Leighton , J. White, Preconditioned, adaptive, multipole-accelerated iterative methods for three-dimensional first-kind integral equations of potential theory, SIAM Journal on Scientific Computing, v.15 n.3, p.713-735, May 1994 [doi>10.1137/0915046]
• 7: W. Press, S. Teukolsky, W. Vettering, B. Flannery Numerical Recipies in C. Cambridge University Press, 1992.
• 8: V. Rokhlin. Rapid solution of integral equations of classical potential theory. Journal of Computational Physics, 60(2):187-207, September, 1985.
• 9: Youcef Saad , Martin H Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, v.7 n.3, p.856-869, July 1986 [doi>10.1137/0907058]
• 10: J. Stoer and R. Bulirsch. Introduction to Numerical Analysis. Springer-Verlag, NY, NY, 1979.
• 11: E. Pettenpaul, et al., CAD models of lumped elements on GaAs up to 18 GHz, IEEE Transaction on Microwave Theory and Techniques, 36(2):294-304, Feb 1988.
• 12: Jinsong Zhao , Wayne Dai , Robert C. Frye , King L. Tai, S Parameter-Based Experimental Modeling of High Q MCM Inductor with Exponential Gradient Learning Algorithm, Proceedings of the 1997 Conference on IEEE Multi-Chip Module Conference, p.108, February 04-05, 1997
• 13: H. Heeb and Albert E. Ruehli, Three-dimensional interconnect analysis using partial element equivalent circuits, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 39(11):974-82, Nov 1992.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
      B.7.2 Design Aids
          Subjects: Simulation

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Measurement, Performance, Theory