Tile size selection using cache organization and data layout
Stephanie Coleman, Kathryn S. McKinley · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 1995
When dense matrix computations are too large to fit in cache, previous research proposes tiling to reduce or eliminate capacity misses. This paper presents a new algorithm for choosing problem-size dependent tile sizes based on the cache size and cache line size for a direct-mapped cache. The algorithm eliminates both capacity and self-interference misses and reduces cross-interference misses. We measured simulated miss rates and execution times for our algorithm and two others on a variety of problem sizes and cache organizations. At higher set associativity, our algorithm does not always achieve the best performance. However on direct-mapped caches, our algorithm improves simulated miss rates and measured execution times when compared with previous work.
Cited by 402 works. doi:10.1145/207110.207162
Authors
References
- Graduate Texts in Mathematics
- Cache Memories
- Graduate Texts in Mathematics
- 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
- More iteration space tiling
- Compiler optimizations for improving data locality
- To copy or not to copy