53降低CACHE失效率的方法

1、(1) 強(qiáng)制性失效(Compulsory miss) 當(dāng)?shù)谝淮卧L問(wèn)一個(gè)塊時(shí)，該塊不在 Cache中，需從下一級(jí)存儲(chǔ)器中調(diào)入Cache， 這就是強(qiáng)制性失效。 (冷啟動(dòng)失效，首次訪問(wèn)失效。)(2) 容量失效(Capacity miss ) 如果程序執(zhí)行時(shí)所需的塊不能全部調(diào) 入Cache中，則當(dāng)某些塊被替換后，若又5.3 降低Cache失效率的方法1. 三種失效(3C)第五章 存儲(chǔ)層次 重新被訪問(wèn)，就會(huì)發(fā)生失效。這種失效稱 為容量失效。(3) 沖突失效(Conflict miss) 在組相聯(lián)或直接映象Cache中，若太多 的塊映象到同一組(塊)中，則會(huì)出現(xiàn)該組 中某個(gè)塊被別的塊替換(即使別的組或塊有

2、 空閑位置)，然后又被重新訪問(wèn)的情況。這 就是發(fā)生了沖突失效。 (碰撞失效，干擾失效)5.3 降低Cache 失效率的方法2. 三種失效所占的比例(SPEC92)表5.5 5.3 降低Cache 失效率的方法圖示I(絕對(duì)值)圖示(相對(duì)值)可以看出：(1) 相聯(lián)度越高，沖突失效就越少；(2) 強(qiáng)制性失效和容量失效不受相聯(lián)度的影響；(3) 強(qiáng)制性失效不受Cache容量的影響，但容 量失效卻隨著容量的增加而減少；(4) 表中的數(shù)據(jù)符合2:1的Cache經(jīng)驗(yàn)規(guī)則，即 大小為N 的直接映象Cache的失效率約等于 大小為N/2 的兩路組相聯(lián)Cache的失效率。強(qiáng)制性失效：增加塊大小，預(yù)取 (本身很少)容

3、量失效：增加容量 (抖動(dòng)現(xiàn)象)沖突失效：提高相聯(lián)度 (理想情況：全相聯(lián))3. 減少三種失效的方法4. 許多降低失效率的方法會(huì)增加命中時(shí)間或 失效開(kāi)銷(xiāo)5.3 降低Cache 失效率的方法5.3.1 增加Cache塊大小1. 失效率與塊大小的關(guān)系 (1) 對(duì)于給定的Cache容量，當(dāng)塊大小增加 失效率開(kāi)始是下降，后來(lái)反而上升了； (2) Cache容量越大，使失效率到達(dá)最低的 塊大小就越大。5.3 降低Cache 失效率的方法2. 增加塊大小會(huì)增加失效開(kāi)銷(xiāo)3. 例題例 5.4 假定存儲(chǔ)系統(tǒng)在延遲40個(gè)時(shí)鐘周期后，每2個(gè)時(shí)鐘周期能送出16個(gè)字節(jié)。即:經(jīng)過(guò)42個(gè)時(shí)鐘周期，它可提供16個(gè)字節(jié)；經(jīng)過(guò)44個(gè)

4、時(shí)鐘周期，可提供32個(gè)字節(jié)；依此類推。試問(wèn)對(duì)于表5-6中列出的各種容量的Cache，在塊大小分別為多少時(shí)，平均訪存時(shí)間最??？解： 解題過(guò)程 1KB、4KB、16KB Cache: 塊大小32字節(jié) 64KB、256KB Cache: 塊大小64字節(jié)5.3 降低Cache 失效率的方法塊大?。ㄗ止?jié)）失效開(kāi)銷(xiāo)（時(shí)鐘周期）Cache容量（字節(jié)）1K4K16K64K256K16427.3214.5992.6551.8571.45832446.8704.1862.2631.5941.30864487.6054.3602.2671.5091.2451285610.3185.3572.5511.5711.27

