MemoryHierarchyReview1Outline7.1IntroductionPrincipleofLocalityMemoryHierarchy7.2BasicofCacheDirectedMappedCacheBitsinaCacheCacheWriteCacheMissesMultiwordCacheBlock7.3CachePerformanceImproveCachePerformanceMemoryisaBottleneckFullyAssociativeCacheSetAssociativeCacheMulti-LevelCache7.1PrincipleofLocalityProgramaccessarelativelysmallportionoftheiraddressspaceatanyinstantoftimeTwokindoflocality:1.TemporallocalityIfanitemisreferenced,itwilltendtobereferencedagainsoon2.SpatiallocalityIfanitemisreferenced,itemswhoseaddressareclosebywilltendtobereferencedsoon7.1MemoryHierarchy–Speedvs.SizeMemoryTypeDiskDRAMSRAM7.1MemoryHierarchy-OperationIfdataisfound(hit)transfertoprocessor,otherwise(miss)transferdatatoupperlevel.AccesstimeHittimeMisspenaltyUserswantlargeandfastmemories!

SRAMaccesstimesare2-25nsatcostof$100to$250perMbyte.

DRAMaccesstimesare60-120nsatcostof$5to$10perMbyte.

Diskaccesstimesare10to20millionnsatcostof$.10to$.20perMbyte.

Tryandgiveittothemanywaybuildamemoryhierarchy7.1MemoryHierarchy7.2CacheCacheMemoryhierarchybetweenCPUandmainmemoryThestoragemanagedtotakeadvantageoflocalityofaccessCachetwoissuesHowdoweknowifadataitemisinthecache?TagandvalidbitIfitis,howdowefindit?MappedapproachesHowdoescacheworkexampleAddXntocacheDirectMappingmapmanymemorywordsontoonelocationincacheAddressismodulothenumberofblocksinthecache(blockaddress)modulo(no.ofcacheblocksinthecache)Example:Cachehas8wordMapping=blockaddressmodule87.2DirectMappedCache7.2DirectMappedCacheTwoissues1.Whichmemorywordinthecache?Usetagtoidentify2.Whetherthememoryblockisvalid?Ex.Initially,thecacheisemptyUsevalidbittoidentifyThusthecachedatastructurearevalidtagdataword…CacheIndex7.2DirectMappedCacheIfatagismatchedandvalidbitison

ThenarequesthitTagiscomparedwithupperportionofaddressReadhitsReadvaliddataoncacheReadmissesstalltheCPU,fetchblockfrommemory,delivertocache,restart

Writehitscanreplacedataincacheandmemory(write-through)writethedataonlyintothecache(write-backthecachelater)

Writemissesreadtheentireblockintothecache,thenwritetheword7.2CacheReadWriteTerminology7.2CacheWriteIssuesTwocachewritescheme:1.WritebackWhenwriteoccurs,onlywritetothecache2.WritethroughWhenwriteoccurs,writetothecacheandmemoryWrite-backproblemcacheandmemoryinconsistence,andcomplextoimplementEx.Whenacacheentryisreplaced,itmustupdatethecorrespondingmemoryaddressWrite-throughproblemWritingtomainmemoryslowsdowntheperformanceEx.CPIwithoutcachemiss=1.2clockcycleswritetomemorycausesextra10cycles13%storeinstructionsingccSolution:writebuffer,storethedataintowritebufferwhilethedataiswaitingtobewrittentomemoryTheprocesscancontinueexecutionafterwritingdataintocacheandwritebuffer7.2DirectMappedCacheCacheExampleonDECstation3100UseMIPSR2000CPU64KBdata98KBcachesize

7.2MultiwordCacheBlockTakeadvantageofspatiallocalityWithacachemiss,wewillfetchmultiplewordsthatareadjacentIncreasingtheblocksizetendstodecreasemissrate:

Usesplitcachesbecausethereismorespatiallocalityincode:

7.2Performance–Missratevs.BlocksizeImprovementoninstructionmissMakereadingmultiplewordseasierbyusingbanksofmemory

7.2Memorysystem-hardwareIssues7.3ImproveCachePerformanceThreewaysLargercacheSetassociativecacheReducecachemissrateNewplacementruleotherthandirectmappingMulti-levelcacheReducecachemisspenalty7.3FlexiblePlacementofBlocksTherearetwomoreflexibleschemes,thendirectedmappedSetassociativecacheFullyassociativecacheExample:block12addressisplacedin8blockcachePlace12%8=4Place12%4=0DirectmappedSetassociativeFullyassociativePlacedanyatblock7.3FullyAssociativecacheAnextremeschemeAmemorydatacanbeplacedinanyblockinthecacheDisadvantage:SearchallentriesinthecacheforamatchParallelcomparators7.3SetAssociativeCacheBetweendirectmappedandfull-associativeAmemorydatacanbeplacedinasetofblocksinthecache(address)modulo(numberofsetsincache)Ex:12modulo4=0Disadvantage:SearchallentriesinthesetforamatchParallelcomparators7.3EightBlockCacheConfigurationTotalsizeofcacheinblocksisequaltothenumberofsetsThus,forfixedcachesize,increaseassociativitydecreasesthenumberofset,butincreasenumberofelementinaset7.3MissRatewithAssociativityHigherdegreeofassociativityLowermissrateMorehardwarecosttosearch7.3Implementationof4-waySet-AssociativeCacheParallelcomparators7.3UseMulti-LevelCachetoReduceMissPenaltyAddasecondlevelcache:oftenprimarycacheisonthesamechipastheprocessoruseSRAMstoaddanothercacheaboveprimarymemory(DRAM)misspenaltygoesdownifdataisin2ndlevelcacheUsingmultilevelcaches:tryandoptimizethehittimeonthe1stlevelcachetryandoptimizethemissrateonthe2ndlevelcachePrimarycache(L1)Secondarycache(L2)L1cachemissL2cachemissCachehit7.3DecreasingMissPenaltywithMultilevelCachesAddasecondlevelcache:oftenprimarycacheisonthesamechipastheprocessoru