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

表4.7列出了在這兩種極端情況之間的各種塊大小和各種 Cache 容量的平均訪存時間。速度最快的情況： Cache 容量為1KB、4KB、16KB的情況下塊大小為32字節時速度最快；容量為64KB和256KB時，64字節最快。實際上，這些塊大小都是當今處理機器 Cache 中最常見的。

??? 如前所述， Cache 設計者一直在努力同時減少失效率和失效開銷。從失效開銷的角度來講，塊大小的選擇取決于下一級存儲器的延遲和帶寬兩個方面。高延遲和高帶寬時，宜采用較大的 Cache 塊，因為這時每次失效時，稍微增加一點失效開銷，就可以獲得許多數據。與之相反，低延遲和低帶寬時，宜采用較小的 Cache 塊，因為采用大 Cache 塊所能節省的時間不多。一個小 Cache 塊失效開銷的兩倍與一個兩倍于其大小的 Cache 塊的失效開銷差不多，而且采用小 Cache 塊，塊的數量多，有可能減少沖突失效。

?4.3.2提高相聯度

??? 表4.5和圖4.3.1、圖4.3.2已經說明了提高相聯度會使失效率下降。從中我們可以得出兩條經驗規則。第一，對于表中所列出的 Cache 容量，從實際應用的角度來看，8路組相聯在降低失效率方面的作用已經和全相聯一樣有效。也就是說，采用相聯度超過8的方法實際意義不大。第二條規則叫做2：1 Cache 經驗規則，它是指容量為N的直接映象 Cache 的失效率和容量為N/2的兩路組相聯 Cache 差不多相同。

??? 許多例子都說明，改進平均訪存時間的某一方面是以損失另一方面為代價的。增加塊大小的方法會在降低失效率的同時增加失效開銷，而提高相聯度則是以增加命中時間為代價。Hill曾發現，當分別采用直接映象和兩路組相聯時，對于 TTL 或 ECL 板級 Cache ，命中時間相差10 %；而對于定制的 CMOS Cache，命中時間相差2 %。所以，為了實現很高的處理器時鐘頻率，就需要設計結構簡單的 Cache；但時鐘頻率越高，失效開銷就越大（所需的時鐘周期數越多）。為減少失效開銷，又要求提高相聯度。下面通過一個例子進一步說明。

??? 例4.5 假定提高相聯度會按下列比例增大處理器時鐘周期：

??? 時鐘周期2路 ＝1.10×時鐘周期1路

??? 時鐘周期4路 ＝1.12×時鐘周期1路

??? 時鐘周期8路 ＝1.14×時鐘周期1路

??? 假定命中時間為1個時鐘，直接映象情況下失效開銷為50個時鐘周期，而且假設不必將失效開銷取整。使用表4.5中的失效率，試問當 Cache 為多大時，以下不等式成立？

??? 平均訪存時間8路 < 平均訪存時間4路

??? 平均訪存時間4路 < 平均訪存時間2路

??? 平均訪存時間2路 < 平均訪存時間1路

??? 解： 在各種相聯度的情況下，平均訪存時間分別為

??? 平均訪存時間8路 = 命中時間8路 + 失效率8路 ×失效開銷8路

??? = 1.14＋失效率8路 ×50

??? 平均訪存時間4路 = 1.12 ＋失效率4路 ×50

??? 平均訪存時間2路 = 1.10 ＋失效率2路 ×50

??? 平均訪存時間1路 = 1.00 ＋失效率1路 ×50

?在每種情況下的失效開銷相同，都是50個時鐘周期。把相應的失效率代入上式，即可得平均訪存時間。例如，1KB的直接映象 Cache 的平均訪存時間為

??? 平均訪存時間1路 = 1.00 ＋（0.133×50） ＝ 7.65

??? 容量為128KB的8路組相聯 Cache 的平均訪存時間為：

??? 平均訪存時間8路 ＝1.14 ＋（0.006×50） ＝ 1.44

??? 利用這些公式和表4.5中給出的失效率，可得各種容量和相聯度情況下 Cache 的平均訪存時間，如表4.8所示。表中的數據說明，當 Cache 容量不超過16KB時，上述三個不等式成立。從32KB開始，對于平均訪存時間有：4路組相聯的平均訪存時間小于2路組相聯的，2路組相聯的小于直接映象的，但8路組相聯的卻比4路組相聯的大。

??? 請注意，本例中沒有考慮時鐘周期增大對程序其它部分的影響。

?4.3.3Victim Cache

??? 增加 Cache 塊大小和提高相聯度是從 Cache 一出現就被體系結構設計者們用來降低失效率的兩種經典方法。從本小節開始，我們來看一看近幾年提出的幾種方法，這些方法能在不影響時鐘周期或失效開銷的前提下降低 Cache 失效率。

