計算機體系結構周學海xhzhou國科學技術大學基本流水線小結流水線提高的是指令帶寬（吞吐率），而不是單條指令的執行速度相關限制了流水線性能的發揮結構相關：需要更多的硬件資源數據相關：需要定向，編譯器調度控制相關：盡早檢測條件，計算目標地址，延遲轉移，預測編譯器可降低數據相關和控制相關的開銷Load延遲槽\Branch延遲槽\Branch預測增加流水線的級數會增加相關產生的可能性異常，浮點運算使得流水線控制更加復雜長流水線（浮點數流水線）引起的“相關”問題長流水線中精確中斷的處理方法浮點數流水線的性能:RAW相關引起的性能損失是主要因素浮點數流水線示例(MIPSR4000)中國科學技術大學chapter3.2第4章存儲層次結構設計4.1存儲層次結構4.2Cache基本知識4.3基本的Cache優化方法4.4高級的Cache優化方法4.5存儲器技術與優化4.6虛擬存儲器－基本原理2025/3/6計算機體系結構34.1存儲層次結構存儲系統設計是計算機體系結構設計的關鍵問題之一價格，容量，速度的權衡用戶對存儲器的“容量，價格和速度”要求是相互矛盾的速度越快，每位價格就高容量越大，每位價格就低容量越大，速度就越慢目前主存一般由DRAM構成Microprocessor與Memory之間的性能差異越來越大CPU性能提高大約60%/yearDRAM性能提高大約9％/year2025/3/6計算機體系結構4技術發展趨勢

Capacity Speed(latency)Logic: 2xin3years 2xin3yearsDRAM: 4xin3years 2xin10yearsDisk: 4xin3years 2xin10years2025/3/6計算機體系結構5YearDRAMSize CycleTime1980 64Kb 250ns1983 256Kb 220ns1986 1Mb 190ns1989 4Mb 165ns1992 16Mb 145ns1995 64Mb 120ns1000:1!2:1!20098192(8Gbi)TrendsinDRAM2025/3/6計算機體系結構6Processor-DRAMMemoryGap(latency)微處理器與DRAM的性能差異2025/3/6計算機體系結構7Processor-MemoryPerformanceGapGrowingMicroprocessor-DRAM性能差異

利用caches緩解微處理器與存儲器性能上的差異Microprocessor-DRAM性能差異timeofafullcachemissininstructionsexecuted1stAlpha:340ns/5.0ns=

68clksx2or136instructions2ndAlpha:266ns/3.3ns=

80clksx4or320instructions3rdAlpha:180ns/1.7ns=108clksx6or648instructions2025/3/6計算機體系結構8Processor$MEMMemoryreferencestream<op,addr>,<op,addr>,<op,addr>,<op,addr>,...op:i-fetch,read,write通過優化存儲系統的組織來使得針對典型應用平均訪存時間最短WorkloadorBenchmarkprograms存儲系統的設計目標2025/3/6計算機體系結構9基本解決方法：多級層次結構多級分層結構M1速度最快，容量最小，每位價格最高Mn速度最慢，容量最大，每位價格最低并行存儲系統接近M1的速度，容量和價格接近Mn2025/3/6計算機體系結構10CPUM1M2Mn………..計算機系統的多級存儲層次2025/3/6計算機體系結構11CPURegisterMEMORYI/OdeviceL1CACHEL2CACHEL3CACHE300ps1ns3-10ns10-20ns50-100ns5-10ms1000B64KB256K2-4MB4-16GB4-16TBCPURegisterMEMORYI/OdeviceL1CACHEL2CACHE500ps2ns10-20ns50-100ns25-50μs500B64KB256K256-512MB4-8GBServerPMD存儲層次工作原理：Locality!TemporalLocality(時間局部性):=>保持最近訪問的數據項最接近微處理器SpatialLocality(空間局部性):以由地址連續的若干個字構成的塊為單位，從低層復制到上一層2025/3/6計算機體系結構12LowerLevelMemoryUpperLevelMemoryToProcessorFromProcessorBlkXBlkY應用程序局部性原理:給用戶一個采用低成本技術達到的存儲容量.（容量大，價格低）一個采用高速存儲技術達到的訪問速度.（速度快）典型的存儲器訪問模式2025/3/6計算機體系結構13存儲層次結構涉及的基本概念BlockBlock:不同層次的Block大小可能不同命中和命中率失效和失效率鏡像和一致性問題高層存儲器是較低層存儲器的一個鏡像高層存儲器內容的修改必須反映到低層存儲器中數據一致性問題尋址：不管如何組織，我們必須知道如何訪問數據要求：不同層次上塊大小可以不同在L0cache可能以Double,Words,Halfwords,或bytes在L1cache僅以cacheline或slot為單位訪問在更低層…..因此總是存在地址映射問題物理地址格式BlockFrameAddress+BlockOffset2025/3/6計算機體系結構14存儲層次的性能參數(1/2)假設采用二級存儲：M1和M2M1和M2的容量、價格、訪問時間分別為：S1、C1、TA1S2、C2、TA22025/3/6計算機體系結構15LowerLevelMemoryUpperLevelMemoryToProcessorFromProcessorBlkXBlkY存儲層次的性能參數(2/2)存儲層次的平均每位價格CC=(C1*S1+C2*S2)/(S1+S2)命中(Hit):訪問的塊在存儲系統的較高層次上若一組程序對存儲器的訪問，其中N1次在M1中找到所需數據，N2次在M2中找到數據則HitRate（命中率）:存儲器訪問在較高層命中的比例H=N1/(N1+N2)HitTime（命中時間）:訪問較高層的時間，TA1失效(Miss):訪問的塊不在存儲系統的較高層次上MissRate（失效）=1-(HitRate)=1–H＝N2/(N1+N2)當在M1中沒有命中時：一般必須從M2中將所訪問的數據所在塊搬到M1中，然后CPU才能在M1中訪問。設傳送一個塊的時間為TB,即不命中時的訪問時間為：TA2+TB+TA1=TA1+TMTM通常稱為失效開銷平均訪存時間:平均訪存時間TA=HTA1+(1-H)(TA1+TM)=TA1+(1-H)TM2025/3/6計算機體系結構16常見的存儲層次的組織Registers<->Memory由編譯器完成調度cache<->memory由硬件完成調度memory<->disks由硬件和操作系統（虛擬管理）由程序員完成調度2025/3/6計算機體系結構17CacheMemory?小而快（SRAM）的存儲技術存儲正在訪問的部分指令和數據用于減少平均訪存時間通過保持最近訪問的數據在處理器附近來挖掘時間局部性通過以塊為單位在不同層次移動數據來挖掘空間局部性主要目標：提高訪存速度降低存儲系統成本2025/3/6計算機體系結構18Cache無處不在體系結構中，Cache無處不在寄存器：Cache

