Data Race Detection for Event-Driven Parallel Runtime Systems
Master of Science
Event-Driven Parallel (EDP) runtime systems (or more simply, EDP runtimes) are growing in popularity in the high-performance computing area because they provide a promising foundation for new programming systems that can support heterogeneous architectures and ever-increasing hardware complexity. EDP runtimes allow the programmer to focus on program logic, such as control and data dependences, thereby enabling portability across a wide range of platforms and system configurations. However, the applications written on top of EDP runtimes remain vulnerable to data races. Existing data race detection tools either do not support the primitives in EDP runtimes, or incur intractable large overheads by failing to utilize the structural information available in event-driven programs. In this dissertation, we propose a graph-traversal based data race detection method for EDP runtimes. It introduces a reachability graph (encodes the dependences in a program), to check the happens-before relation between memory accesses. In order to reduce the time complexity for race detection, we propose a few optimizations, such as reachability cache and reversed reachability graph to avoid unnecessary graph traversals and path compression to reduce the number of steps performed for graph traversal. Based on our race detection technique, we have developed a prototype implementation for the Open Community Runtime (OCR). Our evaluation on a set of open source OCR benchmarks shows that our tool handles all OCR constructs, and that the time overhead for race detection is comparable to that of past work on race detection for more constrained (e.g., fork-join) runimes.
Data Race Detection; Parallel Programming; Graph Traversal