A graph based approach for MPI deadlock detection

ABSTRACT

The MPI standard defines several usage patterns that can lead to deadlock, some of which involve collective communications or non-deterministic operations such as wildcard receives. Further, some MPI programming deadlocks only occur for some MPI implementations or certain configurations. Many tools to detect MPI deadlocks exist; however, none precisely handles the increased complexity of deadlock detection created by the richness of the MPI standard, which requires a general deadlock model.

We present the first general deadlock model for MPI including a novel necessary and sufficient criterion, the OR-Knot, for deadlock in MPI programs. This model enables visualization of MPI deadlocks and motivates the design of a new deadlock detection mechanism. We compare our implementation of this mechanism to the ad-hoc mechanism previously available in Umpire, which reflected MPI non-determinism and, thus, more completely detected MPI deadlocks than any other existing MPI deadlock detection tool. Overall, our results demonstrate that our mechanism improves performance by as much as two orders of magnitude while providing precise characterization of deadlocks.

REFERENCES

• 1: SPEC MPI2007 Benchmark Suite for MPI. http://www.spec.org/mpi2007/.
• 2: D. H. Bailey, L. Dagum, E. Barszcz, and H. D. Simon. Nas parallel benchmark results. Technical report, IEEE Parallel and Distributed Technology, 1992.
• 3: V. C. Barbosa and M. R. F. Benevides. A graph-theoretic characterization of AND-OR deadlocks. 1998.
• 4: H. Brunst, D. Kranzlmüller, and W. Nagel. Tools for Scalable Parallel Program Analysis - Vampir NG and DeWiz. The International Series in Engineering and Computer Science, Distributed and Parallel Systems, 777:92--102, 2005.
• 5: W. Haque, Concurrent deadlock detection in parallel programs, International Journal of Computers and Applications, v.28 n.1, p.19-25, January 2006
• 6: T. Hilbrich Centralized Deadlock Detection for MPI Applications: Complexity and Parallelization. Diploma thesis, Technische Universität Dresden, Oct. 2008.
• 7: Intel Corporation. Intel R Trace Collector 7.1 User's Guide.
• 8: B. Krammer and M. S. M¨ uller. MPI Application Development with MARMOT. In G. R. Joubert, W. E. Nagel, F. J. Peters, O. G. Plata, P. Tirado, and E. L. Zapata, editors, PARCO, volume 33 of John von Neumann Institute for Computing Series, pages 893--900. Central Institute for Applied Mathematics, Jülich, Germany, 2005.
• 9: Lawrence Livermore National Laboratory. The ASCI purple benchmark codes. http://www.llnl.gov/asci/purple/benchmarks/limited/code list.html, Oct. 2002.
• 10: Soojung Lee, Fast, Centralized Detection and Resolution of Distributed Deadlocks in the Generalized Model, IEEE Transactions on Software Engineering, v.30 n.9, p.561-573, September 2004 [doi>10.1109/TSE.2004.51]
• 11: G. R. Luecke, Y. Zou, J. Coyle, J. Hoekstra, and M. Kraeva. Deadlock detection in MPI programs. Concurrency and Computation: Practice and Experience, 14:911--932, 2002.
• 12: Message Passing Interface Forum. MPI: A Message-Passing Interface Standard, Version 2.1. http://www.mpi-forum.org/docs/mpi21-report.pdf, September 2008. and K. Solchenbach. VAMPIR: Visualization and analysis of MPI resources. Supercomputer, 12(1):69--80, 1996.
• 13: W. E. Nagel, A. Arnold, M. Weber, H. C. Hoppe, and Scalable Parallel Program Analysis K. Solchenbach. VAMPIR: Visualization and analysis of MPI resources. Supercomputer, 12(1):69--80, 1996.
• 14: Martin Schulz , Bronis R. de Supinski, P^NMPI tools: a whole lot greater than the sum of their parts, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362663]
• 15: S. Siegel. Using MPI-Spin to Model Check MPI Programs with Nonblocking Communication. In Recent Advances in Parallel Virtual Machine and Message Passing Interface (EuroPVM/MPI), September 2006.
• 16: M. Sfinghal, Deadlock Detection in Distributed Systems, Computer, v.22 n.11, p.37-48, November 1989 [doi>10.1109/2.43525]
• 17: Sarvani Vakkalanka , Michael Delisi , Ganesh Gopalakrishnan , Robert M. Kirby , Rajeev Thakur , William Gropp, Implementing Efficient Dynamic Formal Verification Methods for MPI Programs, Proceedings of the 15th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface, September 07-10, 2008, Dublin, Ireland [doi>10.1007/978-3-540-87475-1_34]
• 18: J. Vetter and C. Chambreau. mpiP: Lightweight, Scalable MPI Profiling. http://www.llnl.gov/CASC/mpip/, Apr. 2005.
• 19: 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
• 20: Omer Zaki , Ewing Lusk , William Gropp , Deborah Swider, Toward Scalable Performance Visualization with Jumpshot, International Journal of High Performance Computing Applications, v.13 n.3, p.277-288, August 1999 [doi>10.1177/109434209901300310]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Theory, Verification

Keywords:
deadlock detection, mpi, parallel programming, umpire