大家好，今天給大家分享一篇關(guān)于 Cache 的硬核的技術(shù)文，基本上關(guān)于Cache的所有知識(shí)點(diǎn)都可以在這篇文章里看到。

關(guān)于 Cache 這方面內(nèi)容圖比較多，不想自己畫(huà)了，所以圖都來(lái)自《Computer Architecture : A Quantitative Approach》。

這是一本體系架構(gòu)方面的神書(shū)，推薦大家看一下。

本文主要內(nèi)容如下，基本涉及了Cache的概念，工作原理，以及保持一致性的入門(mén)內(nèi)容。

1、為什么需要 Cache

1.1 為什么需要 Cache

我們首先從一張圖來(lái)開(kāi)始講為什么需要 Cache.

上圖是 CPU 性能和 Memory 存儲(chǔ)器訪問(wèn)性能的發(fā)展。

我們可以看到，隨著工藝和設(shè)計(jì)的演進(jìn)，CPU 計(jì)算性能其實(shí)發(fā)生了翻天覆地的變化，但是DRAM存儲(chǔ)性能的發(fā)展沒(méi)有那么快。

所以造成了一個(gè)問(wèn)題，存儲(chǔ)限制了計(jì)算的發(fā)展。

容量與速度不可兼得。

如何解決這個(gè)問(wèn)題呢？可以從計(jì)算訪問(wèn)數(shù)據(jù)的規(guī)律入手。

我們隨便貼段代碼:

for(j=0;j100;j=j+1)
for(i=0;i5000;i=i+1)
x[i][j]=2*x[i][j];

可以看到，由于大量循環(huán)的存在，我們?cè)L問(wèn)的數(shù)據(jù)其實(shí)在內(nèi)存中的位置是相近的。

換句專業(yè)點(diǎn)的話說(shuō)，我們?cè)L問(wèn)的數(shù)據(jù)有局部性。

我們只需要將這些數(shù)據(jù)放入一個(gè)小而快的存儲(chǔ)中，這樣就可以快速訪問(wèn)相關(guān)數(shù)據(jù)了。

總結(jié)起來(lái)，Cache是為了給CPU提供高速存儲(chǔ)訪問(wèn)，利用數(shù)據(jù)局部性而設(shè)計(jì)的小存儲(chǔ)單元。

1.2 實(shí)際系統(tǒng)中的 Cache

我們展示一下實(shí)際系統(tǒng)中的 Cache 。

如上圖所示，整個(gè)系統(tǒng)的存儲(chǔ)架構(gòu)包括了 CPU 的寄存器，L1/L2/L3 CACHE，DRAM 和硬盤(pán)。

數(shù)據(jù)訪問(wèn)時(shí)先找寄存器，寄存器里沒(méi)有找 L1 Cache, L1 Cache 里沒(méi)有找 L2 Cache 依次類(lèi)推，最后找到硬盤(pán)中。

同時(shí)，我們可以看到，速度與存儲(chǔ)容量的折衷關(guān)系。容量越小，訪問(wèn)速度越快！

其中，一個(gè)概念需要搞清楚。

CPU 和 Cache 是 word 傳輸?shù)模?Cache 到主存是以塊傳輸?shù)模粔K大約 64Byte 。

現(xiàn)有 SOC 中的 Cache 一般組成如下。

1.3 Cache 的分類(lèi)

Cache按照不同標(biāo)準(zhǔn)分類(lèi)可以分為若干類(lèi)。

• 按照數(shù)據(jù)類(lèi)型劃分：I-Cache與D-Cache。其中I-Cache負(fù)責(zé)放置指令，D-Cache負(fù)責(zé)方式數(shù)據(jù)。兩者最大的不同是D-Cache里的數(shù)據(jù)可以寫(xiě)回，I-Cache是只讀的。

• 按照大小劃分：分為small Cache和large Cache。沒(méi)路組（后文組相連介紹）<4KB叫small Cache, 多用于L1 Cache, 大于4KB叫l(wèi)arge Cache。多用于L2及其他Cache.

• 按照位置劃分：Inner Cache和Outer Cache。一般獨(dú)屬于CPU微架構(gòu)的叫Inner Cache, 例如上圖的L1 L2 CACHE。不屬于CPU微架構(gòu)的叫outer Cache.

• 按照數(shù)據(jù)關(guān)系劃分：Inclusive/exclusive Cache: 下級(jí)Cache包含上級(jí)的數(shù)據(jù)叫inclusive Cache。不包含叫exclusive Cache。舉個(gè)例子，L3 Cache里有L2 Cache的數(shù)據(jù)，則L2 Cache叫exclusive Cache。

2、Cache的工作原理

要講清楚 Cache 的工作原理，需要回答 4 個(gè)問(wèn)題：

• 數(shù)據(jù)如何放置

• 數(shù)據(jù)如何查詢

• 數(shù)據(jù)如何被替換

• 如果發(fā)生了寫(xiě)操作，Cache如何處理

2.1 數(shù)據(jù)如何放置

