本文轉(zhuǎn)自“芯片驗(yàn)證日記”

本篇文章主要聚焦CPU Cache，文章比較長(zhǎng)，主要分成這么幾個(gè)部分：

緩沖基礎(chǔ)知識(shí)

緩存的命中

緩沖的一致性

延伸閱讀

文中會(huì)講述一些多核 CPU 的系統(tǒng)架構(gòu)以及其原理。這篇文章我會(huì)盡量地寫簡(jiǎn)單和通俗易懂一些，主要是講清楚相關(guān)的原理和問題，而對(duì)于一些細(xì)節(jié)和延伸閱讀我會(huì)在文章最后會(huì)給出相關(guān)的資源

因?yàn)闊o論你寫什么樣的代碼都會(huì)交給CPU來執(zhí)行，所以，如果你想寫出性能比較高的代碼，這篇文章中提到的技術(shù)還是值得認(rèn)真學(xué)習(xí)的。另外，千萬別覺得這些東西沒用，這些東西非常有用，十多年前就是這些知識(shí)在性能調(diào)優(yōu)上幫了我的很多大忙，從而跟很多人拉開了差距……

1緩存基礎(chǔ)知識(shí)

首先，我們都知道現(xiàn)在的CPU多核技術(shù)，都會(huì)有幾級(jí)緩存，老的CPU會(huì)有兩級(jí)緩存（L1和L2），新的CPU會(huì)有三級(jí)緩存（L1，L2，L3 ），如下圖所示：

其中：

L1緩存分成兩種，一種是指令緩存，一種是數(shù)據(jù)緩存。L2緩存和L3緩存不分指令和數(shù)據(jù)。

L1緩存和L2緩存在每一個(gè)CPU核中，L3則是所有CPU核心共享的緩存。

L1、L2、L3緩存離CPU越近就越小，速度也越快，離CPU越遠(yuǎn)，速度就越慢。

再往后面就是內(nèi)存，內(nèi)存的后面就是硬盤。我們來看一些他們的速度：

L1 的存取速度：4 個(gè)CPU時(shí)鐘周期

L2 的存取速度：11 個(gè)CPU時(shí)鐘周期

L3 的存取速度：39 個(gè)CPU時(shí)鐘周期

RAM內(nèi)存的存取速度：107 個(gè)CPU時(shí)鐘周期

我們可以看到，L1的速度是RAM的27倍，但是L1/L2的大小基本上也就是KB級(jí)別的，L3會(huì)是MB級(jí)別的。例如：Intel Core i7-8700K ，是一個(gè)6核的CPU，每核上的L1是64KB（數(shù)據(jù)和指令各32KB），L2 是 256K，L3有2MB（我的蘋果電腦是 Intel Core i9-8950HK，和Core i7-8700K的Cache大小一樣）。

我們的數(shù)據(jù)就從內(nèi)存向上，先到L3，再到L2，再到L1，最后到寄存器進(jìn)行CPU計(jì)算。為什么會(huì)設(shè)計(jì)成三層？這里有下面幾個(gè)方面的考慮：

一個(gè)方面是物理速度，如果要更大的容量就需要更多的晶體管，除了芯片的體積會(huì)變大，更重要的是大量的晶體管會(huì)導(dǎo)致速度下降，因?yàn)樵L問速度和要訪問的晶體管所在的位置成反比，也就是當(dāng)信號(hào)路徑變長(zhǎng)時(shí)，通信速度會(huì)變慢。這部分是物理問題。

另外一個(gè)問題是，多核技術(shù)中，數(shù)據(jù)的狀態(tài)需要在多個(gè)CPU中進(jìn)行同步，并且，我們可以看到，cache和RAM的速度差距太大，所以，多級(jí)不同尺寸的緩存有利于提高整體的性能。

這個(gè)世界永遠(yuǎn)是平衡的，一面變得有多光鮮，另一面也會(huì)變得有多黑暗。建立這么多級(jí)的緩存，一定就會(huì)引入其它的問題，這里有兩個(gè)比較重要的問題，

一個(gè)是比較簡(jiǎn)單的緩存的命中率的問題。

另一個(gè)是比較復(fù)雜的緩存更新的一致性問題。

尤其是第二個(gè)問題，在多核技術(shù)下，這就很像分布式的系統(tǒng)了，要對(duì)多個(gè)地方進(jìn)行更新。

2緩存的命中

