# Optimal worst case formulas comparing cache memory associativity

Document type: Journal Articles Original article Yes Håkan Lennerstad, Lars Lundberg Optimal worst case formulas comparing cache memory associativity SIAM JOURNAL ON COMPUTING 2000 872-905 0097-5397 SIAM PUBLICATIONS PHILADELPHIA 000089008300007 Blekinge Institute of Technology Dept. of Telecommunications and Mathematics (Institutionen för telekommunikation och matematik)Dept. of Telecommunications and Mathematics S-37179 Karlskrona+46 455 38 50 00 English In this paper we derive a worst case formula comparing the number of cache hits for two different cache memories. From this various other bounds for cache memory performance may be derived. Consider an arbitrary program P which is to be executed on a computer with two alternative cache memories. The rst 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 derive an explicit formula for the ratio of the number of cache hits h(P, k, u) for a(k, u)-cache compared to a (1, q)-cache for a worst case program P. We assume that the mappings of the program variables to the cache blocks are optimal. The formula quantifies the ratio [GRAPHICS] where the in mum is taken over all programs P with n variables. The formula is a function of the parameters n, k, u, and q only. Note that the quantity h ( P, k, u) is NP-hard. We assume the commonly used LRU (least recently used) replacement policy, that each variable can be stored in one memory block, and that each variable is free to be mapped to any set. Since the bound is decreasing in the parameter n, it is an optimal bound for all programs with at most n variables. The formula for cache hits allows us to derive optimal bounds comparing the access times for cache memories. The formula also gives bounds ( these are not optimal, however) for any other replacement policy, for direct-mapped versus set-associative caches, and for programs with variables larger than the cache memory blocks. Computer Science\ComputersystemsMathematics\Discrete Mathematics cache memory, fully associative cache, set-associative cache, direct-mapped cache, 0, 1-matrices, performance bound, extremal matrices