Feedback loops and large subcircuits in the multiprocessor implementation of a relaxation based circuit simulator

ABSTRACT

This paper presents several new methods for the efficient parallel simulation of VLSI circuits that contain feedback loops or “difficult” parts such as arrays, registers and pass-transistor networks. A new parallel algorithm has been developed for the efficient simulation of circuits containing feedback loops. It is based on dataflow scheduling and local relaxation of the loops. For the simulation of large pass-transistor networks a partitioning method is used that is based on signal flow in the elements. Parallel element evaluation and time-segment pipelining are included to increase the performance of the parallel circuit simulator. Simulation tests with actual circuits show a substantial acceleration for the new methods.

REFERENCES

• 1: L.N. Nagel, "SPICE2: A Computer Prog~e~m to Simulate Semiconductor Circuits", University of Ca}Lifornia, Berkeley, Electronis Research Laboratory, Meraorandum No. EBL-M520, May 197~.
• 2: W.T. Weeks, A.J. Jimenez, G,W. Mahoney. D. Mehta, H. Quasemzadeh t~nd T.R. Scott,"Algorltluns for ASTAP - A Network Analysis Program", IEEE Trans. on Circuit Theory, Vol. CT-20, Nov. 1973, pp.628-634.
• 3: E. Lelarasmee, A. Rueldi, and A.L. Sangiovanni- Vincentclli~ "The waveform relaxation method for the tlme-doma~n analysis of large scale integ.Tated circuits," IEEE "l'~ans. Computer-Aic{ed Design of ISCAS, vol. CAD-l, no. 3, pp.131-145, Aug 1982.
• 4: D. Dumlugol, P. Odent, J. Cockx and H. De Man, "Switch-Electrical Segmented Waveform B.elaxation for Digital MOS VLSI and Its acceleration on Parallel Computers", IEEE Trans. Computer-Aided Design, vol. CAD- 6, no. 6, pp.992-1005, Nov 1987.
• 5: H.Y. Hsleh, A. 11uehli, P. Ledak, "Progress on Toggle: A Waveform Relaxation VLSI-MOSFET CAD Program", Proceedings of ISCAS 85, Kyoto, Japan, pp. 213-216.
• 6: 11. A. Saleh, J.E. Kleckner, A.11. Newton, "Iterated Timing Analysis and SPLICE1", ICCAD'83 Digest, Santa Clara, CA, 1983.
• 7: J. White, 1t. Saleh, A. Sangiovanni-Vincentelli, A. R. Newton, "Accelerating relaxation algorithms for circuit simulation using wavefo~m newton, iterative step si~e refinement, and parallel technlqucs", Int. Conf. on Computer-Aided Design, Santa Clara, California, November 1985, pp. 438-441.
• 8: P. Odent, D. Dunllugol, H. De Man, "Hardware Acceleration of Circuit Simulation on a Multi-microprocessor system", Int. Workshop on Hardware Accelerators, Univ. of" Oxford, 1987.
• 10: Anita Osterhaug, Guide to parallel programming on Sequent computer systems: 2nd edition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 11: A. E. Ruehli, Circuit analysis, simulation, and design: general aspects of circuit analysis and design, North-Holland Publishing Co., Amsterdam, The Netherlands, 1986
• 12: J. White, A. L. Sangiovanni, "Partitioning Algorithms and Parallel Implementations of Wave form Relaxation Algorithms for Circuit Simulation", IEEE Proc. Int. 8ymp. on Circuits and Systems, ISCAS, Kyoto, Japan, June 198S, pp.229-231.
• 13: R. Tarjan,"Depth-first search and linear graph algorithms", SIAM 3. Comput., roll, no. 2, June 1972.
• 14: N. P. Jouppi, "Derivation of Signal Flow Direction in MOS VLSI", IEEE Transactions on CAD, Vol. CAD-6, No 3, May 1987.
• 15: H. Yoshida, S. Kumagai, I. Shirakawa, "A Parallel Implementation of Large-Scale Circuit Simulation", Int. Workshop on Hardware Accelerators, Univ. of Oxford, 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)

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Design, Theory, Verification