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

?學習目標：

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

??? 掌握Cache容量、相聯度等與3C的關系；

??? 掌握2:1Cache經驗規則；

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

??? 理解提高相聯度對失效率的影響；

??? 掌握Victim Cache的思想；

??? 掌握偽相聯Cache的思想。

??? 正文：

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

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

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

??? 當第一次訪問一個塊時，該塊不在 Cache 中，需從下一級存儲器中調入 Cache ，這就是強制性失效。這種失效也稱為冷啟動失效或首次訪問失效。

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

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

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

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

表4.5針對 SPEC92 典型程序給出了上述三種失效所占的比例（這些數據是在 DECstation 5000上測得的。假設 Cache 的塊大小為32字節，并采用 LRU 算法）。為了說明高相聯度的好處，表中列出了在直接映象、兩路組相聯、四路組相聯和八路組相聯的情況下，沖突失效的值。可以看出：

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

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

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

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

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

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

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

4.3.1增加Cache塊大小

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

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

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

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

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

??? 解： 動畫演示

??? 平均訪存時間為

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

??? 假設命中時間與塊大小無關，為1個時鐘，那么對于一個塊大小為16字節，容量為1KB的 Cache 來說：

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

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

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