onvariables一、二級Cache：CacheonmemoryMemory：Cacheonharddisks存儲最近執行的程序和數據Harddisks可以視為主存的擴展（VM）分支目標緩存及分支預測緩存緩存分支目標及預測信息2025/3/6計算機體系結構194.2Cache基本知識2025/3/6計算機體系結構20Q1：映象規則當要把一個塊從主存調入Cache時，如何放置問題三種方式全相聯方式：即所調入的塊可以放在cache中的任何位置直接映象方式：主存中每一塊只能存放在cache中的唯一位置一般，主存塊地址i與cache中塊地址j的關系為：

j＝imod（M)，M為cache中的塊數組相聯映象：主存中每一塊可以被放置在Cache中唯一的一個組中的任意一個位置，組由若干塊構成，若一組由n塊構成，我們稱N路組相聯組間直接映象組內全相聯若cache中有G組，則主存中的第i塊的組號KK=imod(G),2025/3/6計算機體系結構21Q1:Wherecanablockbeplacedintheupperlevel?Block12placedin8blockcache:Fullyassociative,directmapped,2-waysetassociativeS.A.Mapping=BlockNumberModuloNumberSets2025/3/6計算機體系結構2201234567Blockno.Fullyassociative:block12cangoanywhere01234567Blockno.Directmapped:block12cangoonlyintoblock4(12mod8)01234567Blockno.Setassociative:block12cangoanywhereinset0(12mod4)Set0Set1Set2Set301234567890123456789012345678901Block-frameaddress1111111111222222222233Blockno.Q1的討論N-Way組相聯：如果每組由N個塊構成，cache的塊數為M，則cache的組數G為M/N不同相聯度下的路數和組數 路數組數 全相聯M1

直接相聯1M

其他組相聯1<N<M1<G<M相聯度越高，cache空間利用率就越高，塊沖突概率就越小，失效率就越低N值越大，失效率就越低，但Cache的實現就越復雜，代價越大現代大多數計算機都采用直接映象，兩路或四路組相聯。2025/3/6計算機體系結構23Q2(1/2):查找方法在CACHE中每一block都帶有tag域（標記域），標記分為兩類AddressTags：標記所訪問的單元在哪一塊中，這樣物理地址就分為三部分：AddressTags##Blockindex##blockOffset

全相聯映象時，沒有BlockIndex

顯然Addresstag越短，查找所需代價就越小StatusTags：標記該塊的狀態，如Valid,Dirty等2025/3/6計算機體系結構24BlockoffsetBlockAddressTagIndexSetSelectDataSelectQ2（2/2)查找方法原則：所有可能的標記并行查找，cache的速度至關重要，即并行查找并行查找的方法用相聯存儲器實現，按內容檢索用單體多字存儲器和比較器實現顯然相聯度N越大，實現查找的機制就越復雜，代價就越高無論直接映象還是組相聯，查找時，只需比較tag，index無需參加比較2025/3/6計算機體系結構25Tag和數據陣列并行訪問的邏輯結構2025/3/6計算機體系結構26Tag和數據陣列并行訪問的流水線模式2025/3/6計算機體系結構27Tag和數據陣列串行訪問的邏輯結構2025/3/6計算機體系結構28Tag和數據陣列串行訪問的流水線模式2025/3/6計算機體系結構29直接映像Cache查找過程2025/3/6計算機體系結構30全相聯Cache查找過程2025/3/6計算機體系結構31Example:1KBDirectMappedCachewith32BBlocks對于容量為2N

字節的cache:最高(32-N)位部分

為CacheTag最低M位為字節選擇位(BlockSize=2M)2025/3/6計算機體系結構32CacheIndex0123:

CacheDataByte00431:CacheTagExample:0x50Ex:0x010x50Storedaspartofthecache“state”ValidBit:31Byte1Byte31:Byte32Byte33Byte63:Byte992Byte1023:

CacheTagByteSelectEx:0x009BlockaddressExample:SetAssociativeCacheN-waysetassociative:每一個cache索引對應N個cacheentries這N個cache項并行操作Example:Two-waysetassociativecacheCacheindex選擇cache中的一組這一組中的兩塊對應的Tags與輸入的地址同時比較根據比較結果選擇數據2025/3/6計算機體系結構33CacheDataCacheBlock1CacheTagValid:::CacheDataCacheBlock0CacheTagValid:::CacheIndexMux01Sel1Sel0CacheBlockCompareAdrTagCompareORHitQ3：替換算法主存中塊數一般比cache中的塊多，可能出現該塊所對應的一組或一個Cache塊已全部被占用的情況，這時需強制騰出其中的某一塊，以接納新調入的塊，替換哪一塊，這是替換算法要解決的問題：直接映象，因為只有一塊，別無選擇組相聯和全相聯有多種選擇替換方法隨機法（Random)，隨機選擇一塊替換優點：簡單，易于實現缺點：沒有考慮Cache塊的使用歷史，反映程序的局部性較差，失效率較高FIFO－選擇最早調入的塊優點：簡單雖然利用了同一組中各塊進入Cache的順序，但還是反映程序局部性不夠，因為最先進入的塊，很可能是經常使用的塊最近最少使用法（LRU)(LeastRecentlyUsed)優點：較好的利用了程序的局部性，失效率較低缺點：比較復雜，硬件實現較困難2025/3/6計算機體系結構34LRU和Random的比較（失效率）觀察結果（失效率）相聯度高，失效率較低。Cache容量較大，失效率較低。LRU在Cache容量較小時，失效率較低隨著Cache容量的加大，Random的失效率在降低2025/3/6計算機體系結構35DataCachemissesper1000instructionscomparingLRU,Random,FIFOreplacementforseveralsizesandassociativities.Thesedatawerecollectedforablocksizeof64bytesfortheAlphaarchitectureusing10SPEC2000benchmarks.FivearefromSPECint2000(gap,gcc,gzip,mcfandperl)andfivearefromSPECfp2000(applu,art,equake,lucasandswim)Q4:寫策略程序對存儲器讀操作占26％，寫操作占9％寫所占的存儲器訪問比例9/(100+26+9)大約為7％占訪問數據Cache的比例：9/(26+9)大約為25%大概率事件優先原則－優化Cache的讀操作Amdahl定律：不可忽視“寫”的速度“寫”的問題讀出標識，確認命中后，對Cache寫（串行操作）Cache與主存內容的一致性問題寫策略就是要解決:何時更新主存問題2025/3/6計算機體系結構36兩種寫策略寫直達法（Writethrough)優點：易于實現，容易保持不同層次間的一致性缺點：速度較慢寫回法優點：速度快，減少訪存次數缺點：一致性問題當發生寫失效時的兩種策略按寫分配法(Writeallocate)：寫失效時，先把所寫單元所在塊調入Cache，然后再進行寫入，也稱寫時取（FetchonWrite)方法不按寫分配法（no-writeallocate):寫失效時，直接寫入下一級存儲器，而不將相應塊調入Cache，也稱繞寫法（Writearound)原則上以上兩種方法都可以應用于寫直達法和寫回法，一般情況下WriteBack用WriteallocateWritethrough用no-writeallocate2025/3/6計算機體系結構37Write-back,WriteAllocate2025/3/6計算機體系結構38Write-Through,NoWriteAllocate2025/3/6計算機體系結構3904/02-Review存儲系統的性能指標：速度、容量和價格平均訪存時間=命中時間+失效率×失效開銷Cache4Q映射規則查找方法替換策略寫策略2025/3/6計算機體系結構40AlphaAX21064Cache結構（數據Cache)基本技術特性容量8KB，Block32Bytes,共256個Blocks，每個字為8個字節直接映象寫直達法，寫失效時，no-writeallocate方法寫緩沖：4個blocks21064物理地址34位21位tag##8位index##5位塊內偏移Cache命中的步驟讀命中寫命中Cache失效Cache向CPU發暫停信號塊傳送，21064Cache與下一級存儲器之間數據通路16字節，傳送全部32字節需要10個cycles2025/3/6計算機體系結構41AlphaAX21064Cache結構（數據Cache)基本技術特性Block32bytesperBlock,共256個Block直接映象寫直達法，寫失效時，no-writeallocate方法21064物理地址34位21位tag##8位index##5位塊內偏移Cache命中的步驟讀命中寫命中Cache失效Cache向CPU發暫停信號塊傳送，21064Cache與下一級存儲器之間數據通路16字節，傳送全部32字節需要10個cycles2025/3/6計算機體系結構42Alpha21264DataCache基本技術特征Cachesize:64KbytesBlocksize:64-bytesTwo-way組相聯Writeback,寫失效時，writeallocate2126448-bits虛擬地址，虛實映射為44-bits的物理地址，也支持43-bits虛擬地址，虛實映射為41-bits的物理地址29位tags##9位index##6位Blockoffset2025/3/6計算機體系結構43Alpha21264DataCache2025/3/6計算機體系結構44Cache性能分析CPUtime=(CPUexecutionclockcycles+

Memorystallclockcycles)xclockcycletime

Memorystallclockcycles=

(ReadsxReadmissratexReadmisspenalty+

WritesxWritemissratexWritemisspenalty)

Memorystallclockcycles=

MemoryaccessesxMissratexMisspenaltyDifferentmeasure:AMAT

AverageMemoryAccesstime(AMAT)=

