降低Cache失效率的方法1

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

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

學習目標：

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

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

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

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

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

掌握Vic（TI）mCache的思想；

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

正文：

4.3降低Cache失效率的方法

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

(1)強制性失效（Compulsory（mi）ss）

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

(2)容量失效（Capacitymiss）

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

(3)沖突失效（Conflictmiss）

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

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

(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），從而導致整體性能的下降。至于容量失效，除了增大Cache以外，沒有別的辦法。在一個存儲層次中，如果高一級存儲器的容量比程序所需的空間小得多，就有可能出現(xiàn)抖動現(xiàn)象。這時大部分時間是花在兩級存儲器之間移動數(shù)據(jù)。出現(xiàn)抖動時，由于大量進行替換，機器的運行速度接近于只有第二級存儲器的情況，甚至更慢。

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

4.3.1增加Cache塊大小

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

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

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

導致上述失效率先下降后上升的原因，在于增加塊大小會產(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，在塊大小分別為多少時，平均訪存時間最??？

解：動畫演示

平均訪存時間為

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

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

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

而對于塊大小為256