Fast, Precise and Scalable Race Detection for Extreme-Scale Computing

As new and disruptive programming models are being developed, there is a trend that extreme-scale programming languages will embrace a hybrid model of message-passing and shared-memory, over abstractions such as processes, threads, and tasks. Unfortunately, writing parallel programs under a hybrid model if not harder) is as hard as writing shared-memory or message-passing concurrent programs, which have been plagued by concurrency-related bugs such as race conditions. Race conditions are notoriously diffi cult to detect and debug because they are nondeterministic, often leading to unrepeatable computing results, unexpected program failures, hangs, crashes, or data corruptions. Despite intensive R/R&D efforts in both academia and industry, existing techniques and tools for detecting and debugging race conditions such as ThreadSanitizer, TotalView, Intel Inspector and CIVL remain inadequate, because they incur prohibitive runtime perturbation, miss real errors, generate many false alarms, lack diagnostic information, or do not scale to large HPC applications. In particular, most existing approaches are designed for late phases of software development, e.g., testing or production. As a result, it is often too late to find a race condition bug or it becomes too expensive to fix the bug. Moreover, scaling these approaches to large codebases is difficult without sacrificing detection coverage or accuracy. In this project, Coderrect LLC will develop a fast, precise, and scalable static race detector for extreme-scale computing applications written under a hybrid model of MPI, threads and OpenMP constructs. It is expected that the tool will automatically detect race conditions in HPC C/C++ programs containing over a million lines of code with very fast speed and high precision. The key technology behind our innovation is a new compiler-based program analysis abstraction called differential concurrency analysis DCA) that judiciously combines three change-centric analyses —pointer alias analysis, array index analysis, and happens-before analysis— to reduce the average computational complexity of analyzing a parallel program to proportional to the size of the code changes instead of the entire codebase). The technology has the potential to detect all concurrency-related bugs in large-scale complex programs continuously and immediately after they are introduced in an IDE, by a code commit, or by a pull request. For concurrency errors that are undecidable statically, the technology will insert minimal runtime checks to validate them precisely, by a novel combination of static and dynamic analyses to create, validate, replay, and explain the errors, and to prune away false positives. The technical details of DCA, authored by the PI and other key personnel of Coderrect LLC, have been published as full research papers in top ACM venues PLDI’18 and TOPLAS’19), as well as a HPC correctness workshop Correctness’18). Coderrect LLC has already developed a tool based on this technology for JVM-based applications such as Java and Android apps with impressive results over existing state-of-the-art tools such as Facebook’s RacerD. This technology once commercialized can have significant impact in improving reliability and security of HPC software applications. The anticipated outcome of Phase I is a tool that will help HPC application developers in DOE write more reliable hybrid parallel programs without race conditions, and make them more productive for debugging race conditions. Coderrect LLC will evaluate the tool with both user studies and performance experiments on open source HPC applications from LULESH, CORAL, PARSEC, the NAS Parallel Benchmarks and other real-world scientific applications written in C/C++ with MPI/Pthreads/OpenMP. It is expected that in the long term this project will drastically improve the reliability and productivity of extreme-scale parallel programming and enable more widespread adoption of in situ analysis tools to detect defects in parallel programs. It will also significantly reduce the cost of software maintenance, in-house testing, failure diagnosis and debugging of scientific applications.