An empirical comparison of monitoring algorithms for access anomaly detection

Abstract

One of the major disadvantages of parallel programming with shared memory is the nondeterministic behavior caused by uncoordinated access to shared variables, known as access anomalies. Monitoring program execution to detect access anomalies is a promising and relatively unexplored approach to this problem. We present a new algorithm, referred to as task recycling, for detecting anomalies, and compare it to an existing algorithm. Empirical results indicate several significant conclusions: (i) While space requirements are bounded by O(T × V), where T is the maximum number of threads that may potentially execute in parallel and V is the number of variable monitored, for typical programs space requirements are on average O(V). (ii) Task recycling is more efficient in terms of space requirements and often in performance, (iii) The general approach of monitoring to detect access anomalies is practical.