Near-optimal allocation of local memory arrays

scratch pad memory, affine reference This paper considers compiler management of fast, local memories for loop nests that contain affine array references. We show how to reduce the local memory footprint of such arrays by doing an affine reindexing of the array elements. We approximate the best reindexing by a two-step algorithm. The first step uses a generalized Hermite factorization, and the second uses a one-norm lattice basis reduction technique. We improve on earlier work in which a local memory array stores the smallest rectangular subarray of the elements referenced in the loop nest. Our techniques apply directly to nests with families of uniformly generated affine references, and we propose ways to extend them to more general situations