Please use this identifier to cite or link to this item:
Title: Efficient detection of determinacy races in Cilk programs
Authors: Feng, Mingdong 
Leiserson, Charles E. 
Issue Date: 1997
Citation: Feng, Mingdong,Leiserson, Charles E. (1997). Efficient detection of determinacy races in Cilk programs. Annual ACM Symposium on Parallel Algorithms and Architectures : 1-11. ScholarBank@NUS Repository.
Abstract: 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 provably 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 `Nondeterminator,' guarantees to detect and localize the race. The core of the Nondeterminator is an asymptotically efficient serial algorithm (inspired by Tarjan's nearly linear-time least-common-ancestors algorithm) for detecting determinacy races in series-parallel directed acyclic graphs. For a Cilk program that runs in T time on one processor and uses ν shared-memory locations, the Nondeterminator runs in O(Tα(ν,ν)) time, where α 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 Cilk 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.
Source Title: Annual ACM Symposium on Parallel Algorithms and Architectures
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.