How Formal Dynamic Verification Tools Facilitate Novel Concurrency Visualizations

Sriram Aananthakrishnan, Michael Delisi, Sarvani S. Vakkalanka, Anh Vo, Ganesh Gopalakrishnan, Robert M. Kirby, Rajeev ThakurPVM/MPI 2009 · DOI

TL;DR

This paper introduces ISP, a formal dynamic verification tool for MPI programs, which uses novel visualization techniques to help developers understand and debug complex concurrent behaviors. By reducing redundant trace information and providing insightful views like "completes-before" graphs, ISP aims to make concurrent debugging more intuitive and efficient, especially for large-scale MPI applications.

What Problem Does This Paper Address?

Debugging concurrent programs, particularly those using the Message Passing Interface (MPI), is notoriously difficult. As the scale of concurrency explodes, traditional debuggers often present an overwhelming amount of redundant trace information, making it hard to pinpoint errors or understand program behavior. This "cognitive overload" is exacerbated by the inherent complexity of concurrent execution schedules, where seemingly minor changes can lead to vastly different outcomes. The paper addresses the need for tools that can intelligently reduce this complexity, provide intuitive visualizations of concurrent interactions, and help developers gain deeper insights into their programs and the MPI API itself.

Methods

The core of ISP's approach lies in its formal dynamic verification capabilities, specifically its implementation of Dynamic Partial Order Reduction (DPOR), which they term "Partial Order avoiding Elusive interleavings" (POE). This technique intelligently explores only relevant execution schedules, avoiding the exponential explosion of possibilities that plague traditional methods.

Key techniques include:

  • Intelligent Interleaving Exploration (POE): ISP identifies and explores only the "relevant" interleavings, significantly reducing the number of traces presented to the user. This is achieved by dynamically rewriting wildcard receives and replaying the program for each potential match.
  • Completes-Before (CB) Graph: This novel visualization represents the partial order of MPI action occurrences that must be guaranteed by all standard-compliant MPI libraries. It helps users understand the inherent ordering constraints and how different platforms might reorder commands.
  • Intuitive GUI: ISP offers several graphical user interfaces (GUIs) built on top of its core engine. These include a portable Java GUI, a Microsoft Visual Studio plug-in, and an in-progress Eclipse plug-in. These GUIs aim to present information clearly, highlight errors, and facilitate drill-down into specific issues.
  • PMPI Interception: ISP uses the Profiling Interface (PMPI) to intercept MPI program actions, allowing it to delay, reorder, or issue these actions to discover the full extent of non-determinism.

Datasets

Not discussed in the paper. The paper focuses on the tool's capabilities and uses example MPI programs to illustrate its features.

Key Insights and Ideas

  • Reducing Redundancy is Crucial: The paper strongly emphasizes that simply showing all possible interleavings is counterproductive. Intelligent reduction of redundant traces is key to making concurrent debugging manageable.
  • Visualizing Ordering is Powerful: The "completes-before" graph is a significant contribution, offering a way to visualize inherent ordering constraints and potential platform-specific reorderings, which can be a source of portability bugs.
  • Formal Verification Enhances Debugging: By leveraging formal methods, ISP can guarantee the detection of certain classes of errors (deadlocks, assertion violations, resource leaks) and provide deeper insights than traditional debugging approaches.
  • Bridging the Gap to Conventional Debuggers: The integration with tools like Visual Studio allows users to seamlessly transition from ISP's high-level analysis to low-level debugging when needed, combining the strengths of both approaches.
  • Understanding MPI Subtleties: The paper highlights how ISP can educate users about the nuances of the MPI API, such as the behavior of collectives and probes, which can be a source of subtle bugs.

Key Results

The paper doesn't present extensive quantitative results in terms of speedup or accuracy metrics on large benchmarks. Instead, it focuses on the qualitative benefits of its visualization techniques and the effectiveness of ISP in identifying bugs in example programs.

  • ISP has been used to verify large-scale programs like ParMETIS, MADRE, and MPI-BLAST, demonstrating its scalability.
  • The tool effectively identifies deadlocks and other concurrency errors in example scenarios.
  • The visualization techniques, particularly the "completes-before" graph and intuitive trace displays, are shown to help users understand complex concurrent interactions and pinpoint the root cause of bugs.
  • The paper demonstrates how ISP can reveal subtle MPI behaviors, such as the non-deterministic matching of wildcard receives and probes, which can be missed by conventional debuggers.

Limitations and Future Work

  • Downscaling Problems: The authors acknowledge that the current approach, like most concurrency tools, often requires users to downscale problems before using the tool. This is a limitation for resource bugs and suggests that more work is needed in this area.
  • Conceptual Depth: While the GUIs are designed to be intuitive, the paper notes that the conceptual depth of the displays can be significant, implying a learning curve for users to fully leverage them.
  • Future Work: The authors express a desire to further develop the integration with the Eclipse PTP and enhance the facility for cutting into conventional debuggers at selected highlight points. They also mention the potential for exploiting "exponential compression" methods like process symmetries and data-space symmetries in future work.

Summary updated

BibTeX
@inproceedings{aananthakrishnan2009how,
  author = {Sriram Aananthakrishnan and Michael Delisi and Sarvani S. Vakkalanka and Anh Vo and Ganesh Gopalakrishnan and Robert M. Kirby and Rajeev Thakur},
  title = {{How Formal Dynamic Verification Tools Facilitate Novel Concurrency Visualizations}},
  booktitle = {PVM/MPI},
  year = {2009},
  doi = {10.1007/978-3-642-03770-2\_32},
}
Figure