Performance prediction of large parallel applications using parallel simulations

ABSTRACT

Accurate simulation of large parallel applications can be facilitated with the use of direct execution and parallel discrete event simulation. This paper describes the use of COMPASS, a direct execution-driven, parallel simulator for performance prediction of programs that include both communication and I/O intensive applications. The simulator has been used to predict the performance of such applications on both distributed memory machines like the IBM SP and shared-memory machines like the SGI Origin 2000. The paper illustrates the usefulness of COMPASS as a versatile performance prediction tool. We use both real-world applications and synthetic benchmarks to study application scalability, sensitivity to communication latency, and the interplay between factors like communication pattern and parallel file system caching on application performance. We also show that the simulator is accurate in its predictions and that it is also efficient in its ability to use parallel simulation to reduce its own execution time which, in some cases, has yielded a nearlinear speedup.

REFERENCES

• 1: Rajive Bagrodia , Stephen Docy , Andy Kahn, Parallel simulation of parallel file systems and I/O programs, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-17, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509640]
• 2: D. Bailey, T. Harris, W. Shaphir, R. van der Wijngaart, A. Woo, and M. Yarrow. "The NAS Parallel Benchmarks 2.0," Report NAS-95-090, NASA Ames Research Center, 1995.
• 3: S.J. Baylor, C. Benveniste and L.J. Beolhouwer. "A Methodology for Evaluating Parallel I/O Performance for Massively Parallel Processors." In Proceedings of the 27th Annual Simulation Symposium, 1994, pp.31-40.
• 4: E. A. Brewer , C. N. Dellarocas , A. Colbrook , W. E. Weihl, PROTEUS: A HIGH-PERFORMANCE PARALLEL-ARCHITECTURE SIMULATOR, Massachusetts Institute of Technology, Cambridge, MA, 1991
• 5: M. Chandy and J. Misra. "Distributed Simulation: A Case Study in Design And Verification Of Distributed Programs," IEEE Trans. on Software Engineering, Sept. 1979, pp.440- 452.
• 6: Peter F. Corbett , Dror G. Feitelson, The Vesta parallel file system, ACM Transactions on Computer Systems (TOCS), v.14 n.3, p.225-264, Aug. 1996 [doi>10.1145/233557.233558]
• 7: Toni Cortes , Sergi Girona , Jesús Labarta, Avoiding the Cache-Coherence Problem in a Parallel/Distributed File System, Proceedings of the International Conference and Exhibition on High-Performance Computing and Networking, p.860-869, April 28-30, 1997
• 8: R. C. Covington , S. Madala , V. Mehta , J. R. Jump , J. B. Sinclair, The rice parallel processing testbed, Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.4-11, May 24-27, 1988, Santa Fe, New Mexico, United States
• 9: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 10: M.H. Dahlin, R.Y. Wang, T.E. Anderson and D.A. Patterson. "Remote Client Memory to Improve File System Performance." In Proceedings of the 1994 Symposium on Operating Systems.
• 11: H.Davis, S.R. Goldschmidt and Hennessey. "Multiprocessor Simulation and Tracing Using Tango." In Proceedings of ICPP'91, pp. 99-107, August 1991.
• 12: Ewa Deelman , Aditya Dube , Adolfy Hoisie , Yong Luo , Richard L. Oliver , David Sundaram-Stukel , Harvey Wasserman , Vikram S. Adve , Rajive Bagrodia , James C. Browne , Elias Houstis , Olaf Lubeck , John Rice , Patricia J. Teller , Mary K. Vernon, Poems: end-to-end performance design of large parallel adaptive computational systems, Proceedings of the 1st international workshop on Software and performance, p.18-30, October 12-16, 1998, Santa Fe, New Mexico, United States [doi>10.1145/287318.292468]
• 13: 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]
• 14: J2c (Fortran to C converter), http://www.netlib.org/f2c/
• 15: James V. Huber, Jr. , Andrew A. Chien , Christopher L. Elford , David S. Blumenthal , Daniel A. Reed, PPFS: a high performance portable parallel file system, Proceedings of the 9th international conference on Supercomputing, p.385-394, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224638]
• 16: Vipin Kumar , Anshul Gupta, Analysis of scalability of parallel algorithms and architectures: a survey, Proceedings of the 5th international conference on Supercomputing, p.396-405, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109118]
• 17: Vipin Kumar , Ananth Grama , Anshul Gupta , George Karypis, Introduction to parallel computing: design and analysis of algorithms, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994
• 18: David Kotz, Tuning STARFISH, Dartmouth College, Hanover, NH, 1996
• 19: 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
• 20: "ASCI Blue-Pacific IBM RS/6000 TR System at Lawrence Livermore National Laboratory," http://www.llnl.gov/asci/platforms/bluepac/tr.hwtable.html.
• 21: 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
• 22: Y. Luo. "MPI Performance Study on the SGI Origin 2000," Pacific Rim Conference on Communications, Computers and Signal Processing, 1997, pp.269-272.
• 23: S.S. Mukherjee, S.K. Reinhardt, B. Falsafi, M. Litzkow, S. Huss-Lederman, M.D. Hill, J.R. Larus, and D.A. Wood. "Wisconsin Wind Tunnel II: A Fast and Portable Parallel Architecture Simulator," Workshop on Performance Analysis and Its Impact on Design (PAID), 1997.
• 24: Nils Nieuwejaar , David Kotz, The galley parallel file system, Proceedings of the 10th international conference on Supercomputing, p.374-381, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237639]
• 25: 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
• 26: Sundeep Prakash , Rajive Bagrodia, Performance prediction of parallel programs, 1996
• 27: 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
• 28: 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
• 29: J.M. clel Rosario, R. Bordawekar and A. Choudhary. "Improved Parallel I/O via a Two-Phase Runtime Access Strategy." In Proceedings of the IPP '93 Workshop on I/0 in Parallel Computer Systems, 1993, pp. 56-70.
• 30: 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]
• 31: Anand Sivasubramaniam , Aman Singla , Umakishore Ramachandran , H. Venkateswaran, A simulation-based scalability study of parallel systems, Journal of Parallel and Distributed Computing, v.22 n.3, p.411-426, Sept. 1994 [doi>10.1006/jpdc.1994.1101]
• 32: "The ASCI sweep3d Benchmark Code," http://www.llnl.gov/asci_benchmarks/.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Experimentation, Management, Measurement, Performance

Keywords:
MPI, MPI-IO, application scalability, direct execution, parallel discrete event simulation, parallel program simulation