計算機(jī)系統(tǒng)結(jié)構(gòu)（處理器設(shè)計）：LEC09-高速緩存

1高速緩存（Cache）存儲層次的基本概念Cache結(jié)構(gòu)Cache性能優(yōu)化常見處理器的存儲層次2存儲層次的基本概念3CPU與RAM的速度剪刀差摩爾定律CPU的頻率和RAM的容量每18個月翻一番但RAM的速度增加緩慢通過存儲層次來彌補(bǔ)差距寄存器、Cache、存儲器、IO4

處理器和內(nèi)存速度剪刀差早期Alpha處理器Cache失效延遲1stAlpha(7000): 340ns/5.0ns=

68clksx2or1362ndAlpha(8400): 266ns/3.3ns=

80clksx4or3203rdAlpha(t.b.d.): 180ns/1.7ns=108clksx6or648當(dāng)前主流處理器主頻2GHz以上IBMPower6主頻6GHz以上內(nèi)存延遲50ns左右訪存延遲>100拍多發(fā)射加劇了訪存瓶頸5摩爾定律使CPU的內(nèi)容發(fā)生了變化馮諾依曼結(jié)構(gòu)的核心思想存儲程序：指令和數(shù)據(jù)都存放在存儲器中計算機(jī)的五個組成部分運算器、控制器、存儲器、輸入、輸出運算器和控制器合稱中央處理器（CPU）為了緩解存儲瓶頸，把部分存儲器做在片內(nèi)現(xiàn)在的CPU芯片：控制器+運算器+部分存儲器片內(nèi)Cache占了整個芯片的很大一部分面積6外存儲器輸入設(shè)備輸出設(shè)備控制器運算器數(shù)據(jù)線控制線CPU計算機(jī)硬件系統(tǒng)的組成內(nèi)存Cache7CPU中RAM的面積和晶體管比例CPU名稱片內(nèi)RAM面積片內(nèi)RAM晶體管Alpha2116437%77%StrongArmSA11061%94%PentiumPro64%88%龍芯3A31%80%8存儲層次基本原理程序訪問的局部性：時間局部性和空間局部性新型的應(yīng)用（如媒體）對傳統(tǒng)的局部性提出了挑戰(zhàn)越小越簡單的硬件越快越快的硬件越昂貴9Cache結(jié)構(gòu)10Cache的結(jié)構(gòu)Cache的特征Cache的內(nèi)容是主存儲器內(nèi)容的一個子集Cache沒有程序上的意義，只是為了降低訪存延遲處理器訪問Cache和訪問存儲器使用相同的地址Cache的結(jié)構(gòu)特點同時存儲數(shù)據(jù)和地址通過地址的比較判斷相應(yīng)數(shù)據(jù)是否在Cache中需要考慮所需要的數(shù)據(jù)不在Cache中的情況替換機(jī)制，寫策略等CPU讀寫請求Cache返回數(shù)據(jù)Cache訪存請求內(nèi)存返回數(shù)據(jù)處理器存儲器11Cache的類型Cache塊的位置全相聯(lián)（FullyAssociative）組相聯(lián)（SetAssociative）直接相聯(lián)（DirectMapped）Cache失效時的替換機(jī)制?隨機(jī)替換,LRU,FIFO寫策略寫命中策略：寫回（WriteBack）vs.寫穿透（WriteThrough）寫失效策略：寫分配（WriteAllocate）vs.寫不分配（WriteNon-allocate）12全相聯(lián)、直接相聯(lián)、組相聯(lián)同一單元在不同結(jié)構(gòu)Cache中的位置直接相聯(lián)全相聯(lián)組相聯(lián)（a）直接相聯(lián)（b）全相聯(lián)（c）組相聯(lián)內(nèi)存13全相聯(lián)命中率高硬件復(fù)雜、延遲大CCCCCCCCTagOffsetMux+hitdata…14CTagOffsetMuxIndexhitdata直接相聯(lián)硬件簡單、延遲最小命中率低15TagOffsetIndexChitMuxMuxCMuxdata+TagTaghit0hit1data1data0組相聯(lián)介于全相聯(lián)和直接相聯(lián)之間16Cache替換算法對直接相聯(lián)Cache不存在替換算法問題常見的替換算法隨機(jī)替換：LRU：FIFO：每1000條指令失效次數(shù)統(tǒng)計SPECCPU2000中的gap,gcc,gzip,mcf,perl,applu,art,equake,lucas,swim10個程序Aplha結(jié)構(gòu)，塊大小64KB2-way4-way8-wayLRURandFIFOLRURandFIFOLRURandFIFO16KB114.1117.3115.5111.7115.1113.3109.0111.8110.464KB103.4104.3103.9102.4102.3103.199.7100.5100.3256KB92.292.192.592.192.192.592.192.192.517寫命中時采取的策略寫穿透（WriteThrough）寫Cache的同時寫內(nèi)存內(nèi)存里的數(shù)據(jù)永遠(yuǎn)是最新的，Cache替換時直接扔掉