在說明這兩個(gè)問題之前。我們需要了解一個(gè)術(shù)語 Cache Line。緩存基本上來說就是把后面的數(shù)據(jù)加載到離自己近的地方，對(duì)于CPU來說，它是不會(huì)一個(gè)字節(jié)一個(gè)字節(jié)的加載的，因?yàn)檫@非常沒有效率，一般來說都是要一塊一塊的加載的，對(duì)于這樣的一塊一塊的數(shù)據(jù)單位，術(shù)語叫“Cache Line”，一般來說，一個(gè)主流的CPU的Cache Line 是 64 Bytes（也有的CPU用32Bytes和128Bytes），64Bytes也就是16個(gè)32位的整型，這就是CPU從內(nèi)存中撈數(shù)據(jù)上來的最小數(shù)據(jù)單位。

比如：Cache Line是最小單位（64Bytes），所以先把Cache分布多個(gè)Cache Line，比如：L1有32KB，那么，32KB/64B = 512 個(gè) Cache Line。

一方面，緩存需要把內(nèi)存里的數(shù)據(jù)放進(jìn)來，英文叫 Cache Associativity。Cache的數(shù)據(jù)放置策略決定了內(nèi)存中的數(shù)據(jù)塊會(huì)拷貝到CPU Cache中的哪個(gè)位置上，因?yàn)镃ache的大小遠(yuǎn)遠(yuǎn)小于內(nèi)存，所以，需要有一種地址關(guān)聯(lián)的算法，能夠讓內(nèi)存中的數(shù)據(jù)可以被映射到Cache中來。這個(gè)有點(diǎn)像內(nèi)存地址從邏輯地址向物理地址映射的方法，但不完全一樣。

基本上來說，我們會(huì)有如下的一些方法。

一種方法是，任何一個(gè)內(nèi)存地址的數(shù)據(jù)可以被緩存在任何一個(gè)Cache Line里，這種方法是最靈活的，但是，如果我們要知道一個(gè)內(nèi)存是否存在于Cache中，我們就需要進(jìn)行O(n)復(fù)雜度的Cache遍歷，這是很沒有效率的。

另一種方法，為了降低緩存搜索算法，我們需要使用像Hash Table這樣的數(shù)據(jù)結(jié)構(gòu)，最簡(jiǎn)單的hash table就是做“求模運(yùn)算”，比如：我們的L1 Cache有512個(gè)Cache Line，那么，公式（內(nèi)存地址 mod 512）* 64就可以直接找到所在的Cache地址的偏移了。但是，這樣的方式需要我們的程序?qū)?nèi)存地址的訪問要非常地平均，不然沖突就會(huì)非常嚴(yán)重。這成了一種非常理想的情況了。

為了避免上述的兩種方案的問題，于是就要容忍一定的hash沖突，也就出現(xiàn)了 N-Way 關(guān)聯(lián)。也就是把連續(xù)的N個(gè)Cache Line綁成一組，然后，先找到相關(guān)的組，然后再在這個(gè)組內(nèi)找到相關(guān)的Cache Line。這叫 Set Associativity。如下圖所示。

對(duì)于 N-Way 組關(guān)聯(lián)，可能有點(diǎn)不好理解，這里個(gè)例子，并多說一些細(xì)節(jié)（不然后面的代碼你會(huì)不能理解），Intel 大多數(shù)處理器的L1 Cache都是32KB，8-Way 組相聯(lián)，Cache Line 是64 Bytes。這意味著，

32KB的可以分成，32KB / 64 = 512 條 Cache Line。

因?yàn)橛? Way，于是會(huì)每一Way 有 512 / 8 = 64 條 Cache Line。

于是每一路就有 64 x 64 = 4096 Byts 的內(nèi)存。

為了方便索引內(nèi)存地址，

Tag：每條 Cache Line 前都會(huì)有一個(gè)獨(dú)立分配的 24 bits來存的 tag，其就是內(nèi)存地址的前24bits

Index：內(nèi)存地址后續(xù)的6個(gè)bits則是在這一Way的是Cache Line 索引，2^6 = 64 剛好可以索引64條Cache Line

Offset：再往后的6bits用于表示在Cache Line 里的偏移量

如下圖所示：（圖片來自《Cache: a place for concealment and safekeeping》）

當(dāng)拿到一個(gè)內(nèi)存地址的時(shí)候，先拿出中間的 6bits 來，找到是哪組。

