Efficient analytical modelling of multi-level set-associative caches

The time a program takes to execute is significantly affected by the efficiency with which it utilises cache memory. Moreover the cache miss behaviour of a program is highly unstable, in that small changes to input parameters can cause large changes in the number of misses. In this paper we describe novel analytical methods of predicting the cache miss ratio of numerical programs, for sequential hierarchies of set-associative caches. The methods are demonstrated to be applicable to most loop nests. They are also shown to be highly accurate, yet able to be evaluated orders of magnitude faster than a comparable simulation