Parallelizing Compiler: Loop Partitioning
A new technique to parallelize loops with variable distance vectors is
presented. The method extends previous methods in two ways. First, the present
method makes it possible for array subscripts to be any linear combination of
all loop indices. The solutions to the linear dependence equations established
from such array subscripts are characterized by a pseudo distance matrix (PDM).
Second, it allows us to exploit loop parallelism from the PDM by applying
unimodular and partitioning transformations that preserve the lexicographical
order of the dependent iterations. The algorithms to derive the PDM, to find a
suitable loop transformation and to generate parallel code are described,
showing that it is possible to parallelize a wider range of loops
automatically.
The paper has been published in the International Conference on Parallel Processing (ICPP) 2000.
The algorithm has been implemented in the FPT compiler.