什么是cache

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

圖1 現代處理器存儲層次示意圖

Cache的基本原理

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

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

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

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

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

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

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

為什么cache要分級

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

圖2 DRAM（左）和SRAM（右）基本單元結構圖

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

圖3 Cache命中率與容量關系

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

Cache的數據放置策略

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

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

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

圖1 cache組成結構示意圖

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

圖2 直接映射的內存與cache對應關系

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

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

圖3 兩路組相聯cache

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

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

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

Cache的寫策略

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

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

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

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

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

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

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

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

多級cache的包含策略

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

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

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

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

Cache的替換策略

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

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

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