Multilevel integral equation methods for the extraction of substrate coupling parameters in mixed-signal IC's

ABSTRACT

The extraction of substrate coupling resistances can be formulated as a first-kind integral equation, which requires only discretization of the two-dimensional contacts. However, the result is a dense matrix problem which is too expensive to store or to factor directly. Instead, we present a novel, multigrid iterative method which converges more rapidly than previously applied Krylov-subspace methods. At each level in the multigrid hierarchy, we avoid dense matrix-vector multiplication by using moment-matching approximations and a sparsification algorithm based on eigendecomposition. Results on realistic examples demonstrate that the combined approach is up to an order of magnitude faster than a Krylov-subspace method with sparsification, and orders of magnitude faster than not using sparsification at all.

REFERENCES

• 1: A. Brandt. Multi-level adaptive solutions to boundary-value problems. Mathematics of Computation, 31 (I 38):333-390, April 1977.
• 2: William L. Briggs , Van Emden Henson , Steve F. McCormick, A multigrid tutorial: second edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 3: Edoardo Charbon , Ranjit Gharpurey , Alberto Sangiovanni-Vincentelli , Robert S. Meyer, Semi-analytical techniques for substrate characterization in the design of mixed-signal ICs, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.455-462, November 10-14, 1996, San Jose, California, United States
• 4: João Paulo Costa , Mike Chou , L. Miguel Silveira, Efficient techniques for accurate extraction and modeling of substrate coupling in mixed-signal IC's, Proceedings of the conference on Design, automation and test in Europe, p.84-es, January 1999, Munich, Germany [doi>10.1145/307418.307531]
• 5: R. Gharpurey and R.G. Meyer. Modeling and analysis of substrate coupling in integrated circuits. InlEEE 1995 Custom Integrated Circuits Conference, pages 125-128, 1995.
• 6: Ranjit Gharpurey. ModelingandAnalysisofSubstrateCoupling in Integrated Circuits,PhD thesis, Department of Electrical Engineering and Computer Science, University of California at Berkeley, Berkeley, CA, June 1995.
• 7: Ranjit Gharpurey and Robert G. Meyer. Modeling and analysis of substrate coupling in integrated circuits.IEEE Journal Solid-StateCircuits, 31(3):344-353, March 1996.
• 8: L. Greengard. The Rapid Evaluation of Potential Fields in ParticleSystems. M.I.T. Press, Cambridge, Massachusetts, 1988.
• 9: W. Hackbusch. Multi-Grid Methods and Applications. Springer-Verlag, Berlin Heidelberg New York Tokyo, 1985.
• 10: Roger F. Harrington, Field Computation by Moment Methods, Krieger Publishing Co., Inc., Melbourne, FL, 1982
• 11: T. A. Johnson, R.W. Knepper, V. Marcellu, and W. Wang. Chip substrate resistance modeling technique for integrated circuit design. IEEE Transactions on Computer-Aided Design oflntegratedCircuits, CAD-3(2): 126-134, 1984.
• 12: R. Kress. Linear IntegralEquations. Springer-Verlag, 1989.
• 13: Sujoy Mitra, R. A. Rutenbar, L. R. Carley, and D. J. Allstot. A methodology for rapid estimation of substrate-coupled switching noise. In IEEE1995CustomlntegratedCircuits Conference, pages 129-132, 1995.
• 14: K. Nabors and J. White. Fastcap: A Multipole Accelerated 3-D Capacitance Extraction Program.IEEE Transactions on Computer-AidedDesign, pages 1447-1459, November 1991.
• 15: Bram Nauta and Gian Hoogzaad. How to deal with substrate noise in analogcmos circuits. In European Conference on Circuit Theory and Design, pages Late 12: 1-6, Budapest, Hungary, September 1997.
• 16: V. Rohklin. Rapid solution of integral equation of classical potential theory. J. Comput. Phys., 60:187-207, 1985.
• 17: 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]
• 18: A. H. Schatz, ~. Thom6e, and W. L. Wendland. Mathematical TheoryofFiniteandBoundaryElementMethods. Birkh~iuser Verlag, Basel/Boston/Berlin, 1990.
• 19: T. Smedes , N. P. van der Meijs , A. J. van Genderen, Extraction of circuit models for substrate cross-talk, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.199-206, November 05-09, 1995, San Jose, California, United States
• 20: B.R. Stanisic, N.K. Verghese, R.A. Rutenbar, L.R. Carley, and D.J. Allstot. Addressing substrate coupling in mixed-mode ic's: Simulation and power distribution synthesis.ZEEEJSSC, 29(3):226-238, March 1994.
• 21: J. Stoer and R. Bulirsch.lntroductiontoNumericalAnalysis. Spring,?-Verlag, second edition, 1993.
• 22: D.K. ~u, M.J. Loinaz, S. Masui, and B.A. Wooley. Experimental results and modeling techniques for substrate noise in mixed-signal integrated circuits. IEEEJSSC, 28(4):420430, April 1993.
• 23: Nishath Verghese. Extraction and Simulation Techniques for Substrate-Coupled Noise in Mixed-Signal Integrated Circuits. PhD thesis, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, August 1995.
• 24: Nishath K. Verghese, David J. Allstot, and Mark A. Wolfe. Verification techniques for substrate coupling and their application to mixed-s~gnal ic design. IEEE Journal Solid-State Circuits, 31 (3):354--365, March 1996.
• 25: Ivan L. Wemple , Andrew T. Yang, Mixed-signal switching noise analysis using Voronoi-tessellated substrate macromodels, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.439-444, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217567]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Multigrid and multilevel methods
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications

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

Keywords:
emulation, functional simulation, reconstruction, visibility