Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
1995.
Series
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
Identifiers
URN: urn:nbn:se:bth-00049Local ID: oai:bth.se:forskinfoC5DC031C7F31F27FC12568A3002CA9A5OAI: oai:DiVA.org:bth-00049DiVA: diva2:837444
Available from: 2012-09-18 Created: 2000-03-15 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

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

Other links

http://traveler.bth.se/fou/forskinfo.nsf/all/c5dc031c7f31f27fc12568a3002ca9a5/$file/cacherev2.tex

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 65 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: 47 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf