降低Cache失效率的方法[1]

?學(xué)習(xí)目標(biāo)：

??? 理解失效的三種類(lèi)型（3C）；

??? 掌握Cache容量、相聯(lián)度等與3C的關(guān)系；

??? 掌握2:1Cache經(jīng)驗(yàn)規(guī)則；

??? 理解增加Cache塊大小對(duì)失效率的影響；

??? 理解提高相聯(lián)度對(duì)失效率的影響；

??? 掌握Victim Cache的思想；

??? 掌握偽相聯(lián)Cache的思想。

??? 正文：

??? 4.3降低Cache失效率的方法

??? 許多有關(guān) Cache 的研究都致力于降低 Cache 的失效率。本節(jié)就來(lái)討論這個(gè)問(wèn)題。 按照產(chǎn)生失效的原因不同，我們可以把失效分為以下三類(lèi)（簡(jiǎn)稱(chēng)為3C）：

??? (1) 強(qiáng)制性失效 （Compulsory miss）

??? 當(dāng)?shù)谝淮卧L(fǎng)問(wèn)一個(gè)塊時(shí)，該塊不在 Cache 中，需從下一級(jí)存儲(chǔ)器中調(diào)入 Cache ，這就是強(qiáng)制性失效。這種失效也稱(chēng)為冷啟動(dòng)失效或首次訪(fǎng)問(wèn)失效。

??? (2) 容量失效 （Capacity miss）

??? 如果程序執(zhí)行時(shí)所需的塊不能全部調(diào)入 Cache 中，則當(dāng)某些塊被替換后，若又重新被訪(fǎng)問(wèn)，就會(huì)發(fā)生失效。這種失效稱(chēng)為容量失效。

??? (3) 沖突失效 （Conflict miss）

??? 在組相聯(lián)或直接映象 Cache 中，若太多的塊映象到同一組（塊）中，則會(huì)出現(xiàn)該組中某個(gè)塊被別的塊替換（即使別的組或塊有空閑位置），然后又被重新訪(fǎng)問(wèn)的情況。這就是發(fā)生了沖突失效。這種失效也稱(chēng)為碰撞失效或干擾失效。
?

表4.5針對(duì) SPEC92 典型程序給出了上述三種失效所占的比例（這些數(shù)據(jù)是在 DECstation 5000上測(cè)得的。假設(shè) Cache 的塊大小為32字節(jié)，并采用 LRU 算法）。為了說(shuō)明高相聯(lián)度的好處，表中列出了在直接映象、兩路組相聯(lián)、四路組相聯(lián)和八路組相聯(lián)的情況下，沖突失效的值?？梢钥闯觯?

(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 的失效率。

??? 圖4.3.1和圖4.3.2是表4.5中數(shù)據(jù)的圖示，其中圖4.3.1為絕對(duì)失效率，圖4.3.2為各種類(lèi)型失效率所占的百分比。

圖中可以看出， SPEC92 程序的強(qiáng)制失效率很小。其他許多運(yùn)行時(shí)間較長(zhǎng)的程序也是如此。在 3C 中，沖突失效似乎是最容易減少的，只要采用全相聯(lián)，就不會(huì)發(fā)生沖突失效。但是，用硬件實(shí)現(xiàn)全相聯(lián)是很昂貴的，而且可能會(huì)降低處理器的時(shí)鐘頻率（見(jiàn)例4.3），從而導(dǎo)致整體性能的下降。至于容量失效，除了增大 Cache 以外，沒(méi)有別的辦法。在一個(gè)存儲(chǔ)層次中，如果高一級(jí)存儲(chǔ)器的容量比程序所需的空間小得多，就有可能出現(xiàn)抖動(dòng)現(xiàn)象。這時(shí)大部分時(shí)間是花在兩級(jí)存儲(chǔ)器之間移動(dòng)數(shù)據(jù)。出現(xiàn)抖動(dòng)時(shí)，由于大量進(jìn)行替換，機(jī)器的運(yùn)行速度接近于只有第二級(jí)存儲(chǔ)器的情況，甚至更慢。

??? 另一個(gè)減少 3C 的方法是增加塊的大小，以減少?gòu)?qiáng)制性失效。但在下面我們將看到，塊大小增加可能會(huì)增加其它類(lèi)型的失效。下面我們介紹7種降低失效率的方法。需要強(qiáng)調(diào)的是，許多降低失效率的方法會(huì)增加命中時(shí)間或失效開(kāi)銷(xiāo)。因此，在具體使用時(shí)，要綜合考慮，保證降低失效率確能使整個(gè)系統(tǒng)速度提高。

4.3.1增加Cache塊大小

??? 降低失效率最簡(jiǎn)單的方法是增加塊大小。圖4.3.3中對(duì)于一組不同的 Cache 容量，給出了失效率和塊大小的關(guān)系（在與表4.5類(lèi)似的情況下測(cè)得的）。表4.6列出了圖4.3.3的具體數(shù)據(jù)。

(1) 對(duì)于給定的 Cache 容量，當(dāng)塊大小增加（從16字節(jié)開(kāi)始）時(shí)，失效率開(kāi)始是下降，后來(lái)反而上升了。

??? (2) Cache 容量越大，使失效率達(dá)到最低的塊大小就越大。

??? 導(dǎo)致上述失效率先下降后上升的原因，在于增加塊大小會(huì)產(chǎn)生雙重作用。一方面它減少了強(qiáng)制性失效，因?yàn)榫植啃栽碛袃煞矫娴暮x：時(shí)間局部性和空間局部性，增加塊大小利用了空間局部性；另一方面，由于增加塊大小會(huì)減少 Cache 中塊的數(shù)目，所以有可能會(huì)增加沖突失效。在 Cache 容量較小時(shí)，甚至還會(huì)增加容量失效。剛開(kāi)始增加塊大小時(shí)，由于塊大小還不是很大，上述的第一種作用超過(guò)第二種作用，從而使失效率下降。但等到塊大小較大時(shí)，第二種作用超過(guò)第一種作用，使失效率上升。

??? 例4.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è)時(shí)鐘周期，可提供32個(gè)字節(jié)；依此類(lèi)推。請(qǐng)問(wèn)對(duì)于表4.6中列出的各種容量的 Cache ，在塊大小分別為多少時(shí)，平均訪(fǎng)存時(shí)間最小？

??? 解： 動(dòng)畫(huà)演示

??? 平均訪(fǎng)存時(shí)間為

??? 平均訪(fǎng)存時(shí)間 ＝ 命中時(shí)間 ＋ 失效率 × 失效開(kāi)銷(xiāo)

??? 假設(shè)命中時(shí)間與塊大小無(wú)關(guān)，為1個(gè)時(shí)鐘，那么對(duì)于一個(gè)塊大小為16字節(jié)，容量為1KB的 Cache 來(lái)說(shuō)：

??? 平均訪(fǎng)存時(shí)間 ＝ 1＋（15.05 %×42） ＝ 7.321 個(gè)時(shí)鐘周期

??? 而對(duì)于塊大小為256字節(jié)、容量為256KB的 Cache 來(lái)說(shuō)，平均訪(fǎng)存時(shí)間為

??? 平均訪(fǎng)存時(shí)間 ＝ 1＋（0.49 %×76） ＝ 1.353 個(gè)時(shí)鐘周期