計算機系統(tǒng)結(jié)構(gòu)第5章second

1 1/32/32計算機系統(tǒng)結(jié)構(gòu)講義第5章 存儲層次講解者：劉東波講解者：劉東波 聯(lián)系方式：155748848452 2/32/32計算機系統(tǒng)結(jié)構(gòu)講義Cache性能分析降低Cache不命中率的方法本講小結(jié)本講主要內(nèi)容3 3/32/32計算機系統(tǒng)結(jié)構(gòu)講義重點與難點1. 重點根據(jù)平均訪存時間公式和CPU執(zhí)行時間公式進行Cache性能分析降低Cache不命中率的6種方法2. 難點Cache性能分析偽相聯(lián)Cache工作原理4 4/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.2.7 Cache的性能分析1. 不命中率與硬件速度無關(guān)容易產(chǎn)生一些誤導(dǎo)2. 平均訪存時間 平均訪存時間 命中時間失效率失效開銷5.2.7 Cache的性能分析非常重要！5 5/32/32計算機系統(tǒng)結(jié)構(gòu)講義 程序執(zhí)行時間CPUCPU時間（時間（CPUCPU執(zhí)行周期數(shù)執(zhí)行周期數(shù)+ +存儲器停頓周期數(shù)）存儲器停頓周期數(shù)） 時鐘周期時間時鐘周期時間其中：其中： 存儲器停頓時鐘周期數(shù)存儲器停頓時鐘周期數(shù)“讀讀”的次數(shù)的次數(shù)讀不命中率讀不命中率讀不讀不命中開銷命中開銷“寫寫”的次數(shù)的次數(shù)寫不命中率寫不命中率寫不命中開銷寫不命中開銷存儲器停頓時鐘周期數(shù)訪存次數(shù)存儲器停頓時鐘周期數(shù)訪存次數(shù)不命中率不命中率不命中開銷不命中開銷 CPU時間（CPU執(zhí)行周期數(shù)+訪存次數(shù)不命中率不命中開銷） 時鐘周期時間時鐘周期時間不命中開銷不命中率指令數(shù)訪存次數(shù)時間executionCPIICCPU=IC（CPIexecution每條指令的平均訪存次數(shù)不命中率 不命中開銷） 時鐘周期時間6 6/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.2 Cache基本知識 例例5.15.1 用一個和用一個和Alpha AXPAlpha AXP類似的機器作為第一個例子。假類似的機器作為第一個例子。假設(shè)設(shè)CacheCache不命中開銷為不命中開銷為5050個時鐘周期，當(dāng)不考慮存儲器停頓時，個時鐘周期，當(dāng)不考慮存儲器停頓時，所有指令的執(zhí)行時間都是所有指令的執(zhí)行時間都是2.02.0個時鐘周期，訪問個時鐘周期，訪問CacheCache不命中率為不命中率為2%2%，平均每條指令訪存，平均每條指令訪存1.331.33次。試分析次。試分析CacheCache對性能的影響。對性能的影響。 解解 CPU時間時間有有cacheIC （CPIexecution每條指令的平均訪存次數(shù)每條指令的平均訪存次數(shù) 不命中率不命中率不命中開銷）不命中開銷） 時鐘周期時間時鐘周期時間 IC （2.01.332 %50） 時鐘周期時間時鐘周期時間 IC 3.33 時鐘周期時間時鐘周期時間7 7/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.2 Cache基本知識考慮考慮CacheCache的不命中后，性能為：的不命中后，性能為： CPUCPU時間時間有有cachecacheICIC（2.02.01.331.332 %2 %5050）時鐘周期時間時鐘周期時間 ICIC3.333.33時鐘周期時間時鐘周期時間實際實際CPI CPI ：3.333.333.33/2.0 = 1.67(3.33/2.0 = 1.67(倍倍) ) CPUCPU時間也增加為原來的時間也增加為原來的1.671.67倍。倍。 但若不采用但若不采用Cache,Cache,則：則：CPICPI2.02.050501.331.3368.568.58 8/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.2 Cache基本知識 Cache不命中對于一個CPI較小而時鐘頻率較高的CPU來說，影響是雙重的：CPIexecution越低，固定周期數(shù)的Cache不命中開銷的相對影響就越大。在計算CPI時，不命中開銷的單位是時鐘周期數(shù)。因此，即使兩臺計算機的存儲層次完全相同，時鐘頻率較高的CPU的不命中開銷較大，其CPI中存儲器停頓這部分也就較大。 因此Cache對于低CPI、高時鐘頻率的CPU來說更加重要。 9 9/32/32計算機系統(tǒng)結(jié)構(gòu)講義 例例5.25.2 考慮兩種不同組織結(jié)構(gòu)的考慮兩種不同組織結(jié)構(gòu)的CacheCache：直接映像：直接映像CacheCache和兩路組相聯(lián)和兩路組相聯(lián)CacheCache，試問它們對，試問它們對CPUCPU的性能有何影的性能有何影響？先求平均訪存時間，然后再計算響？先求平均訪存時間，然后再計算CPUCPU性能。分析時請性能。分析時請用以下假設(shè)：用以下假設(shè)： 1010/32/32計算機系統(tǒng)結(jié)構(gòu)講義 (1)(1)理想理想CacheCache（命中率為（命中率為100%100%）情況下的）情況下的CPICPI為為2.02.0，時鐘周，時鐘周期為期為2ns2ns，平均每條指令訪存，平均每條指令訪存1.31.3次。次。 (2)(2)兩種兩種CacheCache容量均為容量均為64KB64KB，塊大小都是，塊大小都是3232字節(jié)。字節(jié)。 (3)(3)在組相聯(lián)在組相聯(lián)CacheCache中，中，由于多路選擇器的存在而使由于多路選擇器的存在而使CPU的時的時鐘周期增加到原來的鐘周期增加到原來的1.10倍。這是因為對倍。這是因為對Cache的訪問總是處于的訪問總是處于關(guān)鍵路徑上，對關(guān)鍵路徑上，對CPU的時鐘周期有直接的影響。的時鐘周期有直接的影響。 (4) (4) 這兩種結(jié)構(gòu)這兩種結(jié)構(gòu)CacheCache的不命中開銷都是的不命中開銷都是70ns70ns。（在實際應(yīng)。（在實際應(yīng)用中，應(yīng)取整為整數(shù)個時鐘周期）用中，應(yīng)取整為整數(shù)個時鐘周期） (5) (5) 命中時間為命中時間為1 1個時鐘周期，個時鐘周期，64KB64KB直接映像直接映像CacheCache的不命的不命中率為中率為1.4%1.4%，相同容量的兩路組相聯(lián)，相同容量的兩路組相聯(lián)CacheCache的不命中率為的不命中率為1.0%1.0%。1111/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.2 Cache基本知識 解解 平均訪存時間為：平均訪存時間為： 平均訪存時間命中時間不命中率平均訪存時間命中時間不命中率不命中開銷不命中開銷 因此，兩種結(jié)構(gòu)的平均訪存時間分別是：因此，兩種結(jié)構(gòu)的平均訪存時間分別是： 平均訪存時間平均訪存時間1 1路路2.02.0（0.0140.0147070）2.98ns2.98ns 平均訪存時間平均訪存時間2 2路路2.02.01.101.10（0.0100.0107070）2.90ns2.90ns 兩路組相聯(lián)兩路組相聯(lián)CacheCache的平均訪存時間比較低。的平均訪存時間比較低。 CPU時間時間IC（CPIexecution每條指令的平均訪存次數(shù)每條指令的平均訪存次數(shù) 不命中率不命中率不命中開銷）不命中開銷） 時鐘周期時間時鐘周期時間 IC（CPIexecution 時鐘周期時間每條指令的時鐘周期時間每條指令的 平均訪存次數(shù)平均訪存次數(shù)不命中率不命中率不命中開銷不命中開銷時鐘周期時間）時鐘周期時間）1212/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.2 Cache基本知識因此：因此：CPUCPU時間時間1 1路路 ICIC(2.0(2.02 2(1.3(1.30.0140.01470)70) 5.275.27ICICCPUCPU時間時間2 2路路 ICIC(2.0(2.02 21.101.10(1.3(1.30.0100.01070)70) 5.315.31ICIC直接映像直接映像CacheCache的平均性能好一些。的平均性能好一些。1313/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.2 Cache基本知識1. 平均訪存時間命中時間不命中率不命中開銷2. 可以從三個方面改進Cache的性能：降低不命中率減少不命中開銷減少Cache命中時間3. 17種Cache優(yōu)化技術(shù)q8 8種種用于降低不命中率用于降低不命中率q5 5種種用于減少不命中開銷用于減少不命中開銷q4 4種種用于減少命中時間用于減少命中時間 5.2.8 改進Cache的性能1414/32/32計算機系統(tǒng)結(jié)構(gòu)講義1. 三種類型的不命中(3C)強制性不命中(Compulsory miss)q當(dāng)?shù)谝淮卧L問一個塊時，該塊不在當(dāng)?shù)谝淮卧L問一個塊時，該塊不在CacheCache中，需從下中，需從下一級存儲器中調(diào)入一級存儲器中調(diào)入CacheCache，這就是強制性不命中。，這就是強制性不命中。 ( (冷啟動冷啟動不命中，首次訪問不命中）不命中，首次訪問不命中）容量不命中(Capacity miss ) q如果程序執(zhí)行時所需的塊不能全部調(diào)入如果程序執(zhí)行時所需的塊不能全部調(diào)入CacheCache中，則中，則當(dāng)某些塊被替換后，若又重新被訪問，就會發(fā)生不命當(dāng)某些塊被替換后，若又重新被訪問，就會發(fā)生不命中。這種不命中稱為容量不命中。中。這種不命中稱為容量不命中。5.3 降低Cache不命中率5.3.1 三種類型的不命中1515/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率沖突不命中(Conflict miss)q在組相聯(lián)或直接映像在組相聯(lián)或直接映像CacheCache中，若太多的塊映像到中，若太多的塊映像到同一組同一組( (塊塊) )中，則會出現(xiàn)該組中某個塊被別的塊替中，則會出現(xiàn)該組中某個塊被別的塊替換換( (即使別的組或塊有空閑位置即使別的組或塊有空閑位置) )，然后又被重新訪，然后又被重新訪問的情況。這就是發(fā)生了沖突不命中。問的情況。這就是發(fā)生了沖突不命中。 ( (碰撞不命中，干擾不命中碰撞不命中，干擾不命中) ) 三種不命中所占的比例 圖示I(絕對值)2.圖示(相對值)1616/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率1717/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率1818/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率可以看出：q相聯(lián)度越高，沖突不命中就越少；相聯(lián)度越高，沖突不命中就越少；q強制性不命中和容量不命中不受相聯(lián)度的影響；強制性不命中和容量不命中不受相聯(lián)度的影響；q強制性不命中不受強制性不命中不受CacheCache容量的影響，但容量不命中容量的影響，但容量不命中卻隨著容量的增加而減少。卻隨著容量的增加而減少。1919/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率減少三種不命中的方法q強制性不命中：強制性不命中：增加塊大小，預(yù)取增加塊大小，預(yù)取 （本身很少）（本身很少）q容量不命中：容量不命中：增加容量增加容量 （抖動現(xiàn)象）（抖動現(xiàn)象）q沖突不命中：沖突不命中：提高相聯(lián)度提高相聯(lián)度（理想情況：全相聯(lián)）（理想情況：全相聯(lián)）許多降低不命中率的方法會增加命中時間或不命中開銷2020/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率1. 不命中率與塊大小的關(guān)系對于給定的Cache容量，當(dāng)塊大小增加時，不命中率開始是下降，后來反而上升了。 原因：q一方面它減少了強制性不命中；一方面它減少了強制性不命中；q另一方面，由于增加塊大小會減少另一方面，由于增加塊大小會減少CacheCache中塊的數(shù)目，中塊的數(shù)目，所以有可能會增加沖突不命中。所以有可能會增加沖突不命中。 Cache容量越大，使不命中率達到最低的塊大小就越大。2. 增加塊大小會增加不命中開銷5.3.2 增加Cache塊大小2121/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率 1616 3232 6464 128128 256256 塊大?。ㄗ止?jié)）塊大?。ㄗ止?jié)） 10%10% 5%5% 0%0% 不命中率不命中率 256K256K 64K64K 16K16K 4K4K 不命中率隨塊大小變化的曲線不命中率隨塊大小變化的曲線 2222/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率各種塊大小情況下Cache的不命中率 塊大?。ㄗ止?jié)） Cache容量（字節(jié)） 1K 4K 16K 64K 256K 16 15.05% 8.57% 3.94% 2.04% 1.09% 32 13.34% 7.24% 2.87% 1.35% 0.70% 64 13.76% 7.00% 2.64% 1.06% 0.51% 128 16.64% 7.78% 2.77% 1.02% 0.49% 256 22.01% 9.51% 3.29% 1.15% 0.49% 2323/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率1. 最直接的方法是增加Cache的容量缺點:q增加成本增加成本q可能增加命中時間可能增加命中時間2. 這種方法在片外Cache中用得比較多 5.3.3 增加Cache的容量2424/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率1. 采用相聯(lián)度超過8的方案的實際意義不大。2. 2:1 Cache經(jīng)驗規(guī)則 容量為N的直接映像Cache的不命中率和容量為N/2的兩路組相聯(lián)Cache的不命中率差不多相同。 提高相聯(lián)度是以增加命中時間為代價。 5.3.4 提高相聯(lián)度2525/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率1. 多路組相聯(lián)的低不命中率和直接映像的命中速度2. 偽相聯(lián)Cache的優(yōu)點命中時間小不命中率低5.3.5 偽相聯(lián) Cache (列相聯(lián) Cache )優(yōu)點優(yōu)點缺點缺點直接映像直接映像組相聯(lián)組相聯(lián)命中時間小命中時間大不命中率高不命中率低2626/32/32計算機系統(tǒng)結(jié)構(gòu)講義 基本思想及工作原理 （動畫演示） 在邏輯上把直接映像在邏輯上把直接映像CacheCache的空間上下平分為兩個區(qū)。對于任何的空間上下平分為兩個區(qū)。對于任何一次訪問，偽相聯(lián)一次訪問，偽相聯(lián)CacheCache先按直接映像先按直接映像CacheCache的方式去處理。若命中，的方式去處理。若命中，則其訪問過程與直接映像則其訪問過程與直接映像CacheCache的情況一樣。若不命中，則再到另一的情況一樣。若不命中，則再到另一區(qū)相應(yīng)的位置去查找。若找到，則發(fā)生了偽命中，否則就只好訪問下區(qū)相應(yīng)的位置去查找。若找到，則發(fā)生了偽命中，否則就只好訪問下一級存儲器。一級存儲器。 索引索引 至至 CPUCPU 取出數(shù)據(jù)送往取出數(shù)據(jù)送往 CPUCPU 偽相聯(lián)組偽相聯(lián)組 2727/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率 缺點： 多種命中時間 快速命中與慢速命中 要保證絕大多數(shù)命中都是快速命中。不命中開銷不命中開銷2828/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率1. 指令和數(shù)據(jù)都可以預(yù)取2. 預(yù)取內(nèi)容既可放入Cache，也可放在外緩沖器中。例如：指令流緩沖器例如：指令流緩沖器3. 指令預(yù)取通常由Cache之外的硬件完成4. 預(yù)取效果Joppi的研究結(jié)果q指令預(yù)取指令預(yù)取 (4KB(4KB，直接映像，直接映像CacheCache，塊大小，塊大小1616字節(jié)字節(jié))n1 1個塊的指令流緩沖器：個塊的指令流緩沖器： 捕獲捕獲15152525的不命中的不命中n4 4個塊的指令流緩沖器：個塊的指令流緩沖器： 捕獲捕獲5050n1616個塊的指令流緩沖器：捕獲個塊的指令流緩沖器：捕獲72725.3.6 硬件預(yù)取 2929/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率q數(shù)據(jù)預(yù)取數(shù)據(jù)預(yù)取 (4KB,(4KB,直接映像直接映像Cache)Cache)n1 1個數(shù)據(jù)流緩沖器：捕獲個數(shù)據(jù)流緩沖器：捕獲2525的不命中的不命中n還可以采用多個數(shù)據(jù)流緩沖器還可以采用多個數(shù)據(jù)流緩沖器Palacharla和Kessler的研究結(jié)果q流緩沖器：既能預(yù)取指令又能預(yù)取數(shù)據(jù)流緩沖器：既能預(yù)取指令又能預(yù)取數(shù)據(jù)q對于兩個對于兩個64KB64KB四路組相聯(lián)四路組相聯(lián)CacheCache來說：來說：n8 8個流緩沖器能捕獲個流緩沖器能捕獲50507070的不命中的不命中預(yù)取應(yīng)利用存儲器的空閑帶寬，不能影響對正常不命中的處理，否則可能會降低性能。 3030/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率1. 一種能減少沖突不命中次數(shù)而又不影響時鐘頻率的方法。2. 基本思想在Cache和它從下一級存儲器調(diào)數(shù)據(jù)的通路之間設(shè)置一個全相聯(lián)的小Cache，稱為“犧牲”Cache（Victim Cache）。用于存放被替換出去的塊(稱為犧牲者)，以備重用。工作過程5.3.9 “犧牲” Cache 3131/32/32計算機系統(tǒng)結(jié)構(gòu)講義5.3 降低Cache不命中率 作用對于減小沖突不命中很有效，特別是對于小容量的直接映像數(shù)據(jù)Cache，作用尤其明顯。例如項數(shù)為項數(shù)為4 4的的Victim Cache:Victim Cache: 能使能使4KB4KB CacheCache的沖突不命中減少的沖突不命中減少20%20%90%90%3232/32/32計算機系統(tǒng)結(jié)構(gòu)講義本章小結(jié)1. 掌握Cache性能分析的方法，熟練運用公式計算CPU執(zhí)行時間和平均訪存時間2. 掌握Cache不命中的三種類型的產(chǎn)生原因及其相互關(guān)聯(lián)3. 掌握常見6種降低Cache不命中率的方法