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 metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-01251868
Contributor : Alain Darte <>
Submitted on : Wednesday, January 6, 2016 - 7:12:40 PM
Last modification on : Wednesday, November 20, 2019 - 2:59:21 AM
Long-term archiving on: Friday, April 15, 2016 - 4:50:23 PM

File

RR-8840.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01251868, version 1

Collections

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⟩

Share

Metrics

Record views

308

Files downloads

280