MPIWiz: subgroup reproducible replay of mpi applications

ABSTRACT

Message Passing Interface (MPI) is a widely used standard for managing coarse-grained concurrency on distributed computers. Debugging parallel MPI applications, however, has always been a particularly challenging task due to their high degree of concurrent execution and non-deterministic behavior. Deterministic replay is a potentially powerful technique for addressing these challenges, with existing MPI replay tools adopting either data-replay or order-replay approaches. Unfortunately, each approach has its tradeoffs. Data-replay generates substantial log sizes by recording every communication message. Order-replay generates small logs, but requires all processes to be replayed together. We believe that these drawbacks are the primary reasons that inhibit the wide adoption of deterministic replay as the critical enabler of cyclic debugging of MPI applications.

This paper describes subgroup reproducible replay (SRR), a hybrid deterministic replay method that provides the benefits of both data-replay and order-replay while balancing their trade-offs. SRR divides all processes into disjoint groups. It records the contents of messages crossing group boundaries as in data-replay, but records just message orderings for communication within a group as in order-replay. In this way, SRR can exploit the communication locality of traffic patterns in MPI applications. During replay, developers can then replay each group individually. SRR reduces recording overhead by not recording intra-group communication, and reduces replay overhead by limiting the size of each replay group. Exposing these tradeoffs gives the user the necessary control for making deterministic replay practical for MPI applications.

We have implemented a prototype, MPIWiz, to demonstrate and evaluate SRR. MPIWiz employs a replay framework that allows transparent binary instrumentation of both library and system calls. As a result, MPIWiz replays MPI applications with no source code modification and relinking, and handles non-determinism in both MPI and OS system calls. Our preliminary results show that MPIWiz can reduce recording overhead by over a factor of four relative to data-replay, yet without requiring the entire application to be replayed as in order-replay. Recording increases execution time by 27% while the application can be replayed in just 53% of its base execution time.

REFERENCES