5、42567216.8477.8473.3691.8281.3535.3.2 提高相聯(lián)度1. 采用相聯(lián)度超過(guò)8的方法實(shí)際意義不大2. 2:1 Cache經(jīng)驗(yàn)規(guī)則 容量為N 的直接映象Cache 容量為N/2的兩路組相聯(lián)Cache3. 提高相聯(lián)度是以增加命中時(shí)間為代價(jià) 例如： TTL或ECL板級(jí)Cache，兩路組相聯(lián)： 增加10 定制的CMOS Cache, 兩路組相聯(lián)： 增加25.3 降低Cache 失效率的方法4. 例題 假定提高相聯(lián)度會(huì)按以下比例增大處理器時(shí)鐘周期： 時(shí)鐘周期2路 1.10時(shí)鐘周期1路 時(shí)鐘周期4路 1.12時(shí)鐘周期1路 時(shí)鐘周期8路 1.14時(shí)鐘周期1路 假定命中時(shí)間為1個(gè)

6、時(shí)鐘，直接映象情況下失效開(kāi)銷(xiāo)為50個(gè)時(shí)鐘周期，而且假設(shè)不必將失效開(kāi)銷(xiāo)取整。使用表55中的失效率，試問(wèn)當(dāng)Cache為多大時(shí)，以下不等式成立？例 5.55.3 降低Cache 失效率的方法平均訪存時(shí)間8路 平均訪存時(shí)間4路平均訪存時(shí)間4路 平均訪存時(shí)間2路平均訪存時(shí)間2路 平均訪存時(shí)間1路解： 在各種相聯(lián)度的情況下，平均訪存時(shí)間分別為： 平均訪存時(shí)間8路 = 命中時(shí)間8路 + 失效率8路 失效開(kāi)銷(xiāo)8路 = 1.14失效率8路50 平均訪存時(shí)間4路 = 1.12 失效率4路50 平均訪存時(shí)間2路 = 1.10 失效率2路50 平均訪存時(shí)間1路 = 1.00 失效率1路505.3 降低Cache 失效

7、率的方法 在每種情況下的失效開(kāi)銷(xiāo)相同，都是50個(gè)時(shí)鐘周期。把相應(yīng)的失效率代入上式， 即可得平均訪存時(shí)間。 例如，1KB的直接映象Cache的平均訪存時(shí)間為：平均訪存時(shí)間1路 1.00(0.13350) 7.65 容量為128KB的8路組相聯(lián)Cache的平均訪存時(shí)間為：平均訪存時(shí)間8路 1.14(0.00650) 1.44表5-85.3 降低Cache 失效率的方法Cache容量（K字節(jié)）相聯(lián)度（路）124817.656.606.225.4425.904.904.624.0944.603.953.573.1983.303.002.872.59162.452.202.122.04322.001.8

8、01.771.79641.701.601.571.591281.501.451.421.441. 根本思想 在Cache和它從下一級(jí)存儲(chǔ)器調(diào)數(shù)據(jù) 的通路之間設(shè)置一個(gè)全相聯(lián)的小Cache， 用于存放被替換出去的塊(稱為Victim)， 以備重用。 工作過(guò)程5.3.3 Victim Cache5.3 降低Cache 失效率的方法 對(duì)于減小沖突失效很有效，特別是對(duì)于小容量的直接映象數(shù)據(jù)Cache，作用尤其明顯。 例如，項(xiàng)數(shù)為4的Victim Cache: 使4KB Cache的沖突失效減少20%90%2. 作用5.3 降低Cache 失效率的方法1. 直接映象 vs組相聯(lián)5.3.4 偽相聯(lián)Cache

