Main navigation | Main content

HOME » PROGRAMS/ACTIVITIES » Annual Thematic Program

PROGRAMS/ACTIVITIES

Annual Thematic Program »Postdoctoral Fellowships »Hot Topics and Special »Public Lectures »New Directions »PI Programs »Industrial Programs »Seminars »Be an Organizer »Annual »Hot Topics »PI Summer »PI Conference »Applying to Participate »

Talk Abstract

Some Optimization Problems Related to Automatic Parallelization

Some Optimization Problems Related to Automatic Parallelization

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