Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
2000 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, p. 872-905Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
PHILADELPHIA: SIAM PUBLICATIONS , 2000. p. 872-905
Keywords [en]
cache memory, fully associative cache, set-associative cache, direct-mapped cache, 0, 1-matrices, performance bound, extremal matrices
National Category
Mathematical Analysis Computer Sciences
Identifiers
URN: urn:nbn:se:bth-8138ISI: 000089008300007Local ID: oai:bth.se:forskinfo4C09400216136626C12575B00021294EOAI: oai:DiVA.org:bth-8138DiVA, id: diva2:835827
Available from: 2012-09-18 Created: 2009-05-08 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

No full text in DiVA

Authority records

Lennerstad, HåkanLundberg, Lars

Search in DiVA

By author/editor
Lennerstad, HåkanLundberg, Lars
In the same journal
SIAM journal on computing (Print)
Mathematical AnalysisComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 172 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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