什么是cache

Cache存儲器也被稱為高速緩沖存儲器，位于CPU和主存儲器之間。之所以在CPU和主存之間要加cache是因為現(xiàn)代的CPU頻率大大提高，內(nèi)存的發(fā)展已經(jīng)跟不上CPU訪存的速度。在2001 – 2005年間，處理器時鐘頻率以每年55%的速度增長，而主存的增長速度只是7%。在現(xiàn)在的系統(tǒng)中，處理器需要上百個時鐘周期才能從主存中取到數(shù)據(jù)。如果沒有cache，處理器在等待數(shù)據(jù)的大部分時間內(nèi)將會停滯不動。

圖1 現(xiàn)代處理器存儲層次示意圖

Cache的基本原理

Cache的容量跟主存比起來要小得多，尤其是離CPU最近的L1，通常是幾十KB大小。一般L3也就是幾十MB大小，跟現(xiàn)在以GB為單位的內(nèi)存比起來差了好幾個數(shù)量級。那為什么加入cache還能提高性能呢？

設(shè)想一下，如果提前把CPU接下來最有可能用到的數(shù)據(jù)存放在cache中，那么CPU就可以在很短的時間內(nèi)得到數(shù)據(jù)了，一般如果L1命中的話，CPU在2-3個時鐘周期內(nèi)就會得到想要的數(shù)據(jù)。那么CPU是如何預測到接下來將要用到的數(shù)據(jù)的呢？其實這種預測是基于程序代碼和數(shù)據(jù)在時間和空間上的局部性原理(locality)。

• 時間局部性（temporal locality）：如果一個數(shù)據(jù)現(xiàn)在被訪問了，那么以后很有可能也會被訪問。
• 空間局部性（spatial locally）：如果一個數(shù)據(jù)現(xiàn)在被訪問了，那么它周圍的數(shù)據(jù)在以后可能也會被訪問。

這里要提到一些概念。當CPU在cache中找到需要的數(shù)據(jù)，我們稱之為命中（hit）。反之沒有找到數(shù)據(jù)，我們稱之為缺失（miss），這時候就要去外層存儲中尋找所需數(shù)據(jù)。如果是多級cache設(shè)計，那么對于L1來講L2就是它的外層存儲。

緩存缺失的類型有很多，常見的有以下三種，可以用3C表示

• 強制缺失（Compulsory miss），第一次將數(shù)據(jù)塊讀入cache所產(chǎn)生的缺失，也成為冷缺失（cold miss）。
• 沖突缺失（Conflict miss），由于cache相聯(lián)度有限導致的缺失。
• 容量缺失（Capacity miss），由于cache大小有限導致的缺失。

高速緩存的管理需要考慮多個方面。首先是數(shù)據(jù)放置策略；其次是數(shù)據(jù)替換策略；最后是數(shù)據(jù)寫策略，后面會逐一介紹。

為什么cache要分級

我們經(jīng)常會看到cache分為L1，L2，L3甚至L4等多級。為什么不能把L1的容量做大，不要其它的cache了？原因在于性能/功耗/面積（PPA）權(quán)衡考慮。L1 cache一般工作在CPU的時鐘頻率，要求的就是夠快，可以在2-4時鐘周期內(nèi)取到數(shù)據(jù)。L2 cache相對來說是為提供更大的容量而優(yōu)化的。雖然L1和L2往往都是SRAM，但構(gòu)成存儲單元的晶體管并不一樣。L1是為了更快的速度訪問而優(yōu)化過的，它用了更多/更復雜/更大的晶體管，從而更加昂貴和更加耗電；L2相對來說是為提供更大的容量優(yōu)化的，用了更少/更簡單的晶體管，從而相對便宜和省電。在有一些CPU設(shè)計中，會用DRAM實現(xiàn)大容量的L3 cache（一個DRAM的存儲單元要比SRAM?。，F(xiàn)在也有一些設(shè)計會帶L4 cache，有時放在片外或者和CPU封裝在一起。

圖2 DRAM（左）和SRAM（右）基本單元結(jié)構(gòu)圖

再回到L1 cache，如果容量做大，那么存儲單元的選通將會復雜。從而很難滿足高時鐘頻率的要求。另外，當cache容量很小時增加容量，命中率增加的比較明顯；當容量達到一定程度，提高cache容量對于提高cache命中率的貢獻就很有限了。簡單說就是大容量L1很難做，即使做出來用處不明顯。與其這樣，還不如把節(jié)約下來的晶體管用來做其它的用途。

圖3 Cache命中率與容量關(guān)系

