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||URI:||http://scholarbank.nus.edu.sg/handle/10635/99506|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.