The cache performance and optimizations of blocked algorithms
Monica D. Lam, Edward E. Rothberg, Michael E. Wolf · ACM SIGARCH Computer Architecture News · 1991
Blocking is a well-known optimization technique for improving the effectiveness of memory hierarchies.Instead of operating on entire rows or columns of an array, blocked algorithms operate on submatrices or blocks, so that data loaded into the faster levels of the memory hierarchy are reused.This paper presents cache performance data for blocked programs and evaluates several optimization to improve this performance.The data is obtained by a theoretical model of data conflicts in the cache, which has been validated by large amounts of simulation.We show that the degree of cache interference is highly sensitive to the stride of data accesses and the size of the blocks, and can cause wide variations in machine performance for different matrix sizes.The conventional wisdom of frying to use the entire cache, or even a fixed fraction of the cache, is incorrect.If a fixed block size is used for a given cache size, the block size that minimizes the expected number of cache misses is very small.Tailoring the block size according to the matrix size and cache parameters can improve the average performance and reduce the variance in performance for different matrix sizes.Finally, whenever possible, it is beneficial to copy non-contiguous reused data into consecutive locations.
Cited by 25 works. doi:10.1145/106975.106981 Open-access PDF
Authors
References
- A set of level 3 basic linear algebra subprograms
- Organizing matrices and matrix operations for paged memory systems
- Strategies for cache and local memory management by global program transformation
- I/O complexity
- The Characteristics of Parallel Algorithms.
- Automatic program transformations for virtual memory computers
- Improving register allocation for subscripted variables