Optimal worst case formulas comparing cache memory associativity

Document type: Journal Articles
Article type: Original article
Peer reviewed: Yes
Author(s): Håkan Lennerstad, Lars Lundberg
Title: Optimal worst case formulas comparing cache memory associativity
Journal: SIAM JOURNAL ON COMPUTING
Year: 2000
Pagination: 872-905
ISSN: 0097-5397
Publisher: SIAM PUBLICATIONS
City: PHILADELPHIA
ISI number: 000089008300007
Organization: Blekinge Institute of Technology
Department: Dept. of Telecommunications and Mathematics (Institutionen för telekommunikation och matematik)
Dept. of Telecommunications and Mathematics S-37179 Karlskrona
+46 455 38 50 00
Language: English
Abstract: 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.
Subject: Computer Science\Computersystems
Mathematics\Discrete Mathematics
Keywords: cache memory, fully associative cache, set-associative cache, direct-mapped cache, 0, 1-matrices, performance bound, extremal matrices
Edit