一文看懂CPU cache的基本原理

CPU cache主要是為了解決CPU與內(nèi)存之間的速度不匹配問題。

CPU cache一般分為多級，例如L1、L2、L3 cache等。越靠近CPU的cache，速度越快，成本越高，容量越小。L1 cache一般包括指令cache (I-Cache)和數(shù)據(jù)cache(D-Cache)，它們的原理基本一樣，但是D-Cache需要讀取和寫入，而I-Cache只會被讀取，不會被寫入，因此D-Cache更復(fù)雜一些。

L1 Cache最靠近處理器，需要和處理器保持近似相等的速度。L1 Cache一般使用多端口SRAM來實(shí)現(xiàn)，容量大的SRAM需要更長的時(shí)間來找到一個(gè)指定地址的內(nèi)容。因此，L1 Cache的速度最快，但容量最小。

L2 Cache一般都是指令和數(shù)據(jù)共享，它可以容忍更慢一些，盡量保存更多的內(nèi)容。所以，CPU的L2 Cache一般是以MB為單位的。

cache主要由兩部分組成，Tag RAM和Data RAM。cache利用了程序中的相關(guān)性，一個(gè)被訪問的數(shù)據(jù)，它本身和它周圍的數(shù)據(jù)在最近都有可能被訪問，因此Data部分用來存一片連續(xù)地址的數(shù)據(jù)，而Tag部分則存儲這片連續(xù)數(shù)據(jù)的公共地址，一個(gè)Tag和它對應(yīng)的所有數(shù)據(jù)組成的一行稱為一個(gè)Cache line（cache line大小一般為64B），Cache line中的數(shù)據(jù)部分稱為數(shù)據(jù)塊(Cache data block,也叫Cache block或Data block,在下文不進(jìn)行區(qū)分)。如果一個(gè)數(shù)據(jù)可以存儲在cache中的多個(gè)地方，這些被同一個(gè)地址找到的多個(gè)cache line稱為cache set（即相同index，不同tag）。cache結(jié)構(gòu)如下圖。

cache的結(jié)構(gòu)

上圖表示了一種可能的實(shí)現(xiàn)方式。cache有三種實(shí)現(xiàn)方式，直接映射(direct-mappd)，組相連(set-associative)和全相連(fully associative)，這三種的原理如下圖。對于物理內(nèi)存中的一個(gè)數(shù)據(jù)來說，如果在Cache中只有一個(gè)地方可以容納它，它就是直接映射的Cache；如果Cache中有多個(gè)地方都可以放這個(gè)數(shù)據(jù)，它就是組相連的Cache；如果Cache中任何地方都可以放這個(gè)數(shù)據(jù)，那它就是全相連的Cache。直接映射和全相連是組相連Cache的兩種特殊情況，現(xiàn)代處理器中的TLB和Victim Cache多采用全相連結(jié)構(gòu)，而I-Cache和D-Cache則采用組相連的結(jié)構(gòu)。

cache的三種組成方式

Cache只能保存最近被處理器使用過的內(nèi)容，由于容量有限，很多情況下，要找的指令或者數(shù)據(jù)并不在Cache中，這稱為Cache的缺失(cache miss)。cache miss發(fā)生的頻率直接影響CPU性能，影響Cache缺失的情況如下：

(1) Compulsory。由于Cache只是緩存以前訪問過的內(nèi)容，因此第一次被訪問的指令或數(shù)據(jù)肯定不在Cache中，這個(gè)缺失肯定會發(fā)生?？梢圆捎妙A(yù)取(prefetch)的方法來盡量降低這種缺失。

(2) Capcity。Cache容量越大，可以緩存更多的內(nèi)容，容量是影響Cache缺失的一個(gè)關(guān)鍵因素。例如，當(dāng)程序頻繁使用的5個(gè)數(shù)據(jù)屬于不同的Cache set，而Cache的容量只有4個(gè)Cache set時(shí)，那么就會經(jīng)常發(fā)生缺失。

(3)Conflict。為了解決多個(gè)數(shù)據(jù)映射到Cache中同一個(gè)位置的情況，一般使用組相連Cache，由于實(shí)際硅片面積的限制，相連度不可能很高，例如，在一個(gè)兩路結(jié)構(gòu) (2-way) 的Cache中。如果程序頻繁使用的三個(gè)數(shù)據(jù)屬于同一個(gè)Cache set，那么就會經(jīng)常發(fā)生缺失，此時(shí)可以使用Victim Cache來緩解這個(gè)問題。

影響Cache缺失的這三個(gè)條件，稱為3C定理。在超標(biāo)量處理器中，可以采用預(yù)取和victim cache這兩種方法，但無法從根本上消除cache缺失，只能減少它發(fā)生的頻率。