然后，在這一個(gè)8組的cache line中，再進(jìn)行O(n) n=8 的遍歷，主要是要匹配前24bits的tag。如果匹配中了，就算命中，如果沒有匹配到，那就是cache miss，如果是讀操作，就需要進(jìn)向后面的緩存進(jìn)行訪問了。L2/L3同樣是這樣的算法。而淘汰算法有兩種，一種是隨機(jī)一種是LRU?，F(xiàn)在一般都是以LRU的算法（通過增加一個(gè)訪問計(jì)數(shù)器來實(shí)現(xiàn)）

這也意味著：

L1 Cache 可映射 36bits 的內(nèi)存地址，一共 2^36 = 64GB的內(nèi)存

當(dāng)CPU要訪問一個(gè)內(nèi)存的時(shí)候，通過這個(gè)內(nèi)存中間的6bits 定位是哪個(gè)set，通過前 24bits 定位相應(yīng)的Cache Line。

就像一個(gè)hash Table的數(shù)據(jù)結(jié)構(gòu)一樣，先是O(1)的索引，然后進(jìn)入沖突搜索。

因?yàn)橹虚g的 6bits 決定了一個(gè)同一個(gè)set，所以，對(duì)于一段連續(xù)的內(nèi)存來說，每隔4096的內(nèi)存會(huì)被放在同一個(gè)組內(nèi)，導(dǎo)致緩存沖突。

此外，當(dāng)有數(shù)據(jù)沒有命中緩存的時(shí)候，CPU就會(huì)以最小為Cache Line的單元向內(nèi)存更新數(shù)據(jù)。當(dāng)然，CPU并不一定只是更新64Bytes，因?yàn)樵L問主存實(shí)在是太慢了，所以，一般都會(huì)多更新一些。好的CPU會(huì)有一些預(yù)測(cè)的技術(shù)，如果找到一種pattern的話，就會(huì)預(yù)先加載更多的內(nèi)存，包括指令也可以預(yù)加載。這叫 Prefetching 技術(shù) （參看，Wikipedia 的 Cache Prefetching 和紐約州立大學(xué)的 Memory Prefetching）。比如，你在for-loop訪問一個(gè)連續(xù)的數(shù)組，你的步長(zhǎng)是一個(gè)固定的數(shù)，內(nèi)存就可以做到prefetching。（注：指令也是以預(yù)加載的方式執(zhí)行，參看本站的《代碼執(zhí)行的效率》中的第三個(gè)示例）

了解這些細(xì)節(jié)，會(huì)有利于我們知道在什么情況下有可能導(dǎo)致緩存的失效。

3緩存的一致性

對(duì)于主流的CPU來說，緩存的寫操作基本上是兩種策略（參看本站《緩存更新的套路》），

一種是Write Back，寫操作只寫在cache上，然后再flush到內(nèi)存上。

一種是Write Through，寫操作同時(shí)寫到cache和內(nèi)存上。

為了提高寫操作的性能，一般來說，主流的CPU（如：Intel Core i7/i9）采用的是Write Back的策略，因?yàn)橹苯訉憙?nèi)存實(shí)在是太慢了。

好了，現(xiàn)在問題來了，如果有一個(gè)數(shù)據(jù) x 在 CPU 第0核的緩存上被更新了，那么其它CPU核上對(duì)于這個(gè)數(shù)據(jù) x 的值也要被更新，這就是緩存一致性的問題。（當(dāng)然，對(duì)于我們上層的程序我們不用關(guān)心CPU多個(gè)核的緩存是怎么同步的，這對(duì)上層的代碼來說都是透明的）

一般來說，在CPU硬件上，會(huì)有兩種方法來解決這個(gè)問題。

Directory 協(xié)議。這種方法的典型實(shí)現(xiàn)是要設(shè)計(jì)一個(gè)集中式控制器，它是主存儲(chǔ)器控制器的一部分。其中有一個(gè)目錄存儲(chǔ)在主存儲(chǔ)器中，其中包含有關(guān)各種本地緩存內(nèi)容的全局狀態(tài)信息。當(dāng)單個(gè)CPU Cache 發(fā)出讀寫請(qǐng)求時(shí)，這個(gè)集中式控制器會(huì)檢查并發(fā)出必要的命令，以在主存和CPU Cache之間或在CPU Cache自身之間進(jìn)行數(shù)據(jù)同步和傳輸。

