bringphysicalmemory

Lecture20:CacheHierarchies,VirtualMemoryToday'stopics:CachehierarchiesVirtualmemoryReminder:Assignment8willbepostedsoon(dueTue11/21)ExampleAccessPattern8-bytewords101000Direct-mappedcache:eachaddressmapstoauniqueaddressByteaddressTagCompareDataarrayTagarrayAssumethataddressesare8bitslongHowmanyofthefollowingaddressrequestsarehits/misses4,7,10,13,16,68,73,78,83,88,4,7,10…IncreasingLineSize32-bytecachelinesizeorblocksize10100000ByteaddressTagDataarrayTagarrayOffsetAlargecachelinesizesmallertagarray,fewermissesbecauseofspatiallocalityAssociativity10100000ByteaddressTagDataarrayTagarraySetassociativityfewerconflicts;wastedpowerbecausemultipledataandtagsarereadWay-1Way-2CompareAssociativity10100000ByteaddressTagDataarrayTagarrayHowmanyoffset/index/tagbitsifthecachehas64sets,eachsethas64bytes,4waysWay-1Way-2CompareExample32KB4-wayset-associativedatacachearraywith32bytelinesizesHowmanysetsHowmanyindexbits,offsetbits,tagbitsHowlargeisthetagarrayCacheMissesOnawritemiss,youmayeitherchoosetobringtheblockintothecache(write-allocate)ornot(write-no-allocate)Onareadmiss,youalwaysbringtheblockin(spatialandtemporallocality)–butwhichblockdoyoureplacenochoiceforadirect-mappedcacherandomlypickoneofthewaystoreplacereplacethewaythatwasleast-recentlyused(LRU)FIFOreplacement(round-robin)WritesWhenyouwriteintoablock,doyoualsoupdatethecopyinL2write-through:everywritetoL1writetoL2write-back:marktheblockasdirty,whentheblockgetsreplacedfromL1,writeittoL2WritebackcoalescesmultiplewritestoanL1blockintooneL2writeWritethroughsimplifiescoherencyprotocolsinamultiprocessorsystemastheL2alwayshasacurrentcopyofdataTypesofCacheMissesCompulsorymisses:happensthefirsttimeamemorywordisaccessed–themissesforaninfinitecacheCapacitymisses:happensbecausetheprogramtouchedmanyotherwordsbeforere-touchingthesameword–themissesforafully-associativecacheConflictmisses:happensbecausetwowordsmaptothesamelocationinthecache–themissesgeneratedwhilemovingfromafully-associativetoadirect-mappedcacheVirtualMemoryProcessesdealwithvirtualmemory–theyhavetheillusionthataverylargeaddressspaceisavailabletothemThereisonlyalimitedamountofphysicalmemorythatissharedbyallprocesses–aprocessplacespartofitsvirtualmemoryinthisphysicalmemoryandtherestisstoredondisk(calledswapspace)Thankstolocality,diskaccessislikelytobeuncommonThehardwareensuresthatoneprocesscannotaccessthememoryofadifferentprocessAddressTranslationThevirtualandphysicalmemoryarebrokenupintopagesVirtualaddress8KBpagesizepageoffsetvirtualpagenumberTranslatedtophysicalpagenumberPhysicaladdress13MemoryHierarchyPropertiesAvirtualmemorypagecanbeplacedanywhereinphysicalmemory(fully-associative)ReplacementisusuallyLRU(sincethemisspenaltyishuge,wecaninvestsomeefforttominimizemisses)Apagetable(indexedbyvirtualpagenumber)isusedfortranslatingvirtualtophysicalpagenumberThepagetableisitselfinmemoryTLBSincethenumberofpagesisveryhigh,thepagetablecapacityistoolargetofitonchipAtranslationlookasidebuffer(TLB)cachesthevirtualtophysicalpagenumbertranslationforrecentaccessesATLBmissrequiresustoaccessthepagetable,whichmaynotevenbefoundinthecache–twoexpensivememorylook-upstoaccessonewordofdata!
AlargepagesizecanincreasethecoverageoftheTLBandreducethecapacityofthepagetable,butalsoincreasesmemorywastageTLBandCacheIsthecacheindexedwithvirtualorphysicaladdressToindexwithaphysicaladdress,wewillhavetofirstlookuptheTLB,thenthecachelongeraccesstimeMultiplevirtualaddressescanmaptothesamephysicaladdress–mustensurethatthesedifferentvirtualaddresseswillmaptothesamelocationincache–else,therewillbetwodifferentcopiesofthesamephysicalmemorywordDoesthetagarraystorevirtualorphysicaladdressesSincemultiplevirtualaddressescanmaptothesamephysicaladdress,avirtualtagcomparisoncanflagamissevenifthecorrectphysicalmemorywordispresentCacheandTLBPipelineTLBVirtualaddressTagarrayDataarrayPhysicaltagcomparionVirtualpagenumberVirtualindexOffsetPhysicalpagenumberPhysicaltagVirtuallyIndexed;PhysicallyTaggedCacheBadEventsConsiderthelongestlatencypossibleforaloadinstruction:TLBmiss:mustlookuppagetabletofindtranslationforv.
pagePCalculatethevirtualmemoryaddressforthepagetableentrythathasthetranslationforpageP–let'ssay,thisisv.
pageQTLBmissforv.
pageQ:willrequirenavigationofahierarchicalpagetable(let'signorethiscasefornowandassumewehavesucceededinfindingthephysicalmemorylocation(R)forpageQ)AccessmemorylocationR(findthiseitherinL1,L2,ormemory)Wenowhavethetranslationforv.
pageP–putthisintotheTLBWenowhaveaTLBhitandknowthephysicalpagenumber–thisallowsustodotagcomparisonandchecktheL1cacheforahitIfthere'samissinL1,checkL2–ifthatmisses,checkinmemoryAtanypoint,ifthepagetableentryclaimsthatthepageisondisk,flagapagefault–theOSthencopiesthepagefromdisktomemoryandthehardwareresumeswhatitwasdoingbeforethepagefault…phew!
TitleBullet