| Because of the ever-widening gap between CPU and memory speeds, programs must effectively utilize the memory hierarchy to attain high performance. To this end, researchers have proposed compiler transformations for improving locality such as loop permutation, loop fusion, and tiling. While these optimizations can improve cache performance for many programs, often they are ineffective due to cache conflict misses. A result of limited set associativity, conflict misses can inhibit both spatial and temporal reuse, degrading program performance. Though compiler techniques have been introduced which address conflict misses, their effectiveness has been limited because they either lack accurate methods for statically detecting conflict misses or because they do not alter the program data layout.; My thesis shows that compilers can eliminate most of the conflict misses common in regular scientific codes through data transformations directed by simple compile-time analyses. Compiler analysis may be simplified by focusing only on reference patterns most likely to cause conflict misses, providing transformations the flexibility to avoid conflict misses across entire applications. Two basic data transformations for controlling conflict misses are inter-variable padding, which adjusts variable base addresses, and intra-variable padding, which changes array dimensions sizes. Practical search strategies enable inter-variable padding algorithms to evaluate a small number of positions for each variable. Intra-variable padding algorithms pad array dimensions incrementally until conflicts are eliminated. Guided by efficient compile-time heuristics, data transformations may be used alone or in conjunction with existing locality transformations such as tiling to eliminate conflict misses. |
