R.: Formal verification of practical MPI programs

This paper considers the problem of formal verification of MPI programs operating under a fixed test harness for safety properties without building verification models. In our approach, we directly model-check the MPI/C source code, executing its interleavings with the help of a verification scheduler. Unfortunately, the total feasible number of interleavings is exponential, and impractical to examine even for our modest goals. Our earlier publications for-malized and implemented a partial order reduction approach that avoided exploring equivalent interleavings, and presented a veri-fication tool called ISP. This paper presents algorithmic and en-gineering innovations to ISP, including the use of OpenMP paral-lelization, that now enables it to handle practical MPI programs, including: (i) ParMETIS- a widely used hypergraph partitioner, and (ii) MADRE- a Memory Aware Data Re-distribution Engine, both developed outside our group. Over these benchmarks, ISP has automatically verified up to 14K lines of MPI/C code, producing error traces of deadlocks and assertion violations within seconds