The research for the automatic parallelization of loops has to face many optimization problems that seem, a priori, very different, such as the detection of parallelism in loops (scheduling, software pipelining), the choice of the parallelism grain (tiling, partitioning), the choice of the data mapping (alignment, distribution). However, all these problems have a common characteristic: the search space (a priori infinite) can always be captured through a finite structure:

• lattices described by a system of generators,
• polyhedra described by inequations, or by vertices, rays, and lines,
• cyclic graphs with basis of cycles.

This comes from the underlying repetitive structure of loops, that can generate a non-bounded (often parameterized) number of operations with a finite code (a loop).

In this talk, we give a summary of useful mathematical tools on matrices, polyhedra, lattices and graphs, and we illustrate, through a few examples, how they can contribute to solve or to classify some optimization problems related to the automatic parallelization of nested loops.

Back to Workshop Schedule

1996-1997 Mathematics in High Performance Computing