Aller au contenu principal

Auguste Olivry

Mercredi 8 Juin 2022

Automatic derivation of I/O complexity bounds for affine programs

Evaluating the complexity of an algorithm is an important step when developing applications, as it impacts both its time and energy performance. Computational complexity, which is the number of arithmetic operations of a program, is easy to characterize for affine programs, that are composed of simple loops with static bounds. Data movement (or, I/O) complexity is more complex to evaluate as it refers, when considering all possible valid schedules, to the minimum required number of I/O between a slow memory with large capacity, and a fast storage location with limited capacity.

This thesis presents IOOpt, a fully automated tool that automatically
computes symbolic bounds on the I/O complexity of an affine program.
Given a description of an affine program, it automatically computes:
1. a lower bound of the I/O complexity as a symbolic expression of the cache size and program parameters;
2. an upper bound that allows one to assess the tightness of the lower bound;
3. a tiling recommendation (loop permutation and tile sizes) that matches the upper bound.
This tool is implemented as an open-source program, and a demonstration is available at .
This was made possible by combining advanced mathematical results with
powerful program analysis tools such as polyhedral representation.
Our data movement model is notably based on the one designed by Hong & Kung (red-blue pebble game), adapted to be able de decompose and recompose complex programs.

We demonstrate the effectiveness of our approach by deriving symbolic bounds for a wide range of affine programs. In many cases, the bounds found by IOOpt can be proven optimal, or close to optimal by a constant factor.

Date et Lieu

Mercredi 8 Juin 2022 à 10h30
Auditorium Bâtiment IMAG

Composition du Jury

Sebastian HACK
Professeur, Universität des Saarlandes, Rapporteur
Directrice de recherche, Inria Paris, Rapportrice
Professeure, Université Grenoble Alpes, Examinatrice
Associate professor, Indian Institute of Science, Examinateur
PhD, Cerebras Systems, Examinateur
Directeur de recherche, Inria Grenoble, Directeur de thèse

Publié le 2 juin 2022

Mis à jour le 2 juin 2022