CRPC-TR92232:  Compile-time Support for Efficient Data Race Detection in 
Shared-Memory Parallel Programs

J.M. Mellor-Crummey

September, 1992

Data race detection strategies based on software run time monitoring are 
notorious for dramatically inflating execution times of shared-memory 
parallel programs. Without significant reductions in the execution 
overhead incurred when using these techniques, there is little hope that 
they will be widely used. A promising approach to this problem is to 
apply compile-time analysis to identify variable references that need not 
be monitored at run time because they will never be involved in a data 
race. In this paper we describe ERASER, a data race instrumentation tool 
that uses aggressive program analysis to prune the number of references 
to be monitored. To guantify the effectiveness of our analysis 
techniques, we compare the overhead of race detection with three levels of 
compile-time analysis ranging from little analysis to aggressive 
interprocedural analysis for a suite of test programs. For the programs 
tested, using interprocedural analysis and dependence analysis 
dramatically reduced the data race instrumentation added by ERASER, 
resulting in a corresponding reduction of run-time monitoring overhead.