Detecting Nondeterminism in Shared Memory Parallel Programs
Bud Mishra, Anne Dinning · 2011
This thesis addresses the problem of detecting of a specific type of nondeterminism in shared memory parallel programs known as access anomalies. An access anomaly occurs when an update to a shared variable X is concurrent with either a read of X or another update of X. The first part of the work considers dynamic detection of access anomalies. We introduce a new technique called task recycling that detects access anomalies on the fly by monitoring the program execution. This technique is designed with two goals in mind. The first goal is minimal monitoring cost. Costs re incurred only at thread create, terminate, and coordinate operations and every time a monitored variable is accessed. Because variable accesses are generally the most frequent operation, the task recycling technique reduces the overhead per variable access to a small constant. The second goal is generality. The task recycling technique is applicable to a wide variety of parallel constructs and all common synchronous and asynchronous coordination primitives. Combined with a protocol for specifying ordering constraints, the method of representing concurrency relationships in task recycling can be extended to detect general race conditions in parallel programs. The second part of the thesis involves static detection of several types of nondeterminism that makes dynamic anomaly detection inefficient. In particular, the notion of nondeterminism arising from critical section coordination is refined by distinguishing between three types of nondeterminism--parallel, sequential, and reference nondeterminism. The advantage of this classification si that we are able to efficiently detect all three types of nondeterminism. The presence of these types of nondeterminism in a program impacts access anomaly detection in two significant ways: (i) how critical section coordination is modeled during anomaly detection, and (ii) the confidence level and complexity of guaranteeing that a program has no access anomalies. In particular, it is shown that access anomalies can be detected efficiently only if a program is parallel, sequential and reference deterministic. Heuristics are presented that make access anomaly detection tractable in the presence of other nondeterminism through a better classification and semantic understanding of a coordination protocol.