A virtual 3-D multipole accelerated extractor for VLSI parasitic interconnect capacitance

ABSTRACT

A virtual 3-D extractor of the single dielectric is presented in this paper. In the indirect boundary integral equations, the plane charge distribution on the surface of conductors is replaced with mesh charge distribution, and we use the multipole-accelerated algorithm to further depress the computational complexity. Numerical results show that its computational complexity is about O(n), where n is the number of the discrete variables. Within the comparable accuracy, it runs several times faster than the Fastcap, which is a very advanced multipole-accelerated parasitic capacitance extractor now.

REFERENCES

• 1: 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]
• 2: K. Nabors and J. White, "Multipole accelerated capacitance extraction algorithm for 3-D structures with multiple dielectrics," IEEE Trans. CAS, Vol.39, No. 11, pp.946-954,Nov. 1992
• 3: K. Nabors and J. White, "Fastcap: A multipole accelerated 3-D capacitance extraction program," IEEE Trans. CAD ,Vol.10,No.11,pp.1447- 1459,Nov. 1991
• 4: Jason Cong , Lei He , Andrew B. Kahng , David Noice , Nagesh Shirali , Steve H.-C. Yen, Analysis and justification of a simple, practical 2 1/2-D capacitance extraction methodology, Proceedings of the 34th annual conference on Design automation, p.627-632, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266303]
• 5: E.Barke, "Line-to-Ground Capacitance Calculation for VLSI : A Comparison," IEEE Trans. Computer-Aided Design, Vol 7, No.2, pp.295- 298,1988
• 6: Zhen-qiu Ning and Patrick M. Dewilde, "SPIDER: Capacitance Modeling for VLSI Interconnections," IEEE Transactions On Computer- Aided Design, Vol. 7, No. 12, pp.1121-1228, December 1988
• 7: Zhen-qiu Ning, Patrick M. Dewilde and Fred L. Neerhoff "Capacitance Coefficients for VLSI Multilevel Metallization Lines," IEEE Transactions On Electron Devices, Vol.Ed-34, No.3, pp.646-649, March 1987
• 8: Z. Wang, Y. Yuan and Q. Wu, "A Paralled Multipole Accelerated 3-D Capacitance Simulator Based on an Improved Model," IEEE Trans. CAD, Vol. 15, No.12, pp1441-1450,1996
• 9: Sharad Kapur , Jinsong Zhao, A fast method of moments solver for efficient parameter extraction of MCMs, Proceedings of the 34th annual conference on Design automation, p.141-146, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266051]
• 10: Wayne W.-M. Dai, Chip parasitic extraction and signal integrity verification (extended abstract), Proceedings of the 34th annual conference on Design automation, p.717-719, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266351]
• 11: U.Choudhury and A.Sangiovanni-Vincentelli, "Automatic Generation of Analytical Models for Interconnect Capacitance," IEEE Trans. CAD, Vol. 14,No.4,pp.470-480, 1995
• 12: N.D.Arora, K.V.Raoe, R.Schumann and L.M.Richardson, "Modeling and Extraction of Interconnect Capacitance for Multilayer VLSI Circuits,"IEEE Trans. CAD, Vol. 15, No. 1, pp.58-67,1996
• 13: 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]

INDEX TERMS

Primary Classification:
  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)

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
  B.8 Performance and Reliability

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Algorithms, Design, Performance, Theory