Extended Lattice-Based Memory Allocation
Technique étendue d’allocation mémoire basée sur les réseaux entiers
Résumé
This work extends lattice-based memory allocation, an earlier work on memory (array)
reuse analysis. The main motivation is to handle in a better way the more general forms of
specifications we see today, e.g., with loop tiling, pipelining, and other forms of parallelism available
in explicitly parallel languages. Our extension has two complementary aspects. We show how
to handle more general specifications where conflicting constraints (those that describe the array
indices that cannot share the same location) are specified as a (non-convex) union of polyhedra.
Unlike convex specifications, this also requires to be able to choose suitable directions (or basis) of
array reuse. For that, we extend two dual approaches, previously proposed for a fixed basis, into
optimization schemes to select suitable basis. Our final approach relies on a combination of the
two, also revealing their links with, on one hand, the construction of multi-dimensional schedules
for parallelism and tiling (but with a fundamental difference that we identify) and, on the other
hand, the construction of universal reuse vectors (UOV), which was only used so far in a specific
context, for schedule-independent mapping.
Ce travail étend l’allocation mémoire basée sur les réseaux entiers
précédemment proposée en analyse de réutilisation mémoire (de tableaux). La
motivation principale est de traiter de meilleure façon les formes plus générales
de spécifications rencontrées aujourd’hui, comportant du tuilage de boucles,
du pipeline, et d’autres formes de parallélisme exprimées dans les langages à
parallélisme explicite. Notre extension a deux aspects complémentaires. Nous
montrons comment nous pouvons prendre en compte des spécifications plus
générales où les contraintes de conflit (celles qui décrivent les indices de tableaux
qui ne peuvent pas partager le même emplacement mémoire) sont spécifiées par
une union (non-convexe) de polyèdres. Au contraire des spécifications convexes,
ceci requiert d’être capable de choisir des directions (c’est-à-dire une base)
adéquates de réutilisation des cases de tableaux. Pour cela, nous étendons deux
approches duales, précédemment proposées pour une base fixée, en des schémas
d’optimisation permettant de choisir des bases adaptées. Notre approche finale
consiste en une combinaison des deux approches, révélant également des liens
avec, d’une part, la construction d’ordonnancements multi-dimensionnels pour le
parallélisme et le tuilage (avec une différence fondamentale que nous identifions)
et, d’autre part, la construction de vecteurs de réutilisation universelle (UOV),
qui étaient utilisés jusqu’à présent uniquement dans un contexte spécifique, celui
des allocations valides pour tout ordonnancement.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...