Polytrace project

The Polytrace project is a research project dedicated to studying the use of dynamic analysis to infer compiler optimizations on programs of the polyhedral model. It is funded by INRIA Lyon and co-directed by Christophe Alias and Keiji Kimura. Hugo Thievenaz is a PhD student and contributor to this project.

The polyhedral model encapsulates both the representation of programs as parametric polyhedra, and the optimizations techniques enabled by such framework. All-affine loop nests are represented as polytopes over integer points, or equivalently as systems of affine equations. This makes the loop nests predictable and enables static analysis of the loops, leading to optimization through affine transformations (scheduling, tiling, array contraction, ...). However, those static approaches use potentially costly operations (projection of polyhedra, ILP solving, ...).

Our project is aimed at using dynamic analysis instead: we analyse the program's execution trace to infer polyhedral optimizations. Our first tool, PoLA, is a polyhedral dynamic analyser whose goal is to perform storage optimization, i.e. to reduce the memory footprint of a program by contracting temporary arrays as much as possible.

PoLA: A dynamic analysis tool for array contraction

PoLA is a storage optimizer for polyhedral programs written in C(++). It takes the latter as input and outputs valid reduced memory mappings for the temporary arrays of the program. The use of dynamic analysis is to compute those optimizations faster in both wall-clock and CPU time compared to static polyhedral analysers.

Publications