[PDF][PDF] A data locality optimizing algorithm
ME Wolf, MS Lam - Proceedings of the ACM SIGPLAN 1991 conference …, 1991 - dl.acm.org
ME Wolf, MS Lam
Proceedings of the ACM SIGPLAN 1991 conference on Programming language …, 1991•dl.acm.orgThis paper proposes an algorithm that improves the local-ity 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 …
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 …
Abstract
This paper proposes an algorithm that improves the local-ity 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.