Lightweight fault detection in parallelized programs

A popular approach for producing parallel software is to de-velop a sequential version of an application and then incre-mentally introduce parallel constructs to parallelize differ-ent parts of the application. During the parallelization pro-cess, programming errors may be introduced, causing con-currency bugs. In this paper we develop a technique for run-time detection of data dependence faults (i.e., data races and atomicity violations) introduced during parallelization. By leveraging the availability of two versions of the program, the sequential one and the parallelized one, we comparison check dynamic data dependences exercised during execu-tions of the two versions to identify faults. To reduce the cost of comparison checking we develop three optimizations. The first optimization causes only a sub-set of dynamically exercised data dependences to be com-parison checked. The second optimization shows that not all instances of a dynamically exercised data dependence need to be comparison checked. The third optimization shows that static analysis of parallelizing constructs can be exploited to eliminate the need for executing the parallelized version al-together. In addition, our solution is applicable when differ-ent program executions on the same input may follow dif-ferent execution paths, it is effective in situations where the fault introduced manifests itself rarely during execution, and it is also effective in pinpointing the location of the fault in the program. We implemented and evaluated our approach using ten benchmarks. The experimental results indicate an average slowdown of 3x to perform fault detection