Perils and pitfalls of parallel discrete-event simulation

ABSTRACT

The design of efficient parallel discrete-event simulation (PDES) models often appears to be a mysterious art practiced primarily by academic researchers who have been rigorously ordained in this task. This tutorial attempts to unravel some of the mysteries. It describes the process of generating an efficient parallel implementation of a discrete-event simulation (DES) model. Common pitfalls in the parallel execution of the models are described together with suggestions on their avoidance.

REFERENCES

• 1: Rajive L. Bagrodia, Language support for parallel discrete-event simulations, Proceedings of the 26th conference on Winter simulation, p.1324-1331, December 11-14, 1994, Orlando, Florida, United States
• 2: R. L. Bagrodia , Wen-Toh Liao, Maisie: A Language for the Design of Efficient Discrete-Event Simulations, IEEE Transactions on Software Engineering, v.20 n.4, p.225-238, April 1994 [doi>10.1109/32.277572]
• 3: Baezner, D., G. Lomow, and B. W. Unger. 1990. Sim++: The transition to distributed simulation. In Proc. 1990 SCS Multiconference on Distributed Simulation, 211-218.
• 4: Mary L. Bailey , Jack V. Briner, Jr. , Roger D. Chamberlain, Parallel logic simulation of VLSI systems, ACM Computing Surveys (CSUR), v.26 n.3, p.255-294, Sept. 1994 [doi>10.1145/185403.185424]
• 5: Jason Cong , Zheng Li , Rajive Bagrodia, Acyclic multi-way partitioning of Boolean networks, Proceedings of the 31st annual conference on Design automation, p.670-675, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196609]
• 6: Cota, B. A. and R. G. Sargent. 1989. Automatic lookahead computation for conservative distributed simulation. Technical Report CASE Center 8916, Simulation Research Group and CASE Center, Syracuse University, Syracuse, NY.
• 7: John B. Evans, Structures of discrete event simulation: an introduction to the engagement strategy, Halsted Press, New York, NY, 1988
• 8: Fujimoto, R. 1988. Lookahead in parallel discrete event simulation, lnt'l Conference on Parallel Processing.
• 9: 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]
• 10: A. Gerasoulis , T. Yang, On the Granularity and Clustering of Directed Acyclic Task Graphs, IEEE Transactions on Parallel and Distributed Systems, v.4 n.6, p.686-701, June 1993 [doi>10.1109/71.242154]
• 11: 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]
• 12: D. Jefferson , B. Beckman , F. Wieland , L. Blume , M. Diloreto, Time warp operating system, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.77-93, November 08-11, 1987, Austin, Texas, United States
• 13: Vikas Jha , Rajive L. Bagrodia, Transparent implementation of conservative algorithms in parallel simulation languages, Proceedings of the 25th conference on Winter simulation, p.677-686, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256814]
• 14: Vikas Jha , Rajive L. Bagrodia, A unified framework for conservative and optimistic distributed simulation, Proceedings of the eighth workshop on Parallel and distributed simulation, p.12-19, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 15: Vikas Jha , Rajive Bagrodia, A performance evaluation methodology for parallel simulation protocols, Proceedings of the tenth workshop on Parallel and distributed simulation, p.180-185, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 16: Ulana Legedza , William E. Weihl, Reducing synchronization overhead in parallel simulation, Proceedings of the tenth workshop on Parallel and distributed simulation, p.86-95, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 17: Yi-Bing Lin , Edward D. Lazowska, Understanding the limits of optimistic and conservative parallel simulation, 1990
• 18: Yi-Bing Lin , Bruno R. Preiss , Wayne M. Loucks , Edward D. Lazowska, Selecting the checkpoint interval in time warp simulation, Proceedings of the seventh workshop on Parallel and distributed simulation, p.3-10, May 16-19, 1993, San Diego, California, United States
• 19: Winston W. Liu , Ching-Chuan Chiang , Hsiao-Kuang Wu , Vikas Jha , Mario Gerla , Rajive L. Bagrodia, Parallel simulation environment for mobile wireless networks, Proceedings of the 28th conference on Winter simulation, p.605-612, December 08-11, 1996, Coronado, California, United States [doi>10.1145/256562.256766]
• 20: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 21: David M. Nicol, Parallel discrete-event simulation of FCFS stochastic queueing networks, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.124-137, July 19-21, 1988, New Haven, Connecticut, United States
• 22: David Nicol , Philip Heidelberger, On extending more parallelism to serial simulators, Proceedings of the tenth workshop on Parallel and distributed simulation, p.202-205, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 23: Avinash C. Palaniswamy , Philip A. Wilsey, An analytical comparison of periodic checkpointing and incremental state saving, Proceedings of the seventh workshop on Parallel and distributed simulation, p.127-134, May 16-19, 1993, San Diego, California, United States
• 24: Sundeep Prakash , Rajive Bagrodia, Parallel Simulation of Data Parallel Programs, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.239-253, August 10-12, 1995
• 25: Vivek Sarkar , John Hennessy, Compile-time partitioning and scheduling of parallel programs, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.17-26, June 25-27, 1986, Palo Alto, California, United States
• 26: Behrooz A. Shirazi , Krishna M. Kavi , Ali R. Hurson, Scheduling and Load Balancing in Parallel and Distributed Systems, IEEE Computer Society Press, Los Alamitos, CA, 1995
• 27: Steinman, J. 1991. SPEEDES: synchronous parallel environment for emulation and discrete event simulation, In Advances in Parallel and Distributed Simulation, 95-103. SCS Multiconference, Anaheim, CA.
• 28: West, J. and A. Mullamey. 1988. ModSim: a language for distributed simulation. In Proceedings of 1988 SCS Multiconference on Distributed Simulation, San Diego, CA, 155-159.
• 29: Linda F. Wilson , David M. Nicol, Experiments in automated load balancing, Proceedings of the tenth workshop on Parallel and distributed simulation, p.4-11, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 30: Paul Wonnacott , David Bruce, The APOSTLE simulation language: granularity control and performance data, Proceedings of the tenth workshop on Parallel and distributed simulation, p.114-123, May 22-24, 1996, Philadelphia, Pennsylvania, United States