# Optimal Worst Case Formulas Comparing Cache Memory Associativity

Document type: Researchreports cacherev2.texResearch Report 5-95.pdf Håkan Lennerstad, Lars Lundberg Optimal Worst Case Formulas Comparing Cache Memory Associativity Research Report 1995 5 1103-1581 Blekinge Institute of Technology Dept. of Telecommunications and Mathematics (Institutionen för telekommunikation och matematik)Dept. of Telecommunications and Mathematics S-371 79 Karlskrona+46 455 780 00http://www.hk-r.se/itm/index.html hakan@itm.hk-r.se, lasse@ide.hk-r.se English 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. Computer Science\ComputersystemsMathematics\Discrete Mathematics cache memory, fully assciative cache, set associative cache, direct mapped cache, extremal combinatorics urn:nbn:se:bth-00049