• 1: D. Bailey, T. Harris, W. Saphir, R. van der Wijngaart, A. Woo, and M. Yarrow. The NAS Parallel Benchmarks 2.0. Technical Report Report NAS-95-020, Numerical Aerodynamic Simulation Facility, NASA Ames Research Center, Mail Stop T 27 A-1, Moffett Field, CA 94035- 1000, USA, Dec. 05 1995.
• 2: A. Bouteiller, G. Bosilca, and J. Dongarra. Retrospect: Deterministic Replay of MPI Applications for Interactive Distributed Debugging. In 14th European PVM/MPI User's Group Meeting, pages 297--306, 2007.
• 3: C.-K. Cheng and Y.-C. A. Wei. An Improved Two-way Partitioning Algorithm with Stable Performance. IEEE Transactions on Computer Aided Design, 10(12):1502--1511, 1991.
• 4: Christian Clémençon , Josef Fritscher , M. J. Meehan , Roland Rühl, An Implementation of Race Detection and Deterministic Replay with MPI, Proceedings of the First International Euro-Par Conference on Parallel Processing, p.155-166, August 29-31, 1995
• 5: Jacques Chassin de Kergommeaux , Michiel Ronsse , Koenraad De Bosschere, MPL*: Efficient Record/Play of Nondeterministic Features of Message Passing Libraries, Proceedings of the 6th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface, p.141-148, September 26-29, 1999
• 6: Jayant DeSouza , Bob Kuhn , Bronis R. de Supinski , Victor Samofalov , Sergey Zheltov , Stanislav Bratanov, Automated, scalable debugging of MPI programs with Intel® Message Checker, Proceedings of the second international workshop on Software engineering for high performance computing system applications, May 15-15, 2005, St. Louis, Missouri [doi>10.1145/1145319.1145342]
• 7: C. Falzone, A. Chan, E. L. Lusk, and W. Gropp. Collective Error Detection for MPI Collective Operations. In PVM/MPI'05, pages 138--147, 2005.
• 8: A. Faraj and X. Yuan. Communication Characteristics in the NAS Parallel Benchmarks. In PDCS'02, pages 724--729, 2002.
• 9: J. Garbers, H. J. Prömel, and A. Steger. Finding Clusters in VLSI Circuits. In IEEE International Conference on Computer Aided Design, pages 520--523, Nov. 1990.
• 10: William Gropp , Ewing Lusk , Nathan Doss , Anthony Skjellum, A high-performance, portable implementation of the MPI message passing interface standard, Parallel Computing, v.22 n.6, p.789-828, Sept. 1996 [doi>10.1016/0167-8191(96)00024-5]
• 11: Z. Guo, X. Wang, J. Tang, X. Liu, Z. Xu, M. Wu, M. F. Kaashoek, and Z. Zhang. R2: An Application-Level Kernel for Record and Replay. In OSDI'08, To appear, 2008.
• 12: W. Haque, Concurrent deadlock detection in parallel programs, International Journal of Computers and Applications, v.28 n.1, p.19-25, January 2006
• 13: HPCC. Hpcc 1998 blue book (computing, information, and communications: Technologies for the 21st century). Computing, Information, and Communications (CIC) R&D Subcommittee of the National Science and Technology Council's Committee on Computing, Information, and Communications (CCIC), 1998.
• 14: Performance Evaluation of View-Oriented Parallel Programming, Proceedings of the 2005 International Conference on Parallel Processing, p.251-258, June 14-17, 2005 [doi>10.1109/ICPP.2005.62]
• 15: NAS Parallel Benchmarks: ProActive implementations. http://proactive.inria.fr/index.php?page=nas_benchmarks.
• 16: George Karypis , Vipin Kumar, Multilevel k-way partitioning scheme for irregular graphs, Journal of Parallel and Distributed Computing, v.48 n.1, p.96-129, Jan. 1998 [doi>10.1006/jpdc.1997.1404]
• 17: Thilo Kielmann , Rutger F. H. Hofman , Henri E. Bal , Aske Plaat , Raoul A. F. Bhoedjang, MagPIe: MPI's collective communication operations for clustered wide area systems, ACM SIGPLAN Notices, v.34 n.8, p.131-140, Aug. 1999
• 18: JunSeong Kim , David J. Lilja, Characterization of Communication Patterns in Message-Passing Parallel Scientific Application Programs, Proceedings of the Second International Workshop on Network-Based Parallel Computing: Communication, Architecture, and Applications, p.202-216, January 31-February 01, 1998
• 19: B. Krammer and M. S. Müller. MPI Application Development with MARMOT. In ParCo'05, pages 893--900, 2005.
• 20: Dieter Kranzlmüller , Christian Schaubschläger , Jens Volkert, An Integrated Record&Replay Mechanism for Nondeterministic Message Passing Programs, Proceedings of the 8th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface, p.192-200, September 23-26, 2001
• 21: Dieter Kranzlmüller , Jens Volkert, NOPE: A Nondeterministic Program Evaluator, Proceedings of the 4th International ACPC Conference Including Special Tracks on Parallel Numerics and Parallel Computing in Image Processing, Video Processing, and Multimedia: Parallel Computation, p.490-499, February 01, 1999
• 22: T. J. LeBlanc , J. M. Mellor-Crummey, Debugging Parallel Programs with Instant Replay, IEEE Transactions on Computers, v.36 n.4, p.471-482, April 1987 [doi>10.1109/TC.1987.1676929]
• 23: R. Lovas and P. Kacsuk. Correctness Debugging of Message Passing Programs Using Model Verification Techniques. In 14th European PVM/MPI User's Group Meeting, pages 335--343, 2007.
• 24: G. R. Luecke, H. Chen, J. Coyle, J. Hoekstra, M. Kraeva, and Y. Zou. MPI-CHECK: A Tool for Checking Fortran 90 MPI Programs. Concurrency and Computation: Practice and Experience, 15(2):93--100, 2003.
• 25: M. Maruyama, T. Tsumura, and H. Nakashima. Parallel Program Debugging based on Data-Replay. In PDCS'05, pages 151--156, 2005.
• 26: Gary L. Miller , Shang-Hua Teng , Stephen A. Vavasis, A unified geometric approach to graph separators, Proceedings of the 32nd annual symposium on Foundations of computer science, p.538-547, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185417]
• 27: SIM-MPI Library. http://www.hpctest.org.cn/resources/sim-mpi.tgz.
• 28: Neophytos Neophytou , Paraskevas Evripidou, Net-dbx: A Web-Based Debugger of MPI Programs Over Low-Bandwidth Lines, IEEE Transactions on Parallel and Distributed Systems, v.12 n.9, p.986-995, September 2001 [doi>10.1109/71.954636]
• 29: S. Pervez, G. Gopalakrishnan, R. M. Kirby, R. Palmer, R. Thakur, and W. Gropp. Practical Model-Checking Method for Verifying Correctness of MPI Programs. In 14th European PVM/MPI User's Group Meeting, pages 344--353, 2007.
• 30: PGDBG Graphical Symbolic Debugger. http://www.pgroup.com/products/pgdbg.htm.
• 31: Michael Rudgyard, Novel techniques for debugging and optimizing parallel applications, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188749]
• 32: Bianca Schroeder , Garth A. Gibson, A large-scale study of failures in high-performance computing systems, Proceedings of the International Conference on Dependable Systems and Networks, p.249-258, June 25-28, 2006 [doi>10.1109/DSN.2006.5]
• 33: S. F. Siegel. Model Checking Nonblocking MPI Programs. In 8th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI 2007), pages 44--58, 2007.
• 34: Stephen F. Siegel , George S. Avrunin, Modeling wildcard-free MPI programs for verification, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065957]
• 35: Stephen F. Siegel , Anastasia Mironova , George S. Avrunin , Lori A. Clarke, Using model checking with symbolic execution to verify parallel numerical programs, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA [doi>10.1145/1146238.1146256]
• 36: Totalview. http://www.totalviewtech.com/.
• 37: J. L. Träff and J. Worringen. Verifying Collective MPI Calls. In 11th European PVM/MPI Users' Group Meeting, pages 18--27, 2004.
• 38: Jeffrey S. Vetter , Bronis R. de Supinski, Dynamic software testing of MPI applications with umpire, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.51-es, November 04-10, 2000, Dallas, Texas, United States
• 39: Jeffrey S. Vetter , Frank Mueller, Communication characteristics of large-scale scientific applications for contemporary cluster architectures, Journal of Parallel and Distributed Computing, v.63 n.9, p.853-865, September 2003 [doi>10.1016/S0743-7315(03)00104-7]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Distributed debugging

General Terms:
Design, Performance, Reliability

Keywords:
distributed debugging, message passing interface, non-determinism, record and replay