Lattice-Based Memory Allocation

Alain Darte (1) , Rob Schreiber (1) , Gilles Villard (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

We investigate the technique of storing multiple array elements in the same memory cell, with the goal of reducing the amount of memory used by an array variable. This reduction is both important and achievable during the synthesis of a dedicated processor or code generation for an architecture with a software-controlled scratchpad memory. In the former case, a smaller, less expensive circuit results; in the latter, scratchpad space is saved for other uses, other arrays most likely. The key idea is that once a schedule of operations has been determined, the schedule of references to a given location is known, and elements with disjoint lifetimes may share a single memory cell, in principle. The difficult problem is one of code generation: how does one generate memory addresses in a simple way, so as to achieve a nearly best possible reuse of memory? Previous approaches to memory reuse for arrays consider some particular affine (with modulo expressions) mapping of indices, representing the data to be stored, to memory addresses. We generalize the idea, and develop a mathematical framework based on critical integer lattices that subsumes all previous approaches and gives new insights into the problem.We place the problem in a broader mathematical context, showing its relation to real critical lattices, successive minima, and lattice basis reduction; finally, we propose and analyze various strategies for lattice-based memory allocation.

Nous explorons le problème de la réutilisation de la mémoire, dans le but de réduire la taille nécessaire pour une variable de type tableau, dans le contexte de la synthèse de processeurs dédiés ou de la compilation vers des architectures possédant des mémoires programmables de type “scratchpad”. Dans le premier cas, le résultat est un circuit plus petit, moins coûteux, dans le second cas, de l’espace mémoire est économisé permettant éventuellement le stockage d’autres tableaux. L’idée est qu’une fois l’ordonnancement des calculs défini, l’ordre des accès à une adresse mémoire donnée est connu, et en principe, des éléments de périodes de vie disjointes peuvent partager une même cellule mémoire. Le problème est celui de la génération de code : comment générer les adresses mémoire pour obtenir le meilleur (ou assez bon) partage de la mémoire ? Toutes les approches précédentes considèrent des fonctions d’adressage particulières,affines avec des opérations modulo, associant `a chaque indice représentant une donnée `a sauvegarder une adresse mémoire. Nous développons un modèle ma-thématique basé sur les réseaux critiques entiers qui nous permet de généraliser toutes ces approches et qui offre de nouvelles vues sur le problème. Notre modélisation montre le lien avec les réseaux critiques, les minima successifs et les réductions de base, et nous permet d’analyser différentes stratégies pour les allocations mémoires construites `a partir de réseaux.

Mots clés: program transformation; admissible lattice; critical determinant; memory allocation; memory size reduction; successive minima

Mots clés: optimisation de programmes; optimisation de mémoire; réseau admissible; minima successifs

Domaines: Informatique [cs]

Alain Darte, Rob Schreiber, Gilles Villard. Lattice-Based Memory Allocation. [Research Report] LIP RR-2004-23, Laboratoire de l'informatique du parallélisme. 2004, 2+43p. ⟨hal-02101912⟩