Lattice-Based Memory Allocation

Abstract : 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.
Document type :
Reports
Complete list of metadatas

Cited literature [38 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101912
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:09:38 AM
Last modification on : Wednesday, November 20, 2019 - 7:24:04 AM

File

RR2004-23.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101912, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

22

Files downloads

83