這個(gè)問(wèn)題也好解決。我們舉個(gè)簡(jiǎn)單的栗子來(lái)說(shuō)明問(wèn)題。

假設(shè)我們主存中有 32 個(gè)塊，而我們的 Cache 一共有 8 個(gè) Cache 行( 一個(gè) Cache 行放一行數(shù)據(jù)）。

假設(shè)我們要把主存中的塊 12 放到 Cache 里。

那么應(yīng)該放到 Cache 里什么位置呢？

三種方法：

• 全相連（Fully associative）。可以放在Cache的任何位置。

• 直接映射（Direct mapped）。只允許放在Cache的某一行。比如12 mod 8

• 組相連（set associative）。可以放在Cache的某幾行。例如2路組相連，一共有4組，所以可以放在0,1位置中的一個(gè)。

可以看到，全相連和直接映射是Cache組相連的兩種極端情況。

不同的放置方式主要影響有兩點(diǎn)：

1、組相連組數(shù)越大，比較電路就越大，但Cache利用率更高，Cache miss發(fā)生的概率小。

2、組相連數(shù)目變小，Cache經(jīng)常發(fā)生替換，但是比較電路比較小。

這也好理解，內(nèi)存中的塊在Cache中可放置的位置多，自然找起來(lái)就麻煩。

2.2 如何在Cache中找數(shù)據(jù)

其實(shí)找數(shù)據(jù)就是一個(gè)比對(duì)過(guò)程，如下圖所示。

我們地址都以 Byte 為單位的。

但主存與Cache之間的數(shù)據(jù)交換單位都是塊（block，現(xiàn)代Cache一般一個(gè)block大約64Byte)。所以地址對(duì)最后幾位是block offset。

由于我們采用了組相連，則還有幾個(gè)比特代表的是存儲(chǔ)到了哪個(gè)組。

組內(nèi)放著若干數(shù)據(jù)，我們需要比較Tag, 如果組內(nèi)有Tag出現(xiàn)，則說(shuō)明我們?cè)L問(wèn)的數(shù)據(jù)在緩存中，可以開(kāi)心的使用了。

比如舉個(gè) 2 路組相連的例子，如下圖所示。

