- Authors:
- Hsueh Lu,
- Philip N. Klein,
- Robert H.B. Netzer
We address a problem arising in debugging parallel programs, detecting race conditions in programs using a single semaphore for synchronization. It is NP-complete to detect races in programs that use many semaphores. For the case of a single semaphore, we give an algorithm that takes $O(n^{1.5} p)$ time, where $p$ is the number of processors and $n$ is the total number of semaphore operations executed. Our algorithm constructs a representation from which one can determine in constant time whether a race exists between two given events.
Recommendations
What are race conditions?: Some issues and formalizations
In shared-memory parallel programs that use explicit synchronization, race conditions result when accesses to shared memory are not properly synchronized. Race conditions are often considered to be manifestations of bugs, since their presence can cause ...
Detecting Race Conditions in One-Sided Communication of MPI Programs
ICIS '09: Proceedings of the 2009 Eigth IEEE/ACIS International Conference on Computer and Information ScienceWhile one-sided communication introduced in MPI-2 is convenient to access remote memory, it is easier for programmers to make serious errors such as race conditions. Although there are several tools for detecting race conditions in MPI programs, these ...
Parallel data race detection for task parallel programs with locks
FSE 2016: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software EngineeringProgramming with tasks is a promising approach to write performance portable parallel code. In this model, the programmer explicitly specifies tasks and the task parallel runtime employs work stealing to distribute tasks among threads. Similar to ...