存儲器層次結(jié)構(gòu)C

第五章：存儲器層次結(jié)構(gòu)-C[AdaptedfromComputerOrganizationandDesign,4thEdition,Patterson&Hennessy,?2008,MK]CourtesyforMaryJaneIrwinofPSU復習:一臺計算機的主要部件

處理器控制器數(shù)據(jù)通路存儲器設(shè)備輸入輸出高速緩存主存輔助存儲器（硬盤）怎樣管理存儲層次結(jié)構(gòu)？寄存器

存儲器by編譯器(程序員?)高速緩存

主存bycache控制器硬件主存硬盤（外存）by操作系統(tǒng)(虛擬存儲器)通過快表（TLB）實現(xiàn)虛擬地址到物理地址的轉(zhuǎn)換by程序員(files)復習:存儲器層次結(jié)構(gòu)訪問時間隨離CPU距離的增加而增加L1$L2$MainMemorySecondaryMemoryProcessor(Relative)sizeofthememoryateachlevelInclusive–whatisinL1$isasubsetofwhatisinL2$isasubsetofwhatisinMMthatisasubsetofisinSM(這其實是為了說明存儲器是一個真正的層次結(jié)構(gòu))4-8bytes(word)1to4blocks1,024+bytes(disksector=page)8-32bytes(block)充分利用了局部性的原則，在最快和最廉價的技術(shù)幫助下提供給用戶越來越多可用的存儲空間虛擬存儲器將主存用作輔助存儲器高速緩存的技術(shù)允許在多道程序之間有效而安全地共享存儲器使那些需要比物理存儲器更大的存儲空間的程序能夠運行

提供重定位來簡化執(zhí)行時的程序加載過程(例如,允許將程序加載到主存中的任何位置)工作原理?–還是局部性原則在任何時間內(nèi)，程序都是可能去訪問整個地址空間內(nèi)某一部分相對較小的地址空間每個程序都是編譯到它自己的地址空間–一個“虛擬”的地址空間在程序運行時，每個虛擬地址都是必須要轉(zhuǎn)化為物理地址

(主存中的地址)共享物理內(nèi)存的兩個程序Program1虛擬地址空間主存儲器一個程序的地址空間劃分為很多頁

(所有的頁固定為同一大小)or段(大小可變)每個頁的開始地址(在主存中或輔存中)包含在程序的頁表中Program2虛擬地址空間地址轉(zhuǎn)換虛擬地址(VA)頁內(nèi)偏移虛擬頁號3130...1211...0頁內(nèi)偏移物理頁號物理地址

(PA)29...12110地址變換所以每個訪存需求最開始都需要通過地址變換將虛擬空間轉(zhuǎn)換為物理空間虛擬存儲器中，訪問缺失被稱為缺頁(例如,訪問的頁不在物理存儲器中)虛擬地址到物理地址的轉(zhuǎn)換是需要軟硬件結(jié)合地址轉(zhuǎn)換機制物理頁的基地址主存儲器硬盤存儲器（外存）虛擬頁號V11111101010頁表(在主存中)頁內(nèi)偏移物理頁號頁內(nèi)偏移頁表寄存器VirtualAddressingwithaCache由于頁表存放在主存中，因此程序多出一次額外的訪存-需要一次訪存以獲得物理地址(通過地址變換將虛擬地址VA轉(zhuǎn)換為物理地址PA)，此后的訪存才是獲得數(shù)據(jù)CPUTrans-lationCacheMainMemoryVAPAmisshitdata這樣使存儲器(緩存)訪問變得開銷很大

(程序每次訪存至少需要兩次)現(xiàn)代處理器都包含一個特殊的cache以追蹤最近使用過的地址變換，這個特殊的地址轉(zhuǎn)換cache就是快表TranslationLookasideBuffer(TLB)–用于記錄最近使用地址的映射信息的一個較小的高速緩存，從而可以避免每次都要訪問頁表加速地址轉(zhuǎn)換物理頁基地址主存儲器硬盤存儲器虛擬頁號V1111110101011101標記物理頁基地址V快表頁表(在物理存儲器中)頁表寄存器TranslationLookasideBuffers(TLBs)快表正和其它的cache一樣，TLB的組織形式也是全相聯(lián)，組相聯(lián)，直接映射這幾種TLB的訪問時間通常是要比cache的訪問時間短(因為TLB比cache小很多)TLB通常不會超過512項ATLBintheMemoryHierarchyTLB缺失–判斷是缺頁還是僅僅是一次TLB缺失？

如果該頁在主存中，那么TLB缺失只是一次轉(zhuǎn)換缺失，處理器可以通過將頁表中的變換裝載到TLB并重新訪問來進行缺失處理(TLB缺失既可以通過硬件處理，也可以通過軟件處理)Takes10’sofcyclestofindandloadthetranslationinfointotheTLB如果該頁不在主存中，TLB缺失就是一次真的缺頁Takes1,000,000’sofcyclestoserviceapagefaultTLB缺失比缺頁要頻繁得多CPUTLBLookupCacheMainMemoryVAPAmisshitdataTrans-lationhitmiss?t?tTLB中可能發(fā)生的事件組合TLBPageTableCache可能發(fā)生么?如果可能，什么情況下發(fā)生?HitHitHitHitHitMissMissHitHitMissHitMissMissMissMissHitMissMiss/HitMissMissHit

