Paper Info
Title
Test-driven repair of data races in structured parallel programs
Abstract
A common workflow for developing parallel software is as follows: 1) start with a sequential program, 2) identify subcomputations that should be converted to parallel tasks, 3) insert synchronization to achieve the same semantics as the sequential program, and repeat steps 2) and 3) as needed to improve performance. Though this is not the only approach to developing parallel software, it is sufficiently common to warrant special attention as parallel programming becomes ubiquitous. This paper focuses on automating step 3), which is usually the hardest step for developers who lack expertise in parallel programming. Past solutions to the problem of repairing parallel programs have used static-only or dynamic-only approaches, both of which incur significant limitations in practice. Static approaches can guarantee soundness in many cases but are limited in precision when analyzing medium or large-scale software with accesses to pointer-based data structures in multiple procedures. Dynamic approaches are more precise, but their proposed repairs are limited to a single input and are not reflected back in the original source program. In this paper, we introduce a hybrid static+dynamic test-driven approach to repairing data races in structured parallel programs. Our approach includes a novel coupling between static and dynamic analyses. First, we execute the program on a concrete test input and determine the set of data races for this input dynamically. Next, we compute a set of \"finish\" placements that prevent these races and also respects the static scoping rules of the program while maximizing parallelism. Empirical results on standard benchmarks and student homework submissions from a parallel computing course establish the effectiveness of our approach with respect to compile-time overhead, precision, and performance of the repaired code.
Year
DOI
Venue
2014
10.1145/2594291.2594335
PLDI
Keywords
Field
DocType
parallel program,parallel programming,dynamic approach,dynamic test-driven approach,structured parallel program,data race,test-driven repair,parallel computing course,parallel software,original source program,sequential program,async
Asynchronous communication,Pointer (computer programming),Data structure,Synchronization,Programming language,Computer science,Real-time computing,Software,Soundness,Workflow,Semantics
Conference
Volume
Issue
ISSN
49
6
0362-1340
Citations 
PageRank 
References 
8
0.50
20
Authors
5
Name
Order
Citations
PageRank
Rishi Surendran1211.70
Raghavan Raman223510.70
Swarat Chaudhuri398167.68
John Mellor-Crummey486876.69
Vivek Sarkar54318409.41