Laboratoire d'Informatique de Grenoble

Abstract:
=========
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 https://iocomplexity.corse.inria.fr/ .
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.