计算机组成与结构体系英文课件:Chapter 8 – The Memory System - 2_第1页
计算机组成与结构体系英文课件:Chapter 8 – The Memory System - 2_第2页
计算机组成与结构体系英文课件:Chapter 8 – The Memory System - 2_第3页
计算机组成与结构体系英文课件:Chapter 8 – The Memory System - 2_第4页
计算机组成与结构体系英文课件:Chapter 8 – The Memory System - 2_第5页
已阅读5页,还剩55页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

ComputerOrganization&Architecture

Chapter8–TheMemorySystem-2Contentofthislecture8.5MemoryHierarchyWhyhaveamemoryhierarchy?Whatisamemoryhierarchy?Whydomemoryhierarchieswork?8.6CacheMemoriesMappingSchemeReplacementAlgorithmWritePolicyMemoryHierarchy(1)WhyHaveaMemoryHierarchy?IdeallyInfinitestorageFastCheapCompactColdNon-volatileCan’thaveeverythingBiggerslowerFasterdenserFastermoreexpensiveMemoryHierarchy(2)WhyHaveaMemoryHierarchy?(ctd.)TheCPU-MemoryGapThegapwidensbetweenDRAM,disk,andCPUspeeds.

MemoryHierarchy(3)HowcanWeAchievetheIdeal?Fact:Largememoriesareslow,fastmemoriesaresmall

Howdowecreateamemorythatgivestheillusionofbeinglarge,cheapandfast(mostofthetime)?bytakingadvantageofThePrincipleofLocality(局部性原理):Programsaccessarelativelysmallportionoftheaddressspaceatanyinstantoftime.AddressSpace02n-1ProbabilityofreferenceMemoryHierarchy(4)HowcanWeAchievetheIdeal?(ctd.)ThePrincipleofLocality(ctd.)TemporalLocality–localityintime(时间局部性)Ifitemwasreferencedrecently,itwilllikelybereferencedagainsoon.Spatiallocality–localityinspace(空间局部性)Ifanitemisreferenced,itemsnearitmightbereferencedsoon80/20rule–80%ofthetimeisspentexecuting20%ofthecodeMemoryHierarchy(5)WhatistheMemoryHierarchy?Somefundamentalandenduringpropertiesofhardwareandsoftware:Faststoragetechnologiescostmoreperbyteandhavelesscapacity.ThegapbetweenCPUandmainmemoryspeediswidening.Well-writtenprogramstendtoexhibitgoodlocality.Thesefundamentalpropertiescomplementeachotherbeautifully.Theysuggestanapproachfororganizingmemoryandstoragesystemsknownasamemoryhierarchy.MemoryHierarchy(6)WhatistheMemoryHierarchy?(ctd.)MemoryHierarchy(7)HowistheHierarchyManaged?Registers<->MemoryBycompiler(programmer?)Cache<->MainmemoryBythehardwareMainMemory<->DisksBythehardwareandoperatingsystem(virtualmemory)Bytheprogrammer(files)MemoryHierarchy(8)FourQuestionsforMemoryHierarchyDesignersQ1:Wherecanablockbeplacedintheupperlevel?(Blockplacement)Q2:Howisablockfoundifitisintheupperlevel?

(Blockidentification)Q3:Whichblockshouldbereplacedonamiss?

(Blockreplacement)Q4:Whathappensonawrite?

(Writestrategy)CacheMemories(1)CPU-DRAMGap1980:nocacheinµproc;19952-levelcacheonchip(1989firstIntelµprocwithacacheonchip)DRAM7%/yr.110100100019801981198319841985198619871988198919901991199219931994199519961997199819992000DRAMCPU1982Processor-MemoryPerformanceGap:

(grows50%/year)Performance“Moore’sLaw”µProc60%/yr.CacheMemories(2)PlacementofCacheinaComputerSystemCachememoriesaresmall,fastSRAM-basedmemoriesmanagedautomaticallyinhardware.ServesasabufferbetweenCPUandmainmemoryHoldfrequentlyaccessedblocksofmainmemoryCacheMemories(3)PurposeofCacheMemoryGivemainmemoryspeedapproachingthatofthefastestmemoriesavailable.Atthesametime,providealargememorysizeatthepriceoflessexpensivetypesofsemiconductormemories.StructureofCache/MemorySystemFigureseenextpageCacheMemories(4)StructureofCache/MemorySystem(ctd.)Eachentrycontainsablockfrommainmemory.CopyofcontentsofseveralconsecutivebytesinmainmemoryTagisalsostoredwitheachblock-identifiesaddressesofthesebytesWhenonebytefromablockisneededIfblocknotalreadyincache,entireblockloadedBlockstayedincacheuntilentrymustbereusedCacheMemories(5)CacheReadandWritePoliciesCacheMemories(6)CacheReadFlowchartCacheMemories(7)CacheDesignIssuesWherecanablockbeplacedinacache?MappingSchemeHowisablockfoundifitisinacache?BlockIdentificationWhichblockshouldbeevictedonacachemiss?ReplacementAlgorithmWhathappensonwritehit?Whathappensonwritemiss?WritePolicyCacheMemories(8)MappingSchemeIftheCPUgeneratesanaddressforaparticularwordinmainmemory,andthatdatahappenstobeinthecache,thesamemainmemoryaddresscannotbeusedtoaccessthecache.Henceamappingschemeisrequiredthatconvertsthegeneratedmainmemoryaddressintoacachelocation.Mappingschemealsodetermineswheretheblockwillplacedwhenitoriginallycopiedintothecache.CacheMemories(9)MappingScheme(ctd.)AddressConversionToCacheLocationAddressconversionisdonebygivingspecialsignificancetothebitsofthemainmemoryaddress.Theaddressissplitintodistinctgroupscalledfields.Thegroupfieldsareawaytofind:Whichcachelocation?Whichwordintheblock?Whetheritistherightdataarelookingfor?SomekindofuniqueidentifierCacheMemories(10)MappingScheme(ctd.)ThreeSchemesDirectMappingAssociativeMappingSetAssociativeMappingAssumethatCachelineLii=0,1,…,m–1m=2rMemoryblockBjj=0,1,…,n–1n=2sEachlineorblockconsistsofk=2wconsecutivewordsCacheMemories(11)DirectMappingEachblockofmainmemorymapstoonlyonecachelinei.e.ifablockisincache,itmustbeinonespecificplacei=jmodulom,wherei=cachelinenumberj=mainmemoryblocknumberm=numberoflinesinthecacheCacheMemories(12)DirectMapping(ctd.)CacheLineTableCachelineMainMemoryblocksassigned00,m,2m,…,2s-m11,m+1,2m+1,…,2s-m+1……m–1m-1,2m-1,3m-1,…,2s-1CacheMemories(13)DirectMapping(ctd.)AddressStructureLeastSignificantwbitsidentifyuniquewordMostSignificantsbitsspecifyonememoryblockTheMSBsaresplitintoacachelinefieldrandatagofs-r(mostsignificant)AccessCache(seenextpage)Tags-rLineorSlotrWordwCacheMemories(14)DirectMapping(ctd.)CacheMemories(15)DirectMapping(ctd.)Example:Consideracacheconsistingof128linesof16wordseach.Themainmemoryhas64Kwords.Assumethat:Themainmemoryisaddressablebya16-bitaddress.Consecutiveaddressesrefertoconsecutivewords.Thus,TotalMainMemoryBlocks=64K/16=4Ki=jmodulo128CacheMemories(16)DirectMapping(ctd.)Example(ctd.)CacheMemories(17)DirectMapping(ctd.)AdvantagesSimple,easytoimplementInexpensiveDisadvantageFixedlocationforgivenblockIfaprogramaccesses2blocksthatmaptothesamelinerepeatedly,cachemissesareveryhighCacheMemories(18)AssociativeMappingAmainmemoryblockcanloadintoanylineofcacheAddressStructureMemoryaddressisinterpretedastagandwordTaguniquelyidentifiesblockofmemoryEveryline’stagisexaminedforamatchCachesearchinggetsexpensiveAccessCache(seenextpage)TagsbitWordwbitCacheMemories(19)AssociativeMapping(ctd.)CacheMemories(20)AssociativeMapping(ctd.)ExampleCacheMemories(21)AssociativeMapping(ctd.)AdvantageItgivescompletefreedominchoosingthecachelocationinwhichtoplacethememoryblocks.DisadvantageComplexcircuitryrequiredtoexaminethetagsofallcacheblocksinparallel.

CacheMemories(22)SetAssociativeMappingAcombinationofthedirect-andassociative-mappingtechniques.CacheisdividedintoanumberofsetsEachsetcontainsanumberoflinesAgivenblockmapstoanylineinagivensete.g.BlockBjcanbeinanylineofsetie.g.2linesperset2waysetassociativemappingAgivenblockcanbeinoneof2linesinonlyonesetCacheMemories(23)SetAssociativeMapping(ctd.)Thecacheisdividedintov(=2d)sets,eachofwhichconsistsofklines.(k-waysetassociativemapping)m=v×ki=jmodulov,wherei=cachesetnumberj=mainmemoryblocknumberv=numberofsetsinthecacheSpecialCasesv=m,k=1Directmappingv=1,k=mFullyAssociativemappingv=m/2,k=22-waySetassociativemappingv=m/4,k=44-waySetassociativemappingCacheMemories(24)SetAssociativeMapping(ctd.)AddressStructureSetFieldDeterminewhichsetofthecachemightcontainthedesiredblock.AccessCache(seenextpage)Tag(s-d)bitSetdbitWordwbitCacheMemories(25)SetAssociativeMapping(ctd.)CacheMemories(26)SetAssociativeMapping(ctd.)

