Towards Trace-Based Array Contraction

Array contraction is a compilation optimization used to reduce the memory con-sumption, by shrinking the size of temporary arrays while preserving the correctness. The usualapproach to this problem is to perform a static analysis of the given program, creating overhead inthe compilation cycle. In this report, we take a look at exploiting execution traces of programs ofthe polyhedral model, in order to infer reduced sizes for the temporary arrays used during calcu-lations. We designed a five step process to reduce the storage requirements of a temporary arrayof a given scheduled program, in which we used an algorithm to deduce array access functionsfor which bounds are modulos of affine functions of parameters and counters of the program. Ourpreliminary results show reductions of an order of magnitude on several benchmarks examples fromthe polyhedral community.La contraction de tableau est une optimisation de compilation servant à amoindrir les coûts en mémoire, en réduisant la taille des tableaux temporaires sans en altérer l’exactitude du résultat. L’approche habituelle pour ce problème est l’analyse statique du programme, ce qui engendre plus de travail dans le cycle de compilation. Nous étudions les traces d’exécution de programmes du modèle polyédrique, afin d’en inférer des tailles réduites pour ces tableaux temporaires. Nous proposons une méthode en cinq étapes pour réaliser la contraction de tableaux sur un programme déjà ordonné, comprenant l’utilisation d’un algorithme pour déduire des fonctions d’accès aux tableaux affines. Nos résultats préliminaires comprennent des réductions d’un ordre de grandeur sur plusieurs exemples de la communauté polyédrique