As multi-core processors become more common and cloud computing gains
acceptance, more applications are run in a shared cache environment.
Cache sharing depends on a concept called footprint, which depends on
cache accesses not just cache misses.  Previous work has recognized
the importance of footprint but has not provided a method for accurate
measurement, mainly because the complete measurement requires
measuring all execution windows, and all-window profiling would take
time quadratic to the length of a trace.

We first present an algorithm efficient enough for off-line use to
approximately measure the footprint with a guaranteed precision.  The
cost of the analysis can be adjusted by changing the precision.  Then
a composable model is proposed.  For a set of programs, the model uses
the all-window footprint of each program to predict its cache
interference with other programs without running these programs
together.  We evaluate the efficiency of all-window profiling using
the SPEC 2000 benchmarks and compares the footprint interference model
with a miss-rate based model through exhaustive testing.