A data locality optimizing algorithm
By Michael E. Wolf, Monica S. Lam. 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 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.
Subfields: ML Systems & Hardware
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In ML Systems & Hardware
Citations in the corpus
- FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022, neutral): “…this work [1], but concepts of memory hierarchies are fundamental and has appeared in many forms, from the working set model [23], to data locality [90], to the Roofline model of arithmetic intensity [89], to analyses of scalability [61], to standard textbook treatments of computer architecture…”
- A practical automatic polyhedral parallelizer and locality optimizer (2008, background): “Tiling [28, 58, 61] is a key transformation in optimizing for parallelism and data locality.”
- Tile size selection using cache organization and data layout (1995, background): “Much previous work focuses on how to do the loop nest restructuring step in tiling [CK92, CL95, IT88, GJG88, WL91 , Wol89].”