9、2. 偽相聯(lián)Cache優(yōu)點(diǎn)缺點(diǎn)直接映象組相聯(lián)命中時(shí)間小命中時(shí)間大失效率高失效率低取直接映象及組相聯(lián)兩者的優(yōu)點(diǎn)： 命中時(shí)間小，失效率低5.3 降低Cache 失效率的方法(1) 根本思想及工作原理 (動(dòng)畫(huà)演示) 在邏輯上把直接映象Cache的空間上下 平分為兩個(gè)區(qū)。對(duì)于任何一次訪問(wèn)，偽相聯(lián) Cache先按直接映象Cache的方式去處理。若 命中，則其訪問(wèn)過(guò)程與直接映象Cache的情 況一樣。若不命中，則再到另一區(qū)相應(yīng)的位 置去查找。若找到，則發(fā)生了偽命中，否則 就只好訪問(wèn)下一級(jí)存儲(chǔ)器。(2) 快速命中與慢速命中 要保證絕大多數(shù)命中都是快速命中。5.3 降低Cache 失效率的方法3. 例題例5.

10、6 假設(shè)當(dāng)在按直接映象找到的位置處沒(méi)有發(fā)現(xiàn)匹配、而在另一個(gè)位置才找到數(shù)據(jù)(偽命中)需要2個(gè)額外的周期。仍用上個(gè)例子中的數(shù)據(jù)，問(wèn)：當(dāng)Cache容量分別為2KB和128KB時(shí)，直接映象、兩路組相聯(lián)和偽相聯(lián)這三種組織結(jié)構(gòu)中，哪一種速度最快？5.3 降低Cache 失效率的方法首先考慮標(biāo)準(zhǔn)的平均訪存時(shí)間公式： 平均訪存時(shí)間偽相聯(lián) 命中時(shí)間偽相聯(lián)失效率偽相聯(lián)失效開(kāi)銷(xiāo)偽相聯(lián)由于： 失效率偽相聯(lián)失效率2路 命中時(shí)間偽相聯(lián)命中時(shí)間1路偽命中率偽相聯(lián)2； 偽命中率偽相聯(lián)命中率2路命中率1路 (1失效率2路)(1失效率1路) 失效率1路失效率2路解：5.3 降低Cache 失效率的方法故： 平均訪存時(shí)間偽相聯(lián) 命

11、中時(shí)間1路(失效率1路失效率2路)2 失效率2路失效開(kāi)銷(xiāo)1路將表55中的數(shù)據(jù)代入上面的公式，得： 平均訪存時(shí)間偽相聯(lián)，2KB 1(0.0980.076)2(0.07650) 4.844 平均訪存時(shí)間偽相聯(lián)，128KB 1(0.0100.007)2(0.00750) 1.3565.3 降低Cache 失效率的方法根據(jù)上一個(gè)例子中的表58，對(duì)于2KB Cache，可得： 平均訪存時(shí)間1路 5.90 個(gè)時(shí)鐘 平均訪存時(shí)間2路 4.90 個(gè)時(shí)鐘對(duì)于128KB的Cache有，可得： 平均訪存時(shí)間1路 1.50 個(gè)時(shí)鐘 平均訪存時(shí)間2路 1.45 個(gè)時(shí)鐘可見(jiàn)，對(duì)于這兩種Cache容量，偽相聯(lián)Cache都是

12、速度最快的。缺點(diǎn)：多種命中時(shí)間5.3 降低Cache 失效率的方法5.3.5 硬件預(yù)取技術(shù)1. 指令和數(shù)據(jù)都可以預(yù)取2. 預(yù)取內(nèi)容既可放入Cache，也可放在 外緩沖器中 例如：指令流緩沖器3. 預(yù)取效果 (1) Joppi的研究結(jié)果 指令預(yù)?。?4KB，直接映象Cache, 塊大小16字節(jié))5.3 降低Cache 失效率的方法1個(gè)塊的指令流緩沖器： 捕獲1525 的失效4個(gè)塊的指令流緩沖器： 捕獲5016個(gè)塊的指令流緩沖器：捕獲72 數(shù)據(jù)預(yù)取：(4KB,直接映象Cache) 1個(gè)數(shù)據(jù)流緩沖器：捕獲25的失效 還可以采用多個(gè)數(shù)據(jù)流緩沖器(2) Palacharla和Kessler的研究結(jié)果 流

