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.