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.
pdf