13、緩沖器：既能預(yù)取指令又能預(yù)取數(shù)據(jù) 對(duì)于兩個(gè)64KB四路組相聯(lián)Cache來(lái)說(shuō)： 8個(gè)流緩沖器能捕獲5070的失效。5.3 降低Cache 失效率的方法4. 例題例5.7 Alpha AXP 21064采用指令預(yù)取技術(shù)，其實(shí)際失效率是多少？若不采用指令預(yù)取技術(shù)，AlphaAPX 21064的指令Cache必須為多大才能保持平均訪存時(shí)間不變？解： 假設(shè)從預(yù)取緩沖器中找到所需指令需多花1個(gè)時(shí)鐘周期。 平均訪存時(shí)間預(yù)取 命中時(shí)間失效率預(yù)取命中率1 失效率(1預(yù)取命中率)失效開(kāi)銷(xiāo)5.3 降低Cache 失效率的方法假設(shè)： 預(yù)取命中率25 命中時(shí)間1個(gè)時(shí)鐘周期 失效開(kāi)銷(xiāo)50個(gè)時(shí)鐘周期 由表5.4可知，8KB

14、指令Cache的失效率1.10 故平均訪存時(shí)間預(yù)取 1(1.10 %25 %1) (1.10 %(125 %)50) 10.002750.4125 1.415 由公式： 平均訪問(wèn)時(shí)間命中時(shí)間失效率失效開(kāi)銷(xiāo)5.3 降低Cache 失效率的方法可得相應(yīng)的失效率為：失效率(平均訪問(wèn)時(shí)間命中時(shí)間)/失效開(kāi)銷(xiāo) (1.4511)/500.838KB Cache 帶預(yù)取的8kB Cache失效率1.100.8316KB Cache0.645.3 降低Cache 失效率的方法5.3.6 由編譯器控制的預(yù)取1. 預(yù)取的類型 存放器預(yù)取：把數(shù)據(jù)取到存放器中 Cache預(yù)?。?只將數(shù)據(jù)取到Cache中 故障性預(yù)?。?/p>

15、預(yù)取時(shí)，若出現(xiàn)虛地址故障 或違反訪問(wèn)權(quán)限，就會(huì)發(fā)生異常。 非故障性預(yù)?。侯A(yù)取時(shí)，若出現(xiàn)虛地址故 障或違反訪問(wèn)權(quán)限，并不會(huì)導(dǎo)致異常，只 是轉(zhuǎn)變?yōu)椤安活A(yù)取。由編譯器參加預(yù)取指令，在數(shù)據(jù)被用到之前發(fā)出預(yù)取請(qǐng)求。5.3 降低Cache 失效率的方法4. 例題2. 在預(yù)取數(shù)據(jù)的同時(shí)，處理器應(yīng)能繼續(xù)執(zhí)行 只有這樣，預(yù)取才有意義。 非阻塞Cache (非鎖定Cache)3. 循環(huán)是預(yù)取優(yōu)化的主要對(duì)象 失效開(kāi)銷(xiāo)小時(shí)：循環(huán)體展開(kāi)12次 失效開(kāi)銷(xiāo)大時(shí)：循環(huán)體展開(kāi)許屢次5.3 降低Cache 失效率的方法例 5.8 對(duì)于下面的程序，判斷哪些訪問(wèn)可能會(huì)導(dǎo)致數(shù)據(jù)Cache失效。然后，參加預(yù)取指令以減少失效。最后，計(jì)算所

