Automated cache optimizations using CME driven diagnosis

Determining the exact cause of poor cache behavior and then transforming code accordingly is crucial to compile-time improvements in program cache behavior. This paper presents an efficient and effective diagnosis framework to determine the causes of poor cache behavior and automatically select appropriate cache transformations. The framework is based on the Cache Miss Equations (CMEs). Introduced in our prior work, CMEs axe a precise, analytical representation of cache misses in a loop nest; each CME solution point represents a potential cache miss. The diagnosis framework demonstrated in this paper introduces the concept of the CME Solution Table. The CME solution table summarizes the CME solution counts for all the CMEs in a loop nest. The key concept of our diagnosis framework is to recognize telltale patterns in the CME table that correspond to poor cache behavior. Based on the solution pattern observed, the diagnosis framework selects the appropriate optimizing transformation. Because counting CME solutions is time-consuming, we use a sampled version of the CME solution table. The results in this paper show that the sampled version quite accurately portrays the patterns present in the original table. This paper demonstrates our diagnosis framework on several examples. The framework selects from transformations including loop permutation, array padding, and loop tiling. Although these transformations are not new, the goal of our work is to provide a direct and accurate mechanism for determining when to apply them and in what order. To our knowledge, ours is the first diagnosis framework to directly target both capacity and conflict misses. Demonstrating our framework on a collection of scientific loop nests, we were able to reduce an average of 84% of cache misses in the optimizable loop nests. This work lays the groundwork for handling a wide range of optimizations through further study of solution patterns in the CME solution table.