An efficient quasi-multiple medium algorithm fo the capacitance extraction of actual 3-D VLSI interconnects

ABSTRACT

In this paper, the quasi-multiple medium (QMM) method based on the direct boundary element method (BEM) is used to extract the capacitance of three-dimensional (3-D) VLSI interconnects with multiple dielectrics. Each dielectric in 3-D VLSI parasitic capacitor is cut into several fictitious mediums, so it produces much fewer non-zero entries to the total coefficients matrix. As a result, the QMM algorithm can greatly reduce the CPU time and memory space used in the capacitance extraction. To characterize the efficiency of QMM algorithm, we discuss accuracy, storage and timing statistics in comparison with the analogous information from non-QMM algorithm.

REFERENCES

• 1: [1] K. Nabors and J. White, "Multipole-Accelerated capacitance extraction algorithms for 3-D structures with multiple dielectrics," IEEE Trans. Circuits Syst., Vol. 39, pp. 946-954, Nov. 1992.
• 2: [2] Zeyi Wang, Yanhong Yuan and Qiming Wu, "A parallel multipole accelerated 3-D capacitance simulator based on an improved model," IEEE Trans. on CAD, Vol. 15, pp. 1441-1450, 1996.
• 3: [3] S. Fukuda, N. Shigyo, K. Kato and S. Nakamura, "A ULSI 2-D capacitance simulator for complex structures based on actual processes," IEEE Trans. on CAD, Vol. 9, pp. 39-47, 1990.
• 4: [4] H.M. Hou, C. S. Sheen and C. Y. Wu, "A novel modeling technique for efficiently computing 3-D capacitances of VLSI multilevel interconnections-BFEM," IEEE Trans. Electron Devices, Vol. 45, pp. 200-205, 1998.
• 5: [5] K.K. Mei, R. Pous, Z. Q. Chen, Y. W. Liu, and M. Prouty, "Measured equation of invariance: A new concept in field computation," IEEE Trans. Antennas Propagat., vol. 42, pp. 320-328, Mar. 1994.
• 6: [6] T. Chou and Z. J. Cendes, "Capacitance calculation of IC packages using the finite element method and planes of symmetry," IEEE Trans. Computer Aided Design, Vol. 13, pp. 1159-1166, Sept. 1994.
• 7: [7] W. Sun, W. W. M. Dai and W. Hong, "Fast parameter extraction of general interconnects using geometry independent measured equation of invariance," IEEE Trans. Microwave Theory Tech., Vol. 45, pp. 827-836, May 1997.
• 8: [8] J. Hou, Z. Wang and X. Hong, "The hierarchical h-adaptive 3-D boundary element computation of VLSI interconnect capacitance," in Proc. ASP-DAC'99, Hong Kong, Jan. 1999, pp. 93-96.
• 9: Jiangchun Gu , Zeyi Wang , Xianlong Hong, Hierarchical computation of 3-D interconnect capacitance using direct boundary element method, Proceedings of the 2000 conference on Asia South Pacific design automation, p.447-452, January 2000, Yokohama, Japan [doi>10.1145/368434.368741]
• 10: [10] M. Bachtold, M. Emmenegger, J. G. Korvink and H. Baltes, "An error indicator and automatic adaptive meshing for electrostatic boundary element simulations," IEEE Trans. on CAD, Vol. 16, No. 12, pp. 1439-1446, 1997.
• 11: [11] J.H. Kane, Boundary Element Analysis in Engineering Continuum Mechanics, Prentice Hall, 1994.
• 12: [12] C.A. Brebbia, The Boundary Element Method for Engineers, London: Pentech Press, 1978.
• 13: [13] Jialin Zhu, The Boundary Element Analysis for the Elliptical Boundary Value Problems, Science Press, 1991 (in Chinese).
• 14: [14] Zeyi Wang and Wenjian Yu, "A fast quasi-multiple medium algorithm for 3-D interconnect capacitance calculation," in Proc. IFIP 16th World Computer Congress 2000, Beijing, China. Aug. 2000, pp. 223-230.
• 15: [15] Jiangchun Gu, Zeyi Wang and Xianlong Hong, "A fast boundary element mesh generation approach for multihole surface," Journal of Computer Aided Design and Computer Graphics, Vol. 12, No. 3, pp. 211-215, Mar. 2000 (in Chinese).

INDEX TERMS

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

Additional Classification:
  B. Hardware
  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)

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

General Terms:
Algorithms, Design, Performance, Theory