Automatic Storage Optimization for Arrays

Somashekaracharya Bhaskaracharya 1 Uday Bondhugula 1 Albert Cohen 2
2 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : Efficient memory allocation is crucial for data-intensive applications as a smaller memory footprint ensures better cache performance and allows one to run a larger problem size given a fixed amount of main memory. In this paper, we describe a new automatic storage optimization technique to minimize the dimensionality and storage requirements of arrays used in sequences of loop nests with a predetermined schedule. We formulate the problem of intra-array storage optimization as one of finding the right storage partitioning hyperplanes: each storage partition corresponds to a single storage location. Our heuristic is driven by a dual objective function that minimizes both, the dimensionality of the mapping and the extents along those dimensions. The technique is dimension optimal for most codes encountered in practice. The storage requirements of the mappings obtained also are asymptotically better than those obtained by any existing schedule-dependent technique. Storage reduction factors and other results we report from an implementation of our technique demonstrate its effectiveness on several real-world examples drawn from the domains of image processing, stencil computations, high-performance computing, and the class of tiled codes in general .
Type de document :
Article dans une revue
ACM Transactions on Programming Languages and Systems (TOPLAS), ACM, 2016, 38, pp.1 - 23. 〈10.1145/2845078〉
Liste complète des métadonnées
Contributeur : Albert Cohen <>
Soumis le : mardi 3 janvier 2017 - 16:08:42
Dernière modification le : mardi 24 avril 2018 - 17:20:14
Document(s) archivé(s) le : mardi 4 avril 2017 - 14:40:16


Fichiers produits par l'(les) auteur(s)




Somashekaracharya Bhaskaracharya, Uday Bondhugula, Albert Cohen. Automatic Storage Optimization for Arrays. ACM Transactions on Programming Languages and Systems (TOPLAS), ACM, 2016, 38, pp.1 - 23. 〈10.1145/2845078〉. 〈hal-01425564〉



Consultations de la notice


Téléchargements de fichiers