HitTime+(MissRatexMissPenalty)Note:memoryhittimeisincludedinexecutioncycles.2025/3/6計算機體系結構45性能分析舉例SupposeaprocessorexecutesatClockRate=200MHz(5nspercycle),Ideal(nomisses)CPI=1.150%arith/logic,30%ld/st,20%controlMissBehavior:10%ofmemoryoperationsget50cyclemisspenalty1%ofinstructionsgetsamemisspenaltyCPI =idealCPI+averagestallsperinstruction =1.1(cycles/ins)+

[0.30(DataMops/ins)

x0.10(miss/DataMop)x50(cycle/miss)]+

[1(InstMop/ins)

x0.01(miss/InstMop)x50(cycle/miss)]

=(1.1+1.5+.5)cycle/ins=3.165%(2/3.1)ofthetimetheprocisstalledwaitingformemory!AMAT=(1/1.3)x[1+0.01x50]+(0.3/1.3)x[1+0.1x50]=2.542025/3/6計算機體系結構46Example:HarvardArchitectureUnifiedvsSeparateI&D(Harvard)Statistics(giveninH&P):16KBI&D:Instmissrate=0.64%,Datamissrate=6.47%32KBunified:Aggregatemissrate=1.99%Whichisbetter(ignoreL2cache)?Assume33%dataops