T表示Tag。直接比較Tag，就能得知是不是命中了。如果命中了，則根據(jù)index(組號(hào)）將對(duì)應(yīng)的塊取出來(lái)即可。

如上圖所示。用index選出位于組相連的哪個(gè)組。然后并行的比較Tag, 判斷最后是不是在Cache中。上圖是2路組相連，也就是說(shuō)兩組并行比較。

那如果不在緩存中呢？這就涉及到另一個(gè)問(wèn)題。

不在緩存中如何替換 Cache ？

2.3 如何替換Cache中的數(shù)據(jù)

Cache中的數(shù)據(jù)如何被替換的？這個(gè)就比較簡(jiǎn)單直接。

• 隨機(jī)替換。如果發(fā)生Cache miss里隨機(jī)替換掉一塊。

• Least recently used. LRU。最近使用的塊最后替換。

• First in, first out (FIFO), 先進(jìn)先出。

實(shí)際上第一個(gè)不怎么使用，LRU 和 FIFO 根據(jù)實(shí)際情況選擇即可。

Cache 在什么時(shí)候數(shù)據(jù)會(huì)被替換內(nèi)？也有幾種策略。

• 不在本 Cache 替換。如果Cache miss了，直接轉(zhuǎn)發(fā)訪問(wèn)地址到主存，取到的數(shù)據(jù)不會(huì)寫(xiě)到Cache.

• 在讀MISS時(shí)替換。如果讀的時(shí)候Cache里沒(méi)有該數(shù)據(jù)，則從主存讀取該數(shù)據(jù)后寫(xiě)入Cache。

• 在寫(xiě)MISS時(shí)替換。如果寫(xiě)的時(shí)候Cache里沒(méi)有該數(shù)據(jù)，則將本數(shù)據(jù)調(diào)入Cache再寫(xiě)。

2.4 如果發(fā)生了寫(xiě)操作怎么辦

Cache畢竟是個(gè)臨時(shí)緩存。

如果發(fā)生了寫(xiě)操作，會(huì)造成Cache和主存中的數(shù)據(jù)不一致。如何保證寫(xiě)數(shù)據(jù)操作正確呢？

也有三種策略。

• 通寫(xiě)：直接把數(shù)據(jù)寫(xiě)回Cache的同時(shí)寫(xiě)回主存。極其影響寫(xiě)速度。

• 回寫(xiě)：先把數(shù)據(jù)寫(xiě)回Cache, 然后當(dāng)Cache的數(shù)據(jù)被替換時(shí)再寫(xiě)回主存。

• 通寫(xiě)隊(duì)列：通寫(xiě)與回寫(xiě)的結(jié)合。先寫(xiě)回一個(gè)隊(duì)列，然后慢慢往主存儲(chǔ)寫(xiě)。如果多次寫(xiě)同一個(gè)數(shù)據(jù)，直接寫(xiě)這個(gè)隊(duì)列。避免頻繁寫(xiě)主存。

3、Cache一致性

Cache 一致性是 Cache 中遇到的比較坑的一個(gè)問(wèn)題。

什么原因需要 Cache 處理一致性呢？

主要是多核系統(tǒng)中，假如core 0讀了主存儲(chǔ)的數(shù)據(jù)，寫(xiě)了數(shù)據(jù)。core 1也讀了主存的數(shù)據(jù)。這個(gè)時(shí)候core 1并不知道數(shù)據(jù)已經(jīng)被改動(dòng)了，也就是說(shuō)，core 1 Cache中的數(shù)據(jù)過(guò)時(shí)了，會(huì)產(chǎn)生錯(cuò)誤。

Cache一致性的保證就是讓多核訪問(wèn)不出錯(cuò)。

Cache一致性主要有兩種策略。

策略一：基于監(jiān)聽(tīng)的一致性策略

這種策略是所有Cache均監(jiān)聽(tīng)各Cache的寫(xiě)操作，如果一個(gè)Cache中的數(shù)據(jù)被寫(xiě)了，有兩種處理辦法。

寫(xiě)更新協(xié)議：某個(gè)Cache發(fā)生寫(xiě)了，就索性把所有Cache都給更新了。

寫(xiě)失效協(xié)議：某個(gè)Cache發(fā)生寫(xiě)了，就把其他Cache中的該數(shù)據(jù)塊置為無(wú)效。

策略 1 由于監(jiān)聽(tīng)起來(lái)成本比較大，所以只應(yīng)用于極簡(jiǎn)單的系統(tǒng)中。

策略二：基于目錄的一致性策略

這種策略是在主存處維護(hù)一張表。記錄各數(shù)據(jù)塊都被寫(xiě)到了哪些Cache, 從而更新相應(yīng)的狀態(tài)。一般來(lái)講這種策略采用的比較多。又分為下面幾個(gè)常用的策略。

• SI: 對(duì)于一個(gè)數(shù)據(jù)塊來(lái)講，有share和invalid兩種狀態(tài)。如果是share狀態(tài)，直接通知其他Cache, 將對(duì)應(yīng)的塊置為無(wú)效。

• MSI：對(duì)于一個(gè)數(shù)據(jù)塊來(lái)講，有share和invalid，modified三種狀態(tài)。其中modified狀態(tài)表表示該數(shù)據(jù)只屬于這個(gè)Cache, 被修改過(guò)了。當(dāng)這個(gè)數(shù)據(jù)被逐出Cache時(shí)更新主存。這么做的好處是避免了大量的主從寫(xiě)入。同時(shí)，如果是invalid時(shí)寫(xiě)該數(shù)據(jù)，就要保證其他所有Cache里該數(shù)據(jù)的標(biāo)志位不為M，負(fù)責(zé)要先寫(xiě)回主存儲(chǔ)。

• MESI：對(duì)于一個(gè)數(shù)據(jù)來(lái)講，有4個(gè)狀態(tài)。modified, invalid, shared, exclusive。其中exclusive狀態(tài)用于標(biāo)識(shí)該數(shù)據(jù)與其他Cache不依賴。要寫(xiě)的時(shí)候直接將該Cache狀態(tài)改成M即可。

我們著重講講 MESI。圖中黑線：CPU的訪問(wèn)。紅線：總線的訪問(wèn)，其他Cache的訪問(wèn)。

當(dāng)前狀態(tài)時(shí)I狀態(tài)時(shí)，如果發(fā)生處理器讀操作 prrd。

• 如果其他Cache里有這份數(shù)據(jù)，如果其他Cache里是M態(tài)，先 把M態(tài)寫(xiě)回主存再讀。否則直接讀。最終狀態(tài)變?yōu)镾。

• 其他Cache里沒(méi)這個(gè)數(shù)據(jù)，直接變到E狀態(tài)。

當(dāng)前狀態(tài)為S態(tài)。

• 如果發(fā)生了處理器讀操作，仍然在S態(tài)。

• 如果發(fā)生了處理器寫(xiě)操作，則跳轉(zhuǎn)到M狀態(tài)。

• 如果其他Cache發(fā)生了寫(xiě)操作，跳到I態(tài)。

當(dāng)前狀態(tài)E態(tài)

• 發(fā)生了處理器讀操作還是E。

• 發(fā)生了處理器寫(xiě)操作變成M。

• 如果其他Cache發(fā)生了讀操作，變到S狀態(tài)。

當(dāng)前狀態(tài)M態(tài)

• 發(fā)生了讀操作依舊是M態(tài)。

• 發(fā)生了寫(xiě)操作依舊是M態(tài)。

• 如果其他Cache發(fā)生了讀操作，則將數(shù)據(jù)寫(xiě)回主存儲(chǔ)，變換到S態(tài)。

4、總結(jié)

Cache 在計(jì)算機(jī)體系架構(gòu)中有非常重要的地位，本文講了 Cache中最主要的內(nèi)容，具體細(xì)節(jié)可以再根據(jù)某個(gè)點(diǎn)深入研究。

審核編輯 ：李倩