深入理解 Cache 工作原理

大家好，今天給大家分享一篇關於 Cache 的硬核的技術文，基本上關於 Cache 的所有知識點都可以在這篇文章裏看到。

關於 Cache 這方面內容圖比較多，不想自己畫了，所以圖都來自《Computer Architecture : A Quantitative Approach》。

這是一本體系架構方面的神書，推薦大家看一下。

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

1、爲什麼需要 Cache

1.1 爲什麼需要 Cache

我們首先從一張圖來開始講爲什麼需要 Cache.

上圖是 CPU 性能和 Memory 存儲器訪問性能的發展。

我們可以看到，隨着工藝和設計的演進，CPU 計算性能其實發生了翻天覆地的變化，但是 DRAM 存儲性能的發展沒有那麼快。

所以造成了一個問題，存儲限制了計算的發展。

容量與速度不可兼得。

如何解決這個問題呢？可以從計算訪問數據的規律入手。

我們隨便貼段代碼:

for (j = 0; j < 100; j = j + 1)
    for( i = 0; i < 5000; i = i + 1)
        x[i][j] = 2 * x[i][j];

可以看到，由於大量循環的存在，我們訪問的數據其實在內存中的位置是相近的。

換句專業點的話說，我們訪問的數據有局部性。

我們只需要將這些數據放入一個小而快的存儲中，這樣就可以快速訪問相關數據了。

總結起來，Cache 是爲了給 CPU 提供高速存儲訪問，利用數據局部性而設計的小存儲單元。

1.2 實際系統中的 Cache

我們展示一下實際系統中的 Cache 。

如上圖所示，整個系統的存儲架構包括了 CPU 的寄存器，L1/L2/L3 CACHE，DRAM 和硬盤。

數據訪問時先找寄存器，寄存器裏沒有找 L1 Cache, L1 Cache 裏沒有找 L2 Cache 依次類推，最後找到硬盤中。

同時，我們可以看到，速度與存儲容量的折衷關係。容量越小，訪問速度越快！

其中，一個概念需要搞清楚。

CPU 和 Cache 是 word 傳輸的，而 Cache 到主存是以塊傳輸的，一塊大約 64Byte 。

現有 SOC 中的 Cache 一般組成如下。

1.3 Cache 的分類

Cache 按照不同標準分類可以分爲若干類。

• 按照數據類型劃分：I-Cache 與 D-Cache。其中 I-Cache 負責放置指令，D-Cache 負責方式數據。兩者最大的不同是 D-Cache 裏的數據可以寫回，I-Cache 是隻讀的。

• 按照大小劃分：分爲 small Cache 和 large Cache。沒路組（後文組相連介紹）<4KB 叫 small Cache, 多用於 L1 Cache, 大於 4KB 叫 large Cache。多用於 L2 及其他 Cache.

• 按照位置劃分：Inner Cache 和 Outer Cache。一般獨屬於 CPU 微架構的叫 Inner Cache, 例如上圖的 L1 L2 CACHE。不屬於 CPU 微架構的叫 outer Cache.

• 按照數據關係劃分：Inclusive/exclusive Cache: 下級 Cache 包含上級的數據叫 inclusive Cache。不包含叫 exclusive Cache。舉個例子，L3 Cache 裏有 L2 Cache 的數據，則 L2 Cache 叫 exclusive Cache。

2、Cache 的工作原理

要講清楚 Cache 的工作原理，需要回答 4 個問題：

• 數據如何放置

• 數據如何查詢

• 數據如何被替換

• 如果發生了寫操作，Cache 如何處理

2.1 數據如何放置

這個問題也好解決。我們舉個簡單的栗子來說明問題。

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

假設我們要把主存中的塊 12 放到 Cache 裏。

那麼應該放到 Cache 裏什麼位置呢？

三種方法：

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

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

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

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

不同的放置方式主要影響有兩點：

1、組相連組數越大，比較電路就越大，但 Cache 利用率更高，Cache miss 發生的概率小。2、組相連數目變小，Cache 經常發生替換，但是比較電路比較小。

這也好理解，內存中的塊在 Cache 中可放置的位置多，自然找起來就麻煩。

2.2 如何在 Cache 中找數據

其實找數據就是一個比對過程，如下圖所示。

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

但主存於 Cache 之間的數據交換單位都是塊（block，現代 Cache 一般一個 block 大約 64Byte)。所以地址對最後幾位是 block offset。

由於我們採用了組相連，則還有幾個比特代表的是存儲到了哪個組。

組內放着若干數據，我們需要比較 Tag, 如果組內有 Tag 出現，則說明我們訪問的數據在緩存中，可以開心的使用了。

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

