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

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

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

??? 理解失效的三種類型（3C）；

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

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

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

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

??? 掌握Victim Cache的思想；

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

??? 正文：

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

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

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

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

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

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

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

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

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

(1) 相聯(lián)度越高，沖突失效就越少；

??? (2) 強制性失效和容量失效不受相聯(lián)度的影響；

??? (3) 強制性失效不受 Cache 容量的影響，但容量失效卻隨著容量的增加而減少；

??? (4) 表中的數(shù)據(jù)符合2:1的 Cache 經(jīng)驗規(guī)則，即大小為N的直接映象 Cache 的失效率約等于大小為N/2的兩路組相聯(lián) Cache 的失效率。

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

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

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

4.3.1增加Cache塊大小

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

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

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

??? 導(dǎo)致上述失效率先下降后上升的原因，在于增加塊大小會產(chǎn)生雙重作用。一方面它減少了強制性失效，因為局部性原理有兩方面的含義：時間局部性和空間局部性，增加塊大小利用了空間局部性；另一方面，由于增加塊大小會減少 Cache 中塊的數(shù)目，所以有可能會增加沖突失效。在 Cache 容量較小時，甚至還會增加容量失效。剛開始增加塊大小時，由于塊大小還不是很大，上述的第一種作用超過第二種作用，從而使失效率下降。但等到塊大小較大時，第二種作用超過第一種作用，使失效率上升。

??? 例4.4 假定存儲系統(tǒng)在延遲40個時鐘周期后，每2個時鐘周期能送出16個字節(jié)。即：經(jīng)過42個時鐘周期，它可提供16個字節(jié)；經(jīng)過44個時鐘周期，可提供32個字節(jié)；依此類推。請問對于表4.6中列出的各種容量的 Cache ，在塊大小分別為多少時，平均訪存時間最??？

??? 解： 動畫演示

??? 平均訪存時間為

??? 平均訪存時間 ＝ 命中時間 ＋ 失效率 × 失效開銷

??? 假設(shè)命中時間與塊大小無關(guān)，為1個時鐘，那么對于一個塊大小為16字節(jié)，容量為1KB的 Cache 來說：

??? 平均訪存時間 ＝ 1＋（15.05 %×42） ＝ 7.321 個時鐘周期

??? 而對于塊大小為256字節(jié)、容量為256KB的 Cache 來說，平均訪存時間為

??? 平均訪存時間 ＝ 1＋（0.49 %×76） ＝ 1.353 個時鐘周期