HARVEY MUDD COLLEGE

The concept of “determinism” of parallel programs and parallel systems has received a lot of attention since the dawn of computing, with multiple formal and informal definitions of deterministic execution. In this talk, we start by reviewing two related properties of task-parallel programs —- determinacy and repeatability. Our focus is on structured task parallelism as exemplified by the Habanero-Java (HJ) programming language, and we observe that data races play a central role in establishing determinacy of programs written in such languages.

Type systems that prevent data races are a powerful tool for parallel programming, eliminating whole classes of bugs that are both hard to find and hard to fix. Unfortunately, it is difficult to apply previous work on such type systems to general task-parallel programs, as each such type system is designed around a specific synchronization primitive or parallel pattern, such as locks or disjoint heaps. In contrast, real-world task-parallel programs often have to combine multiple synchronization primitives and parallel patterns. We introduce a permissions-based type system for HJ called “Habanero Java with permissions” (HJp), which supports multiple patterns for parallelism, synchronization, and data access (e.g., task parallelism, object isolation, array-based parallelism). To demonstrate the practicality of this approach, we have ported 15 benchmarks from HJ to HJp, totaling almost 14,000 lines of code and covering a range of parallel patterns. This port only required modifications to 5% of the source code on average. Further, HJp is a gradual type system, meaning that some or all of these annotations can be omitted, and the compiler will insert dynamic type-casts where necessary to ensure race-freedom at run time. We present a simple and effective algorithm for inserting these type-casts, as well as an efficient runtime approach for checking permissions on entry to specific regions of code.

For HJ programs that do not use the HJp type system, we introduce a dynamic data race detection algorithms for structured parallel programs that overcome limitations of past work on dynamic datarace detection, such as worst-case linear space overhead per memory location, worst-case linear time overhead per memory access, dependence on sequential execution, dependence on a specific task scheduling technique, and generation of false positives and false negatives in their data race reports. We refer to our algorithm as SPD3 (Scalable Precise Dynamic Datarace Detection). The SPD3 algorithm supports a rich set of parallel constructs (including async, finish, future, and isolated). For async, finish, and future, SPD3 is guaranteed to be precise and sound for a given input. In the presence of isolated, SPD3 is precise but not sound. An experimental evaluation of SPD3 on programs that use async, finish, and isolated constructs shows that SPD3 performs well in practice, incurring an average (geometric mean) slowdown of 2.78× on a 16- core SMP system for a suite of 15 benchmarks. In contrast, past approaches such as Eraser and FastTrack incurred average overheads that exceed 10× for the same benchmarks and platform. We believe that SPD3 brings us closer to the goal of building dynamic data race detectors that can be “always-on” when developing parallel applications.