Abstract
This tutorial surveys various approaches to executing discrete event simulation programs on a parallel computer. The tutorial is focused on asynchronous simulation programs where different processes may advance asynchronously in simulated time. Parallelization of discrete event simulation programs requires adequate synchronization scheme. We review several synchronization schemes that have appeared in the literature in recent years. The performance result of these schemes will be surveyed and some application areas will be discussed.
Chapter PDF
References
M. Abrams. The object library for parallel simulation (olps). In 1988 Winter Simulation Conference Proceedings, pages 210–219, December 1988.
H. Ahmed, L. Barriga, and R. Ayani. Parallel discrete event simulation using space-time events. Submitted for publication.
I. F. Akyildiz, L. Chen, S. Das, R. M. Fujimoto, and R. F. Serfozo. Performance analysis of “time warp” with limited memory. Technical Report TR-GIT-91-46, College of Computing, Georgia Institute of Technology, Atlanta, GA, October 1991.
I. F. Akyildiz, L. Chen, S. R. Das, R. M. Fujimoto, and R. Serfozo. Performance analysis of time warp with limited memory. In Proceedings of the 1992 ACM SIGMETRICS Conference on Measuring and Modeling Computer Systems, volume 20, pages 213–224, May 1992.
K. Arvind and C. Smart. Hierarchical parallel discrete event simulation in composite elsa. In 6th Workshop on Parallel and Distributed Simulation, volume 24, pages 147–158. SCS Simulation Series, January 1992.
R. Ayani. A parallel simulation scheme based on the distance between objects. In Proceedings of the SCS Multiconference on Distributed Simulation, volume 21, pages 113–118. SCS Simulation Series, March 1989.
R. Ayani and B. Berkman. Parallel discrete event simulation on simd computers. To appear in Journal of Parallel and Distributed Computing, 18, 1993.
R. Ayani and H. Rajaei. Event scheduling in window based parallel simulation schemes. In Proceedings of the Fourth IEEE Symposium on Parallel and Distributed Computing, Dec 1992.
R. Ayani and H. Rajaei. Parallel simulation based on conservative time windows: A performance study. To appear in Journal of Concurrency, 1993.
D. Baezner, G. Lomow, and B. Unger. Sim++: The transition to distributed simulation. In Distributed Simulation, volume 22, pages 211–218. SCS Simulation Series, January 1990.
R. Bagrodia and W.-T. Liao. Maisie: A language and optimizing environment for distributed simulation. In Distributed Simulation, volume 22, pages 205–210. SCS Simulation Series, January 1990.
B. Berkman and R. Ayani. Parallel simulation of multistage interconnection networks on a SIMD computer. In Advances in Parallel and Distributed Simulation, volume 23, pages 133–140. SCS Simulation Series, January 1991.
A. Boukerche and C. Tropper. A performance analysis of distributed simulation with clustered processes. In Advances in Parallel and Distributed Simulation, volume 23, pages 112–124. SCS Simulation Series, January 1991.
K. M. Chandy and J. Misra. Distributed simulation: A case study in design and verification of distributed programs. IEEE Transactions on Software Engineering, SE-5(5):440–452, Sept. 1979.
K. M. Chandy and J. Misra. Asynchronous distributed simulation via a sequence of parallel computations. Communications of the ACM, 24(4):198–205, April 1981.
K. M. Chandy and R. Sherman. Space, time, and simulation. In Proceedings of the SCS Multiconference on Distributed Simulation, volume 21, pages 53–57. SCS Simulation Series, March 1989.
M. Chung and Y. Chung. An experimental analysis of simulation clock advancement in parallel logic simulation on an SIMD machine. In Advances in Parallel and Distributed Simulation, volume 23, pages 125–132. CS Simulation Series, January 1991.
B. Cota and R. Sargent. A framework for automatic lookahead computation in conservative distributed simulations. In Distributed Simulation, volume 22, pages 56–59. SCS Simulation Series, January 1990.
R. W. Earnshaw and A. Hind. A parallel simulator for performance modelling of broadband telecommunication networks. In 1992 Winter Simulation Conference Proceedings, pages 1365–1373, December 1992.
R. Felderman and L. Kleinrock. Two processor Time Warp analysis: Some results on a unifying approach. In Advances in Parallel and Distributed Simulation, volume 23, pages 3–10. SCS Simulation Series, January 1991.
R. Fujimoto. Performance of Time Warp under synthethic workloads. In Distributed Simulation, volume 22, pages 23–28. SCS Simulation Series, January 1990.
R. M. Fujimoto. Performance measurements of distributed simulation strategies. Transactions of the Society for Computer Simulation, 6(2):89–132, April 1989.
R. M. Fujimoto. Time Warp on a shared memory multiprocessor. Transactions of the Society for Computer Simulation, 6(3):211–239, July 1989.
R. M. Fujimoto. Parallel discrete event simulation. Communications of the ACM, 33(10):30–53, October 1990.
P. Goli, P. Heidelberger, D. Towsley, and Q. Yu. Processor assignment and synchronization in parallel simulation of multistage interconnection networks. In Distributed Simulation, volume 22, pages 181–187. SCS Simulation Series, January 1990.
A. Gupta, I. F. Akyildiz, and R. M. Fujimoto. Performance analysis of Time Warp with multiple homogenous processors. IEEE Transactions on Software Engineering, 17(10):1013–1027, October 1991.
P. Heidelberger and D.M. Nicol. Simultaneous parallel simulations of continuous time markov chains at multiple parameter settings. In Proceedings of the 1991 Winter Simulation Conference, pages 602–607, 1991.
P. Heidelberger and H. S. Stone. Parallel trace-driven cache simulation by time partitioning. In Proceedings of the 1990 Winter Simulation Conference, pages 734–737, 1990.
D. R. Jefferson. Virtual time. ACM Transactions on Programming Languages and Systems, 7(3):404–425, July 1985.
D. R. Jefferson, B. Beckman, F. Wieland, L. Blume, M. DiLorento, P. Hontalas, P. Reiher, K. Sturdevant, J. Tupman, J. Wedel, and H. Younger. The Time Warp Operating System. 11th Symposium on Operating Systems Principles, 21(5):77–93, November 1987.
D. R. Jefferson and H. Sowizral. Fast concurrent simulation using the Time Warp mechanism, part I: Local control. Technical Report N-1906-AF, RAND Corporation, December 1982.
D. W. Jones. An empirical comparison of priority-queue and event-set implementations. Communications of the ACM, 29(4):300–311, Apr. 1986.
Y.-B. Lin and E. D. Lazowska. Exploiting lookahead in parallel simulation. IEEE Transactions on Parallel and Distributed Systems, 1(4):457–469, October 1990.
Y.-B. Lin and E. D. Lazowska. Optimality considerations of “Time Warp” parallel simulation. In Proceedings of the SCS Multiconference on Distributed Simulation, volume 22, pages 29–34. SCS Simulation Series, January 1990.
Y.-B. Lin and E. D. Lazowska. A study of Time Warp rollback mechanisms. ACM Transactions on Modeling and Computer Simulation, 1(1):51–72, January 1991.
W. M. Loucks and B. R. Preiss. The role of knowledge in distributed simulation. In Proceedings of the SCS Multiconference on Distributed Simulation, volume 22, pages 9–16. SCS Simulation Series, January 1990.
B. D. Lubachevsky. Bounded lag distributed discrete event simulation. In Proceedings of the SCS Multiconference on Distributed Simulation, volume 19, pages 183–191. SCS Simulation Series, July 1988.
B. D. Lubachevsky. Efficient distributed event-driven simulations of multiple-loop networks. Communications of the ACM, 32(1):111–123, Jan. 1989.
B. D. Lubachevsky, A. Shwartz, and A. Weiss. Rollback sometimes works ... if filtered. In 1989 Winter Simulation Conference Proceedings, pages 630–639, December 1989.
V. Madisetti, D. Hardaker, and R. Fujimoto. The mimdix operating system for parallel simulation. In 6th Workshop on Parallel and Distributed Simulation, volume 24, pages 65–74. SCS Simulation Series, January 1992.
V. Madisetti, J. Walrand, and D. Messerschmitt. Wolf: A rollback algorithm for optimistic distributed simulation systems. In 1988 Winter Simulation Conference Proceedings, pages 296–305, December 1988.
H. Mehl. Speedup of conservative distributed discrete-event simulation methods by speculative computing. In Advances in Parallel and Distributed Simulation, volume 23, pages 163–166. SCS Simulation Series, January 1991.
J. Misra. Distributed-discrete event simulation. ACM Computing Surveys, 18(1):39–65, March 1986.
D. Mitra and I. Mitrani. Analysis and optimum performance of two message passing parallel processors synchronized by rollback. In Performance '84, pages 35–50, Elsevier Science Pub., (North Holland), 1984.
D. Nicol, A. Greenberg, B. Lubachevsky, and S. Roy. Massively parallel algorithms for trace-driven cache simulation. In 6th Workshop on Parallel and Distributed Simulation, volume 24, pages 3–11. SCS Simulation Series, January 1992.
D. M. Nicol. Parallel discrete-event simulation of FCFS stochastic queueing networks. SIGPLAN Notices, 23(9):124–137, September 1988.
D. M. Nicol. Performance bounds on parallel self-initiating discrete-event simulations. ACM Transactions on Modeling and Computer Simulation, 1(1):24–50, January 1991.
J. K. Peacock, J. W. Wong, and E. G. Manning. Distributed simulation using a network of processors. Computer Networks, 3(1):44–56, February 1979.
B. R. Preiss. The Yaddes distributed discrete event simulation specification language and execution environments. In Proceedings of the SCS Multiconference on Distributed Simulation, volume 21, pages 139–144. SCS Simulation Series, March 1989.
H. Rajaei and R. Ayani. Language support for parallel simulation. In 6th Workshop on Parallel and Distributed Simulation, volume 24, pages 191–192. SCS Simulation Series, January 1992.
H. Rajaei and R. Ayani. Design issues in parallel simulation languages. To appear in IEEE Design and Test of Computers, Sep 1993.
H. Rajaei, R. Ayani, and L.-E. Thorelli. The local time warp approach to parallel simulation. In 7th Workshop on Parallel and Distributed Simulation, January 1993.
D. A. Reed, A. D. Malony, and B. D. McCredie. Parallel discrete event simulation using shared memory. IEEE Transactions on Software Engineering, 14(4):541–553, April 1988.
P. L. Reiher and D. Jefferson. Dynamic load management in the Time Warp Operating System. Transactions of the Society for Computer Simulation, 7(2):91–120, June 1990.
P. L. Reiher, F. Wieland, and D. R. Jefferson. Limitation of optimism in the Time Warp Operating System. In 1989 Winter Simulation Conference Proceedings, pages 765–770, December 1989.
R. Righter and J. C. Walrand. Distributed simulation of discrete event systems. Proceedings of the IEEE, 77(1):99–113, Jan. 1989.
R. Ronngren, R. Ayani, R. Fujimoto, and S. Das. Efficient implementation of event sets in time warp. In Workshop on Parallel and Distributed Simulation (PADS), volume 23, pages 101–108. SCS Simulation Series, May 1993.
R. Ronngren, J. Riboe, and R. Ayani. Fast implementation of the pending event set. In International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems. SCS Simulation Series, Jan 1993.
L. Sokol and B. Stucky. MTW: experimental results for a constrained optimistic scheduling paradigm. In Distributed Simulation, volume 22, pages 169–173. SCS Simulation Series, January 1990.
J. Steinman. Speedes:an approach to parallel simulation. In 6th Workshop on Parallel and Distributed Simulation, volume 24, pages 75–84. SCS Simulation Series, January 1992.
S. Turner and M. Xu. Performance evaluation of the bounded Time Warp algorithm. In 6th Workshop on Parallel and Distributed Simulation, volume 24, pages 117–128. SCS Simulation Series, January 1992.
D. B. Wagner and E. D. Lazowska. Parallel simulation of queueing networks: Limitations and potentials. In Proceedings of 1989 ACM SIGMETRICS and PERFORMANCE '89, volume 17, pages 146–155, May 1989.
D. B. Wagner, E. D. Lazowska, and B. N. Bershad. Techniques for efficient shared-memory parallel simulation. In Proceedings of the SCS Multiconference on Distributed Simulation, volume 21, pages 29–37. SCS Simulation Series, March 1989.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ayani, R. (1993). Parallel simulation. In: Donatiello, L., Nelson, R. (eds) Performance Evaluation of Computer and Communication Systems. Performance SIGMETRICS 1993 1993. Lecture Notes in Computer Science, vol 729. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0013847
Download citation
DOI: https://doi.org/10.1007/BFb0013847
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57297-8
Online ISBN: 978-3-540-48044-0
eBook Packages: Springer Book Archive