Scribd
Upload
54 views

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
54 views

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
You are on page 1/ 4

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
cache.Thenitmustberetrievedfromslowmemory
andacopyisstoredinfastmemory.

Thehardwaremuststoreanentirecachelineofdata,soothermemoryvaluesaroundthe
desiredmemorylocationwillalsoberetrievedandstoredfrommemory.

Forastoreinstruction:
Ifthevalueisinthecache,itisacachehit.Thevaluewillbeupdatedinthecacheandstoredin
slowmemory.

Ifthestorevalueisnotinthecache,thisisacachemiss.
Foracachemisstheentirememorylinemustbetransferredfromslowmemorytothecache.

Theidealcacheisfullyassociative.
Thismeansthetransferfromslowmemoryisallowedtogo
toanylineinthecache.
Atsomepoint,thecachewillbefull.Sotoloadanewline,anoldlinewillhavetobeevicted
fromthecache.
Ifthelinethatistobeevictedhasnotbeenwrittentomemory,itisdirty.Adirtylinemustbe
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

TakeacachemodelthatusesaLRUpolicy.Compare
ittoacachethatusesanoptimalreplacementpolicy
thathasthecachesize.

Thislemmacanbeusedinthefollowingway:
Designanalgorithmonanidealmodelwithoptimalreplacement.Itshouldbeasymptotically
closetoamodelwithanLRUpolicyandtwicethecache.

Ifyoudesignanalgorithmforanideal
model,ifthemissesareregular,itwill
performinasimilarfashiontotheideal
model.

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

You might also like