A quasi-newton preconditioned Newton-Krylov method for robust and efficient time-domain simulation of integrated circuits with strong parasitic couplings

ABSTRACT

In this paper, the Newton-Krylov method is explored for robust and efficient time-domain VLSI circuit simulation. Different from the LU-factorization based direct method, the Newton-Krylov method uses a preconditioned Krylov-subspace iterative method for linear system solving. Our key contribution is to introduce an effective quasi-Newton preconditioning scheme for Krylov-subspace methods to reduce the number and cost of LU factorizations during time-domain circuit simulation. Experimental results on a collection of digital, analog and RF circuits have shown that the quasi-Newton preconditioned Krylov-subspace method is as robust and accurate as SPICE3. The proposed Newton-Krylov method is especially attractive for simulating circuits with a large amount of parasitic RLC elements for post-layout verification.

REFERENCES

• 1: E. Acar, F. Dartu, and L. T. Pileggi, "TETA: Transistor-level waveform evaluation for timing analysis", IEEE Trans. on Computer-Aided Design, vol. 21, no. 5, pp. 605--616, May 2002.
• 2: R. Burch, P. Yang, P. Cox, and K. Mayaram, "A new matrix solution technique for general circuit simulation", IEEE Trans. on Computer-Aided Design, vol. 12, no. 2, pp. 225--241, Feb. 1993.
• 3: Tsung-Hao Chen , Charlie Chung-Ping Chen, Efficient large-scale power grid analysis based on preconditioned krylov-subspace iterative methods, Proceedings of the 38th conference on Design automation, p.559-562, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379023]
• 4: P. F. Cox, R. G. Burch, P. Yang, and D. E. Hocevar, "New implicit integration method for efficient latency exploration in circuit simulation", IEEE Trans. on Computer-Aided Design, vol. 8, no. 10, pp. 1051--1064, Oct. 1989.
• 5: J. E. Dennis and J. J. Moré, "Quasi-Newton methods, motivation and theory", SIAM Review, vol. 19, no. 1, pp. 46--89, Jan. 1977.
• 6: T. Fujisawa, E. S. Kuh, and T. Ohtsuki, "A sparse matrix method for analysis of piecewise-linear resistive networks", IEEE Trans. on Circuit Theory, vol. CT-19, no. 6, pp. 571--584, Nov. 1972.
• 7: K. R. Jackson , R. Sacks-Davis, An Alternative Implementation of Variable Step-Size Multistep Formulas for Stiff ODEs, ACM Transactions on Mathematical Software (TOMS), v.6 n.3, p.295-318, Sept. 1980 [doi>10.1145/355900.355903]
• 8: Kevin J. Kerns , Ivan L. Wemple , Andrew T. Yang, Stable and efficient reduction of substrate model networks using congruence transforms, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.207-214, November 05-09, 1995, San Jose, California, United States
• 9: D. A. Knoll , D. E. Keyes, Jacobian-free Newton-Krylov methods: a survey of approaches and applications, Journal of Computational Physics, v.193 n.2, p.357-397, 20 January 2004 [doi>10.1016/j.jcp.2003.08.010]
• 10: Yu Min Lee , Charlie Chung Ping Chen, Power grid transient simulation in linear time based on transmission-line-modeling alternating-direction-implicit method, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 11: Zhao Li , C.-J. Richard Shi, SILCA: Fast-Yet-Accurate Time-Domain Simulation of VLSI Circuits with Strong Parasitic Coupling Effects, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.793, November 09-13, 2003 [doi>10.1109/ICCAD.2003.123]
• 12: L. W. Nagel, SPICE: A Computer Program to Simulate Semiconductor Circuits, University of California, Berkeley, Tech. Rep., UCB/ERL M520, May 1975.
• 13: A. Odabasioglu, M. Celik, and L. T. Pillegi, "PRIMA: Passive reduced-order interconnect macromodeling algorithm", IEEE Trans. on Computer-Aided Design, vol. 17, no. 8, pp. 645--654, Aug. 1998.
• 14: Joel R. Phillips , L. Miguel Silveira, Simulation approaches for strongly coupled interconnect systems, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 15: A. R. Newton and A. Sangiovanni-Vincentelli, "Relaxation-based electrical simulation", IEEE Trans. Computer-Aided Design, vol. 3, no. 4., pp. 308--331, 1984.
• 16: Youcef Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM Journal on Scientific Computing, v.14 n.2, p.461-469, March 1993 [doi>10.1137/0914028]
• 17: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 18: R. Telichevesky, K. Kundert, and J. White, "Fast simulation algorithms for RF circuits", Proc. IEEE Custom Integrated Circuit Conf, pp. 437--444, May 1996.
• 19: B. Wan, B. Hu, L. Zhou and C.-J. R. Shi, "MCAST: An abstract-syntax-tree based model compiler for circuit simulation", Proc. IEEE Custom Integrated Circuits Conf., pp. 249--252, San Jose, CA, Sept. 2003.
• 20: Jacob K. White , Alberto Sangiovanni-Vincentelli, Relaxation techniques for the simulation of VLSI circuits, Kluwer Academic Publishers, Norwell, MA, 1987

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Conditioning (and ill-conditioning); Numerical algorithms
        G.1.10 Applications

General Terms:
Algorithms, Design, Performance