Dynamic testing of flow graph based parallel applications

ABSTRACT

In message-passing parallel applications, messages are not delivered in a strict order. The number of messages, their content and their destination may depend on the ordering of their delivery. Nevertheless, for most applications, the computation results should be the same for all possible orderings. Finding an ordering that produces a different outcome or that prevents the execution from terminating reveals a message race or a deadlock. Starting from the initial application state, we dynamically build an acyclic message-passing state graph such that each path within the graph represents one possible message ordering. All paths lead to the same final state if no deadlock or message race exists. If multiple final states are reached, we reveal message orderings that produce the different outcomes. The corresponding executions may then be replayed for debugging purposes. We reduce the number of states to be explored by using previously acquired knowledge about communication patterns and about how operations read and modify local process variables. We also describe a heuristic that tests a subset of orderings that are likely to reveal existing message races or deadlocks. We applied our approach on several applications developed using the Dynamic Parallel Schedules (DPS) parallelization framework. Compared to the naive execution of all message orderings, the use of a message-passing state graph reduces the cost of testing all orderings by several orders of magnitude. The use of prior information further reduces the number of visited states by a factor of up to fifty in our tests. The heuristic relying on a subset of orderings was able to reveal race conditions in all tested cases. We finally present a first step in generalizing the approach to MPI applications.

REFERENCES

• 1: A. Bouteiller, G. Bosilca, J. Dongarra, Retrospect: Deterministic Replay of MPI Applications for Interactive Distributed Debugging, Recent Advances in Parallel Virtual Machine and Message Passing Interface, Lecture Notes in Computer Science (LNCS), Vol. 4757, pp. 297--306, Springer Verlag, 2007, doi:10.1007/978-3-540-75416-9_41
• 2: F. Chen, G. Roşu, Parametric and Sliced Causality, Proceedings of the 19^th Conference on Computer Aided Verification (CAV'07), Lecture Notes In Computer Science (LNCS), Vol. 4590, Springer, pp 240--253, 2007
• 3: Cormac Flanagan , Stephen N. Freund , Shaz Qadeer, Exploiting Purity for Atomicity, IEEE Transactions on Software Engineering, v.31 n.4, p.275-291, April 2005 [doi>10.1109/TSE.2005.47]
• 4: Cormac Flanagan , Patrice Godefroid, Dynamic partial-order reduction for model checking software, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.110-121, January 12-14, 2005, Long Beach, California, USA
• 5: Sebastian Gerlach , Roger D. Hersch, DPS " Dynamic Parallel Schedules, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.128.2, April 22-26, 2003
• 6: Sebastian Gerlach , Roger D. Hersch, Fault-Tolerant Parallel Applications with Dynamic Parallel Schedules, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 16, p.278.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.226]
• 7: G. H. Golub, C. F. van Loan, Matrix Computations, The Johns Hopkins University Press, pp. 94--116, 1996
• 8: Chul-Eui Hong , Bum-Sik Lee , Gi-Won On , Dong-Hae Chi, Replay for Debugging MPI Parallel Programs, Proceedings of the Second MPI Developers Conference, p.156, July 01-02, 1996
• 9: Re-execution of Distributed Programs to Detect Bugs Hidden by Racing, Proceedings of the 30th Hawaii International Conference on System Sciences: Software Technology and Architecture, p.423, January 03-06, 1997
• 10: Panagiotis Takis Metaxas, Parallel digital halftoning by error-diffusion, Proceedings of the Paris C. Kanellakis memorial workshop on Principles of computing & knowledge: Paris C. Kanellakis memorial workshop on the occasion of his 50th birthday, p.35-41, June 08-08, 2003, San Diego, California, USA [doi>10.1145/778348.778355]
• 11: Neeraj Mittal , Vijay K. Garg, Debugging distributed programs using controlled re-execution, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.239-248, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343624]
• 12: Mohamed Mosbah , Rodrigue Ossamy, Checking Global Properties for Local Computations in Graphs with Applications to Invariant Testing, Proceedings of the Fifth Mexican International Conference in Computer Science, p.35-42, September 20-24, 2004
• 13: Robert H. B. Netzer , Timothy W. Brennan , Suresh K. Damodaran-Kamal, Debugging race conditions in message-passing programs, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.31-40, May 22-23, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/238020.238033]
• 14: M. Otta, S. Racek, A method for testing and debugging distributed applications, Int'l Conference on Trends in Communications (EUROCON'2001), vol. 2, pp. 548--551, July 2001
• 15: Detecting the First Races in Parallel Programs with Ordered Synchronization, Proceedings of the 1998 International Conference on Parallel and Distributed Systems, p.201, December 14-16, 1998
• 16: Shaz Qadeer , Dinghao Wu, KISS: keep it simple and sequential, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 17: J. F. Ruscio, M. A. Heffner, S. Varadarajan, DejaVu: Transparent User-Level Checkpointing, Migration, and Recovery for Distributed Systems, Proc. 21st Int'l Parallel and Distributed Processing Symposium (IPDPS'07), pp. 1--8, Long Beach, USA, March 2007.
• 18: S. Sankaran, J. M. Squyres, B. Barrett, A. Lumsdaine, J. Duell, P. Hargrove, E. Roman}, The LAM/MPI Checkpoint/Restart Framework: System-Initiated Checkpointing, Int'l Journal of High Performance Computing Applications, Vol. 19, No. 4, pp. 479--493, 2005
• 19: B. Schaeli, S. Gerlach, R. D. Hersch, Decomposing Partial Order Execution Graphs to Improve Message Race Detection, Proc. 21st Int'l Parallel and Distributed Processing Symposium (IPDPS'07), pp. 1--8, Long Beach, USA, March 2007.
• 20: 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]
• 21: S. F. Siegel, G. S. Avrunin, Verification of halting properties for MPI programs using nonblocking operations, Proc. 14th European PVM/MPI Users' Group Conference, 2007.
• 22: Sarvani S. Vakkalanka , Subodh Sharma , Ganesh Gopalakrishnan , Robert M. Kirby, ISP: a tool for model checking MPI programs, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345258]
• 23: Liqiang Wang , Scott D. Stoller, Runtime Analysis of Atomicity for Multithreaded Programs, IEEE Transactions on Software Engineering, v.32 n.2, p.93-110, February 2006 [doi>10.1109/TSE.2006.1599419]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids; Testing tools (e.g., data generators, coverage testing)

General Terms:
Experimentation, Reliability, Verification