Compiler optimizations for improving data locality
Steve Carr, Kathryn S. McKinley, Chau‐Wen Tseng · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · 1994
In the past decade, processor speed has become significantly faster than memory speed. Small, fast cache memories are designed to overcome this discrepancy, but they are only effective when programs exhibit data locality. In this paper, we present compiler optimizations to improve data locality based on a simple yet accurate cost model. The model computes both temporal and spatial reuse of cache lines to find desirable loop organizations. The cost model drives the application of compound transformations consisting of loop permutation, loop fusion, loop distribution, and loop reversal. We demonstrate that these program transformations are useful for optimizing many programs.
Cited by 291 works. doi:10.1145/195473.195557 Open-access PDF
Authors
References
- Dependence graphs and compiler optimizations
- A data locality optimizing algorithm
- The cache performance and optimizations of blocked algorithms
- Strategies for cache and local memory management by global program transformation
- Supernode partitioning
- Improving register allocation for subscripted variables
- Practical dependence testing
- Strategies for cache and local memory management by global program transformation
- Estimating interlock and improving balance for pipelined architectures
- Iteration Space Tiling for Memory Hierarchies