A data locality optimizing algorithm
Michael E. Wolf, Monica S. Lam · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 1991
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.
Cited by 1,331 works. doi:10.1145/113445.113449 Open-access PDF
Authors
References
- Matrix Computations
- Theory of Linear and Integer Programming
- A set of level 3 basic linear algebra subprograms
- The cache performance and optimizations of blocked algorithms
- Dependence Analysis for Supercomputing
- 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
- Software methods for improvement of cache performance on supercomputer applications