Performance bounds on parallel self-initiating discrete-event simulations

ABSTRACT

This paper considers the use of massively parallel architectures to execute discrete-event simulations of what we term “self-initiating” models. A logical process in a self-initiating model schedules its own state reevaluation times, independently of any other logical process, and sends its new state to other logical processes following the reevaluation. Our interest is in the effects of that communication on synchronization. Using a model that idealizes the communication topology of a simulation, we consider the performance of various synchronization protocols by deriving upper and lower bounds on optimal performance, upper bounds on Time Warp's performance, and lower bounds on the performance of a new consevative protocol. Our analysis of Time Warp includes some of the overhead costs of state saving and rollback; the effects of propogating rollbacks are ignored. The analysis points out sufficient conditions for the conservitive protocol to outperform Time Warp. The analysis also quantifies the sensitivity of performance to message fanout, lookahead ability, and the probability distributions underlying the simulation.

REFERENCES

• 1: BUZZELL, C. A., FUJIMOTO, R. M., AND ROBB, M. J. Modular VME rollback hardware for Time Warp. In Distributed Simulation 1990, SCS Simulation Series, 1990, pp. 153-156.
• 2: BaEZN~R, D., ET AL. Algorithmic optimizations of simulations on Time Warp. In Dsstributed Simulation 1989, vol. 21, SCS Simulation Series, 1989, pp. 73-78.
• 3: WIELAND, F., ET AL. Distributed combat simulation and Time Warp: The model and its performance. In Distributed Simulation 1989, vol. 21, SCS Simulation Series, 1989, pp. 14-20.
• 4: HONTALAS, P., ET AL. Performance of the colliding pucks simulation on the Time Warp operating system. In Distributed Simulation 1989, vol. 21, SCS Simulation Series, 1989, pp. 3-7.
• 5: R. M. Fujimoto, Parallel discrete event simulation, Proceedings of the 21st conference on Winter simulation, p.19-28, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76741]
• 6: R. M. Fujimoto , J.-J. Tsai , G. Gopalakrishnan, Design and performance of special purpose hardware for time warp, Proceedings of the 15th Annual International Symposium on Computer architecture, p.401-409, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 7: 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]
• 8: LARSON, H. J., AND SHUBERT, B. O. Probabilistic Models in Engineering Sciences, vol. 1. John Wiley, New York, 1979.
• 9: Stephen S. Lavenberg , Richard R. Muntz , Behrokh Samadi, Performance Analysis of a Rollback Method for Distributed Simulation, Proceedings of the 9th International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.117-132, May 25-27, 1983
• 10: LIN, Y-B., BAZR, J-L., AND LAZOWSKA, E. D. Tailoring a parallel trace-driven simulation technique to specific multiprocessor cache coherence protocols. In Distributed Simulation 1989, vol. 21, SCS Simulation Series, 1989, pp. 185-190.
• 11: LIN, Y-B., AND LAZOWSKA, E. D. Optimality considerations for "Time Warp" parallel simulation. In Distributed Simulation 1990, vol. 22, SCS Simulation Series, 1990, pp. 29-34.
• 12: LmTON, R. J., AND MIZELL, D.W. Time Warp vs. Chandy-Misra: A worst-case comparison. In D~stributed Simulatmn 1990, vol. 22, SCS Simulation Series, 1990, pp. 137-143.
• 13: LUBACaEVSKY, B. D. Efficient parallel simulations of asynchronous cellular arrays. Complex Syst. I (1987), pp. 1099-1123
• 14: B. D. Lubachevsky, Efficient distributed event-driven simulations of multiple-loop networks, Communications of the ACM, v.32 n.1, p.111-123, Jan. 1989 [doi>10.1145/63238.63247]
• 15: LUBACHEVSKY, B.D. Scalability of the bounded lag distributed discrete-event simulation. In Distributed Simulation 1989, SCS Simulation Series, 1989, pp. 100-107.
• 16: MADASETTI, V., WALRAND, J., AND MESSERSCHMITT, D. Synchronization in message-passing computers: Models, algorithms, and analysis. In Distributed Simulation 1990, vol. 22, SCS Simulation Series 1990, pp. 35-48.
• 17: MERIFmLD, B. C., RICHARDSON, S. B., AND ROBERTS, J. B.G. Quantative studies of discrete event simulation modeling of road traffic. In D~stributed Simulation 1990, vol. 22, SCS Simulation Series 1990, pp. 188-193.
• 18: Debasis Mitra , Isi Mitrani, Analysis and Optimum Performance of Two Message-Passing Parallel Processors Synchronized by Rollback, Proceedings of the Tenth International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.35-50, December 19-21, 1984
• 19: David M. Nicol, Parallel discrete-event simulation of FCFS stochastic queueing networks, ACM SIGPLAN Notices, v.23 n.9, p.124-137, Sept. 1988
• 20: NICOL, D M. The cost of conservative synchronization in parallel discrete~event simulations. Tech. Rep. 90-20, ICASE, 1990. Available from ICASE, Mail Stop 132C, NASA Langley Research Center, Hampton, VA 23665.
• 21: D. M. Nicol , C. C. Michael , P. Inouye, Efficient aggregation of multiple PLs in distributed memory parallel simulations, Proceedings of the 21st conference on Winter simulation, p.680-685, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76825]
• 22: 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]
• 23: REIHER, P. L., FUJIMOTO, R., BELLENOT, S.~ AND JEFFERSON, D. Cancellation strategies in optimistic execution systems. In Distributed Simulation 1990, SCS Series, 1990, pp. 112-121.
• 24: Ross, H.S. Stochastic Processes. John Wiley, New York, 1983.
• 25: 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
      I.6.8 Types of Simulation
          Subjects: Parallel

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**
  C.2 COMPUTER-COMMUNICATION NETWORKS
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques; Performance attributes

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

General Terms:
Algorithms, Performance

Keywords:
parallel simulation, synchronization protocol