On-the-fly detection of data races for programs with nested fork-join parallelism

Detecting data races in shared-memory parallel programs is an important debugging problem. This paper presents a new protocol for run-time detection of data races in executions of shared-memory programs with nested fork-join parallelism and no other interthread synchronization. This protocol has significantly smaller worst-case run-time overhead than previous techniques. The worst-case space required by our protocol when monitoring an execution of a program P is O(VN), whereV is the number of shared variables in P,andN is the maximum dynamic nesting of parallel constructs in P ’s execution. The worst-case time required to perform any monitoring operation is O(N). We formally prove that our new protocol always reports a non-empty subset of the data races in a monitored program execution and describe how this property leads to an effective debugging strategy. 1