Efficient detection of determinacy races in Cilk programs
M.D. Feng, Charles E. Leiserson · 1997
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.'l%isresearch was supported in PM by tbe Oefense Advanced Research Projects Agency under GrsntNOO014-941 -0985.Mingdong Feng did this work as a Postdoctoral Fellow in the MIT Laboratory for Computer Science.Parsllel computingfacilities were providedby the MSTXOISS Project througha generousdonationby