Cache塊管理簡單，只需有效位寫回（Write-back）只寫Cache不寫內(nèi)存替換時要把Cache塊寫回內(nèi)存Cache塊狀態(tài)復(fù)雜一些，需要有效位和臟位寫回/寫穿透的使用L1到L2用寫穿透的多，L2較快L2到內(nèi)存用寫回的多，內(nèi)存太慢了龍芯2號兩級都采用寫回策略。

18寫失效時采取的策略寫分配（WriteAllocate）先把失效塊讀到Cache，再在Cache中寫一般用在寫命中時采用寫回策略的Cache中

寫不分配（WriteNon-allocate）寫Cache失效時直接寫進(jìn)內(nèi)存

一般用在寫命中時采用寫穿透的Cache中

19Cache性能優(yōu)化20Cache性能分析CPU執(zhí)行時間與訪存延遲的關(guān)系A(chǔ)MAT=AverageMemoryAccessTimeCPIALUOps

不包括訪存指令21Cache性能優(yōu)化降低失效率（MissRate）降低失效延遲（MissPenalty）降低命中延遲（HitTime）提高Cache訪問并行性22降低失效率增加塊大小增加Cache容量增加相聯(lián)數(shù)目路預(yù)測（WayPrediction）軟件優(yōu)化23引起Cache失效的因素（3C/4C）冷失效（ColdMiss或CompulsoryMiss）CPU第一次訪問Cache塊時Cache中還沒有該Cache塊引起的失效冷失效是不可避免的，即使Cache容量再大也會有容量失效（CapacityMiss）程序執(zhí)行過程中，有限的Cache容量導(dǎo)致Cache放不下時替換出部分Cache塊，被替換的Cache塊再被訪問時引起失效一定容量下全相聯(lián)Cache中的失效沖突失效（ConflictMiss）直接相聯(lián)或組相聯(lián)Cache中，不同Cache塊由于index相同引起沖突在全相聯(lián)Cache不存在一致性失效（CoherenceMiss）由于維護(hù)Cache一致性引起的失效24CacheSize(KB)MissRateperType00.020.040.060.080.10.120.1412481632641281-way2-way4-way8-wayCapacity

Compulsory

