A common workflow in developing parallel software is as follows: 1) start with a sequential program, 2) identify sequential subcomputations that can be converted to parallel tasks, 3) insert synchronization to achieve the same semantics as 1), and 4) 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 so as to warrant special attention. The focus of this paper is on automating step 3), since that is often the hardest step for developers who lack expertise in parallel programming. For example, errors in step 3) can lead to data races, which are known to be a pernicious source of bugs in parallel software.
Past work has advocated the use of refactoring tools to assist developers with complex programming tasks. In this paper, we introduce a refactoring tool that can help programmers insert synchronization in step 3) so as to avoid data races and guarantee determinism. Our approach assumes a task-parallel programming model based on terminally-strict parallelism with async and finish (or similar) constructs as in Chapel, Habanero-Java, and X10. In our workflow, a programmer starts by writing an unsynchronized (or under-synchronized) parallel program, and provides a test input to the refactoring tool. The tool sequentially executes the program with the provided input and identifies all potential data races in that execution. If any races are observed during the execution, our refactoring tool will determine where additional synchronization should be inserted so as to eliminate the races while minimizing the loss of parallelism due to synchronization. This methodology can be applied iteratively until no more races are observed for a given set of inputs.