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

第五章：存儲(chǔ)器層次結(jié)構(gòu)-C[AdaptedfromComputerOrganizationandDesign,4thEdition,Patterson&Hennessy,?2008,MK]CourtesyforMaryJaneIrwinofPSU復(fù)習(xí):一臺(tái)計(jì)算機(jī)的主要部件

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

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

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

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

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

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

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

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

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

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

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

寄存器號(hào)說(shuō)明EPC14WheretorestartafterexceptionCause13CauseofexceptionBadVAddr8AddressthatcausedexceptionIndex0LocationinTLBtoberead/writtenRandom1PseudorandomlocationinTLBEntryLo2PhysicalpageaddressandflagsEntryHi10VirtualpageaddressContext4Pagetableaddress&pagenumberTLB缺失處理程序（MIPS）當(dāng)TLB缺失發(fā)生時(shí)，MIPS的硬件將被引用的頁(yè)號(hào)保存在一個(gè)叫BadVAddr的特殊寄存器中，然后產(chǎn)生異常。這個(gè)異常請(qǐng)求操作系統(tǒng)通過(guò)軟件來(lái)處理缺失，控制權(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)容復(fù)制到由控制寄存器

Random所選擇的TLB表項(xiàng)中。TLB缺失大概需要花費(fèi)12個(gè)時(shí)鐘周期一些虛擬存儲(chǔ)器的設(shè)計(jì)參數(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%兩個(gè)機(jī)器的快表參數(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只需要對(duì)cache缺失進(jìn)行地址轉(zhuǎn)換dataCPUTrans-lationCacheMainMemoryVAhitPA

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

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

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

(Entryidentification)Q3:當(dāng)cache缺失時(shí)替換哪一塊？

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

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