Detecting Nondeterminism in Shared Memory Parallel Programs
Author: Anne Dinning
Advisor: Bud Mishra


Abstract

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 overhead. Costs are incurred only at thread create, terminate, and coordinate operations cind 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 appllicable to a wide variety of parallel constructs find all common synchronous and asynchronous coordination primitives. Combined with a protocol for specifying ordering constraints, the method of representing concurrency relationships in task recycling cam be extended to detect general race conditions in parallel programs.

The second pait of the thesis involves static detection of several types of nondeterminism that makes dynamic anomcily detection inefficient. In particulair, the notion of nondeterminism arising from critical section coordination is refined by distinguishing between three types of nondeterminism parallel, sequential, and reference 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 amd semantic understanding of a coordination protocol.