Scaling time warp-based discrete event execution to 104 processors on a Blue Gene supercomputer

ABSTRACT

Lately, important large-scale simulation applications, such as emergency/event planning and response, are emerging that are based on discrete event models. The applications are characterized by their scale (several millions of simulated entities), their fine-grained nature of computation (microseconds per event), and their highly dynamic inter-entity event interactions. The desired scale and speed together call for highly scalable parallel discrete event simulation (PDES) engines. However, few such parallel engines have been designed or tested on platforms with thousands of processors. Here an overview is given of a unique PDES engine that has been designed to support Time Warp-style optimistic parallel execution as well as a more generalized mixed, optimistic-conservative synchronization. The engine is designed to run on massively parallel architectures with minimal overheads. A performance study of the engine is presented, including the first results to date of PDES benchmarks demonstrating scalability to as many as 16,384 processors, on an IBM Blue Gene supercomputer. The results show, for the first time, the promise of effectively sustaining very large scale discrete event execution on up to 104 processors.

REFERENCES

• 1: 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]
• 2: K. M. Chandy and J. Misra, "Distributed Simulation: A Case Study in Design and Verification of Distributed Programs," IEEE Transactions on Software Engineering, vol. SE-5, pp. 440--452, 1978.
• 3: 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]
• 4: Hassan Rajaei , Rassul Ayani , Lars-Erik Thorelli, The local Time Warp approach to parallel simulation, Proceedings of the seventh workshop on Parallel and distributed simulation, p.119-126, May 16-19, 1993, San Diego, California, United States
• 5: Kalyan S. Perumalla, µsik " A Micro-Kernel for Parallel/Distributed Simulation Systems, Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, p.59-68, June 01-03, 2005 [doi>10.1109/PADS.2005.1]
• 6: 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
• 7: R. M. Fujimoto, K. S. Perumalla, A. Park, H. Wu, M. Ammar, and G. F. Riley, "Large-Scale Network Simulation -- How Big? How Fast?," in Modeling, Analysis and Simulation of Computer and Telecommunication Systems, 2003.
• 8: K. S. Perumalla, "Scalable and Flexible Parallel/Distributed Simulation Systems: A Micro-Kernel Approach," Oak Ridge National Laboratory, Technical Memorandum 2005/12/01 2005.
• 9: Gilbert Chen , Boleslaw K. Szymanski, DSIM: scaling time warp to 1,033 processors, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
• 10: K. S. Perumalla, R. M. Fujimoto, and H. Karimabadi, "Scalable Simulation of Electro-magnetic Hybrid Codes," in 6th International Conference on Computational Science, Reading, UK, 2006, pp. 41--49.
• 11: 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
• 12: Kalyan S. Perumalla, Parallel and distributed simulation: traditional techniques and recent advances, Proceedings of the 38th conference on Winter simulation, December 03-06, 2006, Monterey, California
• 13: David O. Rich , Randy E. Michelsen, An assessment of the ModSim/TWOS parallel simulation environment, Proceedings of the 23rd conference on Winter simulation, p.509-518, December 08-11, 1991, Phoenix, Arizona, United States
• 14: Samir Das , Richard Fujimoto , Kiran Panesar , Don Allison , Maria Hybinette, GTW: a time warp system for shared memory multiprocessors, Proceedings of the 26th conference on Winter simulation, p.1332-1339, December 11-14, 1994, Orlando, Florida, United States
• 15: B. Lubachevsky , A. Shwartz , A. Weiss, Rollback sometimes works...if filtered, Proceedings of the 21st conference on Winter simulation, p.630-639, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76819]
• 16: Kalyan S. Perumalla, A systems approach to scalable transportation network modeling, Proceedings of the 38th conference on Winter simulation, December 03-06, 2006, Monterey, California
• 17: K. S. Perumalla and B. Bhaduri, "On Accounting for the Interplay of Kinetic and Non-kinetic Aspects in Population Mobility Models," in European Modeling and Simulation Symposium, Spain, 2006.
• 18: Yarong Tang , Kalyan S. Perumalla , Richard M. Fujimoto , Homa Karimabadi , Jonathan Driscoll , Yuri Omelchenko, Optimistic Parallel Discrete Event Simulations of Physical Systems Using Reverse Computation, Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, p.26-35, June 01-03, 2005 [doi>10.1109/PADS.2005.16]
• 19: Yarong Tang , Kalyan S. Perumalla , Richard M. Fujimoto , Homa Karimabadi , Jonathan Driscoll , Yuri Omelchenko, Optimistic Simulations of Physical Systems Using Reverse Computation, Simulation, v.82 n.1, p.61-73, January 2006 [doi>10.1177/0037549706065481]
• 20: Collin J. Lobb , Zenas Chao , Richard M. Fujimoto , Steve M. Potter, Parallel Event-Driven Neural Network Simulations Using the Hodgkin-Huxley Neuron Model, Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, p.16-25, June 01-03, 2005 [doi>10.1109/PADS.2005.18]
• 21: Kalyan Perumalla , Richard Fujimoto, Virtual time synchronization over unreliable network transport, Proceedings of the fifteenth workshop on Parallel and distributed simulation, p.129-136, May 15-18, 2001, Lake Arrowhead, California, United States
• 22: Christopher D. Carothers , Kalyan S. Perumalla , Richard M. Fujimoto, Efficient optimistic parallel simulations using reverse computation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.9 n.3, p.224-253, July 1999 [doi>10.1145/347823.347828]
• 23: Garrett Yaun , Christopher D. Carothers , Shivkumar Kalyanaraman, Large-Scale TCP Models Using Optimistic Parallel Simulation, Proceedings of the seventeenth workshop on Parallel and distributed simulation, p.153, June 10-13, 2003
• 24: D. M. Davis, R. F. Lucas, P. Amburn, and T. D. Gottschalk, "Joint Experimentation on Scalable Parallel Processors," Journal of the International Test and Evaluation Association, vol. Summer 2005, 2005/05/01 2005.
• 25: 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
• 26: 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 ]
• 27: Rajive L. Bagrodia, Iterative design of efficient simulations using Maisie, Proceedings of the 23rd conference on Winter simulation, p.243-247, December 08-11, 1991, Phoenix, Arizona, United States
• 28: IBM, "Blue Gene Watson Consortium Days," F. Mintzer, Ed. Yorktown, NY, USA, 2006.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

General Terms:
Algorithms, Experimentation, Performance

Keywords:
mixed-mode simulation, parallel discrete event simulation, reverse computation, state saving, time warp