Appeared in the Proceedings of Parallel Architectures and Compilation Techniques ’99. 1 Localizing Non-affine Array References

Existing techniques can enhance the locality of arrays indexed by affine functions of induction variables. This pa-per presents a technique to localize non-affine array ref-erences, such as the indirect memory references common in sparse-matrix computations. Our optimization combines elements of tiling, data-centric tiling, data remapping and inspector-executor parallelization. We describe our technique, bucket tiling, which includes the tasks of permutation generation, data remapping, and loop regeneration. We show that profitability cannot gener-ally be determined at compile-time, but requires an exten-sion to run-time. We demonstrate our technique on three codes: integer sort, conjugate gradient, and a kernel used in simulating a beating heart. We observe speedups of 1.91 on integer sort, 1.57 on conjugate gradient, and 2.69 on the heart kernel. 1