十分鐘教你掌握 CPU 緩存

【CSDN 編者按】由於 CPU 是核心硬件，相信我們在選擇 CPU 的時候都會去關心 CPU 參數方面，而在 CPU 核心參數中，我們經常會看到緩存這個參數，那麼 CPU 緩存有什麼用呢？隨着本文去了解一下吧。

作者 | 神技圈子       責編 | 歐陽姝黎

出品 | CSDN 博客

基礎知識

首先，大家都知道現在 CPU 的多核技術，都會有幾級緩存，現在的 CPU 會有三級內存（L1，L2， L3），如下圖所示。

其中：

L1 緩存分成兩種，一種是指令緩存，一種是數據緩存。L2 緩存和 L3 緩存不分指令和數據。

再往後面就是內存，內存的後面就是硬盤。我們來看一些他們的速度。

我們可以看到，L1 的速度是 RAM 的 27 倍，L1 和 L2 的存取大小基本上是 KB 級的，L3 則是 MB 級別的。例如，Intel Core i7-8700K, 是一個 6 核的 CPU，每核上的 L1 是 64KB（數據和指令各 32KB）,L2 是 256K，L3 有 2MB。

我們的數據從內存向上，先到 L3，再到 L2，再到 L1，最後到寄存器進行計算。那麼，爲什麼會設計成三層？這裏有以下幾方面的考慮：

尤其是第二個問題，在多核技術下，這就很像分佈式系統了，要面對多個地方進行更新。

緩存命中

首先，我們需要了解一個術語 Cache Line。緩存基本上來說就是把後面的數據加載到離自己最近的地方，對於 CPU 來說，它是不會一個字節一個字節的加載的。因爲這非常沒有效率，一般來說都是要一塊一塊的加載的，對於這樣一塊一塊的數據單位，術語叫 “Cache Line”。一般來說，一個主流的 CPU 的 Cache Line 是 64 Bytes(也有的 CPU 用 32Bytes 和 128Bytes),64Bytes 也就是 16 個 32 位的數字, 這就是 CPU 從內存中撈數據上來的最小數據單位。比如：Cache Line 是最小單位（64Bytes），所以先把 Cache 分佈多 個 Cache Line。比如：L1 有 32KB，那麼 32KB/64B = 512 個 Cache Line。

緩存需要把內存裏的數據放進來，英文叫 CPU Associativity，Cache 的數據放置策略決定了內存中的數據會拷貝到 CPU Cache 中的哪個位置上，因爲 Cache 的大小遠遠小於內存，所以，需要有一種地址關聯算法，能夠讓內存中的數據被映射到 Cache 中。這個就有點像內存地址從邏輯地址到物理地址的映射方法。但是不完全一樣。

基本上會有以下的一些方法

對於 N-Way 組關聯，可能有點不好理解。這裏舉個例子，並多說一些細節（不然後面的代碼你會不能理解），Intel 大多數處理器的 L1 Cache 都是 32KB，8-Way 組相聯，Cache Line 是 64 Bytes。這意味着

爲了方便索引內存地址

索引過程如下圖所示：

這也意味着：

此外，當有數據沒有命中緩存的時候，CPU 就會以最小爲 Cache Line 的單元向內存更新數據。當然，CPU 並不一定只是更新 64Bytes，因爲訪問主存實在是太慢了，所以，一般都會多更新一些。好的 CPU 會有一些預測的技術，如果找到一種 pattern 的話，就會預先加載更多的內存，包括指令也可以預加載。這叫 Prefetching 技術。比如，你在 for-loop 訪問一個連續的數組，你的步長是一個固定的數，內存就可以做到 prefetching。

瞭解這些細節，會有利於我們知道在什麼情況下有可以導致緩存的失效。

緩存一致

對於主流的 CPU 來說，緩存的寫操作基本上是兩種策略

爲了提高寫的性能，一般來說，主流的 CPU（如：Intel Core i7/i9）採用的是 Write Back 的策略，因爲直接寫內存實在是太慢了。

好了，現在問題來了，如果有一個數據 x 在 CPU 第 0 核的緩存上被更新了，那麼其它 CPU 核上對於這個數據 x 的值也要被更新，這就是緩存一致性的問題。

一般來說，在 CPU 硬件上，會有兩種方法來解決這個問題。

  1. **Directory 協議。**這種方法的典型實現是要設計一個集中式控制器，它是主存儲器控制器的一部分。其中有一個目錄存儲在主存儲器中，其中包含有關各種本地緩存內容的全局狀態信息。當單個 CPU Cache 發出讀寫請求時，這個集中式控制器會檢查併發出必要的命令，以在主存和 CPU Cache 之間或在 CPU Cache 自身之間進行數據同步和傳輸。

  2. **Snoopy 協議。**這種協議更像是一種數據通知的總線型的技術。CPU Cache 通過這個協議可以識別其它 Cache 上的數據狀態。如果有數據共享的話，可以通過廣播機制將共享數據的狀態通知給其它 CPU Cache。這個協議要求每個 CPU Cache 都可以 “窺探” 數據事件的通知並做出相應的反應。如下圖所示，有一個 Snoopy Bus 的總線。

因爲 Directory 協議是一箇中心式的，會有性能瓶頸，而且會增加整體設計的複雜度。而 Snoopy 協議更像是微服務 + 消息通訊，所以，現在基本都是使用 Snoopy 的總線的設計。

