Parallelism analyzers for parallel discrete event simulation

ABSTRACT

Discrete event simulation is usually time consuming. Recently, there has been a great deal of interest in using parallel computers to speed up the simulation process. Before the parallel simulation approach is applied, it is important to understand the inherent parallelism of simulation applications. A simple technique called critical path analysis was proposed to study paralllelism of simulation applications. This paper describes three critical path analysis algorithms based on different event-scheduling (process scheduling) policies. These algorithms are much simpler than a previous approach, where the events must be recorded in a trace and an extra pass is required to process the event trace. In our approach, the critical path analysis algorithms are integrated with the sequential simulation. At the end of the sequential simulation, the optimal parallel execution time is also computed. Livny proposed an algorithm similar to our approach (His, however, was designed for a specific language). Our algorithms can be integrated with sequential simulation programs written by users or be integrated with simulation languages. Another advantage of our algorithms over previous approaches is that ours can be used to study load balancing under different event-scheduling policies. Since our algorithms can be easily inserted in sequential simulation programs, critical path analysis can be applied to existing sequential programs without difficulty. The results can then be used to predict the performance of parallel simulation on similar applications. An example is given to show how useful information can be obtained from our algorithms.

REFERENCES

• 1: BAILEY, M., AND LIN, Y.-B. Synchronization strategies for logic-level simulation. To appear in Int. J. Comput. Simul., 1992.
• 2: Orna Berry, Performance evaluation of the time warp distributed simulation mechanism, University of Southern California, Los Angeles, CA, 1986
• 3: BERRY, O. Private communication. 1992.
• 4: BERRY, O., AND JEFFERSON, D. Critical path analysis of distributed simulation. In Proceed- ~ngs 1985 SCS Mult~conference on D~str~buted Szmulation (Jan. 1985), pp. 57-60.
• 5: CHANDY, K. M., AND MISRA, J. Distributed simulation: A case study in design and verification of distributed programs. 1EEE Trans. Softw. Eng. SE-5, 5 (Sept. 1979), 440-452.
• 6: FUJIMOTO, R.M. Lookahead in parallel discrete event simulation. In Proceedings International Conference on Parallel Processing, Vol. III, 1988, pp. 34-41.
• 7: Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990 [doi>10.1145/84537.84545]
• 8: Philip Heidelberger, Discrete event simulations and parallel processing: statistical properties, SIAM Journal on Scientific and Statistical Computing, v.9 n.6, p.1114-1132, November 1988 [doi>10.1137/0909077]
• 9: 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]
• 10: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 11: LIN, Y.-B., ANn LAZOWSKA, E.D. Optimality considerations for Time Warp parallel simulation. In Proceedings 1990 SCS Multzconference on D~strzbuted Simulation (Jan. 1990), pp. 29-34.
• 12: Yi-Bing Lin , Edward D. Lazowska, A time-division algorithm for parallel simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.1, p.73-83, Jan. 1991 [doi>10.1145/102810.214307]
• 13: LIN, Y.-B., AND LAZOWSKA, E.D. Effects of process scheduling in parallel smlulation. Int. J. Comput. Szmul., 2, i (1992).
• 14: LIN, Y.-B., AND MAK, V.K. On simulating a large-scale mobile radio system. Submitted for publication, 1992.
• 15: LIN, Y.-B., LAZOWSKA, E. D., ANn BAER, J.-L. Conservative parallel simulation for systems with no lookahead. In Proceedings 1990 SCS Multzconference on D~strzbuted S~mulat~on (Jan. 1990), pp. 144 149.
• 16: LrvNY, M A study of parallelism in distributed simulation. In Proceedzngs 1985 SCS Multtconference on Distrtbuted Simulation (Jan. 1985), pp. 94-98.
• 17: LUBACHEVSKY, B. Efficient distributed event-driven simulations of multiple-loop networks. Commun. ACM 21, 2 (March 1989).
• 18: NANDY, B., AND LOUCKS, W. M. An algorithm for partitioning and mapping conservative parallel simulation onto multicomputers. In Proceedtngs 6th Workshop on Parallel and Distributed Stmulatzon (Jan. 1992), pp. 139-146
• 19: NICOL, D. M. The cost of conservative synchronization in parallel discrete event simulations. Tech. Rep., Dept. of Computer Science, College of Wilham and Mary, 1989.
• 20: REIHER, P, FUJIMOTO, R., BELLENOT, S., AND JEFFERSON, D. Cancellation strategies in optimistic execution systems. In Proc. 1990 SCS Multiconference on Distributed Simulation (Jan. 1990), pp. 112-121.
• 21: SOKOL, L. M., MUTCHLER, P. A., AND WEISSMAN, J. B. The role of event granularity m parallel simulation design. In Proceedings 6th Workshop on Parallel and Distrzbuted Sirnulatton (Jan. 1992)~ pp. 178-185.
• 22: D. B. Wagner , E. D. Lazowska, Parallel simulation of queueing networks: limitations and potentials, Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.146-155, May 23-26, 1989, Oakland, California, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

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

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Discrete event; Parallel

General Terms:
Algorithms, Performance

Keywords:
discrete event simulation, event precedence graph, inherent parallelism parallel simulation