計(jì)算機(jī)組織與結(jié)構(gòu)：LEC09_高速緩存

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