Research Home


Research Areas



Illinois Impact





Participants: Danny Dig and external collaborators Cosmin Radoi, Mihai Tarce, Marius Minea (Politechnica University of Timisoara)

Executive Summary

Build interactive tools that enable programmers to retrofit parallelism into sequential programs incrementally. The programmer selects some code and a target refactoring, and the tool analyzes the safety of the transformation and rewrites the program.

Goals - Extended Description

Parallelizing existing sequential programs to run efficiently on multicores is hard. Several libraries (e.g., TPL, TBB, ForkJoinTask) support writing parallel programs: much of the complexity of writing thread-safe and scalable programs is hidden in the library. To use these libraries, programmers still need to refactor the existing code. This is tedious because it requires changing many lines of code, is error-prone because programmers can use the wrong APIs, and is non-trivial because the programmer still needs to ensure non-interference of parallel constructs.

We are developing a refactoring toolset that enables programmers to refactor sequential code into parallel code that uses the parallel libraries. Our growing refactoring toolset supports data parallelism, task parallelism, and concurrent collections. We are expanding the toolset with both enabling refactorings (i.e., refactorings that make sequential code thread-safe, for example convert mutable classes into immutable classes) and multi-threaded refactorings (i.e., refactoring that transform single-threaded code into multi-threaded code).

We are also exploring bridging the gap between refactoring tools and tools that find performance bottlenecks (e.g., performance profilers). Once we learn about the performance bottlenecks, our tools can suggest parallelizing refactorings.

We are also exploring collaboration between refactoring tools and autotuners (e.g., David Padua's toolset). The refactoring tools can provide explicit "knobs" for autotuners. For example, when parallelizing a divide-and-conquer algorithm, the refactoring tool delegates to the autotuner the task of figuring out the cut-off threshold between the sequential and the parallel case.


Our refactoring toolset currently supports data parallelism (e.g., convert array to Parallelarray), task parallelism (e.g., convert sequential divide-and-conquer to task parallelism), and concurrent collections (e.g., replace primitive types with Atomic types, replace HashMap with ConcurrentHashMap). These automated refactorings do not require any program annotations, yet the transformations span multiple, non-adjacent, program statements. A find-and-replace tool can not perform such transformations, which require control- and data-flow analysis. Empirical evaluation shows that our toolset is useful: it reduces the burden of analyzing and rewriting code, is fast enough to be used interactively, and it correctly identifies and applies transformations that some open-source developers overlooked.

Additional Resources

Autotuning Gluon: Interface for
Trusted Programming
Interactive Porting Libraries Optimizations for Power
Refactoring Safe Parallel Prog. Languages Scheduling Verification & Validation