1. cache的組成方式

1.1 直接映射

直接映射（direct-mapped）的Cache是最容易實(shí)現(xiàn)的一種方式，處理器訪問存儲器的地址分為三部分，Tag、Index和Block Offset。使用Index從Cahce中找到一個(gè)對應(yīng)的Cache line，但是所有Index相同的地址都會尋址到這個(gè)Cache line，因此Cache line中還有Tag部分，用來和地址中的Tag進(jìn)行比較，只有它們相等，才表明這個(gè)Cache line是想要的那個(gè)。一個(gè)Cache line中有多個(gè)數(shù)據(jù)（通常為64 Bytes），通過地址中的Block Offset定位到每個(gè)字節(jié)。Cache line中還有一個(gè)有效位valid，用來標(biāo)記Cache line中的數(shù)據(jù)是否有效，只有在之前被訪問過的存儲器地址，它的數(shù)據(jù)才會存在于對應(yīng)的Cache line中，相應(yīng)的有效位也會被置1。

直接映射的cache

對于所有Index相同的存儲器地址，都會尋址到同一個(gè)Cache line中，這就會發(fā)生沖突，這是直接映射Cache的一大缺點(diǎn)。如果兩個(gè)Index相同的地址交叉訪問Cache，就會一直導(dǎo)致Cache缺失，嚴(yán)重降低CPU執(zhí)行效率。

下面通過一個(gè)例子來說明存儲器地址的劃分對Cache的影響，下圖為一個(gè)32位存儲器地址，Block Offset有5位，所以Data block的大小是2^5 = 32字節(jié)，Index是6位，表示Cache中共有2^6=64個(gè)Cache line(在直接映射中，Cache line和Cache Set是同義的)，存儲器地址中剩余的32-5-6=21位作為Tag值，因此這個(gè)Cache中可以存儲的數(shù)據(jù)大小為64*32=2048字節(jié)，即2KB；而Tag部分的大小是64*21=1344位，約為1.3Kb；有效位占用的大小為64*1=64位。一般以數(shù)據(jù)部分的大小來表示Cache的大小，因此這個(gè)Cache是一個(gè)2KB直接映射的Cache，實(shí)際它還額外占用多于1.3Kb的存儲空間。

存儲器的地址劃分

直接映射的Cache在實(shí)現(xiàn)上最簡單，它不需要替換算法，執(zhí)行效率也是最低的，現(xiàn)代處理器很少使用這種方式。

1.2 組相連

組相連(set-associative)是為了解決直接映射Cache的不足而提出的。存儲器中的一個(gè)數(shù)據(jù)不是只能放在一個(gè)Cache line中，而是可以放在多個(gè)Cache line中，對于一個(gè)組相連的Cache來說，如果一個(gè)數(shù)據(jù)可以放在n個(gè)位置，則稱這個(gè)Cache是n路組相連(n-way)。下圖為一個(gè)2-way組相連的cache。

2-way組相連的cache

這種結(jié)構(gòu)仍然使用地址的Index部分對Cache進(jìn)行尋址，此時(shí)可以得到2個(gè)Cache line，這2個(gè)Cache line稱為一個(gè)Cache set，哪個(gè)Cache line是最終需要的，需要根據(jù)Tag比較結(jié)果來確定。如果兩個(gè)Cache line的Tag比較都不相等，那么就發(fā)生了Cache缺失。

因?yàn)樾枰獜亩鄠€(gè)Cache line中選擇一個(gè)匹配的結(jié)果，這種Cache的實(shí)現(xiàn)方式和直接映射Cache相比，延遲會更大，但這種方式可以顯著減少Cache缺失發(fā)生的頻率，因此在現(xiàn)代處理器中廣泛應(yīng)用。

Tag和Data部分是分開放置的，稱為Tag SRAM和Data SRAM，可以同時(shí)訪問這兩個(gè)部分，稱為并行訪問；相反，如果先訪問Tag SRAM，根據(jù)Tag比較的結(jié)果再去訪問Data SRAM，稱為串行訪問。這兩種方式各有優(yōu)缺點(diǎn)。

對于并行訪問，當(dāng)Tag部分的某個(gè)地址被讀取的同時(shí)，這個(gè)地址在Data部分對應(yīng)的所有數(shù)據(jù)也會被讀出來，并送到一個(gè)多路選擇器上，這個(gè)多路選擇器受到Tag比較結(jié)果的控制，選出相應(yīng)的Data block，然后根據(jù)存儲器地址中的Block offset的值，選擇出合適的字節(jié)，一般將選擇字節(jié)的這個(gè)過程稱為數(shù)據(jù)對齊。

并行訪問Cache中的Tag和Data

