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.