Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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
Abstract : 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.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Alain Darte Connect in order to contact the contributor
Submitted on : Wednesday, January 6, 2016 - 7:12:40 PM
Last modification on : Wednesday, October 26, 2022 - 8:14:23 AM
Long-term archiving on: : Friday, April 15, 2016 - 4:50:23 PM


Files produced by the author(s)


  • HAL Id : hal-01251868, version 1


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



Record views


Files downloads