Abstract Efficient Detection of Determinacy Races in Cilk Programs

A parallel multithreaded program that is ostensibly deterministic may nevertheless behave nondeterministically due to bugs in the code. These bugs are called determinacy races, and they result when one thread updates a location in shared memory while another thread is concurrently accessing the location. We have implemented a provabl y efficient determinacy-race detector for Cilk, an algorithmic multithreaded programming language. If a Cilk program run on a given input data set has a determinacy race, our debugging tool, which we call the “Nondeterrninator, ” guarantees to detect and localize the race. The core of the Nondeterrninator is an asymptotically efficient serial algorithm (inspired by Tarjan’s nearly linear-time leastcommon-ancestors algorithm) for detecting deterrninacy races in series-parallel directed acyclic graphs. For a Cilk program that runs in T time on one processor and uses v shared-memory locations, the Nondeterminator runs in 0 ( Tct(v, v)) time, where ct is Tarjan’s functional inverse of Ackermann’s function, a very slowly growing function which, for all practical purposes, is bounded above by 4. The Nondeterminator uses at most a constant factor more space than does the original program. On a variety of Cifk program benchmarks, the Nondeterminator exhibits a slowdown of less than 12 compared with the serial execution time of the original optimized code, which we contend is an acceptable slowdown for debugging purposes.