什么是cache

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

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

Cache的基本原理

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

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

• 時(shí)間局部性（temporal locality）：如果一個(gè)數(shù)據(jù)現(xiàn)在被訪問(wèn)了，那么以后很有可能也會(huì)被訪問(wèn)。
• 空間局部性（spatial locally）：如果一個(gè)數(shù)據(jù)現(xiàn)在被訪問(wèn)了，那么它周?chē)臄?shù)據(jù)在以后可能也會(huì)被訪問(wèn)。

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

緩存缺失的類(lèi)型有很多，常見(jiàn)的有以下三種，可以用3C表示

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

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

為什么cache要分級(jí)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

兩路組相聯(lián)緩存的硬件成本相對(duì)于直接映射緩存更高。因?yàn)槠涿看伪容^tag的時(shí)候需要比較多個(gè)cache line對(duì)應(yīng)的tag（某些硬件可能還會(huì)做并行比較，增加比較速度，這就增加了硬件設(shè)計(jì)復(fù)雜度）。為什么我們還需要兩路組相聯(lián)緩存呢？因?yàn)槠淇梢杂兄诮档蚦ache顛簸可能性。

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

Cache的寫(xiě)策略

第一個(gè)寫(xiě)策略問(wèn)題是，當(dāng)處理器修改了高速緩存中的數(shù)據(jù)后，這些修改什么時(shí)候會(huì)被傳播到外層的存儲(chǔ)層次。對(duì)于D-cache來(lái)說(shuō)，當(dāng)執(zhí)行一條store指令時(shí)，如果只是向D-Cache中寫(xiě)入數(shù)據(jù)，而并不改變它的下級(jí)存儲(chǔ)器中的數(shù)據(jù)，這樣就會(huì)導(dǎo)致D-cache和下級(jí)存儲(chǔ)器中，對(duì)于這一個(gè)地址有著不同的數(shù)據(jù)，這稱(chēng)作不一致(non-consistent)。對(duì)應(yīng)的兩種策略是：

• 寫(xiě)直達(dá)（write through），緩存中任何一個(gè)字節(jié)的修改都會(huì)被立即傳播到外層的存儲(chǔ)層次。
• 寫(xiě)回（write back），只有當(dāng)緩存塊被替換的時(shí)候，被修改的數(shù)據(jù)塊會(huì)寫(xiě)回并覆蓋外層存儲(chǔ)層次中的過(guò)時(shí)數(shù)據(jù)。

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

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

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

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

寫(xiě)直達(dá)策略可能會(huì)使用寫(xiě)分配或者寫(xiě)不分配策略。然而，一個(gè)寫(xiě)回策略通常會(huì)使用寫(xiě)分配策略，否則如果使用寫(xiě)不分配策略，寫(xiě)缺失會(huì)被直接傳播到外層存儲(chǔ)層次，從而變的與寫(xiě)直達(dá)相似。

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

多級(jí)cache的包含策略

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

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

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

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

Cache的替換策略

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

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

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