Detecting Data Races in Parallel Program Executions

Several methods currently exist for detecting data races in an execution of a shared-memory parallel program. Although these methods address an important aspect of parallel program debugging, they do not precisely define the notion of a data race. As a result, it is not possible to precisely state which data races are detected, nor is the meaning of the reported data races always clear. Furthermore, these methods can sometimes generate false data race reports. They can determine whether a data race was exhibited during an execution, but when more than one data race is reported, only limited indication is given as to which ones are real. This paper addresses these two issues. We first present a model for reasoning about data races, and then present a two-phase approach to data race detection that attempts to validate the accuracy of each detected data race. Our model of data races distinguishes among those data races that actually occurred during an execution (actual data races), those that could have occurred because of timing variations (feasible data races), and those that appeared to have occurred (apparent data races). The first phase of our two-phase approach to data race detection is similar to previous methods and detects a set of data race candidates (the apparent data races). We prove that this set always contains all actual data races, although it may contain other data races, both feasible and infeasible. Unlike previous methods, we then employ a second phase which validates the apparent data races by attempting to determine which ones are feasible. This second phase requires no more information than previous methods collect, and involves making a conservative estimate of the data dependences among the shared data to determine how these dependences may have constrained alternate orderings potentially exhibited by the execution. Each apparent data race can then be characterized as either being feasible, or as belonging to a set of apparent data races where at least one is feasible