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. 1.V. Adve, R. Bagrodia, E. Deelman, T. Phan, and R. Sakellariou. "Compiler-Supported Simulation of Highly Scalable Parallel Applications," Proceedings of Supercomputing '99, Portland, Oregon, November 1999.
2. 2.R. Bagrodia, R. Meyer, M. Takai, Y. Chen, X. Zeng, J. Martin, B. Park, and H. Song. "PARSEC: A Parallel Simulation Environment for Complex Systems," IEEE Computer, vol. 31 ( 1 ), October 1998.
3. 3.R. Bagrodia, E. Deelman, S. Docy, and T. Phan. "Performance Prediction of Large Parallel Applications Using Parallel Simulations," in Proceedings of ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Atlanta, Georgia, May 4-6, 1999.
4. 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. 5.S. Chandrasekaran and M. Hill. "Optimistic Simulation of Parallel Architectures Using Program Executahles," Workshop on Parallel and Distributed Simulation, May 1996.
6. 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. 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. 8.P. Dickens, P. Heidelberger, and D. Nicol. "Parallelized Network Simulators for Message-Passing Parallel Programs," In Proceedings of the Third huernational Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS), Durham, NC, USA, 18-20 Jan. 1995.
9. 9.E Dickens, R Heidelberger, and D. Nicol. "Parallelized Direct Execution Simulation of Message-Passing Parallel Programs," 1EEl" Transactions on Parallel and Distributed Svstents, vol.7, (no. 10), Oct. 1996.
10. 10.M. Dikaiakos, A. Rogers, and K. Steiglitz. "FAST: a Functional Algorithm Simulation Testbed," In Proceedings of MASCOTS 94.
11. 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. 12.D. Jefferson. "Virtual Time," ACM Transactions on Programming Languages and Systems, vol. 7, 1985.
13. 13.S. Horwitz, T. Reps, and D. Binkley. "lnterprocedural Slicing Using Dependence Graphs," ACM Transactions on Programming Languages and Systems, 12( 1 ), January 1990.
14. 14.J. Laudon and D. Lenoski. "The SGI Origin: A ccNUMA Highly Scalable Server," The 24th Annual International Symposium on Computer Architecture, May 1997.
15. 15.U. Legedza. "Reducing Synchronization Overhead in Parallel Programs," MIT Technical Report MIT/LCS/'TR-655.
16. 16.J. Martin and R. Bagrodia. "COMPOSE: An Object- Oriented Environment for Parallel Discrete-Event Simulations," In Proceedings of the 1995 Winter Simulation Conference, December 1995.
17. 17."Message-Passing Interface - MPI," www. mcs. a n l . gov/mpi /
18. 18."The NAS Parallel Benchmarks," www.nas .nasa.gov/Software/NPB/
19. 19.The POEMS Homepage. www. cs .utexas. edu/usera/poems/
20. 20.S. Prakash and R. Bagrodia. "Parallel Simulation of Data Parallel Programs," In Proceedings of the 8th Workshop on Languages and Compilers for Parallel Computing, Columbus, Ohio, 1995.
21. 21.S. Prakash and R. Bagrodia. "'Using Parallel Simulation to Evaluate MPI Programs," in Proceedings of the 1998 Winter Simulation Conference.
22. 22.S. Reinhardt, M. Hill, J. Larus, A. Lebeck, J. Lewis, and D. Wood. "The Wisconsin Wind Tunnel: Virtual Prototyping of Parallel Computers," In Proceedings of the 1993 ACM S1G- METRIC Conference, May 1993.
23. 23.M. Rosenblum, E. Bugnion, S. Devine, and S. Herrod. "'Using the SimOS Machine Simulator to Study Complex Computer Systems," ACM Transactions ol7 Modeling and Computer Simulation, 7( 1 ), January 1997.
24. 24.J. Steinman. "Incremental State Saving in SPEEDES Using C++," In Proceedings of the 1993 Winter Simulation Conference, December 1993.
25. 25.Sweep3D."The ASCISweep3D Benchmark," www.llnl.gov/asci_benchmarks/asci/ limited/sweep3d.html

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Simulation types and techniques

      • Discrete-event simulation

      • Massively parallel and high-performance simulations

• Networks

  • Network protocols

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Communications management

          • Message passing

• Theory of computation

  • Models of computation

    • Concurrency

      • Parallel computing models