Scribd
Upload
74 views4 pages

Lesson 3 4 Cache Oblivious Algorithms: The Ideal Cache Model

This document discusses cache-oblivious algorithms and the ideal cache model. It introduces some key concepts: 1. Cache-aware algorithms are optimized for a specific cache size L, while cache-oblivious algorithms do not reference the cache parameters (z,L) and aim to perform well on any cache. 2. The ideal cache model assumes the cache size L is equal to the transfer size, with a fully associative cache and optimal replacement policy. 3. Under this model, accessing a value is a cache hit if in cache and miss if not, requiring a full line transfer from slow to fast memory on a miss.

Uploaded by

Projectlouis
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
74 views4 pages

Lesson 3 4 Cache Oblivious Algorithms: The Ideal Cache Model

This document discusses cache-oblivious algorithms and the ideal cache model. It introduces some key concepts: 1. Cache-aware algorithms are optimized for a specific cache size L, while cache-oblivious algorithms do not reference the cache parameters (z,L) and aim to perform well on any cache. 2. The ideal cache model assumes the cache size L is equal to the transfer size, with a fully associative cache and optimal replacement policy. 3. Under this model, accessing a value is a cache hit if in cache and miss if not, requiring a full line transfer from slow to fast memory on a miss.

Uploaded by

Projectlouis
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Lesson34CacheObliviousAlgorithms

Inacacheawarealgorithm,thevalueofLisdeterminedbythecachesize.
Q
(nzL)= (n/L)
aware

Ifthealgorithmmakesnoreferencetofastmemoryoritsparameters(z,L)thenthealgorithm
isoblivious(tofastmemory).

Q
(nzL)=O(n/L)
oblivious

Therearetwoquestionsthatneedtobeasked.

1. Howdowemodelautomaticfastmemory?
2. CananobliviousalgorithmmatchI/Operformanceofanawarealgorithm?

TheIdealCacheModel

Thisistheidealcachemodelthatwillbeusedin
thelesson.

TheListhesameasthetransfersize.


Inaprogramloadsandstoresareissuedfortheslow
memoryaddress.
Forexample:
Theprogramwantstoloadavaluefrommemorya.
Firstitcheckstoseeifthevalueofaisinfastmemory.
Ifitis,itjustusesitthisisacachehit.

Acachemissoccurswhenthevalueisnotinthe
[Link]
andacopyisstoredinfastmemory.

Thehardwaremuststoreanentirecachelineofdata,soothermemoryvaluesaroundthe
desiredmemorylocationwillalsoberetrievedandstoredfrommemory.

Forastoreinstruction:
Ifthevalueisinthecache,[Link]
slowmemory.

Ifthestorevalueisnotinthecache,thisisacachemiss.
Foracachemisstheentirememorylinemustbetransferredfromslowmemorytothecache.

Theidealcacheisfullyassociative.
Thismeansthetransferfromslowmemoryisallowedtogo
toanylineinthecache.
Atsomepoint,[Link],anoldlinewillhavetobeevicted
fromthecache.
Ifthelinethatistobeevictedhasnotbeenwrittentomemory,[Link]
writtenbeforeitcanbeevicted,thisiscalledastoreeviction.

Optimalreplacementevictlineorblockaccessedfurthestinthefuture.

SummaryofIdealCacheModel
1. Programissuesloadandstoreops
2. HardwaremanagesZ/Lcachelines
3. SlowmemorycachetransfersinlinesorblocksofsizeL
4. Accessingavalueincache=cachehit,otherwiseitisacachemiss
5. Cacheisfullyassociative
6. Assumeoptimalreplacementpolicy

Q(nZ,L)=#misses+storeevictions

LRUleastrecentlyused
Thisreplacementpolicylooksfortheleastrecentlyusedaddresstoevictfromthecache.
LRUwillcausemoreevictionsthatoptimalreplacement.

Howidealistheidealcache?
Keyassumptions:
1. optimalreplacement
2. twolevelsofmemory
3. Automaticreplacement
4. fullyassociative

[Link]
ittoacachethatusesanoptimalreplacementpolicy
thathasthecachesize.

Thislemmacanbeusedinthefollowingway:
[Link]
closetoamodelwithanLRUpolicyandtwicethecache.

Ifyoudesignanalgorithmforanideal
model,ifthemissesareregular,itwill
performinasimilarfashiontotheideal
model.

TheTallCacheAssumption
Thecacheshouldbetaller(withregardstothenumberoflinesz)thanitiswide(thesizeof
thelines,L).
Thismeansanefficientalgorithmmightbelinkedtothechoiceofdatastructure.

You might also like