75%accessesfrominstructions(1.0/1.33)hittime=1,misstime=50Notethatdatahithas1stallforunifiedcache(onlyoneport)AMATHarvard=75%x(1+0.64%x50)+25%x(1+6.47%x50)=2.05AMATUnified=75%x(1+1.99%x50)+25%x(1+1+1.99%x50)=2.242025/3/6計算機體系結構47ProcI-Cache-1ProcUnifiedCache-1UnifiedCache-2D-Cache-1ProcUnifiedCache-22025/3/6計算機體系結構48以順序執行的計算機UltraSPARCIII為例.假設Cache失效開銷為100clockcycles，所有指令忽略存儲器停頓需要1個cycle,Cache失效可以用兩種方式給出（1）假設平均失效率為2%，平均每條指令訪存1.5次（2）假設每1000條指令cache失效次數為30次分別基于上述兩種條件計算處理器的性能結論：CPUtime=IC*(1+2%*1.5*100)*T=IC*4*T(1)CPI越低，固定周期數的Cache失效開銷的相對影響就越大(2)在計算CPI時，失效開銷的單位是時鐘周期數。因此，即使兩臺計算機的存儲層次完全相同，時鐘頻率較高的CPU的失效開銷會較大，其CPI中存儲器停頓部分也就較大。因此Cache對于低CPI，高時鐘頻率的CPU來說更加重要2025/3/6計算機體系結構49考慮不同組織結構的Cache對性能的影響:B-19例題：直接映像Cache和兩路組相聯Cache，試問他們對CPU性能的影響？先求平均訪存時間，然后再計算CPU性能。分析時請用以下假設：（1）理想Cache(命中率為100%）情況下CPI為1.0，時鐘周期為0.35ns，平均每條指令訪存1.4次（2）兩種Cache容量均為128KB，塊大小都是64B（3）采用組相聯時，由于多路選擇器的存在，時鐘周期增加到原來的1.35倍（4）兩種結構的失效開銷都是65ns(在實際應用中，應取整為整數個時鐘周期）（5）命中時間為1個cycle，128KB直接映像Cache的失效率為2.1%,相同容量的兩路組相聯Cache的失效率為1.9%2025/3/6計算機體系結構50失效開銷與Out-of-Order執行的處理器需要確定兩個參數：LengthofmemorylatencyLengthoflatencyoverlap例如：在前面的例子中，若假設允許處理器亂序執行，則對于直接映射方式，假設30%的失效開銷可以覆蓋（overlap)，那么原來的70ns失效開銷就變為49ns.2025/3/6計算機體系結構51-reviewCache基本原理4QCache性能分析CPUtime=(CPUexecutionclockcycles+

Memorystallclockcycles)xclockcycletimeMemorystallclockcycles=

(ReadsxReadmissratexReadmisspenalty+

WritesxWritemissratexWritemisspenalty)Memorystallclockcycles=

MemoryaccessesxMissratexMisspenaltyDifferentmeasure:AMAT

AverageMemoryAccesstime(AMAT)=

HitTime+(MissRatexMissPenalty)2025/3/6計算機體系結構52Summaryofperformanceequationsinthischapter2025/3/6計算機體系結構534.3基本Cache優化方法降低失效率1、增加Cache塊的大小2、增大Cache容量3、提高相聯度減少失效開銷4、多級Cache5、使讀失效優先于寫失效縮短命中時間6、避免在索引緩存期間進行地址轉換2025/3/6計算機體系結構54改進Cache性能的方法平均訪存時間＝命中時間＋失效率×失效開銷從上式可知，基本途徑降低失效率減少失效開銷縮短命中時間2025/3/6計算機體系結構55降低失效率Cache失效的原因可分為三類3C強制性失效(Compulsory)第一次訪問某一塊，只能從下一級Load，也稱為冷啟動或首次訪問失效容量失效（Capacity)如果程序執行時，所需塊由于容量不足，不能全部調入Cache，則當某些塊被替換后，若又重新被訪問，就會發生失效。可能會發生“抖動”現象沖突失效（Conflict(collision))組相聯和直接相聯的副作用若太多的塊映像到同一組（塊）中，則會出現該組中某個塊被別的塊替換（即使別的組或塊有空閑位置)，然后又被重新訪問的情況，這就屬于沖突失效2025/3/6計算機體系結構56各種類型的失效率2025/3/6計算機體系結構57從統計規律中得到的一些結果相聯度越高，沖突失效就越小強制性失效和容量失效不受相聯度的影響強制性失效不受Cache容量的影響容量失效隨著容量的增加而減少符合2:1Cache經驗規則即大小為N的直接映象Cache的失效率約等于大小為N/2的兩路組相聯的Cache失效率。2025/3/6計算機體系結構58減少3C的方法從統計規律可知增大Cache容量對沖突和容量失效的減少有利增大塊減緩強制性失效可能會增加沖突失效（因為在容量不變的情況下，塊的數目減少了）通過預取可幫助減少強制性失效必須小心不要把你需要的東西換出去需要預測比較準確（對數據較困難，對指令相對容易）2025/3/6計算機體系結構59增加塊的大小2025/3/6計算機體系結構60塊大小、容量對失效率的影響Given:missratesfordifferentcachesizes&blocksizesMemorylatency=80cycles+1cycleper8bytesLatencyof16-byteblock=80+2=82clockcyclesLatencyof32-byteblock=80+4=84clockcyclesLatencyof256-byteblock=80+32=112clockcyclesWhichblockhassmallestAMATforeachcachesize?2025/3/6計算機體系結構61塊大小、容量對AMAT的影響Solution:assumehittime=1clockcycleRegardlessofblocksizeandcachesizeCacheSize=4KB,BlockSize=16bytesAMAT=1+8.57%×82=8.027clockcyclesCacheSize=256KB,BlockSize=256bytesAMAT=1+0.49%×112=1.549clockcycles2025/3/6計算機體系結構62塊大小、容量對AMAT的影響降低失效率最簡單的方法是增加塊大小；統計結果如圖所示假定存儲系統在延遲40個時鐘周期后，每2個時鐘周期能送出16個字節，即：經過42個時鐘周期，它可提供16個字節；經過44個四周周期，可提供32個字節；依此類推。試根據圖5-6列出的各種容量的Cache，在塊大小分別為多少時，平均訪存時間最小？2025/3/6計算機體系結構63塊大小、容量的權衡從統計數據可得到如下結論對于給定Cache容量，塊大小增加時，失效率開始是下降，但后來反而上升Cache容量越大，使失效率達到最低的塊大小就越大分析塊大小增加，可使強制性失效減少（空間局部性原理）塊大小增加，可使沖突失效增加（Cache中塊數量減少）失效開銷增大（上下層間移動，數據傳輸時間變大）設計塊大小的原則，不能僅看失效率原因：平均訪存時間＝命中時間＋失效率×失效開銷2025/3/6計算機體系結構64提高相聯度8路組相聯在降低失效率方面的作用已經和全相聯一樣有效2:1Cache經驗規則容量為N的直接映象Cache失效率與容量為N/2的兩路組相聯Cache的失效率差不多相同提高相聯度，會增加命中時間2025/3/6計算機體系結構65VictimCache(1/2)在Cache和Memory之間增加一個小的全相聯Cache2025/3/6計算機體系結構66VictimCache(2/2)基本思想通常Cache為直接映象時沖突失效率較大Victimcache采用全相聯－失效率較低Victimcache存放由于失效而被丟棄的那些塊失效時，首先檢查Victimcache是否有該塊，如果有就將該塊與Cache中相應塊比較。Jouppi(DECSRC)發現，含1到5項的Victimcache對減少失效很有效，尤其是對于那些小型的直接映象數據Cache。測試結果，項為4的VictimCache能使4KB直接映象數據Cache沖突失效減少20%-90%2025/3/6計算機體系結構67減少失效開銷減少CPU與存儲器間性能差異的重要手段平均訪存時間＝命中時間＋失效率×失效開銷基本手段：4、多級Cache技術(MultilevelCaches)5、讓讀優先于寫(GivingPrioritytoReadMissesoverWrites)2025/3/6計算機體系結構68采用多級Cache一級cache保持較小容量降低命中時間降低每次訪問的能耗增加二級cache減少與存儲器的gap減少存儲器總線的負載多級cache的優點減少失效開銷縮短平均訪存時間（AMAT）較大容量的L2

cache可以捕捉許多L1

cache的失效降低全局失效率2025/3/6計算機體系結構69多級包容性(multilevelinclusive)L1cache的塊總是存在于L2cache中浪費了L2cache空間，L2還應當有存放其他塊的空間L1中miss,但在L2中命中，則從L2拷貝相應的塊到L1在L1和L2中均miss,則從更低級拷貝相應的塊到L1和L2對L1寫操作導致將數據同時寫到L1和L2Write-through策略用于L1到L2Write-back策略可用于L2到更低級存儲器，以降低存儲總線的數據傳輸壓力L2的替換動作（或無效)對L1可見即L2的一塊被替換出去，那么其在L1中對應的塊也要被替換出去。2025/3/6計算機體系結構70訪問的塊序列10246替換策略：LRU塊大小相同2025/3/6計算機體系結構71012345670110244161602421Invalid0(0)0(1)2025/3/6計算機體系結構7201012345670(0)0(1)1(2)1(3)2(4)2(5)3(6)3(7)41L1和L2的塊大小不同，L1的blockSize是L2的blockSize的1/2替換策略：LRU考察按L1的塊劃分的訪問序列：0148812(4)2(5)Invalid4(8)4(9)Invalid多級不包容（MultilevelExclusive）L1cache中的塊不會在L2

