Automatic Intra-Array Storage Optimization

Somashekaracharya G Bhaskaracharya, Uday Bondhugula & Albert Cohen

Abstract: Efficient memory allocation is crucial for data-intensive applications as a smaller memory footprint ensures better cache performance and also allows more applications to fit in memory. In this report, we describe a new automatic storage optimization technique to minimize the dimensionality and storage requirements of array variables in a sequence of loop nests with a pre-determined schedule. We view the problem of intra-array storage optimization as one of finding the right storage partitioning hyperplanes: each storagepartition corresponds to a single storage location. Our heuristic is driven by a dual objective function that minimizes both the dimensionality of the obtained mapping and the degree of contraction along those dimensions. The technique is dimension optimal for most codes encountered in practice. We discuss several examples from real-world applications from the domains of image processing, stencil computations, high-performance computing, and the class of tiled codes in general, where our technique leads to storage mappings whose storage requirements are asymptotically better than those obtained by any existing technique.