3C失效率分析（SPEC92）Conflict25大?。↘B）相聯(lián)度失效率冷失效容量失效沖突失效冷失效百分比容量失效百分比沖突失效百分比41-way0.0980.00010.0700.0270.1%72%28%42-way0.0760.00010.0700.0050.1%93%7%44-way0.0710.00010.0700.0010.1%99%1%48-way0.0710.00010.0700.0000.1%100%0%81-way0.0680.00010.0440.0240.1%65%35%82-way0.0490.00010.0440.0050.1%90%10%84-way0.0440.00010.0440.0000.1%99%1%88-way0.0440.00010.0440.0000.1%100%0%161-way0.0490.00010.0400.0090.1%82%17%162-way0.0410.00010.0400.0010.2%98%2%164-way0.0410.00010.0400.0000.2%99%0%168-way0.0410.00010.0400.0000.2%100%0%321-way0.0420.00010.0370.0050.2%89%11%322-way0.0380.00010.0370.0000.2%99%0%324-way0.0370.00010.0370.0000.2%100%0%328-way0.0370.00010.0370.0000.2%100%0%641-way0.0370.00010.0280.0080.2%77%23%642-way0.0310.00010.0280.0030.2%91%9%644-way0.0300.00010.0280.0010.2%95%4%648-way0.0290.00010.0280.0010.2%97%2%1281-way0.0210.00010.0190.0020.3%91%8%1282-way0.0190.00010.0190.0000.3%100%0%1284-way0.0190.00010.0190.0000.3%100%0%1288-way0.0190.00010.0190.0000.3%100%0%2561-way0.0130.00010.0120.0010.5%94%6%2562-way0.0120.00010.0120.0000.5%99%0%2564-way0.0120.00010.0120.0000.5%99%0%2568-way0.0120.00010.0120.0000.5%99%0%SPECCPU2000,Alpha結(jié)構(gòu)26通過增加塊大小降低失效率利用空間局部性降低冷失效，增加沖突失效以及容量失效SPEC92，DECstation5000小容量Cache塊較小27通過增加Cache大小提高命中率一級Cache訪問直接決定時鐘周期尤其是在深亞微米的情況下，連線延遲很大PIII一級Cache為16KB，PIV一級Cache為8KB。增加片內(nèi)Cache大小增加芯片面積有的處理器片內(nèi)Cache面積占整個芯片面積的80%以上現(xiàn)代處理器二級或三級Cache大小已經(jīng)達(dá)到幾MB甚至幾十MB?，F(xiàn)代通用處理器的一級Cache大小HPPA8700：一級Cache為1MB+1.5MB，沒有二級Cache其他RISC處理器（Alpha,Power,MIPS,UltraSPARC）32/64KB+32/64KBPIV12KopTracecache+8KB數(shù)據(jù)Cache（PIII:16KB+16KB）反映出設(shè)計人員的不同取舍28通過增加相聯(lián)度降低失效率增加相聯(lián)度2:1規(guī)則：大小為N的直接相聯(lián)的Cache命中率與大小為N/2的二路組相聯(lián)的Cache命中率相當(dāng)八路組相聯(lián)的效果已經(jīng)與全相聯(lián)的失效率相差很小增加相聯(lián)度會增加時鐘周期延遲例如，直接相連時鐘周期為1ns，2路組相聯(lián)為1.36ns，4路組相聯(lián)為1.44ns，8路組相聯(lián)為1.52ns，失效延遲為25時鐘周期Cache訪問可能是整個處理器的關(guān)鍵路徑Cache容量（KB）相聯(lián)度124843.443.253.223.2882.692.582.552.62162.232.402.462.53322.062.302.372.45641.922.142.182.251281.521.841.922.002561.321.661.741.8229通過“路猜測”和“偽相聯(lián)”提高命中率結(jié)合直接相聯(lián)訪問時間短和組相聯(lián)命中率高的優(yōu)點在多路相聯(lián)的結(jié)構(gòu)中，每次Cache訪問只檢查一路，如果不命中再檢查其他路兩種命中：hit和pseudohit直接判斷第0路，或進(jìn)行Way-Prediction：Alpha21264ICache路猜測命中率85%，hit時間為1拍，pseudohit時間3拍不用并行訪問每一路，可以大幅度降低功耗缺點：流水線控制復(fù)雜，在L2以下cache中用得較多，包括MIPSR10000以及UltraSPARC的L2。HitTimePseudoHitTimeMissPenaltyTime30通過軟件優(yōu)化降低失效率McFarling[1989]在8KB直接相聯(lián)的Cache上通過軟件優(yōu)化降低失效率75%常見軟件優(yōu)化技術(shù)數(shù)組合并（MergingArrays）循環(huán)交換（LoopInterchange）循環(huán)合并（LoopFusion）數(shù)組分塊（ArrayBlocking）31數(shù)組合并通過數(shù)組合并降低數(shù)組val和key的沖突，增加空間局部性/*Before:2sequentialarrays*/intval[SIZE];intkey[SIZE];/*After:1arrayofstuctures*/structmerge{ intval; intkey;};structmergemerged_array[SIZE];32循環(huán)交換通過循環(huán)交換提高空間局部性，把非連續(xù)訪問變換成連續(xù)訪問/*Before*/for(k=0;k<100;k=k+1)