cache中，以避免浪費空間在L1中miss,但在L2中命中，將導致Cache間塊的互換在L1和L2中均miss,將僅僅從更低層拷貝相應的塊到L1L1的被替換的塊移至L2L2存儲L1拋棄的塊，以防后續L1還需要使用L1到L2的寫策略為Write-BackL2到更低級cache的寫策略為Write-BackL1和L2的塊大小可以相同也可以不同Pentium4had64-byteblocksinL1but128-byteblocksinL2Corei7uses64-byteblocksatallcachelevels(simpler)2025/3/6計算機體系結構73012025/3/6計算機體系結構7400123456L1：1-wayL2：2-way訪問的塊序列01234563替換策略：LRU塊大小相同2123434565WriteBack00101201234--2363452--L2#3L1#5互換

------------2025/3/6計算機體系結構7501012345678910110(0)0(1)1(2)1(3)2(4)2(5)3(6)3(7)4(8)4(9)5(10)23L1和L2的塊大小不同，L1的blockSize是L2的blockSize的1/2替換策略：LRU考察按L1的塊劃分的訪問序列：012345678910114(L2#4與L1中的#10互換）878910921434565671011WriteBack0(0)0(1)411------------0(0)------------0(0)0(1)--------0(0)0(1)1(2)--------0(0)0(1)1(2)1(3)------0(0)0(1)1(2)1(3)2(4)------0(0)0(1)1(2)1(3)2(4)2(5)----0(0)0(1)1(2)1(3)2(4)2(5)3(6)--0(0)0(1)1(2)1(3)2(4)2(5)3(6)3(7)4(8)1(2)1(3)2(4)2(5)3(6)3(7)4(8)4(9)1(2)1(3)2(4)2(5)3(6)3(7)4(8)4(9)5(10)----2(5)3(6)3(7)04/04-review基本Cache優化方法降低失效率：引起失效的3C1、增加Cache塊的大小2、增大Cache容量3、提高相聯度減少失效開銷4、多級Cache5、使讀失效優先于寫失效縮短命中時間6、避免在索引緩存期間進行地址轉換2025/3/6計算機體系結構7604/04-課堂練習:直接映像Cache和兩路組相聯Cache，試問他們對CPU性能的影響？先求平均訪存時間，然后再計算CPU性能。分析時請用以下假設：（1）理想Cache(命中率為100%）情況下CPI為1.0，時鐘周期為0.35ns，平均每條指令訪存1.4次（2）兩種Cache容量均為128KB，塊大小都是64B（3）采用組相聯時，由于多路選擇器的存在，時鐘周期增加到原來的1.35倍（4）兩種結構的失效開銷都是65ns(在實際應用中，應取整為整數個時鐘周期）（5）命中時間為1個cycle，128KB直接映像Cache的失效率為2.1%,相同容量的兩路組相聯Cache的失效率為1.9%2025/3/6計算機體系結構77多級cache的性能分析局部失效率：該級Cache的失效次數/到達該級Cache的訪存次數Miss

rateL1

forL1cacheMissrateL2forL2cache全局失效率：該級Cache的失效次數/CPU發出的訪存總次數MissrateL1forL1cacheMissrateL1×MissrateL2forL2cache全局失效率是度量L2cache性能的更好方法性能參數AMAT=HitTimeL1+MissrateL1×MisspenaltyL1MisspenaltyL1=HitTimeL2+MissrateL2×MisspenaltyL2AMAT=HitTimeL1+MissrateL1×(HitTimeL2+MissrateL2×MisspenaltyL2)2025/3/6計算機體系結構78L1

cache失效率對于I-Cache和D-Cache分開的L1

Cache

MissRateL1=%inst×MissRateI-Cache+%data×MissRateD-Cache

%inst=PercentofInstructionAccesses=1/(1+%LS)

%data=PercentofDataAccesses=%LS/(1+%LS)

%LS=FrequencyofLoadandStoreinstructions每條指令的L1失效次數:

MissesperInstructionL1=MissRateL1×(1+%LS)

MissesperInstructionL1=MissRateI-Cache+%LS×MissRateD-Cache2025/3/6計算機體系結構79具有二級Cache的AMAT舉例Problem:計算AMATI-Cache失效率=

1%，D-Cache失效率=

10%L2

Cache失效率=

40%L1命中時間=

1

cycle(I-Cache和D-Cache相同）L2命中時間=

8

cycles，L2失效開銷=

100cyclesLoad+Store指令頻度=

25%Solution：平均每條指令訪存次數=

1+25%

=

1.25平均每條指令的失效次數=

1%+25%×10%

=

0.035L1的失效率=

0.035/1.25=0.028L1的失效開銷=

8

+

0.4×100

=

48

cyclesAMAT

=

1+0.028×48

=

2.3442025/3/6計算機體系結構80Memory

Stall

CyclesPerInstructionMemoryStallCyclesperInstruction=MemoryAccessperInstruction×MissRateL1×MissPenaltyL1=(1+%LS)×MissRateL1×MissPenaltyL1=(1+%LS)×MissRateL1×(HitTimeL2+MissRateL2×MissPenaltyL2)MemoryStallCyclesperInstruction=MissesperInstructionL1×HitTimeL2+MissesperInstructionL2×MissPenaltyL2MissesperInstructionL1=(1+%LS)×MissRateL1MissesperInstructionL2=(1+%LS)×MissRateL1×MissRateL22025/3/6計算機體系結構81兩級Cache的性能Problem:程序運行產生1000個存儲器訪問I-Cachemisses=5,D-Cachemisses=35,L2Cachemisses=8L1Hit=1cycle,L2Hit=8cycles,L2Misspenalty=80cyclesLoad+Storefrequency=25%,CPIexecution=1.1(perfectcache)計算memorystallcyclesperinstruction和有效的CPI如果沒有L2

cache,有效的CPI是多少？Solution：L1MissRate=(5+35)/1000=0.04(or4%peraccess)L1missesperInstruction=0.04×(1+0.25)=0.05L2missesperInstruction=(8/1000)×1.25=0.01MemorystallcyclesperInstruction=0.05×8+0.01×80=1.2CPIL1+L2=

1.1+1.2=2.3,CPI/CPIexecution=2.3/1.1=2.1xslowerCPIL1only=1.1+0.05×80=5.1(worse)2025/3/6計算機體系結構82不同大小的L2cache對應的執行時間2025/3/6計算機體系結構83Missratesversuscachesizeformultilevelcaches2025/3/6計算機體系結構84兩級Cache的一些研究結論在L2比L1大得多得情況下，兩級Cache全局失效率和容量與第二級Cache相同的單級Cache的失效率接近局部失效率不是衡量第二級Cache的好指標它是第一級Cache失效率的函數不能全面反映兩級Cache體系的性能第二級Cache設計需考慮的問題容量：一般很大，可能沒有容量失效，只有強制性失效和沖突失效相聯度對第二級Cache的作用Cache可以較大，以減少失效次數多級包容性問題：第一級Cache中的數據是否總是同時存在于第二級Cache中。如果L1和L2的塊大小不同，增加了多級包容性實現的復雜性2025/3/6計算機體系結構85多級Cache舉例Giventhedatabelow,whatistheimpactofsecond-levelcacheassociativityonitsmisspenalty?HittimeL2fordirectmapped=10clockcyclesTwo-waysetassociativityincreaseshittimeby0.1clockcyclesto10.1clockcyclesLocalmissrateL2fordirectmapped=25%LocalmissrateL2fortwo-waysetassociative=20%MisspenaltyL2=100clockcycles結論：提高相聯度，可減少第一級Cache的失效開銷第二級Cache特點：容量大，高相聯度，塊較大，重點減少失效次數。2025/3/6計算機體系結構86讓讀優先于寫圖示2025/3/6計算機體系結構87讓讀失效優先于寫由于讀操作為大概率事件，需要讀失效優先，以提高性能Write-ThroughCache->WriteBuffer(寫緩沖)，特別對寫直達法更有效WriteBuffer:CPU不必等待寫操作完成，即將要寫的數據和地址送到WriteBuffer后，CPU繼續作其他操作。寫緩沖導致對存儲器訪問的復雜化在讀失效時寫緩沖中可能保存有所讀單元的最新值，還沒有寫回例如，直接映射、寫直達、512和1024映射到同一塊。則SWR3,512(R0)LWR1,1024(R0)失效

LWR2,512(R0)失效解決問題的方法推遲對讀失效的處理，直到寫緩沖器清空，導致新的問題——讀失效開銷增大。在讀失效時，檢查寫緩沖的內容，如果沒有沖突，而且存儲器可訪問，就可以繼續處理讀失效寫回法時，也可以利用寫緩沖器來提高性能把臟塊放入緩沖區，然后讀存儲器，最后寫存儲器Write-BackCache->VictimBuffer被替換的臟塊放到了victimbuffer在臟塊被寫回前，需要處理讀失效問題:victimbuffer可能含有該讀失效要讀取的塊Solution:查找victimbuffer，如果命中直接將該塊調入Cache2025/3/6計算機體系結構88縮短命中時間Copyright?2011,ElsevierInc.AllrightsReserved.FigureB.16Missrateversusvirtuallyaddressedcachesizeofaprogrammeasuredthreeways:withoutprocessswitches(uniprocess),withprocessswitchesusingaprocess-identifiertag(PID),andwithprocessswitchesbutwithoutPIDs(purge).PIDsincreasetheuniprocessabsolutemissrateby0.3%to0.6%andsave0.6%to4.3%overpurging.Agarwal[1987]collectedthesestatisticsfortheUltrixoperatingsystemrunningonaVAX,assumingdirect-mappedcacheswithablocksizeof16bytes.Notethatthemissrategoesupfrom128Kto256K.Suchnonintuitivebehaviorcanoccurincachesbecausechangingsizechangesthemappingofmemoryblocksontocacheblocks,whichcanchangetheconflictmissrate.虛擬地址CacheVS.物理地址CacheCopyright?2011,ElsevierInc.AllrightsReserved.FigureB.17TheoverallpictureofahypotheticalmemoryhierarchygoingfromvirtualaddresstoL2cacheaccess.Thepagesizeis16KB.TheTLBistwo-waysetassociativewith256entries.TheL1cacheisadirect-mapped16KB,andtheL2cacheisafour-waysetassociativewithatotalof4MB.Bothuse64-byteblocks.Thevirtualaddressis64bitsandthephysicaladdressis40bits.虛擬地址轉換與Cache定位并行84.4高級Cache優化方法縮短命中時間1、小而簡單的第一級Cache2、路預測方法增加Cache帶寬3、Cache訪問流水化4、無阻塞Cache減小失效開銷5、多體Cache6、關鍵字優先和提前重啟7、合并寫降低失效率8、編譯優化通過并行降低失效代價或失效率9、硬件預取10、編譯器控制的預取2025/3/6計算機體系結構911、SmallandsimplefirstlevelcachesSmallandsimplefirstlevelcaches容量小，一般命中時間短，有可能做在片內另一方案，保持Tag在片內，塊數據在片外，如DECAlpha第一級Cache應選擇容量小且結構簡單的設計方案Criticaltimingpath:1)定位組(tag),確定tag的位置

2)比較tags,3)選擇正確的塊Direct-mappedcachescanoverlaptagcompareandtransmissionofdata數據傳輸和tag比較并行Lowerassociativityreducespowerbecausefewercachelinesareaccessed簡單的Cache結構、可有效減少tag比較的次數，進而降低功耗2025/3/6計算機體系結構92L1SizeandAssociativity2025/3/6計算機體系結構93Accesstimevs.sizeandassociativityL1SizeandAssociativity2025/3/6計算機體系結構94Energyperreadvs.sizeandassociativity2、WayPrediction為改進命中時間，預測被選中的路(way)預測錯誤會導致更長的命中時間預測的準確性90%+fortwo-way80%+forfour-wayI-cache比D-cache具有更好的準確性90年代中期第一次用于MIPSR10000用于ARMCortex-A8WayPrediction方法也可降低功耗：直接預測要訪問的塊也稱“路選擇”“Wayselection”可有效降低功耗，但一旦預測錯誤會有更長的命中時間2025/3/6計算機體系結構95

