Change search
ReferencesLink to record
Permanent link

Direct link
Optimal Worst Case Formulas Comparing Cache Memory Associativity
Responsible organisation
1995 (English)Report (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Blekinge Tekniska Högskola Forskningsrapport, ISSN 1103-1581 ; 5
Keyword [en]
cache memory, fully assciative cache, set associative cache, direct mapped cache, extremal combinatorics
National Category
Mathematical Analysis Computer Science
URN: urn:nbn:se:bth-00049Local ID: diva2:837444
Available from: 2012-09-18 Created: 2000-03-15 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

fulltext(439 kB)29 downloads
File information
File name FULLTEXT01.pdfFile size 439 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links$file/cacherev2.tex

Search in DiVA

By author/editor
Lennerstad, HåkanLundberg, Lars
Mathematical AnalysisComputer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 29 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 17 hits
ReferencesLink to record
Permanent link

Direct link