16、執(zhí)行的預(yù)取指令的條數(shù)以及通過(guò)預(yù)取防止的失效次數(shù)。假定： (1) 我們用的是一個(gè)容量為8KB、塊大小為 16B的直接映象Cache，它采用寫(xiě)回法并 且按寫(xiě)分配。 (2) a、b分別為3100(3行100列)和1013 的雙精度浮點(diǎn)數(shù)組，每個(gè)元素都是8個(gè) 字節(jié)。當(dāng)程序開(kāi)始執(zhí)行時(shí)，這些數(shù)據(jù)都 不在Cache內(nèi)。5.3 降低Cache 失效率的方法for (i0 ; i 3 ; ii1 ) for (j0 ; j 100 ; jj1 ) aijbj0bj10;解：(1) 計(jì)算過(guò)程(2) 失效情況 總的失效次數(shù)251次 (3) 改進(jìn)后的程序5.3 降低Cache 失效率的方法for (j0，j100；j

17、j1) prefetch (bj70); /* 預(yù)取7次循環(huán)后所需的b(j ,0 ) */ prefetch (a0j7); /* 預(yù)取7次循環(huán)后所需的a(0,j ) */ a0jbj 0 * b j10 for (i1; i 3; ii1) for (j0; j 100; jj1) prefetch(aij7); /* 預(yù)取7次循環(huán)后所需的a(i , j ) */ aijbj0 * bj10; 5.3 降低Cache 失效率的方法例 59 在以下條件下，計(jì)算例5.8中所節(jié)約的時(shí)間： (1) 忽略指令Cache失效，并假設(shè)數(shù)據(jù)Cache 無(wú)沖突失效和容量失效。 (2) 假設(shè)預(yù)取可以被重疊或與C

18、ache失效重 疊執(zhí)行，從而能以最大的存儲(chǔ)帶寬傳送 數(shù)據(jù)。 (3) 不考慮Cache失效時(shí)，修改前的循環(huán)每7 個(gè)時(shí)鐘周期循環(huán)一次。修改后的程序中，失效情況 總的失效次數(shù)19次5.3 降低Cache 失效率的方法解： 修改前： 循環(huán)時(shí)間3007 2100 失效開(kāi)銷(xiāo)2515012550/14650 21001255014650 第一個(gè)預(yù)取循環(huán)每9個(gè)時(shí)鐘周期循環(huán)一次， 而第二個(gè)預(yù)取循環(huán)每8個(gè)時(shí)鐘周期循環(huán)一 次(包括外層for循環(huán)的開(kāi)銷(xiāo))。(4) 一次失效需50個(gè)時(shí)鐘周期。5.3 降低Cache 失效率的方法 修改后： 循環(huán)時(shí)間100920082500 失效時(shí)間1950950 25009503450

19、加速比14650/34504.25.3 降低Cache 失效率的方法5.3.7 編譯器優(yōu)化2KB Cache: 降低508KB Cache：降低75%1. 根本思想 在編譯時(shí)，對(duì)程序中的指令和數(shù)據(jù)進(jìn)行重新組織，以降低Cache失效率。2. McFaring 發(fā)現(xiàn)：通過(guò)對(duì)指令進(jìn)行重新排序， 可有效地降低指令Cache的失效率。5.3 降低Cache 失效率的方法3. 數(shù)據(jù)對(duì)存儲(chǔ)位置的限制比指令的少，因此 更便于優(yōu)化。 通過(guò)把數(shù)據(jù)重新組織，使得在一塊數(shù) 據(jù)被從Cache替換出去之前，能最大限度 利用其中的數(shù)據(jù)(訪問(wèn)次數(shù)最多) (1) 數(shù)組合并 舉例： /* 修改前 */ int val SIZE; int key SIZE;5.3 降低Cache 失效率的方法(2) 內(nèi)外循環(huán)交換 舉例： /* 修改前 */ for (j0 ;j100 ;jj1) for (i0 ;i5000 ;ii1) xij2*xij; /* 修改后 */ struct merge int val ; int key ; ; struct merge merged_arraysize;5