Abstract | ||
---|---|---|
We propose a dynamic verification approach for large-scale message passing programs to locate correctness bugs caused by unforeseen nondeterministic interactions. This approach hinges on an efficient protocol to track the causality between nondeterministic message receive operations and potentially matching send operations. We show that causality tracking protocols that rely solely on logical clocks fail to capture all nuances of MPI program behavior, including the variety of ways in which nonblocking calls can complete. Our approach is hinged on formally defining the matches-before relation underlying the MPI standard, and devising lazy update logical clock based algorithms that can correctly discover all potential outcomes of nondeterministic receives in practice. can achieve the same coverage as a vector clock based algorithm while maintaining good scalability. LLCP allows us to analyze realistic MPI programs involving a thousand MPI processes, incurring only modest overheads in terms of communication bandwidth, latency, and memory consumption. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1109/PACT.2011.64 | PACT |
Keywords | Field | DocType |
lazy update,large scale verification,thousand mpi,mpi program behavior,nondeterministic message,dynamic verification approach,logical clock,unforeseen nondeterministic interaction,realistic mpi program,mpi programs,mpi standard,approach hinge,lamport clocks,causality tracking protocol,testing,vectors,synchronization,protocols,message passing,semantics,computer bugs | Vector clock,Nondeterministic algorithm,Computer science,Correctness,Parallel computing,Software bug,Lamport timestamps,Logical clock,Real-time computing,Message passing,Scalability,Distributed computing | Conference |
Citations | PageRank | References |
9 | 0.59 | 10 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Vo Anh | 1 | 1244 | 91.60 |
Ganesh Gopalakrishnan | 2 | 1619 | 130.11 |
Robert M. Kirby | 3 | 1443 | 115.55 |
de Supinski, Bronis R. | 4 | 2667 | 154.44 |
Martin Schulz | 5 | 2227 | 129.64 |
Greg Bronevetsky | 6 | 949 | 44.91 |