Distributed and parallel demand driven logic simulation

ABSTRACT

Based on the demand-driven approach, distributed and parallel simulation algorithms are proposed. Demand-driven simulation tries to minimize the number of component computations by performing only those required for the watched output requests. For a specific output value request, the input line values that are required are requested from the related component. The process continues until known system input signal values are requested. We present a distributed demand-driven algorithm with an infinite memory requirement (but still the memory required by each process is not greater than that of sequential demand-driven simulation), and a parallel demand-driven simulation with reduced memory requirement. In our algorithms, each component is assigned a logical process.

REFERENCES

• 1: n.E. Bryant, "Simulation on a Distributed System," Proc. of the 1st Intl. Conference on Distributed Computer Systems, Oct., 1979, pp. 544-552.
• 2: K.M. Chandy, and J. Misra, "DistributeCl Simulation: A Case Study in Design and Verification of distributed programs," IEEE Trans. on Software Eng., vol.SE-5, no.5, Sept. 1979, pp. 440-452.
• 3: K. M. Chandy , J. Misra, Asynchronous distributed simulation via a sequence of parallel computations, Communications of the ACM, v.24 n.4, p.198-206, April 1981 [doi>10.1145/358598.358613]
• 4: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 5: D.R. Jefferson, and H. Sowizral, "Fast Concurrent Simulation Using the Time Warp Mechanism," Distributed Simulation, Simulation Council Inc., La Jolla, Jan., 1985, pp. 63-69.
• 6: Fred J. Kaudel, A literature survey on distributed discrete event simulation, ACM SIGSIM Simulation Digest, v.18 n.2, p.11-21, June 1987 [doi>10.1145/29497.29499]
• 7: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 8: Daniel A. Reed , Allen D. Malony , Bradley McCredie, Parallel Discrete Event Simulation Using Shared Memory, IEEE Transactions on Software Engineering, v.14 n.4, p.541-553, April 1988 [doi>10.1109/32.4677]
• 9: S. P. Smith , M. R. Mercer , B. Brodk, Demand driven simulation: BACKSIM, Proceedings of the 24th ACM/IEEE conference on Design automation, p.181-187, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37915]
• 10: L. Soule , R. Blank, Statistics for parallelism and abstraction level in digital simulation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.588-591, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37980]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Performance