Optimal Worst Case Formulas Comparing Cache Memory Associativity

Consider an arbitrary program $P$ which is to be executed on a computer with two alternative cache memories. The first cache is set associative or direct mapped. It has $k$ sets and $u$ blocks in each set, this is called a (k,u)$-cache. The other is a fully associative cache with $q$ blocks - a $(1,q)$-cache. We present formulas optimally comparing the performance of a $(k,u)$-cache compared to a $(1,q)$-cache for worst case programs. Optimal mappings of the program variables to the cache blocks are assumed. Let $h(P,k,u)$ denote the number of cache hits for the program $P$, when using a $(k,u)$-cache and an optimal mapping of the program variables of $P$ to the cache blocks. We establish an explicit formula for the quantity $$\inf_P \frac{h(P,k,u)}{h(P,1,q)},$$ where the infimum is taken over all programs $P$ which contain $n$ variables. The formula is a function of the parameters $n,k,u$ and $q$ only. We also deduce a formula for the infimum taken over all programs of any number of variables, this formula is a function of $k,u$ and $q$. We further prove that programs which are extremal for this minimum may have any hit ratio, i.e. any ratio $h(P,1,q)/m(P)$. Here $m(P)$ is the total number of memory references for the program P. We assume the commonly used LRU replacemant policy, that each variable can be stored in one memory block, and is free to be stored in any block. Since the problems of finding optimal mappings are NP-hard, the results provide optimal bounds for NP-hard quantities. The results on cache hits can easily be transformed to results on access times for different cache architectures