因此出于PPA的權(quán)衡，我們先看到的cache系統(tǒng)一般是這樣的：32-64KB的指令cache和數(shù)據(jù)cache（一般L1的指令和數(shù)據(jù)cache是分開的），2-4個時鐘周期訪問時間；256KB-2MB的L2 cache（一般從L2開始指令和數(shù)據(jù)就不分開了），10-20個時鐘周期的訪問時間；8-80MB的L3 cache，20-50個時鐘周期的訪問時間。注意，這里所說的時鐘周期都是指的CPU的時鐘周期。一般L2和L3的工作時鐘頻率要比CPU的低，這個時鐘周期是折算后的數(shù)值。

Cache的數(shù)據(jù)放置策略

在講cache的構(gòu)成前，先要講幾個概念。首先，緩存的大小稱之為cache size，其中每一個緩存行稱之為cache line。Cache主要由兩部分組成，Tag部分和Data部分。因為cache是利用了程序中的相關(guān)性，一個被訪問的數(shù)據(jù)，它本身和它周圍的數(shù)據(jù)在最近都有可能被訪問，因此Data部分就是用來保存一片連續(xù)地址的數(shù)據(jù)，而Tag部分則是存儲著這片連續(xù)地址的公共地址，一個Tag和它對應的所有數(shù)據(jù)Data組成一行稱為cache line，而cache line中的數(shù)據(jù)部分成為數(shù)據(jù)塊(cache data block，也稱做cache block或data block)。如果一個數(shù)據(jù)可以存儲在cache的多個地方，這些被同一個地址找到的多個cache line稱為cache set。當CPU在讀取緩存數(shù)據(jù)時，一個cache line的多字節(jié)會被同時讀出。

假設(shè)我們現(xiàn)在的cache size是32KB，一個cache line是64Bytes。通過簡單的除法我們就知道在cache中有512條cache line。假設(shè)我們的系統(tǒng)中地址寬度是32bit，當一個地址發(fā)下來，會用最低的6bits作為塊內(nèi)的偏移地址（offset），用較高的9bits作為cache索引地址（index），將其余的17bits地址作為標志位（tag）作為比對。

使用Index來從cache中找到一個對應的cache line，但是所有Index相同的地址都會尋址到這個cache line，因此在cache line中還有Tag部分，用來和地址中的Tag進行比較，只有它們相等才表明這個cache line就是想要的那個。在一個cache line中有很多數(shù)據(jù)，通過存儲器地址中的Offset部分可以找到真正想要的數(shù)據(jù)，它可以定位到每個字節(jié)。在cache line中還有一個有效位(Valid)，用來標記這個Cache line是否保存著有效的數(shù)據(jù)，只有在之前被訪問過的存儲器地址，它的數(shù)據(jù)才會存在于對應的cache line中，相應的有效位也會被置為1。每個cache line中會有一個bit位記錄數(shù)據(jù)是否被修改過，稱之為dirty bit。

圖1 cache組成結(jié)構(gòu)示意圖

上面的地址對應關(guān)系被稱為直接映射（direct-mapped）。直接映射緩存在硬件設(shè)計上會更加簡單，因此成本上也會較低。根據(jù)直接映射，我們可以畫出主存地址與cache的對應關(guān)系如下圖：

圖2 直接映射的內(nèi)存與cache對應關(guān)系

問題來了，如果CPU需要連續(xù)訪問0x0000_0000，0x0001_0000，0x0002_0000地址，會發(fā)生什么呢？這三個地址的index位是一樣的，tag位不同，因此對應的cache line是同一個。所以當訪問0x0000_0000時，cache缺失，需要從主存中搬入數(shù)據(jù)（假設(shè)只有一級cache）；當訪問0x0001_0000時，同樣是cache缺失，需要從主存中搬入數(shù)據(jù)，替換掉cache中的上一條數(shù)據(jù)；當訪問0x0002_0000時，依然cache缺失，需要從主存中搬入數(shù)據(jù)。這就相當于每次訪問數(shù)據(jù)都要從主存中讀取，所以cache的存在并沒有對性能有什么提升。這種現(xiàn)象叫做cache顛簸（cache thrashing）。

組相聯(lián)的方式是為了解決直接映射結(jié)構(gòu)Cache的不足而提出的，存儲器中的一個數(shù)據(jù)不單單只能放在一個cache line中，而是可以放在多個cache line中，對于一個組相聯(lián)結(jié)構(gòu)的cache來說，如果一個數(shù)據(jù)可以放在n個位置，則稱這個cache是n路組相聯(lián)的cache(n way set-associative Cache)。下圖為一個兩路組相聯(lián)Cache的原理圖。

圖3 兩路組相聯(lián)cache

