計(jì)算機(jī)組織與結(jié)構(gòu):LEC09_高速緩存_第1頁
計(jì)算機(jī)組織與結(jié)構(gòu):LEC09_高速緩存_第2頁
計(jì)算機(jī)組織與結(jié)構(gòu):LEC09_高速緩存_第3頁
計(jì)算機(jī)組織與結(jié)構(gòu):LEC09_高速緩存_第4頁
計(jì)算機(jī)組織與結(jié)構(gòu):LEC09_高速緩存_第5頁
已閱讀5頁,還剩60頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、1,高性能計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),2,高速緩存(Cache),存儲(chǔ)層次的基本概念 Cache結(jié)構(gòu) Cache性能優(yōu)化 常見處理器的存儲(chǔ)層次,3,存儲(chǔ)層次的基本概念,4,CPU與RAM的速度剪刀差,摩爾定律 CPU的頻率和RAM的容量每18個(gè)月翻一番 但RAM的速度增加緩慢 通過存儲(chǔ)層次來彌補(bǔ)差距 寄存器、Cache、存儲(chǔ)器、IO,5,處理器和內(nèi)存速度剪刀差,早期Alpha處理器Cache失效延遲 1st Alpha (7000): 340 ns/5.0 ns = 68 clks x 2 or 136 2nd Alpha (8400):266 ns/3.3 ns = 80 clks x 4 or 320

2、 3rd Alpha (t.b.d.):180 ns/1.7 ns =108 clks x 6 or 648 當(dāng)前主流處理器主頻2GHz以上 IBM Power 6主頻6GHz以上 內(nèi)存延遲50ns左右 訪存延遲100拍 多發(fā)射加劇了訪存瓶頸,6,摩爾定律使CPU的內(nèi)容發(fā)生了變化,馮諾依曼結(jié)構(gòu)的核心思想 存儲(chǔ)程序:指令和數(shù)據(jù)都存放在存儲(chǔ)器中 計(jì)算機(jī)的五個(gè)組成部分 運(yùn)算器、控制器、存儲(chǔ)器、輸入、輸出 運(yùn)算器和控制器合稱中央處理器(CPU) 為了緩解存儲(chǔ)瓶頸,把部分存儲(chǔ)器做在片內(nèi) 現(xiàn)在的CPU芯片:控制器+運(yùn)算器+部分存儲(chǔ)器 片內(nèi)Cache占了整個(gè)芯片的很大一部分面積,7,外存儲(chǔ)器,輸入設(shè)備,輸出

3、設(shè)備,控制器,運(yùn)算器,數(shù)據(jù)線,CPU,計(jì)算機(jī)硬件系統(tǒng)的組成,內(nèi)存,Cache,8,CPU中RAM的面積和晶體管比例,9,存儲(chǔ)層次基本原理,程序訪問的局部性:時(shí)間局部性和空間局部性 新型的應(yīng)用(如媒體)對(duì)傳統(tǒng)的局部性提出了挑戰(zhàn) 越小越簡(jiǎn)單的硬件越快 越快的硬件越昂貴,10,Cache結(jié)構(gòu),11,Cache的結(jié)構(gòu),Cache的特征 Cache的內(nèi)容是主存儲(chǔ)器內(nèi)容的一個(gè)子集 Cache沒有程序上的意義,只是為了降低訪存延遲 處理器訪問Cache和訪問存儲(chǔ)器使用相同的地址 Cache的結(jié)構(gòu)特點(diǎn) 同時(shí)存儲(chǔ)數(shù)據(jù)和地址 通過地址的比較判斷相應(yīng)數(shù)據(jù)是否在Cache中 需要考慮所需要的數(shù)據(jù)不在Cache中的情況

4、 替換機(jī)制,寫策略等,12,Cache的類型,Cache塊的位置 全相聯(lián)(Fully Associative) 組相聯(lián)( Set Associative) 直接相聯(lián)( Direct Mapped) Cache失效時(shí)的替換機(jī)制? 隨機(jī)替換, LRU, FIFO 寫策略 寫命中策略:寫回(Write Back)vs. 寫穿透( Write Through) 寫失效策略:寫分配(Write Allocate)vs. 寫不分配(Write Non-allocate),13,全相聯(lián)、直接相聯(lián)、組相聯(lián),同一單元在不同結(jié)構(gòu)Cache中的位置 直接相聯(lián) 全相聯(lián) 組相聯(lián),(a)直接相聯(lián),(b)全相聯(lián),(c)組相

5、聯(lián),內(nèi)存,14,全相聯(lián),命中率高 硬件復(fù)雜、延遲大,hit,data,15,直接相聯(lián),硬件簡(jiǎn)單、延遲最小 命中率低,16,組相聯(lián),介于全相聯(lián)和直接相聯(lián)之間,17,Cache替換算法,對(duì)直接相聯(lián)Cache不存在替換算法問題 常見的替換算法 隨機(jī)替換: LRU: FIFO: 每1000條指令失效次數(shù)統(tǒng)計(jì) SPEC CPU2000中的gap, gcc, gzip, mcf, perl, applu, art, equake, lucas, swim 10個(gè)程序 Aplha結(jié)構(gòu),塊大小64KB,18,寫命中時(shí)采取的策略,寫穿透(Write Through) 寫Cache的同時(shí)寫內(nèi)存 內(nèi)存里的數(shù)據(jù)永遠(yuǎn)是

6、最新的,Cache替換時(shí)直接扔掉 Cache塊管理簡(jiǎn)單,只需有效位 寫回(Write-back) 只寫Cache不寫內(nèi)存 替換時(shí)要把Cache塊寫回內(nèi)存 Cache塊狀態(tài)復(fù)雜一些,需要有效位和臟位 寫回/寫穿透的使用 L1到L2用寫穿透的多,L2較快 L2到內(nèi)存用寫回的多,內(nèi)存太慢了 龍芯2號(hào)兩級(jí)都采用寫回策略。,19,寫失效時(shí)采取的策略,寫分配( Write Allocate ) 先把失效塊讀到Cache,再在Cache中寫 一般用在寫命中時(shí)采用寫回策略的Cache中 寫不分配(Write Non-allocate) 寫Cache失效時(shí)直接寫進(jìn)內(nèi)存 一般用在寫命中時(shí)采用寫穿透的Cache中,

7、20,Cache性能優(yōu)化,21,Cache性能分析,CPU執(zhí)行時(shí)間與訪存延遲的關(guān)系 AMAT = Average Memory Access Time CPIALUOps 不包括訪存指令,22,Cache性能優(yōu)化,降低失效率(MissRate) 降低失效延遲(MissPenalty) 降低命中延遲(HitTime) 提高Cache訪問并行性,23,降低失效率,增加塊大小 增加Cache容量 增加相聯(lián)數(shù)目 路預(yù)測(cè)(Way Prediction) 軟件優(yōu)化,24,引起Cache失效的因素(3C/4C),冷失效(Cold Miss或Compulsory Miss) CPU第一次訪問Cache塊時(shí)Ca

8、che中還沒有該Cache塊引起的失效 冷失效是不可避免的,即使Cache容量再大也會(huì)有 容量失效(Capacity Miss) 程序執(zhí)行過程中,有限的Cache容量導(dǎo)致Cache放不下時(shí)替換出部分Cache塊,被替換的Cache塊再被訪問時(shí)引起失效 一定容量下全相聯(lián)Cache中的失效 沖突失效(Conflict Miss) 直接相聯(lián)或組相聯(lián)Cache中,不同Cache塊由于index相同引起沖突 在全相聯(lián)Cache不存在 一致性失效(Coherence Miss) 由于維護(hù)Cache一致性引起的失效,25,3C失效率分析(SPEC92),Conflict,26,SPEC CPU2000, A

9、lpha結(jié)構(gòu),27,通過增加塊大小降低失效率,利用空間局部性 降低冷失效,增加沖突失效以及容量失效 SPEC92,DECstation 5000 小容量Cache塊較小,28,通過增加Cache大小提高命中率,一級(jí)Cache訪問直接決定時(shí)鐘周期 尤其是在深亞微米的情況下,連線延遲很大 PIII一級(jí)Cache為16KB,PIV一級(jí)Cache為8KB。 增加片內(nèi)Cache大小增加芯片面積 有的處理器片內(nèi)Cache面積占整個(gè)芯片面積的80%以上 現(xiàn)代處理器二級(jí)或三級(jí)Cache大小已經(jīng)達(dá)到幾MB甚至幾十MB。 現(xiàn)代通用處理器的一級(jí)Cache大小 HP PA8700:一級(jí)Cache為1MB+1.5MB,

10、沒有二級(jí)Cache 其他RISC處理器( Alpha, Power, MIPS, Ultra SPARC) 32/64KB+32/64KB PIV 12Kop Trace cache+8KB數(shù)據(jù)Cache(PIII: 16KB+16KB) 反映出設(shè)計(jì)人員的不同取舍,29,通過增加相聯(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)度會(huì)增加時(shí)鐘周期延遲 例如,直接相連時(shí)鐘周期為1ns,2路組相聯(lián)為1.36ns,4路組相聯(lián)為1.44ns,8路組相聯(lián)為1.52ns,失效

11、延遲為25時(shí)鐘周期 Cache訪問可能是整個(gè)處理器的關(guān)鍵路徑,30,通過“路猜測(cè)”和“偽相聯(lián)”提高命中率,結(jié)合直接相聯(lián)訪問時(shí)間短和組相聯(lián)命中率高的優(yōu)點(diǎn) 在多路相聯(lián)的結(jié)構(gòu)中,每次Cache訪問只檢查一路,如果不命中再檢查其他路 兩種命中:hit和pseudohit 直接判斷第0路,或進(jìn)行Way-Prediction:Alpha 21264 ICache路猜測(cè)命中率85%,hit時(shí)間為1拍,pseudohit時(shí)間3拍 不用并行訪問每一路,可以大幅度降低功耗 缺點(diǎn):流水線控制復(fù)雜,在L2以下cache中用得較多,包括 MIPS R10000以及UltraSPARC的L2。,Hit Time,Pseu

