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 :
Reports
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02127064
Contributor : Colette Orange <>
Submitted on : Monday, May 13, 2019 - 10:56:13 AM
Last modification on : Wednesday, May 15, 2019 - 6:13:31 AM

File

RR2007-44.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02127064, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

13

Files downloads

9