這種結(jié)構(gòu)仍舊使用存儲器地址的Index部分對cache進行尋址，此時可以得到兩個cache line，這兩個cache line稱為一個cache set，究竟哪個cache line才是最終需要的，是根據(jù)Tag比較的結(jié)果來確定的，如果兩個cache line的Tag比較結(jié)果都不相等，那么就說明這個存儲器地址對應的數(shù)據(jù)不在cache中，也就是發(fā)生了cache缺失。上圖所示為并行訪問，如果先訪問Tag SRAM部分，根據(jù)Tag比較的結(jié)果再去訪問Data SRAM部分，就稱為串行訪問。

兩路組相聯(lián)緩存的硬件成本相對于直接映射緩存更高。因為其每次比較tag的時候需要比較多個cache line對應的tag（某些硬件可能還會做并行比較，增加比較速度，這就增加了硬件設(shè)計復雜度）。為什么我們還需要兩路組相聯(lián)緩存呢？因為其可以有助于降低cache顛簸可能性。

既然組相聯(lián)緩存那么好，如果所有的cache line都在一個組內(nèi)。豈不是性能更好？由于所有的cache line都在一個組內(nèi)，因此地址中不需要set index部分。因為，只有一個組讓你選擇，間接來說就是你沒得選。我們根據(jù)地址中的tag部分和所有的cache line對應的tag進行比較（硬件上可能并行比較也可能串行比較）。哪個tag比較相等，就意味著命中某個cache line。因此，在全相連緩存中，任意地址的數(shù)據(jù)可以緩存在任意的cache line中。所以，這可以最大程度的降低cache顛簸的頻率。但是硬件成本上也是更高。

Cache的寫策略

第一個寫策略問題是，當處理器修改了高速緩存中的數(shù)據(jù)后，這些修改什么時候會被傳播到外層的存儲層次。對于D-cache來說，當執(zhí)行一條store指令時，如果只是向D-Cache中寫入數(shù)據(jù)，而并不改變它的下級存儲器中的數(shù)據(jù)，這樣就會導致D-cache和下級存儲器中，對于這一個地址有著不同的數(shù)據(jù)，這稱作不一致(non-consistent)。對應的兩種策略是：

• 寫直達（write through），緩存中任何一個字節(jié)的修改都會被立即傳播到外層的存儲層次。
• 寫回（write back），只有當緩存塊被替換的時候，被修改的數(shù)據(jù)塊會寫回并覆蓋外層存儲層次中的過時數(shù)據(jù)。

采用寫直達還是寫回策略，首先要考慮的系統(tǒng)帶寬。對于處理器芯片最外層的高速緩存，由于片外帶寬有限，往往采用寫回策略；而對于內(nèi)層高速緩存，由于片上帶寬較大，因此往往采用寫直達策略。

一個影響是要考慮兩種策略在硬件故障下的容錯。例如，當遇到阿爾法粒子或者宇宙射線時存儲在高速緩存中的數(shù)據(jù)會反轉(zhuǎn)其存儲的值。在寫直達策略中，當檢測到故障時，可以安全的丟棄出故障的數(shù)據(jù)塊并從外層存儲中重新讀取該數(shù)據(jù)塊。但在寫回策略中，僅僅有故障檢測并不夠。為了增加糾錯功能，需要添加冗余的數(shù)據(jù)位ECC。但由于ECC計算開銷大，因此ECC會增加高速緩存的訪問時延。

另一個影響是要考慮兩種策略中外層高速存儲的功耗。在寫直達策略中，外層高速緩存會被頻繁寫入，導致外層高速緩存較高的功耗。解決辦法之一是在內(nèi)層緩存和外層緩存中間增加一個寫緩沖，用于臨時保存對內(nèi)層緩存的最近若干更新。當寫緩沖滿的時候，將存儲最久的或最近最少使用的數(shù)據(jù)塊寫入外層緩存。當內(nèi)層緩存缺失時，首先檢查寫緩沖區(qū)。

