Y. He, J. Wang, and W.J. Hsu (Singapore)
Algorithm, race detection, debugging, parallel programming.
We present a novel dynamic on-the-fly race detection mech anism called Parallel Nondeterminator to check for determi nacy races during the parallel execution of a program with Spawn-Sync parallelism. The Parallel Nondeterminator pro vides provable correctness and efficiency. Let D denote the maximum depth of the recursion in the parallel program. The worst case slowdown in execution incurred for each spawn operation is O(D), the overhead for each sync operation is O(1) and the time required to monitor any shared memory access is O(log D). Moreover, we have implemented the Par allel Nondeterminator in Cilk, a parallel language developed at MIT. Both theoretical and experimental results give strong evidences for the efficiency of our algorithm.
Important Links:
Go Back
