Exact Analysis of the Cache Behavior of Nested Loops

Description

In class, we presented several models for predicting cache performance. These models were ad-hoc, in the sense that they required certain methods of reasoning about asymptotic functions that is not easily automated.

Sid Chatterjee, et al., have a paper in PLDI'01 that shows how cache misses can be counted exactly, using Presburger arithmetic to model cache behavior. Presberger arithmetic is a subset of the first order logic with equality or inequality constraints on integer variables. The Omega library can be used to manipulate and simplify Presberger formula.

There are two issue left open by this paper. First, the authors validate their approach using cache simulation and not experimentation on real hardware. Second, the authors demonstrate their work as a standalone piece, and not part of a transforming compiler.

Project Goals

There are two goals,

• To verify the authors' model experimentally, using cache miss measurements taken from real hardware.
• To see if this approach for predicting cache performance can be used to guide a transforming compiler.

What You Need To Do

• Read and understand the paper.
• Using the Omega calculator, develop Presberger formula that predict the performance of a number of benchmark codes. Compare these predictions with performance measurements taken using CPUMON or PERFMON on real hardware.
• Write code that will analyze a loop nest and form the Omega queries necessary for predicting its performance. Use this analysis to picking "optimal" loop orderings for a tiling transformation in SUIF.

References

• Exact Analysis of the Cache Behavior of Nested Loops, Chatterjee, et al.