A tile selection algorithm for data locality and cache interference
Jacqueline Chame, Sungdo Moon · International Conference on Supercomputing · 1999
Loop tiling is a well-known compiler transformation that increases data locality, exposes parallelism and reduces synchronization costs.Tiling increases the amount of data reuse that can be exploited by reordering the loop iterations so that accesses to the same data are closer together in time.However, tiled loops often suffer from cache interference in the direct-mapped or low-associativity caches typically found in state-of-the-art microprocessors.A solution to this problem is to choose a tile size that does not exhibit self interference.In this paper, we propose a new tile selection algorithm for eliminating self interference and simultaneously minimizing capacity and cross-interference misses.We have automated the algorithm in the SUIF compiler and used it to generate tiles for a range of problem sizes for three scientific computations.Our experimental results show that the algorithm consistently finds tiles that yield lower miss rates than existing tile selection algorithms.
Cited by 65 works. doi:10.1145/305138.305245 Open-access PDF
Authors
References
- The cache performance and optimizations of blocked algorithms
- Internal organization of the Alpha 21164, a 300-MHz 64-bit quad-issue CMOS RISC microprocessor
- More iteration space tiling
- Tile size selection using cache organization and data layout
- On estimating and enhancing cache effectiveness
- Improving locality and parallelism in nested loops
- Cache miss equations
- To copy or not to copy
- Precise miss analysis for program transformations with caches of arbitrary associativity
- Improving data locality for caches