Boundary element method macromodels for 2-D hierachical capacitance extraction

ABSTRACT

We presen t a new algorithm for computing the capacitance of three-dimensional perfect electrical conductors of complex structures. The new algorithm is significantly faster and uses muc h less memory than previous best algorithms, and is kernel independent. The new algorithm is based on a hierarchical algorithm for the n-body problem, and is an acceleration of the boundary-element method for solving the integral equation associated with the capacitance extraction problem. The algorithm first adaptively subdivides the conductor surfaces into panels according to an estimation of the potential coefficients and a user-supplied error band. The algorithm stores the poten tial coefficient matrix in a hierarchical data structure of size O(n), although the matrix is size n2 if expanded explicitly, wheren is the n umber of panels. The hierarchical data structure allows us to multiply the coefficient matrix with an y vector in O(n) time. Finally, w e use a generalized minimal residual algorithm to solve m linear systems each of size n × n in O(mn) time, where m is the n umber of conductors. The new algorithm is implemented and the performance is compared with previous best algorithms. F or the k × k bus example, our algorithm is 100 to 40 times faster than F astCap, and uses 1/100 to 1/60 of the memory used by F astCap. The results computed by the new algorithm are within 2.7% from that computed by FastCap.

REFERENCES

• 1: Anand, M.B. et aI. "Fully Integrated Back End of the Line Interconnect Process;' 1994VLSIMultilevellnterconnect Conference, June 7-8, 1994, IEEE 1994 pp. 15-21
• 2: Brebbia, C.A; Telles, J.C.F; Wrobel, L.C. Boundury Element Techniques, Springer-Verlag, Berlin, Heidelberg, 1984
• 3: Dengi, E.A.; "A Parasitic Capacitance Extraction Method for VLSI Interconnect Modeling", PhD Thesis, Carnegie Mellon University, March 1997
• 4: E. Aykut Dengi , Ronald A. Rohrer, Hierarchical 2-D field solution for capacitance extraction for VLSI interconnect modeling, Proceedings of the 34th annual conference on Design automation, p.127-132, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266048]
• 5: Fukuda, S; Shigyo, N; Kato, K; Nakamura, S. "A ULSI 2-D Capacitance Simulator for Complex Structures Based on Actual Processes," IEEE Trans. Computer-Aided Design, TCAD-9 no. 1, pp.39-47, Jan. 1990
• 6: L. J. Gray , E. Lutz, On the treatment of corners in the boundary element method, Journal of Computational and Applied Mathematics, v.32 n.3, p.369-386, Nov. 27, 1990 [doi>10.1016/0377-0427(90)90043-Y]
• 7: J. H. Kane , S. Saigal, An arbitrary condensing, noncondensing solution strategy for large scale, multi-zone boundary element analysis, Computer Methods in Applied Mechanics and Engineering, v.79 n.2, p.219-244, March 1990 [doi>10.1016/0045-7825(90)90133-7]
• 8: Patterson, C; Sheikh, M.A. "Interelement continuity in the boundary element method," in Topics in Boundury Element Research, Vol. I, C.A. Brebbia (ed.), Springer-Verlag, Berlin, 1984
• 9: Ruehli, A.E; Brennan, PA. "Efficient Capacitance Calculations for Three Dimensional Multiconductor Systems,'}rEEE Trans. MicrowaveTheoryTech. MTr-21, pp. 76-82, 1973
• 10: W. L. Wendland , D. Yu, Adaptive boundary element methods for strongly elliptic integral equations, Numerische Mathematik, v.53 n.5, p.539-558, August 1988 [doi>10.1007/BF01397551]
• 11: ~an, G; Lin, F. "Treatment of corner node problems and its singularity," Engineering Analysis with Boundary Elements Vol.13, pp.75-81,1994

INDEX TERMS

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

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)

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

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

General Terms:
Design, Measurement, Performance, Theory

Keywords:
emulation, functional simulation, reconstruction, visibility