Detecting Data Races by Analyzing Sequential Traces

This paper describes techniques which automatically detect data races in parallel programs by analyzing program traces. We view a program execution as a partial ordering of events, and define which executions are consistent with a given trace. In general, it is not possible to determine which of the consistent executions occurred. Therefore we introduce the notion of "safe orderings" between events which are guaranteed to hold in every execution which is consistent with the trace. The main result of the paper is a series of algorithms which determine many of the "safe orderings". An algorithm is also presented to distinguish unordered sequential events from concurrent events. A working trace analyzer has been implemented. The trace analyzer can report various data races in parallel programs by finding unordered pairs of events and variable access conflicts. Keywords: data race, time vector, program trace, parallel programming, debugging, distributed systems 1. Introduction