計算機組織與結構：LEC09_高速緩存

1、1,高性能計算機系統(tǒng)結構,2,高速緩存（Cache）,存儲層次的基本概念 Cache結構 Cache性能優(yōu)化 常見處理器的存儲層次,3,存儲層次的基本概念,4,CPU與RAM的速度剪刀差,摩爾定律 CPU的頻率和RAM的容量每18個月翻一番 但RAM的速度增加緩慢 通過存儲層次來彌補差距 寄存器、Cache、存儲器、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 當前主流處理器主頻2GHz以上 IBM Power 6主頻6GHz以上 內(nèi)存延遲50ns左右 訪存延遲100拍 多發(fā)射加劇了訪存瓶頸,6,摩爾定律使CPU的內(nèi)容發(fā)生了變化,馮諾依曼結構的核心思想 存儲程序：指令和數(shù)據(jù)都存放在存儲器中 計算機的五個組成部分 運算器、控制器、存儲器、輸入、輸出 運算器和控制器合稱中央處理器（CPU） 為了緩解存儲瓶頸，把部分存儲器做在片內(nèi) 現(xiàn)在的CPU芯片：控制器+運算器+部分存儲器 片內(nèi)Cache占了整個芯片的很大一部分面積,7,外存儲器,輸入設備,輸出

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

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

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

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

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

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

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

10、沒有二級Cache 其他RISC處理器（ Alpha, Power, MIPS, Ultra SPARC） 32/64KB+32/64KB PIV 12Kop Trace cache+8KB數(shù)據(jù)Cache（PIII: 16KB+16KB） 反映出設計人員的不同取舍,29,通過增加相聯(lián)度降低失效率,增加相聯(lián)度 2:1規(guī)則：大小為N的直接相聯(lián)的Cache命中率與大小為N/2的二路組相聯(lián)的 Cache命中率相當 八路組相聯(lián)的效果已經(jīng)與全相聯(lián)的失效率相差很小 增加相聯(lián)度會增加時鐘周期延遲 例如，直接相連時鐘周期為1ns，2路組相聯(lián)為1.36ns，4路組相聯(lián)為1.44ns，8路組相聯(lián)為1.52ns，失效

11、延遲為25時鐘周期 Cache訪問可能是整個處理器的關鍵路徑,30,通過“路猜測”和“偽相聯(lián)”提高命中率,結合直接相聯(lián)訪問時間短和組相聯(lián)命中率高的優(yōu)點 在多路相聯(lián)的結構中，每次Cache訪問只檢查一路，如果不命中再檢查其他路 兩種命中：hit和pseudohit 直接判斷第0路，或進行Way-Prediction：Alpha 21264 ICache路猜測命中率85%，hit時間為1拍，pseudohit時間3拍 不用并行訪問每一路，可以大幅度降低功耗 缺點：流水線控制復雜，在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ù)組合并（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,關鍵字優(yōu)先 讀失效優(yōu)先 Victim Cache 寫合并 多級Cache,38,通過關鍵字優(yōu)先降低失效延遲,

16、在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)存 關鍵字優(yōu)先的實現(xiàn)只需要對訪問地址進行簡單變換。 在失效的數(shù)據(jù)從內(nèi)存取回之后，往Cache送的同時直接送回到寄存器也可以降低失效延遲。,39,通過讀優(yōu)先降低失效延遲,讀Cache失效對指令流水線效率的影響比寫失效大 在處理器中一般都有寫緩存（Write Buffer），寫指令只要把要寫的數(shù)據(jù)寫到寫緩存就可以提交，再由寫緩存寫到Cache或內(nèi)存 取數(shù)

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

18、操作、外設的DMA操作等 Write-back的Cache也使用WB來臨時存放替換出去的cache塊 通過把寫緩存中對同一Cache塊的寫操作進行合并來提高寫緩存使用率，減少處理器等待 注意IO操作不能合并,41,通過Victim Cache降低失效延遲,在直接相聯(lián)的Cache中避免沖突失效 增加緩存（Victim Cache）保存從Cache中替換出來的數(shù)據(jù) Jouppi 1990：4項victim cache可消除直接相聯(lián)4KB Cache中20%-95%的沖突訪問 在Alpha, HP等處理器中應用,42,通過二級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,簡化Cache設計 并行訪問Cache與TLB 增加Cache訪問流水級,44,簡化Cache設計,訪問Cache常常是整個CPU的時鐘關鍵路徑 Cache越小，延遲越小 直接相聯(lián)的Cache延遲小 簡化一級Cache設計需要統(tǒng)籌考慮 PIV數(shù)據(jù)Cache從PIII的16KB降低為8KB，而且只有定點可以訪問，從而達到高主頻 但PIV的二級Cache只有6拍的訪問延遲,45,避免地址轉換延遲：虛地址Cache,通過虛地址直接訪問Cache減少虛實地址轉換時間 區(qū)分進程問題：不同進程的虛地址空間是一樣的，需要在進程切換時候刷Cache以維護一致性

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

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

23、，需要類似與保留棧的訪存隊列機制 在亂序執(zhí)行的CPU中使用，顯著增加Cache控制器復雜度 多個層次的非阻塞訪問 L1、L2、內(nèi)存控制器 龍芯2號支持24個L1非阻塞訪問，8個L2非阻塞訪問,51,SPEC程序的非阻塞訪存效果,8 KB直接相聯(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.19,Integer,Floating Point,52,通過硬件預取降低失效率,指令預取 Alpha 21064 在Cache失效時取連續(xù)兩塊，多取的Cache塊存放在

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

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

26、相聯(lián),57,HP PA-8x00存儲層次,L1: 0.51.5MB 8500之前為片外（直接映射），之后為片內(nèi)（4路組相聯(lián)） L2 一直到8700，無 2個load/store部件 28項address reorder隊列 特點：巨大的一級cache,58,UltraSparc III存儲層次,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個load/store部件，片上內(nèi)存控制器 特點：Sum-Addressed-Memory，片上L2 tag和內(nèi)存控制器,59,Alp