On ReLooper

Retrofitting parallelism into existing sequential applications is likely to be successful only for certain classes of problems such as for example the so-called embarrassingly parallel problems. These are problems where either computations are large, data sets are large, or some combination of the two, and where the processing that goes on is easily divisible. Re-architecting a complete system for parallelism may take significant amounts of time and efforts. When possible, refactoring for parallelism by using a refactoring tool is a good choice.

The paper introduces ReLooper, an Eclipse based refactoring tool for Java that reduces the burden of analyzing and rewriting parallel loops, and is fast enough to be used interactively. There are two ways in which ReLooper helps Java programmers who want to parallelize their programs by using ParallelArray: it helps them discover when parallelizing a loop is unsafe and it performs the messy conversion of the loop, selecting a good operator from the 132 that come with ParallelArray.

ReLooper relies on Java’s ParallelArray. There are many libraries that target concurrency and parallelism (e.g., Java's ParallelArray, Microsoft's TPL, Intel's TBB, OpenMP, MPI, etc.). The disadvantage of using such a library directly is that the parallel constructs provided by libraries are in general more verbose than parallel constructs provided by programming languages, thus they require many code changes. This is where a refactoring tool comes in handy. In addition, these libraries assume that all parallel computations do not interfere with each other, so they run without any synchronization. It is the programmer’s responsibility to verify non-interference; and this is why ReLooper is interactive, with minimal user input.

Automatic loop parallelization has been a long time topic in the Fortran community, with compilers having various degrees of success. Much of this work is done in the context of numerical computation on scalar arrays and does not deal with the problems posed by sharing heap-allocated array elements, which are common to object oriented languages.

Automatic parallelizing compilers perform full program analysis to find loops that can be safely and automatically parallelized. In contrast ReLooper attempts to parallelize loops explicitly chosen by the programmer, employing a demand driven analysis to signal problems that the human may have missed. The aim here is to quickly and correctly identify dependencies for most cases occurring in practice.

Some of the transformations presented in the paper make the code harder to understand (e.g., replacing a loop with a parallel operation). ReLooper infers the parallel operations based on the kind of array accesses in the loop. If a loop contains accesses triggering more than one operation, ReLooper chooses the most specific operation. This is both simpler to understand, and is faster at runtime.