Large-scale capacitance calculation

ABSTRACT

We describe a new method for accurate large-scale capacitance calculations. The algorithm uses an integral equation formulation, but with a new representation for charge distributions that decouples charge variation from conductor geometry. This separation significantly reduces the problem size compared to a traditional discretization, resulting in a large speed increase. The full capacitance matrix of typical interconnect problems with thousands of nets can be computed in a few hours.

REFERENCES

• 1: W. C. Chew. Waves and Fields in Inhomogeneous Media. IEEE Press, 1995.
• 2: L. Greengard and V. Rokhlin. A new version of the fast multipole method for the Laplace equation in three dimensions. Acta Numerica, 6:229-269, 1997.
• 3: Sharad Kapur , David E. Long, IES3: Efficient Electrostatic and Electromagnetic Simulation, IEEE Computational Science & Engineering, v.5 n.4, p.60-67, October 1998 [doi>10.1109/99.735896]
• 4: Y. L. Le Coz and R. B. Iverson. A stochastic algorithm for high speed capacitance extraction in integrated circuits. Solid State Elect., 35(7):1005-1012, July 1992.
• 5: K. Nabors and J. K. White. FastCap: A multipole accelerated 3-D capacitance extraction program. IEEE Trans. on CAD, 10(11):1447-1459, Nov. 1991.
• 6: J. R. Phillips and J. K. White. A precorrected-FFT method for electrostatic analysis of complicated 3-D structures. IEEE Trans. on CAD, 16(10):1059-1072, Oct. 1997.
• 7: 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]
• 8: Weiping Shi , Jianguo Liu , Naveen Kakani , Tiejun Yu, A fast hierarchical algorithm for 3-D capacitance extraction, Proceedings of the 35th annual conference on Design automation, p.212-217, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277101]

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
  B.8 Performance and Reliability

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

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