Data locality is a key issue to high performance, for either uniprocessors and multiprocessors. Both hand-tuning and compiler optimization techniques are often used to improve data locality. Effective transformations require detailed knowledge about the frequency and causes of cache misses in the code.
Cache Miss Equations (CME) is a framework that provides a detailed representation of the cache misses in loop-oriented scientific applications. Computing the solutions of cache miss equations for a particular reference inside a loop nest allows to determine the number of misses. Unfortunately, computing the number of solutions is an NP-hard problem.
In this work we use statistical methods to compute the number of solutions. Our approach mantains the accuracy of CME and is computationally tractable. For each reference, a confidence interval with a bounded error is given instead the exact miss ratio. It is possible to tune the computation time by adjusting the width of the interval.
We have evaluated the approach on loops from 7 SPECfp95 programs representing more than 70% of the execution time. More than 200 loops have been analyzed, with an interval width of 0.05 and a confidence of 95%, in less than 15 minutes. In all the cases, the misses obtained by simulation belong to the confidence interval.