Skip to Main content Skip to Navigation

Lattice-Based Array Contraction: From Theory to Practice

Abstract : We build on prior work on intra-array memory reuse, for which a general theoretical framework was proposed based on lattice theory. Intra-array memory reuse is a way of reducing the size of a temporary array by folding, thanks to affine mappings and modulo operations, reusing memory locations when they contain a value not used later. We describe the algorithms needed to implement such a strategy. Our implementation has two parts. The first part, Bee, uses the source-to-source transformer ROSE to extract from the program all necessary information on the lifetime of array elements and to generate the code after memory reduction. The second part is a stand-alone mathematical tool dedicated to optimizations on polyhedra, in particular the computation of successive minima and the computation of good admissible lattices, which are the basis for lattice-based memory reuse. Both tools are developed in C++ and use linear programming and polyhedra manipulations. These tools can be used either for memory reduction in programs – e.g, to limit memory expansion introduced for parallelization – or for memory reduction in high-level synthesis – e.g., to design adequate memories between communicating hardware accelerators.
Document type :
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Monday, May 13, 2019 - 10:56:13 AM
Last modification on : Thursday, November 21, 2019 - 2:38:41 AM


Files produced by the author(s)


  • HAL Id : hal-02127064, version 1



Christophe Alias, Alain Darte, Fabrice Baray. Lattice-Based Array Contraction: From Theory to Practice. [Research Report] LIP RR-2007-44, LIP - Laboratoire de l’Informatique du Parallélisme. 2007. ⟨hal-02127064⟩



Record views


Files downloads