for(j=0;j<100;j=j+1) for(i=0;i<5000;i=i+1) x[i][j]=2*x[i][j];/*After*/for(k=0;k<100;k=k+1)

for(i=0;i<5000;i=i+1)

for(j=0;j<100;j=j+1) x[i][j]=2*x[i][j];33循環(huán)合并通過循環(huán)合并提高空間局部性，數(shù)組a&c的失效次數(shù)從2次降低到1次/*Before*/for(i=0;i<N;i=i+1) for(j=0;j<N;j=j+1)

a[i][j]

=1/b[i][j]*c[i][j];for(i=0;i<N;i=i+1) for(j=0;j<N;j=j+1) d[i][j]=a[i][j]

+c[i][j];/*After*/for(i=0;i<N;i=i+1) for(j=0;j<N;j=j+1)

{ a[i][j]=1/b[i][j]*c[i][j];

d[i][j]=a[i][j]+c[i][j];}34數(shù)組分塊分塊前，y和z失效N3次，x失效N2次，總失效次數(shù)從2N3+N2

分塊后，由于可以在cache中放下BxB的小矩陣，y和z失效1次，可以用B次，因此失效次數(shù)從2N3+N2

降為2N3/B+N2/*Before*/for(i=0;i<N;i=i+1) for(j=0;j<N;j=j+1) {r=0; for(k=0;k<N;k=k+1){ r=r+y[i][k]*z[k][j];}; x[i][j]=r; };/*After*/for(jj=0;jj<N;jj=jj+B)for(kk=0;kk<N;kk=kk+B)for(i=0;i<N;i=i+1) for(j=jj;j<min(jj+B-1,N);j=j+1) {r=0; for(k=kk;k<min(kk+B-1,N);k=k+1){ r=r+y[i][k]*z[k][j];}; x[i][j]=x[i][j]+r; };35軟件優(yōu)化的效果36降低MissPenalty關(guān)鍵字優(yōu)先讀失效優(yōu)先VictimCache寫合并多級Cache37通過關(guān)鍵字優(yōu)先降低失效延遲在Cache訪問失效時，優(yōu)先訪問讀訪問需要的字例如，Cache塊大小為64字節(jié)，分為8個8字節(jié)的雙字，如果取數(shù)指令訪問其中的第6個雙字引起Cache失效，就按6、7、0、1、2、3、4、5的次序，而不是按0、1、2、3、4、5、6、7的次序訪問內(nèi)存關(guān)鍵字優(yōu)先的實現(xiàn)只需要對訪問地址進(jìn)行簡單變換。在失效的數(shù)據(jù)從內(nèi)存取回之后，往Cache送的同時直接送回到寄存器也可以降低失效延遲。block38通過讀優(yōu)先降低失效延遲讀Cache失效對指令流水線效率的影響比寫失效大在處理器中一般都有寫緩存（WriteBuffer），寫指令只要把要寫的數(shù)據(jù)寫到寫緩存就可以提交，再由寫緩存寫到Cache或內(nèi)存取數(shù)在數(shù)據(jù)讀回來回前取數(shù)指令不能提交，與取數(shù)指令存在數(shù)據(jù)相關(guān)的后續(xù)指令要等待取數(shù)操作讀回來的數(shù)據(jù)才能執(zhí)行，可見讀Cache失效容易堵塞指令流水線在進(jìn)行Cache失效處理時，優(yōu)先處理讀失效以減小堵塞讀失效時要注意與WriteBuffer的RAW相關(guān)，不能等寫緩存為空，要動態(tài)檢查寫緩存讀失效可能需要替換dirty塊，不要把替換塊寫回到內(nèi)存再讀，可以把替換塊寫到寫緩存，然后先讀，后把寫緩存的內(nèi)容寫回內(nèi)存39通過寫合并降低失效延遲Write-through的Cache依賴于寫緩存（WriteBuffer）處理器寫到WB就算完成寫操作，由WB寫到下一級存儲器注意一致性問題：處理器后續(xù)的讀操作、外設(shè)的DMA操作等Write-back的Cache也使用WB來臨時存放替換出去的cache塊通過把寫緩存中對同一Cache塊的寫操作進(jìn)行合并來提高寫緩存使用率，減少處理器等待注意IO操作不能合并塊地址vvvv1001word01081word11161word21241word3塊地址vvvv1001word01word11word21word340通過VictimCache降低失效延遲在直接相聯(lián)的Cache中避免沖突失效增加緩存（VictimCache）保存從Cache中替換出來的數(shù)據(jù)Jouppi[1990]：4項victimcache可消除直接相聯(lián)4KBCache中20%-95%的沖突訪問在Alpha,HP等處理器中應(yīng)用41通過二級Cache降低失效延遲通過L2降低失效延遲

