Optimistic simulation of parallel message-passing applications

ABSTRACT

Optimistic techniques can improve the performance of discrete-event simulations, but one area where optimistic simulators have been unable to show performance improvement is in the simulation of parallel programs. Unfortunately parallel program simulation using direct execution is difficult: the use of direct execution implies that the memory and computation requirements of the simulator are at least as large as that of the target application, which restricts the target systems and application problem sizes that can be studied. Memory usage is especially important for optimistic simulators due to the need for periodic state-saving and rollback. In our research we addressed this problem and have implemented a simulation library running a Time-Warp-based optimistic engine that uses direct execution to simulate and predict the performance of parallel MPI programs while attaining good simulation speedup. For programs with data sets too large to be directly executed with our optimistic simulator, we reduced the memory and computational needs of these programs by utilizing a static task graph and code-slicing methodology; an approach which also exhibited good performance speedup.

REFERENCES

• 1: Vikram S. Adve , Rajive Bagrodia , Ewa Deelman , Thomas Phan , Rizos Sakellariou, Compiler-supported simulation of highly scalable parallel applications, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.1-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331533]
• 2: Rajive Bagrodia , Richard Meyer , Mineo Takai , Yu-an Chen , Xiang Zeng , Jay Martin , Ha Yoon Song, Parsec: A Parallel Simulation Environment for Complex Systems, Computer, v.31 n.10, p.77-85, October 1998 [doi>10.1109/2.722293]
• 3: Rajive Bagrodia , Ewa Deeljman , Steven Docy , Thomas Phan, Performance prediction of large parallel applications using parallel simulations, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.151-162, May 04-06, 1999, Atlanta, Georgia, United States
• 4: D. Bailey, T. Harris, W. Shaphir, R. van der Winjngaart, A. Woo, and M. Yarrow. "The NAS Parallel Benchmarks 2.0," Report NAS-95-090, NASA Ames Research Center, 1995.
• 5: Sashikanth Chandrasekaran , Mark D. Hill, Optimistic simulation of parallel architectures using program executables, Proceedings of the tenth workshop on Parallel and distributed simulation, p.143-150, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 6: R. Covington, S. Dwarkadas, J. Jump, J. Sinclair, and S. Madala. "'The Efficient Simulation of Parallel Computer Systems," International Journal in Computer Simulation, vol. 1, 1991.
• 7: H. Davis, S. Goldschmidt, and J. Hennessy. "Multiprocessot Simulation and Tracing Using Tango," In Proceedings of the 1991 International Conference on Parallel Processing, August 1991.
• 8: Phillip M. Dickens , Philip Heidelberger , David M. Nicol, Parallelized Network Simulators for Message-Passing Parallel Programs, Proceedings of the 3rd International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.72-76, January 10-18, 1995
• 9: Phillip M. Dickens , Philip Heidelberger , David M. Nicol, Parallelized Direct Execution Simulation of Message-Passing Parallel Programs, IEEE Transactions on Parallel and Distributed Systems, v.7 n.10, p.1090-1105, October 1996 [doi>10.1109/71.539740]
• 10: Marios D. Dikaiakos , Anne Rogers , Kenneth Steiglitz, FAST: A Functional Algoritm Simulation Testbed, Proceedings of the Second International Workshop on Modeling, Analysis, and Simulation On Computer and Telecommunication Systems, p.142-146, January 31-February 02, 1994
• 11: M. Dikaiakos, A. Rogers, and K. Steiglitz. "Function Algorithm Simulation of the Fast Multipole Method: Architectural Implications," Parallel Processing Letters, 6( 1 ), March 1996.
• 12: 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]
• 13: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 14: James Laudon , Daniel Lenoski, The SGI Origin: a ccNUMA highly scalable server, Proceedings of the 24th annual international symposium on Computer architecture, p.241-251, June 01-04, 1997, Denver, Colorado, United States
• 15: U. Legedza, Reducing Synchronization Overhead in Parallel Simulation, Massachusetts Institute of Technology, Cambridge, MA, 1995
• 16: Jay M. Martin , Rajive L. Bagrodia, Compose: an object-oriented environment for parallel discrete-event simulations, Proceedings of the 27th conference on Winter simulation, p.763-767, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224727]
• 17: "Message-Passing Interface - MPI," www. mcs. a n l . gov/mpi /
• 18: "The NAS Parallel Benchmarks," www.nas .nasa.gov/Software/NPB/
• 19: The POEMS Homepage. www. cs .utexas. edu/usera/poems/
• 20: 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
• 21: Sundeep Prakash , Rajive L. Bagrodia, MPI-SIM: using parallel simulation to evaluate MPI programs, Proceedings of the 30th conference on Winter simulation, p.467-474, December 13-16, 1998, Washington, D.C., United States
• 22: Steven K. Reinhardt , Mark D. Hill , James R. Larus , Alvin R. Lebeck , James C. Lewis , David A. Wood, The Wisconsin Wind Tunnel: virtual prototyping of parallel computers, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.48-60, May 10-14, 1993, Santa Clara, California, United States
• 23: Mendel Rosenblum , Edouard Bugnion , Scott Devine , Stephen A. Herrod, Using the SimOS machine simulator to study complex computer systems, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.1, p.78-103, Jan. 1997 [doi>10.1145/244804.244807]
• 24: Jeff S. Steinman, Incremental state saving in SPEEDES using C++, Proceedings of the 25th conference on Winter simulation, p.687-696, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256816]
• 25: Sweep3D."The ASCISweep3D Benchmark," www.llnl.gov/asci_benchmarks/asci/ limited/sweep3d.html

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Message sending

  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: Parallel

General Terms:
Design, Measurement, Performance, Standardization, Theory