Final-value ODEs: stable numerical integration and its application to parallel circuit analysis

ABSTRACT

While solving initial-value ODEs is the de facto approach to time-domain circuit simulation, the opposite act, solving final-value ODEs, has been neglected for a long time. Stable numerical integration of initial-value ODEs involves significant complications; the application of standard integration methods simply leads to instability. We show that not only practically meaningful applications of final-value ODE problems exist, but also the inherent stability challenges may be addressed by recently proposed numerical methods. Furthermore, we demonstrate an elegant bi-directional parallel circuit simulation scheme, where one time-domain simulation task is sped up by simultaneously solving initial and final-value ODEs, one from each end of the time axis. The proposed approach has unique and favorable properties: the solutions of the two ODE problems are completely data independent with built-in automatic load balancing. As a specific application study, we demonstrate the proposed technique under the contexts of parallel digital timing simulation and the shooting-Newton based steady-state analysis.

References

1. L. W. Nagel. SPICE2: A Computer Program to Simulate Semiconductor Circuits. ERL-M520, University of California, Berkeley, CA, USA, 1975.
2. K. S. Kundert. The Designer's Guide to Spice and Spectre. Kluwer Academic Publishers, Massachusetts, USA, 1995.
3. E. Lelarasmee, A. E. Ruehli, and A. L. Sangiovanni-Vincentelli. The waveform relaxation method for time-domain analysis of large scale integrated circuits. TCAD, 1(3):131--145, July 1982.
4. M. W. Reichelt, A. Lumsdaine, and J. K. White. Accerlerated waveform methods for parallel transient simulation of semiconductor devices. In IEEE/ACM ICCAD, pages 270--274. IEEE/ACM, November 1993.
5. A. Devgan and R. A. Rohrer. Adaptively controlled explicit simulation. TCAD, 13(6):746--762, June 1994.
6. U. Wever and Q. Zheng. Parallel transient analysis for circuit simulation. In HICSS, pages 442--447. IEEE, January 1996.
7. R. Griffith and M. Nakhla. A new high-order absolutely-stable explicit numerical integration algorithm for the time-domain simulation of nonlinear circuits. In IEEE/ACM ICCAD, pages 276--280, 1997.
8. W. Dong, P. Li, and X. Ye. Wavepipe: parallel transient simulation of analog and digital circuits on multi-core shared-memory machines. In IEEE/ACM DAC, pages 238--243, 2008.
9. X. Ye, W. Dong, P. Li, and S. Nassif. Maps: Multi-algorithm parallel circuit simulation. In IEEE/ACM ICCAD, pages 73--78, 2008.
10. H. Peng and C. K. Cheng. Parallel transistor level circuit simulation using domain decomposition methods. In ASP-DAC, pages 397--402, 2009.
11. W. Dong and P. Li. Parallelizable stable explicit numerical integration for efficient circuit simulation. In IEEE/ACM DAC, pages 382--385, 2009.
12. W. Dong, P. Li, and G. Huang. Sram dynamic stability: theory, variability and analysis. In IEEE/ACM ICCAD, pages 378--385, 2008.
13. F. Colon and T. N. Trick. Fast periodic steady-state analysis for large-signal electronic circuits. JSSC, sc-8(4):260--269, August 1973.
14. R. Telichevesky, K. Kundert, I. Elfadel, and J. White. Fast simulation algorithms for rf circuits. In CICC, pages 437--444, May 1996.
15. C. W. Gear and I. G. Kevrekidis. Telescopic projective methods for parabolic differential equations. J. Comput. Phys., 187(1):95--109, 2003.
16. C. W. Gear and I. G. Kevrekidis. Computing in the past with forward integration. Physics Letter A, 321:335--343, 2004.
17. C. W. Gear. Numerical Initial Value Problems in Ordinary Differential Equations. Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1971.
18. C. W. Gear and I. G. Kevrekidis. Projective methods for stiff differential equations: Problems with gaps in their eigenvalue spectrum. SIAM J. Sci. Comput., 24(4):1091--1106, 2002.
19. T. J. Aprille and T. N. Trick. Steady-state analysis of nonlinear circuits with periodic inputs. Proceedings of The IEEE, 60(1):108--114, January 1972.

Index Terms

• Hardware

  • Hardware validation

    • Functional verification

      • Simulation and emulation