AMAT=HitTimeL1+MissRateL1xMissPenaltyL1

MissPenaltyL1=HitTimeL2+MissRateL2xMissPenaltyL2 AMAT=HitTimeL1+

MissRateL1

x(HitTimeL2+

MissRateL2

xMissPenaltyL2)L2的失效率局部失效率（Localmissrate）—L2失效次數(shù)除以L2訪問次數(shù)全局失效率（Globalmissrate）

—L2失效次數(shù)除以所有訪存次數(shù)（MissRateL1xMissRateL2）局部失效率較高（10%-20%），全局失效率很低（<1%）42降低HitTime簡化Cache設(shè)計并行訪問Cache與TLB增加Cache訪問流水級43簡化Cache設(shè)計訪問Cache常常是整個CPU的時鐘關(guān)鍵路徑Cache越小，延遲越小直接相聯(lián)的Cache延遲小簡化一級Cache設(shè)計需要統(tǒng)籌考慮PIV數(shù)據(jù)Cache從PIII的16KB降低為8KB，而且只有定點可以訪問，從而達(dá)到高主頻但PIV的二級Cache只有6拍的訪問延遲44避免地址轉(zhuǎn)換延遲：虛地址CacheAddrTLBL1MEMVAPAPA通過虛地址直接訪問Cache減少虛實地址轉(zhuǎn)換時間區(qū)分進(jìn)程問題：不同進(jìn)程的虛地址空間是一樣的，需要在進(jìn)程切換時候刷Cache以維護(hù)一致性，增加了冷失效別名（aliases）問題：操作系統(tǒng)有時候（如為了進(jìn)程間共享）需要不同的虛地址對應(yīng)同一物理地址AddrL1TLBTagCmpVAPATagsPA45虛地址Cache中多進(jìn)程對Cache命中率的影響進(jìn)程切換問題可以通過在TLB中增加進(jìn)程號的方式來解決單進(jìn)程、多進(jìn)程切換時刷Cache、多進(jìn)程用ID號來區(qū)分虛地址Y軸表示Cache失效率；X軸表示Cache大?。?KB-1024KB）46虛Index實Tag技術(shù)在用Index從cache中讀Tag的同時，進(jìn)行虛實地址轉(zhuǎn)換，可以使用物理地址做tag如何保證虛實地址Index位的一致？增加頁大小、增加相聯(lián)度軟件保證：頁著色（Pagecoloring）PageaddressPageOffsetAddressTagIndexBlockOffset47增加Cache訪問流水級Cache訪問時間是處理器主頻的決定因素之一其他因素包括加法及bypass時間等把cache訪問分成多拍以提高主頻MIPS：1拍Alpha：2拍增加流水節(jié)拍增加了load-use延遲48提高Cache訪問并行性非阻塞Cache硬件預(yù)取軟件預(yù)取49非阻塞Caches非阻塞（Non-blocking/Lockup-free）Cache在訪問失效時允許后續(xù)的訪問繼續(xù)進(jìn)行hitundermiss、hitundermultiplemiss、missundermiss前面的失效訪問不影響后續(xù)訪問，需要支持多個outstanding訪問，需要類似與保留棧的訪存隊列機(jī)制在亂序執(zhí)行的CPU中使用，顯著增加Cache控制器復(fù)雜度多個層次的非阻塞訪問L1、L2、內(nèi)存控制器龍芯2號支持24個L1非阻塞訪問，8個L2非阻塞訪問50SPEC程序的非阻塞訪存效果8KB直接相聯(lián)數(shù)據(jù)Cache，塊大小32字節(jié)，失效延遲16拍浮點程序AMAT=0.68->0.52->0.34->0.26定點程序AMAT=0.24->0.20->0.19->0.19IntegerFloatingPoint51通過硬件預(yù)取降低失效率指令預(yù)取Alpha21064在Cache失效時取連續(xù)兩塊，多取的Cache塊存放在流緩存（streambuffer）中，下一次Cache失效時先檢查指令是否在流緩存中。數(shù)據(jù)預(yù)取Jouppi[1990]：對4KB的Cache，1項流緩存可以命中25%的Cache失效訪問，4項流緩存可以命中43%的Cache失效訪問Palacharla&Kessler[1994]：指令和數(shù)據(jù)Cache各為四路組相聯(lián)的64KB，對科學(xué)計算程序，8項流緩存可以命中50%-70%的Cache失效訪問預(yù)取對訪存帶寬提出了更高的要求52通過軟件預(yù)取降低失效率軟件預(yù)取都是數(shù)據(jù)預(yù)取預(yù)取到寄存器:(HPPA-RISCloads)預(yù)取到Cache:(MIPSIV,PowerPC,SPARCv.9)預(yù)取指令不發(fā)生例外，預(yù)取到Cache的指令可以不等待數(shù)據(jù)返回預(yù)取指令開銷：占用指令槽多發(fā)射結(jié)構(gòu)對預(yù)取指令占用指令槽不怎么敏感龍芯2號對軟件預(yù)取的支持目標(biāo)寄存器為0號寄存器的取數(shù)指令不發(fā)生例外，不阻塞流水線53Cache優(yōu)化小結(jié)優(yōu)化技術(shù)失效延遲命中率命中時間硬件復(fù)雜度多級cache+2關(guān)鍵字優(yōu)先+2讀失效優(yōu)先+1合并寫緩存+1Victimcache++2增加塊大小-+0增加cache大小+-1增加相聯(lián)度+-1偽相聯(lián)、路猜測+2編譯優(yōu)化+0非阻塞cache+3硬件預(yù)取++2i,3d軟件預(yù)取++3小而簡單的cache-+0Cache和TLB訪問并行+2流水cache訪問+154常見處理器的存儲層次55MIPSR10000存儲層次L1Dcache：32KB，2路，2拍延遲Icache：32KB，2路L2片外，2路偽相聯(lián)（wayprediction）

512KB-16MB1個load/store部件16項addressqueue特點：predecodeicache，L2偽相聯(lián)56HPPA-8x00存儲層次L1:0.5~1.5MB8500之前為片外（直接映射），之后為片內(nèi)（4路組相聯(lián)）L2一直到8700，無2個load/store部件28項addr