Active Testing: Predicting and Confirming Concurrency Bugs for Concurrent and Distributed Memory Parallel Systems

Parallel and concurrent software sometimes exhibit incorrect behavior because ofunintended interference between different threads of execution. Common classesof concurrency bugs include data races, deadlocks, and atomicity violations.These bugs are often non-deterministic and hard to find without sophisticatedtools. We present Active Testing, a methodology to effectively find concurrencybugs that scales to large distributed memory parallel systems.Active Testing combines the coverage and predictive power of program analysiswith the familiarity of testing. It works in two phases: in the predictiveanalysis phase, a program is executed and monitored for potential concurrencybugs and in the testing phase, Active Testing re-executes the program whilecontrolling the thread schedules in an attempt to reproduce the bug predicted inthe first phase. We have implemented Active Testing for multi-threaded Java programs in theCalFuzzer framework. We have also developed UPC-Thrille, an Active Testing frameworkfor Unified Parallel C (UPC) programs written in the Single Program MultipleData (SPMD) programming model combined with the Partitioned Global Address Space(PGAS) memory model. We explain in detail the design decisions and optimizationsthat were necessary to scale Active Testing to thousands of cores. We presentextensions to UPC-Thrille that support hybrid memory models as well. We evaluate the effectiveness of Active Testing by running our tools on severalJava and UPC benchmarks, showing that it can predict and confirm realconcurrency bugs with low overhead. We demonstrate the scalability of ActiveTesting by running benchmarks with UPC-Thrille on large clusters with thousandsof cores