第二個問題是，如果要寫入字節(jié)的數(shù)據(jù)塊不在高速緩存中時，是否將其讀入高速緩存中。上面所講述的情況都是假設(shè)在寫D-cache時，要寫入的地址總是D-cache中存在的，而實際當中，有可能發(fā)現(xiàn)這個地址并不在D-cache中，這就發(fā)生了寫缺失(write miss)，此時最簡單的處理方法就是將數(shù)據(jù)直接寫到下級存儲器中，而并不寫到D-cache中，這種方式稱為寫不分配（Write non-Allocate）。與之相對應的方法就是寫分配（Write Allocate），在這種方法中，如果寫cache時發(fā)生了缺失，會首先從下級存儲器中將這個發(fā)生缺失的地址對應的整個數(shù)據(jù)塊(data block)取出來，將要寫入到D-cache中的數(shù)據(jù)合并到這個數(shù)據(jù)塊中，然后將這個被修改過的數(shù)據(jù)塊寫到D-cache中。如果為了保持存儲器的一致性，將這個數(shù)據(jù)塊也寫到下級存儲器中，這種方法就是剛才提到的寫直達(Write Through)。如果只是將D-cache中對應的line標記為臟(Dirty)的狀態(tài)，只有等到這個line要被替換時，才將其寫回到下級存儲器中，則這種方法就是前面提到的寫回(WriteBack)。Write Allocate為什么在寫缺失時，要先將缺失地址對應的數(shù)據(jù)塊從下級存儲器中讀取出來，然后在合并后寫到cache中？因為通常對于寫D-cache來說，最多也就是寫入一個字，直接寫入cache的話，會造成數(shù)據(jù)塊中的其它部分和下級存儲器中對應的數(shù)據(jù)不一致，且是無效的，如果這個cache line由于被替換而寫回到下級存儲器中時，就會使下級存儲器中的正確數(shù)據(jù)被篡改。

寫直達策略可能會使用寫分配或者寫不分配策略。然而，一個寫回策略通常會使用寫分配策略，否則如果使用寫不分配策略，寫缺失會被直接傳播到外層存儲層次，從而變的與寫直達相似。

對于多核處理器設(shè)計來說，往往最后一級cache（last level cache，LLC）是所有處理器共享，而其它級cache是某處理器獨享，因此還有一個寫操作如何傳播的問題。有兩種實現(xiàn)方式：寫更新（write update）和寫無效（write invalidate）。區(qū)別是對某個處理器的緩存中的某個值執(zhí)行寫操作時，對于保有該數(shù)據(jù)副本的其他所有緩存的值是全部更新還是全部置為無效。

多級cache的包含策略

在多級高速緩存的設(shè)計中，另一個相關(guān)的問題是內(nèi)層高速緩存的內(nèi)容是否包含在外層高速緩存中。如果外層高速緩存包含了內(nèi)層高速緩存的內(nèi)容，則稱外層高速緩存為包含的（inclusive），相反如果外層高速緩存只包含不在內(nèi)層高速緩存中的數(shù)據(jù)塊，則稱外層高速緩存是排他的（exclusive）。包含性和排他性需要特殊的協(xié)議才能實現(xiàn)，否則無法保證包含性或者排他性，這種情況稱之為不包含又不排他（non-inclusive non-exclusive，NINE）。

包含策略的優(yōu)點是，前處理器緩存缺失的時候想看看所需的塊是不是在其他處理器的私有cache中，不需要再去一個個查其他處理器的cache了，只需要看看共享的外層cache中有沒有即可，對于實現(xiàn)cache一致性非常方便，也有效降低了緩存缺失時的總線負載和miss penalty；缺點是整體cache的容量變小。

包含策略的特性會產(chǎn)生兩個影響。一是在采用包含策略的高速緩存中，緩存缺失的時延較短，而采用排他和NINE策略則較長。二是對對所有內(nèi)層高速緩存檢查訪問的數(shù)據(jù)塊是否存在意味著增加對高速緩存控制器和內(nèi)層高速緩存標簽陣列的占用。

排他策略正好相反，其優(yōu)點是，可以最大限度的存儲不同的數(shù)據(jù)塊，相當于增大整體了cache的容量；其缺點是需要頻繁填充新的數(shù)據(jù)塊，會消耗更多的內(nèi)外層間緩存帶寬，并且對標簽和數(shù)據(jù)陣列產(chǎn)生更高的占用率。

Cache的替換策略

在一個cache set內(nèi)的所有l(wèi)ine都已經(jīng)被占用的情況下，如果需要存放從下游存儲器中讀過來的其它地址的數(shù)據(jù)，那么就需要從其中替換一個，如何從這些有效的cache line找到一個并替換之，這就是替換(cache replacement)策略。常見的替換算法有以下幾種：

• 先進先出（FIFO）算法
• 最不經(jīng)常使用（LFU）算法
• 近期最少使用（LRU）算法
• 隨機替換算法

評價cache數(shù)據(jù)替換策略的標準是，被替換出的數(shù)據(jù)塊應該是將來最晚被訪問的數(shù)據(jù)塊。這也好理解，就是要盡量降低隨后訪問的緩存缺失。目前，大部分高速緩存采用LRU或者近似的替換策略。但是LRU的性能也不是完美的，特別是當程序的工作集遠大于緩存大小時，LRU的性能會出現(xiàn)斷崖式下跌。