Precise miss analysis for program transformations with caches of arbitrary associativity
Somnath Ghosh, Margaret Martonosi, Sharad Malik · 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