Examplei=jmodulo64tagtagtagCachememoryBlock0Block1Block63Block64Block65Block127Block128Block129Block4095Block0Block64Block63tagtagBlock1Block65tagBlock127Mainmemoryaddress664TagSetWordSet0Set1Set63CacheMemories(27)SetAssociativeMapping(ctd.)AdvantagesThecontentionproblemofthedirectmethodiseasedbyhavingafewchoicesforblockreplacement.Thehardwarecostisreducedbydecreasingthesizeoftheassociativesearch.DisadvantagesTags

ofeachblockinasetneedtobematched

(inparallel)tofigureoutwhetherthedataispresentincache.Needk

comparators.Although,thehardwarecostformatchingislessthanfullyassociative(needncomparators,wheren=#blocks),butitismorethandirectmapped(needonlyonecomparator)CacheMemories(28)Tag&ValidBitTofinddatastoredinthecache,weneedtoadd

tagstodistinguishbetweendifferentmemorylocationsthatmaptothesamecacheblock.Weincludeasinglevalid

bitperblocktodistinguishfullandemptyblocks.0–notvalid,1–validAllblocksatstartupwouldbenotvalidIfdatafrommainmemoryisgotintocacheforaparticularblock,thenvalidbitforthatfieldissetValidbitwillcontributetothecachesizeCacheMemories(29)Hit&MissinCacheHitmeansthatweactuallyfounddatainthecacheAhitoccurswhenvalidbit=1ANDtaginthecachematchesthetagfieldoftheaddressMissIfbothconditionsdon’tholdthenwedidnotfindthedataincache.Onamiss,thedataisbroughtfrommainmemoryintothecache,andthevalidbitisset.CacheMemories(30)ReplacementAlgorithmsDirectMappedCacheNochoiceEachblockonlymapstoonelineReplacethatlineAssociativeandSetAssociativeMappedCacheHardwareimplementedalgorithm(speed)LRU(LeastRecentlyUsed)ReplaceblocknotaccessedforlongesttimeFIFO(FirstInFirstOut)PushblockontoqueuewhenaccessedChooseblocktoreplacebypoppingqueueRandomReplaceblockchosenatrandomCacheMemories(31)ExampleofMappingTechniqueAssumethatTheprocessorhasseparateinstructionanddatacaches.Thedatacachehasspaceforonly8blocksofdata.Eachblockconsistsofonlyone16-bitwordofdataandthememoryisword-addressablewith16-bitaddresses.TheLRUreplacementalgorithmisusedforblockreplacementinthecache.Examinethechangesinthedatacacheentriescausedbyrunningthefollowingapplications:A4×10arrayofnumbers,eachoccupyingoneword,isstoredinmemorylocations7A00through7A27.Theelementsofthisarray,A,arestoredincolumnorder.CacheMemories(32)ExampleofMappingTechnique(ctd.)Examinethechangesinthedatacacheentriescausedbyrunningthefollowingapplications:(ctd.)TheapplicationnormalizestheelementsofthefirstrowofAwithrespecttotheaveragevalueoftheelementsintherow.Thatis,fori=0,1,…,9CacheMemories(33)ExampleofMappingTechnique(ctd.)CacheMemories(34)ExampleofMappingTechnique(ctd.)DirectMappedCache3MainmemoryaddressTagBlock13BlockpositionContentsofdatacacheafterpass:j1=j3=j5=j7=j9=i6=i4=i2=i0=A(0,0)A(0,2)A(0,4)A(0,6)A(0,8)A(0,6)A(0,4)A(0,2)A(0,0)A(0,1)A(0,3)A(0,5)A(0,7)A(0,9)A(0,7)A(0,5)A(0,3)A(0,1)01234567Figure8.21.

Contentsofadirect-mappeddatacacheEightelementsarereplacedwhilethesecondloopisexecuted.CacheMemories(35)ExampleofMappingTechnique(ctd.)AssociativeMappedCacheTwoelementsarereplacedwhilethesecondloopisexecuted.MainmemoryaddressTag16BlockpositionContentsofdatacacheafterpass:j7=j8=j9=i1=i0=A(0,0)A(0,8)A(0,8)A(0,8)A(0,0)A(0,4)A(0,4)A(0,4)A(0,4)A(0,4)01234567A(0,1)A(0,1)A(0,9)A(0,1)A(0,1)A(0,2)A(0,2)A(0,2)A(0,2)A(0,2)A(0,3)A(0,3)A(0,3)A(0,3)A(0,3)A(0,5)A(0,5)A(0,5)A(0,5)A(0,5)A(0,6)A(0,6)A(0,6)A(0,6)A(0,6)A(0,7)A(0,7)A(0,7)A(0,7)A(0,7)Figure8.22.Contentsofanassociative-mappeddatacacheinCacheMemories(36)ExampleofMappingTechnique(ctd.)SetAssociativeMappedCacheSixelementsmustbereloadedduringexecutionofthesecondloop.Mainmemoryaddress151TagSetContentsofdatacacheafterpass:j3=j7=j9=i4=i2=i0=A(0,0)A(0,4)A(0,8)A(0,4)A(0,4)A(0,0)A(0,1)A(0,5)A(0,9)A(0,5)A(0,5)A(0,1)A(0,2)A(0,6)A(0,6)A(0,6)A(0,2)A(0,2)A(0,3)A(0,7)A(0,7)A(0,7)A(0,3)A(0,3)Set0Set1Figure8.23.Contentsofaset-associative-mappeddatacacheCacheMemories(37)WritePolicyWriteHit:Updatethedatainthecache,butwhataboutthemainmemory?WriteThroughThecachelocationandthemainmemorylocationareupdatedsimultaneously.AdvantageKeepscachemainmemoryconsistentatthesametime.DisadvantagesAllwritesrequiremainmemoryaccess(bustransaction).Slowsdownthesystem-Ifthereisanotherreadrequestformainmemoryduetomissincache,thereadrequesthastowaituntiltheearlierwritewasserviced.CacheMemories(38)WritePolicy(ctd.)WriteHit(ctd.)WriteBackUpdateonlythecachelocationandtomarkitasupdatedwithanassociatedflagbit(dirtyormodifiedbit).Whentheblockcontainingthemarkedwordistoberemovedfromthecache,updatethemainmemorylocationoftheword.AdvantagesFasterthanwrite-through,timeisnotspentaccessingmainmemory.Writestomultiplewordswithinablockrequireonlyonewritetothemain-memory.CacheMemories(39)WritePolicy(ctd.)WriteHit(ctd.)WriteBack(ctd.)DisadvantagesPortionsofmainmemoryareinvalid,andhenceaccessesbyI/Omodulescanbeallowedonlythroughthecache.Needextrabitincachetoindicatewhichblockhasbeenmodified.0–NotDirty,1–Dirty(modified).Addstosizeofthecache.CacheMemories(40)WritePolicy(ctd.)WriteMissNo-WriteAllocateWrite-throughcache:Theinformationiswrittendirectlyintothemainmemoryandnotloadedintothecache.WriteAllocateWrite-backcache:Theblockcontainingtheaddressedwordisfirstbroughtintothecache,andthenthedesiredwordinthecacheisoverwrittenwiththenewinformation.CacheMemories(41)HitRateandMissPenalty(see8.7.1)HitRateHit:Asuccessfulaccesstodatainacacheiscalledahit.HitRate:Thenumberofhitsstatedasafractionofallattemptedaccessesiscalledthehitrate.Highhitrates,wellover0.9,areessentialforhigh-performancecomputers.MissPenaltyMissRate:Thenumberofmissesstatedasafractionofattemptedaccesses.MissPenalty:Thetotalaccesstimeseenbytheprocessorwhenamissoccursasthemisspenalty.Themisspenaltyconsistsalmostentirelyofthetimetoaccessablockofdatainthemainmemory,inasystemwithonelevelofcache.CacheMemories(42)HitRateandMissPenalty(ctd.)ImpactofthecacheontheoverallperformanceofthecomputerTheaverageaccesstimeexperiencedbytheprocessortavg=hC+(1–h)Mh:hitrateC:thetimetoaccessinformationinthecacheM:misspenaltyCacheMemories(43)HitRateandMissPenalty(ctd.)Example8.1:Consideracomputerthathasthefollowingparameters.Accesstimestothecacheandthemainmemoryareτ

and10τ

,respectively.Whenacachemissoccurs,ablockof8wordsistransferredfromthemainmemorytothecache.Ittakes10τ

totransferthefirstwordoftheblock,andtheremaining7wordsaretransferredattherateofonewordeveryτ

seconds.Themisspenaltyalsoincludesadelayofτ

fortheinitialaccesstothecache,whichmisses,andanotherdelayofτ

totransferthewordtotheprocessoraftertheblockisloadedintothecache(assumingnoload-through).Thus,themisspenaltyinthiscomputerisgivenby:M=τ+10τ+7τ+τ=19τCacheMemories(44)HitRateandMissPenalty(ctd.)Example8.1(ctd.)Assumethat30percentoftheinstructionsinatypical

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论