Optimal Worst Case Formulas Comparing Cache Memory Associativity

Document type: Researchreports
Full text:
Author(s): Håkan Lennerstad, Lars Lundberg
Title: Optimal Worst Case Formulas Comparing Cache Memory Associativity
Series: Research Report
Year: 1995
Issue: 5
ISSN: 1103-1581
Organization: Blekinge Institute of Technology
Department: Dept. of Telecommunications and Mathematics (Institutionen för telekommunikation och matematik)
Dept. of Telecommunications and Mathematics S-371 79 Karlskrona
+46 455 780 00
Authors e-mail: hakan@itm.hk-r.se, lasse@ide.hk-r.se
Language: English
Abstract: 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$

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.
Subject: Computer Science\Computersystems
Mathematics\Discrete Mathematics
Keywords: cache memory, fully assciative cache, set associative cache, direct mapped cache, extremal combinatorics
URN: urn:nbn:se:bth-00049