Cache的訪問一般是處理器關(guān)鍵路徑，并行訪問Cache若在一個(gè)周期內(nèi)完成，在現(xiàn)實(shí)中會占據(jù)很大延遲，要想使處理器運(yùn)行在較高的頻率下，Cache的訪問就需要使用流水線。前面說過，對于指令Cache來說，流水線的結(jié)構(gòu)不會有太大的影響，仍舊可以實(shí)現(xiàn)每周期讀取指令的效果；而對于數(shù)據(jù)Cache來說，使用流水線則會增大load指令的延遲，對處理器的性能造成影響。

并行訪問cache的流水線如下圖。流水線的地址計(jì)算階段可以計(jì)算出存儲器的地址，接下來的Disambiguation階段對load/store指令之間存在的相關(guān)性進(jìn)行檢查，然后在Cache Access階段就可以直接并行訪問Tag SRAM和Data SRAM，并使用Tag比較的結(jié)果對輸出的數(shù)據(jù)進(jìn)行選擇，然后在下一個(gè)流水線階段Result Drive，使用地址中的block offset值選出最終需要的數(shù)據(jù)。將整個(gè)Cache的訪問放到幾個(gè)周期內(nèi)完成，降低處理器的周期。

并行訪問cache的流水線

而對于串行訪問來說，首先對Tag SRAM進(jìn)行訪問，根據(jù)Tag比較的結(jié)果，就可以知道數(shù)據(jù)部分中的哪一路需要訪問，此時(shí)可以直接訪問這一路數(shù)據(jù)，就不需要多路選擇器了，而且只需訪問數(shù)據(jù)部分指定的那個(gè)SRAM，其他的SRAM由于都不需要被訪問，可以將它們的使能信號置為無效，這樣可以節(jié)省很多功耗。

串行訪問Cache中的Tag和Data

完全串行Tag SRAM和Data SRAM這兩部分的訪問，它的延遲會更大，仍舊需要使用流水線來降低對處理器的周期時(shí)間的影響，用流水線降低了訪問Tag SRAM和Data RAM的延遲，因?yàn)榇藭r(shí)已經(jīng)不再需要多路選擇器，這對降低處理器的周期時(shí)間是有好處的，但是一個(gè)明顯的缺點(diǎn)就是Cache的訪問增加了一個(gè)周期，這也就增大了load指令的延遲，因?yàn)閘oad指令處于相關(guān)性的頂端，會對執(zhí)行效率造成影響。

并行訪問會有較低的時(shí)鐘頻率和較大功耗，但是訪問Cache的時(shí)間縮短一個(gè)周期。考慮到亂序執(zhí)行的超標(biāo)量處理器可以將訪問Cache的這段時(shí)間，通過填充其他的指令而掩蓋起來，所以對于超標(biāo)量處理器，當(dāng)Cache的訪問處于關(guān)鍵路徑時(shí)，可以采用串行訪問來提高CPU時(shí)鐘頻率，同時(shí)并不會由于訪問Cache的時(shí)間增加了一個(gè)周期而引起性能的明顯降低；相反，對于普通的順序執(zhí)行的處理器來說，由于無法對指令進(jìn)行調(diào)度，訪問Cache如果增加了一個(gè)周期，很可能會引起處理器性能的降低，因此這種處理器使用并行訪問比較合適。

1.3 全相連

在全相連cache中，對于一個(gè)存儲器地址來說，它的地址可以放在任意一個(gè)Cache line中。地址不再有Index部分，而是直接在整個(gè)Cache中進(jìn)行Tag比較，找到比較結(jié)果相等的那個(gè)Cache line，相當(dāng)于直接使用存儲器的內(nèi)容來尋址，從存儲器中找到匹配的項(xiàng)，這其實(shí)就是內(nèi)容尋址的存儲器（Content Address Memory，CAM）。實(shí)際處理器在使用全相連的Cache時(shí)，都是使用CAM來存儲Tag值，使用普通的SRAM來存儲數(shù)據(jù)。全相連的Cache有著最大的靈活度，延遲也是最大的，因此這種結(jié)構(gòu)的Cache不會有很大的容量，例如TLB就會使用這種全相連的方式來實(shí)現(xiàn)。

全相聯(lián)的cache

2. cache的替換策略

不管是讀取還是寫入Cache時(shí)發(fā)生了缺失，都需要從有效的Cache line中找到一個(gè)并替換，這就是替換(cache replacement)策略，本節(jié)介紹兩種最常用的替換算法。

2.1 近期最少使用法