高級Cache優化方法縮短命中時間1、小而簡單的第一級Cache2、路預測方法增加Cache帶寬3、Cache訪問流水化4、無阻塞Cache減小失效開銷5、多體Cache6、關鍵字優先和提前重啟7、合并寫降低失效率8、編譯優化通過并行降低失效代價或失效率9、硬件預取10、編譯器控制的預取2025/3/6計算機體系結構963、PipeliningCache實現Cache訪問的流水化提高Cache的帶寬，有利于采用高相聯度的緩存L1

cache的訪問由多個時鐘周期構成Pentium:1cyclePentiumPro–PentiumIII:2cyclesPentium4–Corei7:4cyclesIBM

Power7：3

cycles缺點：增加流水線的段數增加了分支預測錯誤造成的額外開銷增加了Load指令與要使用其結果的指令間的latency增加了I-Cache和D-Cache的延時2025/3/6計算機體系結構972025/3/6計算機體系結構982025/3/6計算機體系結構9904/09-review基本Cache優化方法降低失效率：引起失效的3C1、增加Cache塊的大小2、增大Cache容量3、提高相聯度減少失效開銷4、多級Cache5、使讀失效優先于寫失效縮短命中時間6、避免在索引緩存期間進行地址轉換2025/3/6計算機體系結構10004/09-review高級Cache優化方法縮短命中時間1、小而簡單的第一級Cache2、路預測方法增加Cache帶寬3、Cache訪問流水化4、無阻塞Cache減小失效開銷5、多體Cache6、關鍵字優先和提前重啟7、合并寫降低失效率8、編譯優化通過并行降低失效代價或失效率9、硬件預取10、編譯器控制的預取2025/3/6計算機體系結構1014、NonblockingCaches2025/3/6計算機體系結構102允許在Cache失效下繼續命中在Cache失效時，CPU無需stall主要用于亂序執行和多線程處理器HitunderaMiss減少有效的失效開銷增加Cache的帶寬HitunderMultipleMisses針對多個未解決的Cache失效可能會更多地減少有效的失效開銷增加了Cache控制器的復雜性存儲系統可以支持多個失效時的存儲服務NonblockingCacheTimeline2025/3/6計算機體系結構103EffectivenessofNon-BlockingCache2025/3/6計算機體系結構104MissStatusHoldingRegister(MSHR)MSHR包含正在等待處理的失效相同的塊可以包含多個未解決的Load/Store失效可以有多個未解決的塊地址失效可以分為Primary:第一次發起存取請求時的失效塊Secondary:在后續過程中的失效StructuralStallmiss：MSHR硬件資源耗盡2025/3/6計算機體系結構105NonBlockingCacheOperation當Cache失效時，檢查MSHR是否有匹配的塊地址如果有，為該地址分配新的load/store表項如果沒有，分配新的MSHR和load/store表項如果所有MSHR資源都分配完，則Stall（結構相關）當從底層傳輸Cache塊時處理該塊中的Load和Store指令引起的失效Load：根據blockoffset從該塊中裝載數據到寄存器Store：根據blockoffset將數據寫入該塊指定位置完成該塊所有的失效的Load/Store后，釋放MSHR中的對應表項

2025/3/6計算機體系結構106Multi-PortedCacheDual-PortedDataCache兩個地址端口（每個Cycle支持兩條load/store指令）在現代處理器中保持較高的指令吞吐率TrueMulti-portedCacheDesign所有的控制和數據通路在Cache中是多份的顯著地增加了Cache的面積和訪問時間Multi-BankedCache將cache組織成多個banks每個bank是一個端口可以并行訪問不同的Bank2025/3/6計算機體系結構1075、MultibankedCaches將Cache組織為多個獨立的banks，以支持并行訪問ARMCortex-A8supports1-4banksforL