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

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

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

?4.3.2提高相聯(lián)度

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

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

??? 例4.5 假定提高相聯(lián)度會按下列比例增大處理器時(shí)鐘周期：

??? 時(shí)鐘周期2路 ＝1.10×?xí)r鐘周期1路

??? 時(shí)鐘周期4路 ＝1.12×?xí)r鐘周期1路

??? 時(shí)鐘周期8路 ＝1.14×?xí)r鐘周期1路

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

??? 平均訪存時(shí)間8路 < 平均訪存時(shí)間4路

??? 平均訪存時(shí)間4路 < 平均訪存時(shí)間2路

??? 平均訪存時(shí)間2路 < 平均訪存時(shí)間1路

??? 解： 在各種相聯(lián)度的情況下，平均訪存時(shí)間分別為

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

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

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

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

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

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

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

??? 容量為128KB的8路組相聯(lián) Cache 的平均訪存時(shí)間為：

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

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

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

?4.3.3Victim Cache

??? 增加 Cache 塊大小和提高相聯(lián)度是從 Cache 一出現(xiàn)就被體系結(jié)構(gòu)設(shè)計(jì)者們用來降低失效率的兩種經(jīng)典方法。從本小節(jié)開始，我們來看一看近幾年提出的幾種方法，這些方法能在不影響時(shí)鐘周期或失效開銷的前提下降低 Cache 失效率。

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

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

?4.3.4偽相連Cache

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

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

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

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

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

下面通過一個(gè)例子來說明偽相聯(lián)帶來的好處。

??? 例4.6 假設(shè)當(dāng)在按直接映象找到的位置處沒有發(fā)現(xiàn)匹配，而在另一個(gè)位置才找到數(shù)據(jù)（偽命中）需要2個(gè)額外的周期。仍用上個(gè)例子中的數(shù)據(jù)，問：當(dāng) Cache 容量分別為2KB和128KB時(shí)，直接映象、兩路組相聯(lián)和偽相聯(lián)這三種組織結(jié)構(gòu)中，哪一種速度最快？

??? 解： 首先考慮標(biāo)準(zhǔn)的平均訪存時(shí)間公式：

??? 平均訪存時(shí)間偽相聯(lián) ＝ 命中時(shí)間偽相聯(lián)＋失效率偽相聯(lián)×失效開銷偽相聯(lián)

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

??? 失效率偽相聯(lián) ＝ 失效率2路

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

??? 命中時(shí)間偽相聯(lián)＝命中時(shí)間1路＋偽命中率偽相聯(lián)×2

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

??? 偽命中率偽相聯(lián) ＝命中率2路－命中率1路

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

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

??? 綜合上述分析，有

??? 平均訪存時(shí)間偽相聯(lián)＝命中時(shí)間1路＋（失效率1路－失效率2路）×2

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

??? 將表4.5中的數(shù)據(jù)代入上面的公式，得

??? 平均訪存時(shí)間偽相聯(lián)，2KB ＝1＋（0.098－0.076）×2＋（0.076×50）＝4.844

??? 平均訪存時(shí)間偽相聯(lián)，128KB＝1＋（0.010－0.007）×2＋（0.007×50）＝1.356

??? 根據(jù)上一個(gè)例子中的表4.8，對于2KB Cache ，可得

??? 平均訪存時(shí)間1路 ＝5.90 個(gè)時(shí)鐘

??? 平均訪存時(shí)間2路 ＝4.90 個(gè)時(shí)鐘

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

??? 平均訪存時(shí)間1路 ＝1.50 個(gè)時(shí)鐘

??? 平均訪存時(shí)間2路 ＝1.45 個(gè)時(shí)鐘

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

??? 盡管從理論上來說，偽相聯(lián)是一種很有吸引力的方法，但它的多種命中時(shí)間會使 CPU 流水線的設(shè)計(jì)復(fù)雜化。因此偽相聯(lián)技術(shù)往往應(yīng)用在離處理器比較遠(yuǎn)的 Cache 上，如二級Cache。