Stable and compact inductance modeling of 3-D interconnect structures

ABSTRACT

Recent successful techniques for the efficient simulation of largescale interconnect models rely on the sparsification of the inverse of the inductance matrix L. While there are several techniques for sparsifying L^-1, the stability of these approximations for general interconnect structures has not been established, i.e., the sparsified reluctance and inductance matrices are not guaranteed to be positive-definite. In this paper, we present a novel technique for reluctance sparsification for general interconnect structures that enjoys several advantages: First, the resulting sparse approximation is guaranteed to be positive definite. Second, the approximation is optimal, in a certain well-defined sense. Third, owing to its computational efficiency and numerical stability, the algorithm is applicable for very large problem sizes. Finally our approach yields a compact representation of both inductance and reluctance matrices for general cases.

REFERENCES

• 1: Michael W. Beattie , Lawrence T. Pileggi, Modeling magnetic coupling for on-chip interconnect, Proceedings of the 38th conference on Design automation, p.335-340, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378504]
• 2: Tsung-Hao Chen , Clement Luk , Hyungsuk Kim , Charlie Chung-Ping Chen, INDUCTWISE: inductance-wise interconnect simulator and extractor, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.215-220, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774604]
• 3: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 4: Anirudh Devgan , Hao Ji , Wayne Dai, How to efficiently capture on-chip inductance effects: introducing a new circuit element K, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 5: Hao Ji , Anirudh Devgan , Wayne Dai, KSim: a stable and efficient RKC simulator for capturing on-chip inductance effect, Proceedings of the 2001 conference on Asia South Pacific design automation, p.379-384, January 2001, Yokohama, Japan [doi>10.1145/370155.370415]
• 6: H. Li, V. Balakrishnan, and C.-K. Koh. http://web.ics.purdue.edu/~li73/report1.pdf.
• 7: Hong Li , Venkataramanan Balakrishnan , Cheng-Kok Koh , Guoan Zhong, Compact and stable modeling of partial inductance and reluctance matrices, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120923]
• 8: Tao Lin , Michael W. Beattie , Lawrence T. Pileggi, On the efficacy of simplified 2D on-chip inductance models, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514108]
• 9: P. Rozsa. On the inverse of band matrices. Integral Equations and Operator Theory, 10:82--95, 1987.
• 10: A. E. Ruehli. Equivalent circuit models for three dimensional multiconductor systems. In IEEE Trans. on Microwave Theory and Techniques, pages 216--221, 1974.
• 11: G. Strang. Linear Algebra and its Applications. Thomson Learning, 1986.
• 12: G. Zhong, C.-K. Koh, and K. Roy. On-chip interconnect modeling by wire duplication. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22:1521--1532, 2003.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Design, Performance