Fast methods for extraction and sparsification of substrate coupling

ABSTRACT

The sudden increase in systems-on-a-chip designs has renewed interest in techniques for analyzing and eliminating substrate coupling problems. Previous work on the substrate coupling analysis has focused primarily on faster techniques for extracting coupling resistances, but has offered little help for reducing the resulting network whose number of resistors grows quadratically with the number of contacts. In this paper we show that an approach inspired by wavelets can be used in two ways. First, the wavelet method can be used to accurately sparsify the dense contact conductance matrix. In addition, we show that the method can be used to compute the sparse representation directly. Computational results are presented that show that for a problems with a few thousand contacts, the method can be almost ten times faster at constructing the matrix.

REFERENCES

• 1: D.K. Su, M. Loinaz, S. Masui, and B. Wooley, "Experimental results and modeling techniques for substrate noise in mixed-signal integrated circuits," IEEE Journal Solid-State Circuits, vol. 28, no. 4, pp. 420-430, April 1993.
• 2: F. J. R. Clement, E. Zysman, M. Kayal, and M. Declercq, "LAYIN: Toward a global solution for parasitic coupling modeling and visualization," in Proc. IEEE Custom Integrated Circuit Conference, May 1994, pp. 537-540.
• 3: Nishath K. Verghese , Timothy J. Schmerbeck , David J. Allstot, Simulation Techniques and Solutions for Mixed-Signal Coupling in Integrated Circuits, Kluwer Academic Publishers, Norwell, MA, 1995
• 4: 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
• 5: R. Gharpurey and R. Meyer, "Modeling and analysis of substrate coupling in integrated circuits," IEEE Journal Solid-State Circuits, vol. 31, no. 3, pp. 344-353, March 1996.
• 6: K. Nabors, S. Kim, and J. White, "Fast capacitance extraction of general three-dimensional structure," IEEE Trans. on Microwave Theory and Techniques, vol. 40, no. 7, pp. 1496-1507, July 1992.
• 7: J. R. Phillips and J. K. White, "A precorrected-FFT method for electrostatic analysis of complicated 3D structures," IEEE Trans. CAD, pp. 1059-1072, 1997.
• 8: Sharad Kapur , David E. Long, IES3: a fast integral equation solver for efficient 3-dimensional extraction, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.448-455, November 09-13, 1997, San Jose, California, United States
• 9: Johannes Tausch , Jacob White, A multiscale method for fast capacitance extraction, Proceedings of the 36th ACM/IEEE conference on Design automation, p.537-542, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309994]
• 10: Ranjit Gharpurey , Srinath Hosur, Transform domain techniques for efficient extraction of substrate parasitics, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.461-467, November 09-13, 1997, San Jose, California, United States
• 11: Mike Chuan Chou , Jacob K. White, Fast algorithms for ill-conditioned dense-matrix problems in vlsi interconnect and substrate modeling, 1998
• 12: J. P. Costa, M. Chou, and L. M. Silveira, "Precorrected-DCT techniques for modeling and simulation of substrate coupling in mixed-signal IC's," in Proc. IEEE International Symposium on Circuits and Systems, May 1998, vol. 6, pp. 358-362.
• 13: B. Alpert , G. Beylkin , R. Coifman , V. Rokhlin, Wavelet-like bases for the fast solutions of second-kind integral equations, SIAM Journal on Scientific Computing, v.14 n.1, p.159-184, Jan. 1993 [doi>10.1137/0914010]
• 14: P. Concus, G. H. Golub, and D. P. O'Leary, "A generalized conjugate gradient method for the numerical solution of elliptic PDE," in Sparse Matrix Computations, J. R. Bunch and D. J. Rose, Eds., pp. 309-332. Academic Press, New York, 1976.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Advanced technologies
  B.8 Performance and Reliability

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Finite difference methods
      G.1.8 Partial Differential Equations
          Subjects: Finite difference methods

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