1;3409;0c A data locality optimizing algorithm

A data locality optimizing algorithm

ACM SIGPLAN Notices, vol. 26, no. 6, 1991
Pages: 30-44DOI: 10.1145/113446.113449



This paper proposes an algorithm that improves the locality of a loop nest by transforming the code via interchange, reversal, skewing and tiling. The loop transformation rrlgorithm is based on two concepts: a mathematical formulation of reuse and locality, and a loop transformation theory that unifies the various transforms as unimodular matrix tmnsfonnations. The algorithm haa been implemented in the SUIF (Stanford University Intermediate Format) compiler, and is successful in optimizing codes such as matrix multiplication, successive over-relaxation (SOR), LU decomposition without pivoting, and Givens QR factorization. Performance evaluation indicates that locatity optimization is especially crucial for scaling up the performance of parallel code