Parallel LoopsReLooper: Refactoring for Loop Parallelism



Problem Description

In the multicore era, sequential programs need to be refactored for parallelism. The next version of Java provides ParallelArray, an array data structure that supports parallel operations over the array elements. For example, one can apply a procedure to each element, or reduce all elements to a new element in parallel. Refactoring an array to a ParallelArray requires (i) analyzing whether the loop iterations are safe for parallel execution, and (ii) replacing loops with the equivalent parallel operations. When done manually, these tasks are non-trivial and time-consuming. We present ReLooper, an Eclipse-based refactoring tool, that performs these tasks automatically. Experience with refactoring real programs shows that ReLooper is useful: it reduces the burden of analyzing and rewriting parallel loops, and it is fast enough to be used interactively.


Using ReLooper

ReLooper is implemented as an Eclipse plugin that extends Eclipse's refactoring engine. The process of using ReLooper has two steps. In the first step, the programmer (who understands the problem domain) expresses the intent to parallelize some loops by selecting an array (from now on simply referred as the target array) and the ConvertToParallelArray operation from the refactoring menu. ReLooper analyses whether the loops intended for parallelism can be safely parallelized and reports to the programmer any potential problems, e.g., data races in the to-be parallelized loops. The programmer can decide to ignore the warnings and to proceed to the next step, or she can cancel the current refactoring, fix the problems, then re-run ReLooper.

In the second step, the programmer confirms the changes that she intends ReLooper to apply. For each loop, there are two choices: (i) replace the loop with the parallel operation, or (ii) leave the loop sequential, but replace accesses to the indexed elements from the target array with indexed elements from ParallelArray. By default, ReLooper chooses the first choice for those loops where it did not find any problems, and chooses the second choice for loops where it found problems. The programmer can overwrite ReLooper's default selection, and choose to parallelize some loops, but leave others sequential.


Below is a screenshot of ReLooper in action.





When a loop intended for parallelism might have a conflicting memory update (e.g., data-races between loop iterations), ReLooper helps the programmer identify the problem. The screenshot below shows the stack of the statements that participate in the race. The statement where the race manifests is on the top of the stack. The statements that contribute to the flow of shared objects into the loop appear on the bottom of the stack.



Download and Install

ReLooper requires that you use Eclipse 3.5. We are currently working on releasing ReLooper as an open-source Eclipse plugin (under the Eclipse Public License). Please check this page again for the source release. Meanwhile, you can use the binary distribution. To use ReLooper, download the distribution archive. Unpack the archive. It contains three jar files: edu.uiuc.parallelArray (the main ReLooper code), and two other jar files, com.ibm.wala.core and com.ibm.wala.shrike, from the WALA open source library for static analysis. Copy these three jar files into your Eclipse's plugins directory, then restart Eclipse. If the installation is successfull, you will see the new menu entry "Concurrency Refactorings" in the context menu (i.e., right-click) of a selected array field.

Publications

More details about the safety analysis can be found in our technical report.

If you are at OOPSLA'09, you can attend two demos of ReLooper: Demo sessions 1 and 2.

Testimonials

This is what Doug Lea, the architect of the ParallelArray library, says about ReLooper:

"I was very impressed when Danny demoed ReLooper a few weeks ago at OOPSLA.
Some of the sample refactored programs are realistic enough that I expect it
will be useful to just about anyone interested in exploring these forms of
parallelization"

You can read Doug's full post here.

Team

Acknowledgements

Feedback

If you found ReLooper useful, we would love to hear from you. Please send constructive feedback to Danny Dig.