12、do Hit Time,Miss Penalty,Time,31,通過軟件優(yōu)化降低失效率,McFarling 1989在8KB直接相聯(lián)的Cache上通過軟件優(yōu)化降低失效率75% 常見軟件優(yōu)化技術(shù) 數(shù)組合并(Merging Arrays) 循環(huán)交換(Loop Interchange) 循環(huán)合并(Loop Fusion) 數(shù)組分塊(Array Blocking),32,數(shù)組合并,通過數(shù)組合并降低數(shù)組val和key的沖突,增加空間局部性 /* Before: 2 sequential arrays */ int valSIZE; int keySIZE; /* After: 1 array of s

13、tuctures */ struct merge int val; int key; ; struct merge merged_arraySIZE;,33,循環(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) xij = 2 * xij; /* After */ for (k = 0; k 100; k = k+1) for (i = 0; i 5000; i = i+1) for (j

14、 = 0; j 100; j = j+1) xij = 2 * xij;,34,循環(huán)合并,通過循環(huán)合并提高空間局部性,數(shù)組a ,35,數(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 + yik*zkj; xij = r; ;

15、 /* 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 + yik*zkj; xij = xij + r; ;,36,軟件優(yōu)化的效果,37,降低MissPenalty,關(guān)鍵字優(yōu)先 讀失效優(yōu)先 Victim Cache 寫合并 多級(jí)Cache,38,通過關(guān)鍵字優(yōu)先降低失效延遲,

16、在Cache訪問失效時(shí),優(yōu)先訪問讀訪問需要的字 例如,Cache塊大小為64字節(jié),分為8個(gè)8字節(jié)的雙字,如果取數(shù)指令訪問其中的第6個(gè)雙字引起Cache失效,就按6、7、0、1、2、3、4、5的次序,而不是按0、1、2、3、4、5、6、7的次序訪問內(nèi)存 關(guān)鍵字優(yōu)先的實(shí)現(xiàn)只需要對(duì)訪問地址進(jìn)行簡(jiǎn)單變換。 在失效的數(shù)據(jù)從內(nèi)存取回之后,往Cache送的同時(shí)直接送回到寄存器也可以降低失效延遲。,39,通過讀優(yōu)先降低失效延遲,讀Cache失效對(duì)指令流水線效率的影響比寫失效大 在處理器中一般都有寫緩存(Write Buffer),寫指令只要把要寫的數(shù)據(jù)寫到寫緩存就可以提交,再由寫緩存寫到Cache或內(nèi)存 取數(shù)

17、在數(shù)據(jù)讀回來回前取數(shù)指令不能提交,與取數(shù)指令存在數(shù)據(jù)相關(guān)的后續(xù)指令要等待取數(shù)操作讀回來的數(shù)據(jù)才能執(zhí)行,可見讀Cache失效容易堵塞指令流水線 在進(jìn)行Cache失效處理時(shí),優(yōu)先處理讀失效以減小堵塞 讀失效時(shí)要注意與Write Buffer的RAW相關(guān),不能等寫緩存為空,要?jiǎng)討B(tài)檢查寫緩存 讀失效可能需要替換dirty塊,不要把替換塊寫回到內(nèi)存再讀,可以把替換塊寫到寫緩存,然后先讀,后把寫緩存的內(nèi)容寫回內(nèi)存,40,通過寫合并降低失效延遲,Write-through的Cache依賴于寫緩存(Write Buffer) 處理器寫到WB就算完成寫操作,由WB寫到下一級(jí)存儲(chǔ)器 注意一致性問題:處理器后續(xù)的讀

18、操作、外設(shè)的DMA操作等 Write-back的Cache也使用WB來臨時(shí)存放替換出去的cache塊 通過把寫緩存中對(duì)同一Cache塊的寫操作進(jìn)行合并來提高寫緩存使用率,減少處理器等待 注意IO操作不能合并,41,通過Victim Cache降低失效延遲,在直接相聯(lián)的Cache中避免沖突失效 增加緩存(Victim Cache)保存從Cache中替換出來的數(shù)據(jù) Jouppi 1990:4項(xiàng)victim cache可消除直接相聯(lián)4KB Cache中20%-95%的沖突訪問 在Alpha, HP等處理器中應(yīng)用,42,通過二級(jí)Cache降低失效延遲,通過L2降低失效延遲 AMAT = Hit Tim

19、eL1 + Miss RateL1 x Miss PenaltyL1 Miss PenaltyL1 = Hit TimeL2 + Miss RateL2 x Miss PenaltyL2 AMAT = Hit TimeL1 + Miss RateL1 x (Hit TimeL2 + Miss RateL2 x Miss PenaltyL2) L2的失效率 局部失效率(Local miss rate) L2失效次數(shù)除以L2訪問次數(shù) 全局失效率(Global miss rate) L2失效次數(shù)除以所有訪存次數(shù)(Miss RateL1 x Miss RateL2) 局部失效率較高(10%-20%),

20、全局失效率很低(1%),43,降低HitTime,簡(jiǎn)化Cache設(shè)計(jì) 并行訪問Cache與TLB 增加Cache訪問流水級(jí),44,簡(jiǎn)化Cache設(shè)計(jì),訪問Cache常常是整個(gè)CPU的時(shí)鐘關(guān)鍵路徑 Cache越小,延遲越小 直接相聯(lián)的Cache延遲小 簡(jiǎn)化一級(jí)Cache設(shè)計(jì)需要統(tǒng)籌考慮 PIV數(shù)據(jù)Cache從PIII的16KB降低為8KB,而且只有定點(diǎn)可以訪問,從而達(dá)到高主頻 但PIV的二級(jí)Cache只有6拍的訪問延遲,45,避免地址轉(zhuǎn)換延遲:虛地址Cache,通過虛地址直接訪問Cache減少虛實(shí)地址轉(zhuǎn)換時(shí)間 區(qū)分進(jìn)程問題:不同進(jìn)程的虛地址空間是一樣的,需要在進(jìn)程切換時(shí)候刷Cache以維護(hù)一致性

21、,增加了冷失效 別名(aliases)問題:操作系統(tǒng)有時(shí)候(如為了進(jìn)程間共享)需要不同的虛地址對(duì)應(yīng)同一物理地址,46,虛地址Cache中多進(jìn)程對(duì)Cache命中率的影響,進(jìn)程切換問題可以通過在TLB中增加進(jìn)程號(hào)的方式來解決 單進(jìn)程、多進(jìn)程切換時(shí)刷Cache、多進(jìn)程用ID號(hào)來區(qū)分虛地址 Y軸表示Cache失效率;X軸表示Cache大?。? KB - 1024 KB),47,虛Index實(shí)Tag技術(shù),在用Index從cache中讀Tag的同時(shí),進(jìn)行虛實(shí)地址轉(zhuǎn)換,可以使用物理地址做tag 如何保證虛實(shí)地址Index位的一致? 增加頁大小、增加相聯(lián)度 軟件保證:頁著色(Page coloring),48

22、,增加Cache訪問流水級(jí),Cache訪問時(shí)間是處理器主頻的決定因素之一 其他因素包括加法及bypass時(shí)間等 把cache訪問分成多拍以提高主頻 MIPS:1拍 Alpha:2拍 增加流水節(jié)拍增加了load-use延遲,49,提高Cache訪問并行性,非阻塞Cache 硬件預(yù)取 軟件預(yù)取,50,非阻塞Caches,非阻塞(Non-blocking/Lockup-free)Cache在訪問失效時(shí)允許后續(xù)的訪問繼續(xù)進(jìn)行 hit under miss、hit under multiple miss、miss under miss 前面的失效訪問不影響后續(xù)訪問,需要支持多個(gè)outstanding訪問

23、,需要類似與保留棧的訪存隊(duì)列機(jī)制 在亂序執(zhí)行的CPU中使用,顯著增加Cache控制器復(fù)雜度 多個(gè)層次的非阻塞訪問 L1、L2、內(nèi)存控制器 龍芯2號(hào)支持24個(gè)L1非阻塞訪問,8個(gè)L2非阻塞訪問,51,SPEC程序的非阻塞訪存效果,8 KB直接相聯(lián)數(shù)據(jù)Cache,塊大小32字節(jié),失效延遲16拍 浮點(diǎn)程序AMAT= 0.68 - 0.52 - 0.34 - 0.26 定點(diǎn)程序AMAT= 0.24 - 0.20 - 0.19 - 0.19,Integer,Floating Point,52,通過硬件預(yù)取降低失效率,指令預(yù)取 Alpha 21064 在Cache失效時(shí)取連續(xù)兩塊,多取的Cache塊存放在

24、流緩存(stream buffer)中,下一次Cache失效時(shí)先檢查指令是否在流緩存中。 數(shù)據(jù)預(yù)取 Jouppi 1990:對(duì)4KB的Cache,1項(xiàng)流緩存可以命中25%的Cache失效訪問, 4項(xiàng)流緩存可以命中43%的Cache失效訪問 Palacharla & Kessler 1994:指令和數(shù)據(jù)Cache各為四路組相聯(lián)的64KB,對(duì)科學(xué)計(jì)算程序,8項(xiàng)流緩存可以命中 50%-70%的Cache失效訪問 預(yù)取對(duì)訪存帶寬提出了更高的要求,53,通過軟件預(yù)取降低失效率,軟件預(yù)取都是數(shù)據(jù)預(yù)取 預(yù)取到寄存器: (HP PA-RISC loads) 預(yù)取到Cache: (MIPS IV, PowerP

25、C, SPARC v. 9) 預(yù)取指令不發(fā)生例外,預(yù)取到Cache的指令可以不等待數(shù)據(jù)返回 預(yù)取指令開銷:占用指令槽 多發(fā)射結(jié)構(gòu)對(duì)預(yù)取指令占用指令槽不怎么敏感 龍芯2號(hào)對(duì)軟件預(yù)取的支持 目標(biāo)寄存器為0號(hào)寄存器的取數(shù)指令不發(fā)生例外,不阻塞流水線,54,Cache優(yōu)化小結(jié),55,常見處理器的存儲(chǔ)層次,56,MIPS R10000存儲(chǔ)層次,L1 Dcache:32KB,2路,2拍延遲 Icache:32KB,2路 L2 片外,2路偽相聯(lián)(way prediction) 512KB-16MB 1個(gè)load/store部件 16項(xiàng)address queue 特點(diǎn):predecode icache,L2偽

26、相聯(lián),57,HP PA-8x00存儲(chǔ)層次,L1: 0.51.5MB 8500之前為片外(直接映射),之后為片內(nèi)(4路組相聯(lián)) L2 一直到8700,無 2個(gè)load/store部件 28項(xiàng)address reorder隊(duì)列 特點(diǎn):巨大的一級(jí)cache,58,UltraSparc III存儲(chǔ)層次,L1 Dcache:64KB,4路,2拍延遲 Icache:32KB,4路 Prefetch:2KB,4路,3拍延遲 Write cache:2KB,4路,1拍延遲 L2 1/4/8MB,直接映射,12拍延遲 片上tag,片外data 1個(gè)load/store部件,片上內(nèi)存控制器 特點(diǎn):Sum-Addressed-Memory,片上L2 tag和內(nèi)存控制器,59,Alp

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論