Automatic Parallelization: Executing Sequential Programs on a Task-Based Parallel Runtime
Authors
Abstract
There are billions of lines of sequential code inside nowadays' softwarewhich do not benefit from the parallelism available in modern multicore
architectures. Automatically parallelizing sequential code, to promote an
efficient use of the available parallelism, has been a research goal for some
time now. This work proposes a new approach for achieving such goal. We created
a new parallelizing compiler that analyses the read and write instructions, and
control-flow modifications in programs to identify a set of dependencies
between the instructions in the program. Afterwards, the compiler, based on the
generated dependencies graph, rewrites and organizes the program in a
task-oriented structure. Parallel tasks are composed by instructions that
cannot be executed in parallel. A work-stealing-based parallel runtime is
responsible for scheduling and managing the granularity of the generated tasks.
Furthermore, a compile-time granularity control mechanism also avoids creating
unnecessary data-structures. This work focuses on the Java language, but the
techniques are general enough to be applied to other programming languages. We
have evaluated our approach on 8 benchmark programs against OoOJava, achieving
higher speedups. In some cases, values were close to those of a manual
parallelization. The resulting parallel code also has the advantage of being
readable and easily configured to improve further its performance manually.