J.S. Harper, D.J. Kerbyson and G.R. Nudd, Predicting the Cache Miss Ratio of Loop-Nested Array References (December 5, 1997).
The time a program takes to execute can be massively affected by the efficiency with which it utilizes cache memory. Moreover the cache-miss behavior of a program can be highly unpredictable, in that small changes to input parameters can cause large changes in the number of misses. In this paper we present novel analytical models of the cache behavior of programs consisting mainly of array operations inside nested loops, for direct-mapped caches. The models are used to predict the miss-ratios of three example loop nests; the results are shown to be largely within ten percent of simulated values. A significant advantage is that the calculation time is proportional to the number of array references in the program, typically several orders of magnitude faster than traditional cache simulation methods.