A combined waveform relaxation: waveform relaxation newton algorithm for efficient parallel circuit simulation

ABSTRACT

This paper presents two new techniques for accelerating circuit simulation. The first technique is an improvement of the parallel Waveform Relaxation Newton (WRN) method. The computations of all the timepoints are executed concurrently. Static task partitioning is shown to be an efficient method to limit the scheduling overhead. The second technique combines in a dynamic way the efficiency of the parallel version of the Waveform Relaxation (WR) method and the parallelism of the new developed parallel WRN algorithm.

REFERENCES

• 1: D. Dumlugol, P. Odent, J. Cockx, H. De Man, "Switch-Electrical Segmented Waveform Relaxation for Digital MOS VLSI and its Acceleration on Parallel Computers", IEEE Transactions on Computer-Aided Design, Vol. CAD-6, no. 6, pp. 992--1005, Nov. 1987.
• 2: H. Y. Hsieh, A. Ruehli, P. Ledak, "Progress on Toggle: A Waveform Relaxation VLSI-MOSFET CAD Program", Proceedings of the Int. Symp. on Circuits And Systems, Kyoto, Japan, pp. 213--216.
• 3: E. Lelarasmee, A. E. Ruehli, A. L. Sangionanni-Vincentelli, "The Waveform Relaxation Method for Time Domain Analysis of Large Scale Integrated Circuits", IEEE Transactions on Computer Aided Design of IC, Vol. CAD-1, No. 3, July 1982, pp. 131--145.
• 4: S. Mattison, "CONCISE a Concurrent Circuit Simulation Program", PhD thesis, Department of Applied Electronics, Lund Institude of Technology, Lund, 1986.
• 5: L. N. Nagel, "SPICE2: A Computer Program to Simulate Semiconductor Circuits", University of California, Berkeley, Electronics Research Laboratory, Memorandum No. ERL-M520, May 1975.
• 6: A. Osterhaug, "Guide to parallel programming", Sequent Technical Publications, Beaverton, Oregon, 1985.
• 7: P. Odent, L. Claesen, H. De Man, "New parallel techniques for simulating MOS circuits with waveform relaxation algorithms in CSWAN", Proc. Int. Sym. on Circuit And Systems 1989. Portland, May 1989, pp. 1166--1169.
• 8: P. Odent , L. Claesen , H. De Man, Feedback loops and large subcircuits in the multiprocessor implementation of a relaxation based circuit simulator, Proceedings of the 26th ACM/IEEE conference on Design automation, p.25-30, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74388]
• 9: W. T. Weeks, A. J. Jimenez, G. W. Mahoney. D. Mehta, H. Quasemzadeh and T. R. Scott, "Algorithms for ASTAP - A Network Analysis Program", IEEE Transactions on Circuit Theory, Vol. CT-20, Nov. 1973, pp. 628--634.
• 10: R. A. Saleh, D. Webber, E. Xia, A. Sangiovanni-Vincentelli, "Parallel Waveform-Newton algorithms for circuit simulation", Proc. of the Int. Conf. on Computer Design, Rye Brook, New York, 1987, pp. 660--663.
• 11: J. White, R. Saleh, A. Sangiovanni-Vincentelli, A. R. Newton, "Accelerating Relaxation Algorithms for Circuit Simulation Using Waveform Newton, lterative Step Size Refinement, and Parallel Techniques", Digest of Technical Papers of the International Conference on Computer Aided Design, Santa Clara, CA, Nov. 1985, pp. 5--7.
• 12: J. White, A. L. Sangiovanni-Vincentelli, "Partitioning Algorithms and Parallel implementation of Waveform Relaxation Algorithms for Circuit Simulation", IEEE Proceedings of the International Symposium on Circuits and Systems, Kyoto, Japan, June 1985, pp. 221--224.
• 13: Jacob K. White , Alberto Sangiovanni-Vincentelli, Relaxation techniques for the simulation of VLSI circuits, Kluwer Academic Publishers, Norwell, MA, 1987