Automatic Parallelization of Loop Programs for Distributed Memory Architectures
Martin Griebl · 2004
Parallel computers, especially in the form of clusters of standard PCs, have become reasonably cheap within the last few years. It is an obvious desire to use the increased computation power of such parallel hardware in order to speed up any given application. However, for that purpose, these application programs must be transformed such that they take benefit of the parallel hardware. One solution to generate the necessary parallel software is to use automatic parallelization, i.e., a parallelizing compiler. Such a tool takes a program in which nothing is specified about parallelism, and automatically transforms it to a parallel program. This idea allows to introduce parallelism easily, i.e., without much effort and, simultaneously, with guaranteed correctness with respect to the input program. This thesis presents a way to build up such a parallelizing compiler. In order to be efficient, we restrict ourselves to arbitrarily nested loops as the only control structure causing repeated computations. We apply a mathematical model, the polyhedron model, that gives a unified framework for the various parallelization tasks, and that allows a directed search for optimal solutions. We touch