Precise miss analysis for program transformations with caches of arbitrary associativity
Somnath Ghosh, Margaret Martonosi, Sharad Malik · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · 1998
Analyzing and optimizing program memory performance is a pressing problem in high-performance computer architec-tures. Currently, software solutions addressing the processor-memory performance gap include compiler- or programmer-applied optimizations like data structure padding, matrix blocking, and other program transformations. Compiler op-timization can be effective, but the lack of precise analysis and optimization frameworks makes it impossible to confi-dently make optimal, rather than heuristic-based, program transformations. Imprecision is most problematic in situa-tions where hard-to-predict cache conflicts foil heuristic ap-proaches. Furthermore, the lack of a general framework for compiler memory performance analysis makes it impossi-ble to understand the combined effects of several program transformations. The Cache Miss Equation (CME) framework discussed in this paper addresses these issues. We express memory ref-erence and cache conflict behavior in terms of sets of equa-tions. The mathematical precision of CMEs allows us to find true optimal solutions for transformations like block-ing or padding. The generality of CMEs also allows us to reason about interactions between transformations applied in concert. Unlike our prior work, this framework applies to caches of arbitrary associativity. This paper also demon-strates the utility of CMEs by presenting precise algorithms for intra-variable padding, inter-variable padding, and se-lecting tile sizes. Our experiences with CMEs implemented in the SUIF system show that they are a unifying mathemat-ical framework offering the generality and precision impera-tive for compiler optimizations on current high-performance architectures. 1
Cited by 118 works. doi:10.1145/291069.291051
Authors
References
- Computer Architecture: A Quantitative Approach
- Computer architecture (2nd ed.): a quantitative approach
- Automatic translation of FORTRAN programs to vector form
- A data locality optimizing algorithm
- The cache performance and optimizations of blocked algorithms
- Design and evaluation of a compiler algorithm for prefetching
- SUIF
- More iteration space tiling
- The Omega test: a fast and practical integer programming algorithm for dependence analysis
- A practical algorithm for exact array dependence analysis