Lattice-Based Array Contraction: From Theory to Practice

We build on prior work on intra-array memory reuse, for which a general theoretical framework was proposed based on lattice theory. Intra-array memory reuse is a way of reducing the size of a temporary array by folding, thanks to affine mappings and modulo operations, reusing memory locations when they contain a value not used later. We describe the algorithms needed to implement such a strategy. Our implementation has two parts. The first part, Bee, uses the source-to-source transformer ROSE to extract from the program all necessary information on the lifetime of array elements and to generate the code after memory reduction. The second part is a stand-alone mathematical tool dedicated to optimizations on polyhedra, in particular the computation of successive minima and the computation of good admissible lattices, which are the basis for lattice-based memory reuse. Both tools are developed in C++ and use linear programming and polyhedra manipulations. These tools can be used either for memory reduction in programs – e.g, to limit memory expansion introduced for parallelization – or for memory reduction in high-level synthesis – e.g., to design adequate memories between communicating hardware accelerators.Nous étendons les résultats (théoriques) antérieurs concernant la réutilisation mémoire basée sur les réseaux entiers. Celle-ci permet de réduire la taille des tableaux temporaires, grâce à des fonction d’accès affines et des modulos, en réutilisant des cases contenant des valeurs non lues plus tard. Nous décrivons les algorithmes nécessaires pour mettre en œuvre une telle stratégie. La première partie de notre implantation, Bee, utilise la bibliothèque de transformation au niveau source, ROSE, pour extraire du programme les durées de vie des cases des tableaux et pour générer le code après réduction mémoire. La seconde, Cl@k, est un programme indépendant d’optimisations sur les polyèdres, effectuant en particulier le calcul des minima successifs et d’un bon réseau entier admissible, bases de cette réutilisation mémoire. Les deux programmes ont été développés en C++ et utilisent la programmation linéaire et les manipulations de polyèdres. On peut s’en servir soit en optimisation de programmes, par exemple pour limiter l’expansion mémoire introduite par la parallélisation, soit en synthèse de haut niveau, par exemple pour concevoir des mémoires adaptées entre des accélérateurs matériels communicant