??? 一種能減少沖突失效次數而又不影響時鐘頻率的方法是：在 Cache 和它與下一級存儲器的數據通路之間增設一個全相聯的小 Cache ，稱為Victim Cache。圖4.3.4為其結構框圖。 Victim Cache 中存放由于失效而被丟棄（替換）的那些塊（即victim）。每當發生失效時，在訪問下一級存儲器之前，先檢查 Victim Cache 中是否含有所需的塊。如果有，就將該塊與 Cache 中某個塊做交換。Jouppi于1990年發現，含1到5項的 Victim Cache 對減少沖突失效很有效，尤其是對于那些小型的直接映象數據 Cache 更是如此。對于不同的程序，一個項數為4的 Victim Cache能使一個4KB直接映象數據 Cache 的沖突失效減少20%～90%。

??? 從 Cache 的層次來看， Victim Cache 可以看成位于 Cache 和存儲器之間的又一級 Cache ，采用命中率較高的全相聯策略，容量小，而且僅僅在替換時發生作用。

?4.3.4偽相連Cache

??? 有一種方法既能獲得多路組相聯 Cache 的低失效率又能保持直接映象 Cache 的命中速度，這種方法稱為偽相聯或列相聯。

??? 1. 基本思想及工作原理

??? 采用這種方法時，在命中情況下，訪問 Cache 的過程和直接映象 Cache 中的情況相同；而發生失效時，在訪問下一級存儲器之前，會先檢查 Cache 另一個位置（塊），看是否匹配。確定這個另一塊的一種簡單的方法是將索引字段的最高位取反，然后按照新索引去尋找偽相聯組中的對應塊。如果這一塊的標識匹配，則稱發生了偽命中。否則，就只好訪問下一級存儲器。

??? 2. 快速命中與慢速命中

??? 偽相聯 Cache 具有一快一慢兩種命中時間，它們分別對應于正常命中和偽命中的情況。圖4.3.5中繪出了它們的相對關系。使用偽相聯技術存在一定的危險：如果直接映象 Cache 里的許多快速命中在偽相聯 Cache 中變成慢速命中，那么這種優化措施反而會降低整體性能。所以，要能夠指出同一組中的兩個塊哪個為快速命中，哪個為慢速命中，這是很重要的。一種簡單的解決方法就是交換兩個塊的內容。

下面通過一個例子來說明偽相聯帶來的好處。

??? 例4.6 假設當在按直接映象找到的位置處沒有發現匹配，而在另一個位置才找到數據（偽命中）需要2個額外的周期。仍用上個例子中的數據，問：當 Cache 容量分別為2KB和128KB時，直接映象、兩路組相聯和偽相聯這三種組織結構中，哪一種速度最快？

??? 解： 首先考慮標準的平均訪存時間公式：

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

??? 我們從該公式的最后一部分著手。不管我們對命中的情況做了何種改進，失效開銷總是相同的。為了確定失效率，需要知道什么時候會發生失效。只要我們總是通過把索引的最高位變反的方法來尋找另一塊，在同一“偽相聯”組中的兩塊就是用同一個索引選擇得到的，這與在兩路組相聯 Cache 中所用的方法是一樣的，因而它們的失效率相同，即

??? 失效率偽相聯 ＝ 失效率2路

??? 再看命中時間。偽相聯 Cache 的命中時間等于直接映象 Cache 的命中時間加上在偽相聯查找過程中命中（即偽命中）的百分比乘以該命中所需的額外時間開銷，即

??? 命中時間偽相聯＝命中時間1路＋偽命中率偽相聯×2

??? 偽相聯查找的命中率等于兩路組相聯 Cache 的命中率和直接映象 Cache 命中率之差：

??? 偽命中率偽相聯 ＝命中率2路－命中率1路

??? ＝（1－失效率2路）－（1－失效率1路）

??? ＝失效率1路－失效率2路

??? 綜合上述分析，有

??? 平均訪存時間偽相聯＝命中時間1路＋（失效率1路－失效率2路）×2

??? ＋失效率2路×失效開銷1路

??? 將表4.5中的數據代入上面的公式，得

??? 平均訪存時間偽相聯，2KB ＝1＋（0.098－0.076）×2＋（0.076×50）＝4.844

??? 平均訪存時間偽相聯，128KB＝1＋（0.010－0.007）×2＋（0.007×50）＝1.356

??? 根據上一個例子中的表4.8，對于2KB Cache ，可得

??? 平均訪存時間1路 ＝5.90 個時鐘

??? 平均訪存時間2路 ＝4.90 個時鐘

??? 對于128KB的 Cache 有，可得

??? 平均訪存時間1路 ＝1.50 個時鐘

??? 平均訪存時間2路 ＝1.45 個時鐘

??? 可見，對于這兩種 Cache 容量，偽相聯 Cache 都是速度最快的。

??? 盡管從理論上來說，偽相聯是一種很有吸引力的方法，但它的多種命中時間會使 CPU 流水線的設計復雜化。因此偽相聯技術往往應用在離處理器比較遠的 Cache 上，如二級Cache。