Yes–whatwewant!Yes–althoughthepagetableisnotcheckediftheTLBhitsYes–TLBmiss,PAinpagetableYes–TLBmiss,PAinpagetable,butdatanotincacheYes–pagefaultImpossible–TLBtranslationnotpossibleifpageisnotpresentinmemoryImpossible–datanotallowedincacheifpageisnotinmemory處理一次TLB缺失考慮一次TLB缺頁在存儲器中發(fā)生(例如，

設(shè)置頁表中的有效位)TLB缺失(缺頁異常)必須在訪存發(fā)生的同一時鐘周期的末尾被判定，因此下一個時鐘周期就開始進行異常處理而不是繼續(xù)正常的指令執(zhí)行。下表見圖5-27寄存器CP0

寄存器號說明EPC14WheretorestartafterexceptionCause13CauseofexceptionBadVAddr8AddressthatcausedexceptionIndex0LocationinTLBtoberead/writtenRandom1PseudorandomlocationinTLBEntryLo2PhysicalpageaddressandflagsEntryHi10VirtualpageaddressContext4Pagetableaddress&pagenumberTLB缺失處理程序（MIPS）當TLB缺失發(fā)生時，MIPS的硬件將被引用的頁號保存在一個叫BadVAddr的特殊寄存器中，然后產(chǎn)生異常。這個異常請求操作系統(tǒng)通過軟件來處理缺失，控制權(quán)被轉(zhuǎn)移到地址80000000hex,TLB缺失處理程序的位置TLBmiss:mfc0$k1,Context #copyaddrofPTEinto$k1lw$k1,0($k1) #putPTEinto$k1mtc0$k1,EntryLo

#putPTEintoEntryLo

tlbwr #putEntryLointoTLB # atRandomeret #returnfromexception指令tlbwr

把控制寄存器EntryLo

中的內(nèi)容復制到由控制寄存器

Random所選擇的TLB表項中。TLB缺失大概需要花費12個時鐘周期一些虛擬存儲器的設(shè)計參數(shù)PagedVMTLBsTotalsize16,000to250,000words16to512entriesTotalsize(KB)250,000to1,000,000,0000.25to16Blocksize(B)4000to64,0004to8Hittime0.5to1clockcycleMisspenalty(clocks)10,000,000to100,000,00010to100Missrates0.00001%to0.0001%0.01%to1%兩個機器的快表參數(shù)IntelNehalemAMDBarcelonaAddresssizes48bits(vir);44bits(phy)48bits(vir);48bits(phy)Pagesize4KB4KBTLBorganizationL1TLBforinstructionsandL1TLBfordatapercore;bothare4-waysetassoc.;LRUL1ITLBhas128entries,L2DTLBhas64entriesL2TLB(unified)is4-waysetassoc.;LRUL2TLBhas512entriesTLBmisseshandledinhardwareL1TLBforinstructionsandL1TLBfordatapercore;botharefullyassoc.;LRUL1ITLBandDTLBeachhave48entriesL2TLBforinstructionsandL2TLBfordatapercore;eachare4-waysetassoc.;roundrobinLRUBothL2TLBshave512entriesTLBmisseshandledinhardware為什么不用虛擬尋址cache？虛擬尋址cache只需要對cache缺失進行地址轉(zhuǎn)換dataCPUTrans-lationCacheMainMemoryVAhitPA

但是使用虛擬地址訪問cache，并且兩個程序之間共享數(shù)據(jù)時，可能有別名-兩個虛擬地址對應到同一個物理地址，所以在cache中有共享數(shù)據(jù)的兩個備份，在TLB中有兩個表項，這將導致一致性問題Mustupdateallcacheentrieswiththesamephysicaladdressorthememorybecomesinconsistent減短地址變換時間可以使cache訪問和TLB訪問重疊虛擬地址的高位用于訪問TLB，低位用于cache的索引TagData=TagData=CacheHitDesiredwordVATagPATagTLBHit2-wayAssociativeCacheIndexPATagBlockoffsetPageoffsetVirtualpage#TheHardware/SoftwareBoundary虛擬地址到物理地址的轉(zhuǎn)換過程中哪些部分是需要硬件支持的呢？TLB快表：用于記錄最近用過的地址變換的高速緩存TLBaccesstimeispartofthecachehittimeMayallotanextrastageinthepipelineforTLBaccess（多一級）頁表存儲，故障檢測和更新Pagefaultsresultininterrupts(precise)thatarethenhandledbytheOS缺頁導致的中斷由操作系統(tǒng)處理Hardwaremustsupport(i.e.,updateappropriately)DirtyandReferencebits(e.g.,~LRU)inthePageTables

硬件要支持頁表中的重寫位、引用位存儲器層次結(jié)構(gòu)的4個問題Q1:一個塊可以被放到何處？

(Entryplacement)Q2:如何找到一個塊？

(Entryidentification)Q3:當cache缺失時替換哪一塊？

(Entryreplacement)Q4:寫操作如何處理？

(Writestrategy)Q1&Q2:塊可以被放到哪以及如何找到一個塊#ofsetsEntriespersetDirectmapped#ofentries1Setassociative(#ofentries)/associativityAssociativity(typically2to16)Fullyassociative1#ofentriesLocationmethod#ofcomparisonsDirectmappedIndex1SetassociativeIndextheset;compareset’stagsDegreeofassociativityFullyassociativeCompareallentries’tagsSeparatelo