Snoopy 協(xié)議。這種協(xié)議更像是一種數(shù)據(jù)通知的總線型的技術(shù)。CPU Cache通過這個(gè)協(xié)議可以識(shí)別其它Cache上的數(shù)據(jù)狀態(tài)。如果有數(shù)據(jù)共享的話，可以通過廣播機(jī)制將共享數(shù)據(jù)的狀態(tài)通知給其它CPU Cache。這個(gè)協(xié)議要求每個(gè)CPU Cache 都可以“窺探”數(shù)據(jù)事件的通知并做出相應(yīng)的反應(yīng)。如下圖所示，有一個(gè)Snoopy Bus的總線。

因?yàn)镈irectory協(xié)議是一個(gè)中心式的，會(huì)有性能瓶頸，而且會(huì)增加整體設(shè)計(jì)的復(fù)雜度。而Snoopy協(xié)議更像是微服務(wù)+消息通訊，所以，現(xiàn)在基本都是使用Snoopy的總線的設(shè)計(jì)。

這里，我想多寫一些細(xì)節(jié)，因?yàn)檫@種微觀的東西，讓人不自然地就會(huì)跟分布式系統(tǒng)關(guān)聯(lián)起來，在分布式系統(tǒng)中我們一般用Paxos/Raft這樣的分布式一致性的算法。而在CPU的微觀世界里，則不必使用這樣的算法，原因是因?yàn)镃PU的多個(gè)核的硬件不必考慮網(wǎng)絡(luò)會(huì)斷、會(huì)延遲的問題。所以，CPU的多核心緩存間的同步的核心就是要管理好數(shù)據(jù)的狀態(tài)就好了。

這里介紹幾個(gè)狀態(tài)協(xié)議，先從最簡(jiǎn)單的開始，MESI協(xié)議，這個(gè)協(xié)議跟那個(gè)著名的足球運(yùn)動(dòng)員梅西沒什么關(guān)系，其主要表示緩存數(shù)據(jù)有四個(gè)狀態(tài)：Modified（已修改）, Exclusive（獨(dú)占的）,Shared（共享的），Invalid（無效的）。

這些狀態(tài)的狀態(tài)機(jī)如下所示（有點(diǎn)復(fù)雜，你可以先不看，這個(gè)圖就是想告訴你狀態(tài)控制有多復(fù)雜）：

下面是個(gè)示例（如果你想看一下動(dòng)畫演示的話，這里有一個(gè)網(wǎng)頁（MESI Interactive Animations），你可以進(jìn)行交互操作，這個(gè)動(dòng)畫演示中使用的Write Through算法）：

MESI 這種協(xié)議在數(shù)據(jù)更新后，會(huì)標(biāo)記其它共享的CPU緩存的數(shù)據(jù)拷貝為Invalid狀態(tài)，然后當(dāng)其它CPU再次read的時(shí)候，就會(huì)出現(xiàn) cache miss 的問題，此時(shí)再?gòu)膬?nèi)存中更新數(shù)據(jù)。從內(nèi)存中更新數(shù)據(jù)意味著20倍速度的降低。我們能不能直接從我隔壁的CPU緩存中更新？是的，這就可以增加很多速度了，但是狀態(tài)控制也就變麻煩了。還需要多來一個(gè)狀態(tài)：Owner(宿主)，用于標(biāo)記，我是更新數(shù)據(jù)的源。于是，出現(xiàn)了 MOESI 協(xié)議

MOESI協(xié)議的狀態(tài)機(jī)和演示示例我就不貼了（有興趣可以上Berkeley上看看相關(guān)的課件），我們只需要理解MOESI協(xié)議允許 CPU Cache 間同步數(shù)據(jù)，于是也降低了對(duì)內(nèi)存的操作，性能是非常大的提升，但是控制邏輯也非常復(fù)雜。

順便說一下，與 MOESI 協(xié)議類似的一個(gè)協(xié)議是MESIF，其中的 F 是 Forward，同樣是把更新過的數(shù)據(jù)轉(zhuǎn)發(fā)給別的 CPU Cache 但是，MOESI 中的 Owner 狀態(tài) 和MESIF 中的 Forward 狀態(tài)有一個(gè)非常大的不一樣——Owner狀態(tài)下的數(shù)據(jù)是dirty的，還沒有寫回內(nèi)存，F(xiàn)orward狀態(tài)下的數(shù)據(jù)是clean的，可以丟棄而不用另行通知。

需要說明的是，AMD用MOESI，Intel用MESIF。所以，F(xiàn) 狀態(tài)主要是針對(duì) CPU L3 Cache 設(shè)計(jì)的（前面我們說過，L3是所有CPU核心共享的）。（相關(guān)的比較可以參看StackOverlow上這個(gè)問題的答案）