A data locality optimizing algorithm
Monica S. Lam, Michael E. Wolf · ACM SIGPLAN Notices · 2004
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 algorithm 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 transformations.The algorithm has 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 locality optimization is especially crucial for scaling up the performance of parallel code.
Cited by 38 works. doi:10.1145/989393.989437
Authors
References
- A set of level 3 basic linear algebra subprograms
- Theory of Linear and Integer Programming
- A data locality optimizing algorithm
- The cache performance and optimizations of blocked algorithms
- Organizing matrices and matrix operations for paged memory systems
- Strategies for cache and local memory management by global program transformation
- A loop transformation theory and an algorithm to maximize parallelism
- Supernode partitioning
- More iteration space tiling
- Global optimizations for parallelism and locality on scalable parallel machines