Extended Lattice-Based Memory Allocation

Alain Darte 1 Alexandre Isoard 1, 2 Tomofumi Yuki 1
1 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Résumé : 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.
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01251868
Contributeur : Alain Darte <>
Soumis le : mercredi 6 janvier 2016 - 19:12:40
Dernière modification le : samedi 21 avril 2018 - 01:27:17
Document(s) archivé(s) le : vendredi 15 avril 2016 - 16:50:23

Fichier

RR-8840.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01251868, version 1

Citation

Alain Darte, Alexandre Isoard, Tomofumi Yuki. Extended Lattice-Based Memory Allocation. [Research Report] RR-8840, CNRS; ENS Lyon; Inria. 2015, pp.31. 〈hal-01251868〉

Partager

Métriques

Consultations de la notice

262

Téléchargements de fichiers

109