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