T 表示 Tag。直接比較 Tag，就能得知是不是命中了。如果命中了，則根據 index(組號）將對應的塊取出來即可。

如上圖所示。用 index 選出位於組相連的哪個組。然後並行的比較 Tag, 判斷最後是不是在 Cache 中。上圖是 2 路組相連，也就是說兩組並行比較。

那如果不在緩存中呢？這就涉及到另一個問題。

不在緩存中如何替換 Cache ？

2.3 如何替換 Cache 中的數據

Cache 中的數據如何被替換的？這個就比較簡單直接。

• 隨機替換。如果發生 Cache miss 裏隨機替換掉一塊。

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

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

實際上第一個不怎麼使用，LRU 和 FIFO 根據實際情況選擇即可。

Cache 在什麼時候數據會被替換內？也有幾種策略。

• 不在本 Cache 替換。如果 Cache miss 了，直接轉發訪問地址到主存，取到的數據不會寫到 Cache.

• 在讀 MISS 時替換。如果讀的時候 Cache 裏沒有該數據，則從主存讀取該數據後寫入 Cache。

• 在寫 MISS 時替換。如果寫的時候 Cache 裏沒有該數據，則將本數據調入 Cache 再寫。

2.4 如果發生了寫操作怎麼辦

Cache 畢竟是個臨時緩存。

如果發生了寫操作，會造成 Cache 和主存中的數據不一致。如何保證寫數據操作正確呢？

也有三種策略。

• 通寫：直接把數據寫回 Cache 的同時寫回主存。極其影響寫速度。

• 回寫：先把數據寫回 Cache, 然後當 Cache 的數據被替換時再寫回主存。

• 通寫隊列：通寫與回寫的結合。先寫回一個隊列，然後慢慢往主存儲寫。如果多次寫同一個數據，直接寫這個隊列。避免頻繁寫主存。

3、Cache 一致性

Cache 一致性是 Cache 中遇到的比較坑的一個問題。

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

主要是多核系統中，假如 core 0 讀了主存儲的數據，寫了數據。core 1 也讀了主從的數據。這個時候 core 1 並不知道數據已經被改動了，也就是說，core 1 Cache 中的數據過時了，會產生錯誤。

Cache 一致性的保證就是讓多核訪問不出錯。

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

策略一：基於監聽的一致性策略

這種策略是所有 Cache 均監聽各 Cache 的寫操作，如果一個 Cache 中的數據被寫了，有兩種處理辦法。

**寫更新協議：**某個 Cache 發生寫了，就索性把所有 Cache 都給更新了。

**寫失效協議：**某個 Cache 發生寫了，就把其他 Cache 中的該數據塊置爲無效。

策略 1 由於監聽起來成本比較大，所以只應用於極簡單的系統中。

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

這種策略是在主存處維護一張表。記錄各數據塊都被寫到了哪些 Cache, 從而更新相應的狀態。一般來講這種策略採用的比較多。又分爲下面幾個常用的策略。

• SI: 對於一個數據塊來講，有 share 和 invalid 兩種狀態。如果是 share 狀態，直接通知其他 Cache, 將對應的塊置爲無效。

• MSI：對於一個數據塊來講，有 share 和 invalid，modified 三種狀態。其中 modified 狀態表表示該數據只屬於這個 Cache, 被修改過了。當這個數據被逐出 Cache 時更新主存。這麼做的好處是避免了大量的主從寫入。同時，如果是 invalid 時寫該數據，就要保證其他所有 Cache 裏該數據的標誌位不爲 M，負責要先寫回主存儲。

• MESI：對於一個數據來講，有 4 個狀態。modified, invalid, shared, exclusive。其中 exclusive 狀態用於標識該數據與其他 Cache 不依賴。要寫的時候直接將該 Cache 狀態改成 M 即可。

我們着重講講 MESI。圖中黑線：CPU 的訪問。紅線：總線的訪問，其他 Cache 的訪問。

當前狀態時 I 狀態時，如果發生處理器讀操作 prrd。

• 如果其他 Cache 裏有這份數據，如果其他 Cache 裏是 M 態，先 把 M 態寫回主存再讀。否則直接讀。最終狀態變爲 S。

• 其他 Cache 裏沒這個數據，直接變到 E 狀態。

當前狀態爲 S 態。

• 如果發生了處理器讀操作，仍然在 S 態。

• 如果發生了處理器寫操作，則跳轉到 M 狀態。

• 如果其他 Cache 發生了寫操作，跳到 I 態。

當前狀態 E 態

• 發生了處理器讀操作還是 E。

• 發生了處理器寫操作變成 M。

• 如果其他 Cache 發生了讀操作，變到 S 狀態。

當前狀態 M 態

• 發生了讀操作依舊是 M 態。

• 發生了寫操作依舊是 M 態。

• 如果其他 Cache 發生了讀操作，則將數據寫回主存儲，變換到 S 態。

4、總結

Cache 在計算機體系架構中有非常重要的地位，本文講了 Cache 中最主要的內容，具體細節可以再根據某個點深入研究。

作者：桔裏貓

https://zhuanlan.zhihu.com/p/386919471

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Icj4qqN93c2mrd2yVHEXOA