在分佈式系統中我們一般用 Paxos/Raft 這樣的分佈式一致性的算法。而在 CPU 的微觀世界裏，則不必使用這樣的算法。因爲 CPU 的多個核的硬件不必考慮網絡會斷會延遲的問題。所以，CPU 的多核心緩存間的同步的核心就是要管理好數據的狀態就好了。

這裏介紹幾個狀態協議，先從最簡單的開始，MESI 協議，這個協議跟那個著名的足球運動員梅西沒什麼關係，其主要表示緩存數據有四個狀態：Modified（已修改）, Exclusive（獨佔的）,Shared（共享的），Invalid（無效的）。

MESI 這種協議在數據更新後，會標記其它共享的 CPU 緩存的數據拷貝爲 Invalid 狀態，然後當其它 CPU 再次 read 的時候，就會出現 cache miss 的問題，此時再從內存中更新數據。從內存中更新數據意味着 20 倍速度的降低。我們能不能直接從我隔壁的 CPU 緩存中更新？是的，這就可以增加很多速度了，但是狀態控制也就變麻煩了。還需要多來一個狀態：Owner(宿主)，用於標記，我是更新數據的源。於是，出現了 MOESI 協議。

**MOESI 協議允許 CPU Cache 間同步數據，於是也降低了對內存的操作，**性能是非常大的提升，但是控制邏輯也非常複雜。

順便說一下，與 MOESI 協議類似的一個協議是 MESIF，其中的 F 是 Forward，同樣是把更新過的數據轉發給別的 CPU Cache 但是，MOESI 中的 Owner 狀態 和 MESIF 中的 Forward 狀態有一個非常大的不一樣—— Owner 狀態下的數據是 dirty 的，還沒有寫回內存，Forward 狀態下的數據是 clean 的，可以丟棄而不用另行通知。

需要說明的是，AMD 用 MOESI，Intel 用 MESIF。所以，F 狀態主要是針對 CPU L3 Cache 設計的（前面我們說過，L3 是所有 CPU 核心共享的）。

程序性能

瞭解了我們上面的這些東西后，我們來看一下對於程序的影響。

示例一

首先，假設我們有一個 64M 長的數組，設想一下下面的兩個循環：

       const int LEN = 64*1024*1024;
       int *arr = new int[LEN];
          for (int i = 0; i < LEN; i += 2) arr[i] *= i;
          for (int i = 0; i < LEN; i += 8) arr[i] *= i;

按我們的想法，第二個循環要比第一個循環少 4 倍的計算量。其應該要快 4 倍的。但實際跑下來並不是，在我的機器上，第一個循環需要 128 毫秒，第二個循環則需要 122 毫秒，相差無幾。這裏最主要的原因就是 Cache Line，因爲 CPU 會以一個 Cache Line 64Bytes 最小時單位加載，也就是 16 個 32bits 的整型，所以，無論你步長是 2 還是 8，都差不多。而後面的乘法其實是不耗 CPU 時間的。

示例二

接下來，我們再來看個示例。下面是一個二維數組的兩種遍歷方式，一個逐行遍歷，一個是逐列遍歷，這兩種方式在理論上來說，尋址和計算量都是一樣的，執行時間應該也是一樣的。

const int row = 1024;
const int col = 512
int matrix[row][col];
//逐行遍歷
int sum_row=0;
for(int _r=0; _r<row; _r++) {
    for(int _c=0; _c<col; _c++){
        sum_row += matrix[_r][_c];
    }
}
//逐列遍歷
int sum_col=0;
for(int _c=0; _c<col; _c++) {
    for(int _r=0; _r<row; _r++){
        sum_col += matrix[_r][_c];
    }
}

然而，並不是，在我的機器上，得到下面的結果。

逐行遍歷：0.083ms

逐列遍歷：1.072ms

執行時間有十幾倍的差距。其中的原因，就是逐列遍歷對於 CPU Cache 的運作方式並不友好，所以，付出巨大的代價。

示例三

接下來，我們來看一下多核下的性能問題，參看如下的代碼。兩個線程在操作一個數組的兩個不同的元素（無需加鎖），線程循環 1000 萬次，做加法操作。在下面的代碼中，我高亮了一行，就是 p2 指針，要麼是 p[1]，或是 p[30]，理論上來說，無論訪問哪兩個數組元素，都應該是一樣的執行時間。

 void fn (int* data) {
    for(int i = 0; i < 10*1024*1024; ++i)
        *data += rand();
}
int p[32];
int *p1 = &p[0];
int *p2 = &p[1]; // int *p2 = &p[30];
thread t1(fn, p1);
thread t2(fn, p2);

然而，並不是，在我的機器上執行下來的結果是：

對於 p[0] 和 p[1] ：570ms

對於 p[0] 和 p[30]：105ms

這是因爲 p[0] 和 p[1] 在同一條 Cache Line 上，而 p[0] 和 p[30] 則不可能在同一條 Cache Line 上 ，CPU 的緩存最小的更新單位是 Cache Line，所以，這導致雖然兩個線程在寫不同的數據，但是因爲這兩個數據在同一條 Cache Line 上，就會導致緩存需要不斷進在兩個 CPU 的 L1/L2 中進行同步，從而導致了 5 倍的時間差異。

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

猜你喜歡