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:
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