Augmenting loop tiling with data alignment for improved cache performance
- 1 February 1999
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 48 (2), 142-149
- https://doi.org/10.1109/12.752655
Abstract
Loop blocking (tiling) is a well-known compiler optimization that helps improve cache performance by dividing the loop iteration space into smaller blocks (tiles); reuse of array elements within each tile is maximized by ensuring that the working set for the tile fits into the data cache. Padding is a data alignment technique that involves the insertion of dummy elements into a data structure for improving cache performance. In this work, we present DAT, a technique that augments loop tiling with data alignment, achieving improved efficiency (by ensuring that the cache is never under-utilized) as well as improved flexibility (by eliminating self-interference cache conflicts independent of the tile size). This results in a more stable and better cache performance than existing approaches, in addition to maximizing cache utilization, eliminating self-interference, and minimizing cross-interference conflicts. Further, while all previous efforts are targeted at programs characterized by the reuse of a single array, we also address the issue of minimizing conflict misses when several tiled arrays are involved. To validate our technique, we ran extensive experiments using both simulations as well as actual measurements on SUN Sparc5 and Sparc10 workstations. The results on benchmarks exhibiting varying memory access patterns demonstrate the effectiveness of our technique through consistently high hit ratios and improved performance across varying problem sizes.This publication has 9 references indexed in Scilit:
- Compiler blockability of numerical algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Lazy prefetchingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Improving cache performance through tiling and data alignmentLecture Notes in Computer Science, 1997
- Tile size selection using cache organization and data layoutPublished by Association for Computing Machinery (ACM) ,1995
- Cache profiling and the SPEC benchmarks: a case studyComputer, 1994
- To copy or not to copyPublished by Association for Computing Machinery (ACM) ,1993
- A data locality optimizing algorithmPublished by Association for Computing Machinery (ACM) ,1991
- The cache performance and optimizations of blocked algorithmsPublished by Association for Computing Machinery (ACM) ,1991
- More iteration space tilingPublished by Association for Computing Machinery (ACM) ,1989