近期最少使用法（Least Recently Used，LRU）會選擇最近被使用次數(shù)最少的Cahce line，因此這個(gè)算法需要跟蹤每個(gè)Cache line的使用情況，為每個(gè)Cache line都設(shè)置一個(gè)年齡（age）部分，每次當(dāng)一個(gè)Cache line被訪問時(shí)，它對應(yīng)的年齡就會增加，或者減少其他Cache line的年齡值。當(dāng)進(jìn)行替換時(shí)，選擇age值最小的進(jìn)行替換。但是隨著Cache相關(guān)度的增加（也就是way數(shù)的增加），要精確實(shí)現(xiàn)這種LRU方式就非常昂貴了。因此在way的個(gè)數(shù)很多的情況下，都是使用偽LRU的方法。

偽LRU算法的工作流程

2.2 隨機(jī)替換

在處理器中，Cache的替換算法一般都是使用硬件來實(shí)現(xiàn)，因此如果做得很復(fù)雜，會影響處理器的周期時(shí)間，于是就有了隨機(jī)替換（Random replacement）的方法。

隨機(jī)替換無需記錄每個(gè)way的年齡信息，而是隨機(jī)選擇一個(gè)way進(jìn)行替換。相比于LRU替換，隨機(jī)替換發(fā)生缺失的頻率會更高一些，但是隨著Cache容量的增大，這個(gè)差距會越來越小。

實(shí)際設(shè)計(jì)很難做到嚴(yán)格的隨機(jī)，一般采用時(shí)鐘算法的方法來實(shí)現(xiàn)近似隨機(jī)，其本質(zhì)上是一個(gè)計(jì)數(shù)器，計(jì)數(shù)器的寬度由Cache的相關(guān)度，也就是way的個(gè)數(shù)來決定，例如8way就需要三位，每次當(dāng)Cache中的某個(gè)line需要被替換時(shí)，就會訪問這個(gè)計(jì)數(shù)器，使用計(jì)數(shù)器當(dāng)前的值，從被選定的Cache set找出要替換的line，這樣就近似實(shí)現(xiàn)一種隨機(jī)替換。理論上其性能不是最優(yōu)，但是它的硬件復(fù)雜度比較低，也不會損失過多的性能。

3. VIVT、PIPT、VIPT分類

CPU發(fā)出的地址是虛擬地址，要經(jīng)過TLB或MMU轉(zhuǎn)換成物理地址，最終從這個(gè)物理地址讀寫數(shù)據(jù)。cache的設(shè)計(jì)可以采用虛擬地址、物理地址、或者取兩者地址部分組合來查找cache。

VIVT（Virtual Index Virtual Tag）：index和tag均使用虛擬地址；

PIPT（Physical Index Physical Tag）：index和tag均使用物理地址，一般用于L2 cache；

VIPT（Virtual Index Physical Tag）：index采用虛擬地址，tag采用物理地址，一般用于L1 cache（I-cache和D-cache）。

3.1 VIVT

使用虛擬地址尋址的cache稱為虛擬cache。VIVT使用虛擬地址來尋址cache，如果cache hit，直接從cache中獲得數(shù)據(jù)，不需要訪問TLB；如果cache miss，則把虛擬地址發(fā)往TLB，使用TLB將VA轉(zhuǎn)換成PA，然后使用PA去尋址 L2 Cache，從而得到缺失的數(shù)據(jù)（現(xiàn)代處理器中，L2及其下層的Cache都是物理Cache)。

虛擬cache的優(yōu)點(diǎn)是不需要每次操作都把虛擬地址經(jīng)過TLB轉(zhuǎn)換為物理地址，這可以提升訪問cache的速度，同時(shí)硬件設(shè)計(jì)也比較簡單。但是使用了虛擬地址作為tag，引入很多軟件使用上的問題，主要會面臨兩個(gè)問題：歧義(ambiguity)和別名(alias)。

3.2 PIPT

使用物理地址尋址的cache稱為物理cache。由于tag和index都取自物理地址，物理的地址tag部分是獨(dú)一無二的，而針對同一個(gè)物理地址，index也是唯一的，因此不存在歧義和別名的問題，這是PIPT最大的優(yōu)點(diǎn)。CPU發(fā)出的虛擬地址先經(jīng)過TLB轉(zhuǎn)換成物理地址，然后使用物理地址來尋址cache。

3.3 VIPT

這種方式使用了虛擬Cache，根據(jù)Cache的大小，直接使用虛擬地址的—部分來尋址這個(gè)Cache(這就是virtually-indexed)，而在Cache 中的Tag則使用物理地址中的PFN(這就是physically-tagged)，這種Cache是目前被使用最多的，現(xiàn)代處理器的L1 cache（I-cache和D-cache）基本都使用這種方式。

VIPT以物理地址作為tag，因此不存在歧義問題。但是采用虛擬地址作為index，所以可能存在別名問題。