如何利用CPU Cache寫(xiě)出高性能代碼，看這些圖就夠了！

作者：程序喵大人 2020-09-23 09:21:56

存儲(chǔ) 存儲(chǔ)軟件

我們平時(shí)編寫(xiě)的代碼最后都會(huì)交給CPU來(lái)執(zhí)行，如何能巧妙利用CPU寫(xiě)出性能比較高的代碼呢?看完這篇文章您可能會(huì)有所收獲。

[[343372]]

本文轉(zhuǎn)載自微信公眾號(hào)「程序喵大人」，作者程序喵大人。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序喵大人公眾號(hào)。

先提出幾個(gè)問(wèn)題，之后我們逐個(gè)擊破：[[343373]]

初入寶地：什么是CPU Cache?
連類(lèi)比事：為什么要有Cache?為什么要有多級(jí)Cache?
挑燈細(xì)覽：Cache的大小和速度如何?
追本溯源：什么是Cache Line?
旁枝末葉：什么是Cache一致性?
觸類(lèi)旁通：Cache與主存的映射關(guān)系如何?
更上一層：如何巧妙利用CPU Cache編程?

1. 什么是CPU Cache?

如圖所示：

CPU Cache可以理解為CPU內(nèi)部的高速緩存，當(dāng)CPU從內(nèi)存中讀取數(shù)據(jù)時(shí)，并不是只讀自己想要的那一部分，而是讀取更多的字節(jié)到CPU高速緩存中。當(dāng)CPU繼續(xù)訪問(wèn)相鄰的數(shù)據(jù)時(shí)，就不必每次都從內(nèi)存中讀取，可以直接從高速緩存行讀取數(shù)據(jù)，而訪問(wèn)高速緩存比訪問(wèn)內(nèi)存速度要快的多，所以速度會(huì)得到極大提升。

2. 為什么要有Cache?為什么要有多級(jí)Cache?

為什么要有Cache這個(gè)問(wèn)題想必大家心里都已經(jīng)有了答案了吧，CPU直接訪問(wèn)距離較遠(yuǎn)，容量較大，性能較差的主存速度很慢，所以在CPU和內(nèi)存之間插入了Cache，CPU訪問(wèn)Cache的速度遠(yuǎn)高于訪問(wèn)主存的速度。

CPU Cache是位于CPU和內(nèi)存之間的臨時(shí)存儲(chǔ)器，它的容量比內(nèi)存小很多但速度極快，可以將內(nèi)存中的一小部分加載到Cache中，當(dāng)CPU需要訪問(wèn)這一小部分?jǐn)?shù)據(jù)時(shí)可以直接從Cache中讀取，加快了訪問(wèn)速度。

想必大家都聽(tīng)說(shuō)過(guò)程序局部性原理，這也是CPU引入Cache的理論基礎(chǔ)，程序局部性分為時(shí)間局部性和空間局部性。時(shí)間局部性是指被CPU訪問(wèn)的數(shù)據(jù)，短期內(nèi)還要被繼續(xù)訪問(wèn)，比如循環(huán)、遞歸、方法的反復(fù)調(diào)用等。空間局部性是指被CPU訪問(wèn)的數(shù)據(jù)相鄰的數(shù)據(jù)，CPU短期內(nèi)還要被繼續(xù)訪問(wèn)，比如順序執(zhí)行的代碼、連續(xù)創(chuàng)建的兩個(gè)對(duì)象、數(shù)組等。因?yàn)槿绻麑倓傇L問(wèn)的數(shù)據(jù)和相鄰的數(shù)據(jù)都緩存到Cache時(shí)，那下次CPU訪問(wèn)時(shí)，可以直接從Cache中讀取，提高CPU訪問(wèn)數(shù)據(jù)的速度。

一個(gè)存儲(chǔ)器層次大體結(jié)構(gòu)如圖所示，速度越快的存儲(chǔ)設(shè)備自然價(jià)格也就越高，隨著數(shù)據(jù)訪問(wèn)量的增大，單純的增加一級(jí)緩存的成本太高，性?xún)r(jià)比太低，所以才有了二級(jí)緩存和三級(jí)緩存，他們的容量越來(lái)越大，速度越來(lái)越慢(但還是比內(nèi)存的速度快)，成本越來(lái)越低。

3. Cache的大小和速度如何?

通常越接近CPU的緩存級(jí)別越低，容量越小，速度越快。不同的處理器Cache大小不同，通?，F(xiàn)在的處理器的L1 Cache大小都是64KB。

那CPU訪問(wèn)各個(gè)Cache的速度如何呢?

如圖所示，級(jí)別越低的高速緩存，CPU訪問(wèn)的速度越快。

CPU多級(jí)緩存架構(gòu)大體如下：

L1 Cache是最離CPU最近的，它容量最小，速度最快，每個(gè)CPU都有L1 Cache，見(jiàn)上圖，其實(shí)每個(gè)CPU都有兩個(gè)L1 Cache，一個(gè)是L1D Cache，用于存取數(shù)據(jù)，另一個(gè)是L1I Cache，用于存取指令。

L2 Cache容量較L1大，速度較L1較慢，每個(gè)CPU也都有一個(gè)L2 Cache。L2 Cache制造成本比L1 Cache更低，它的作用就是存儲(chǔ)那些CPU需要用到的且L1 Cache miss的數(shù)據(jù)。

L3 Cache容量較L2大，速度較L2慢，L3 Cache不同于L1 Cache和L2 Cache，它是所有CPU共享的，可以把它理解為速度更快，容量更小的內(nèi)存。

當(dāng)CPU需要數(shù)據(jù)時(shí)，整體流程如下：

會(huì)最先去CPU的L1 Cache中尋找相關(guān)的數(shù)據(jù)，找到了就返回，找不到就去L2 Cache，再找不到就去L3 Cache，再找不到就從內(nèi)存中讀取數(shù)據(jù)，尋找的距離越長(zhǎng)，自然速度也就越慢。

4. Cache Line?

Cache Line可以理解為CPU Cache中的最小緩存單位。Main Memory-Cache或Cache-Cache之間的數(shù)據(jù)傳輸不是以字節(jié)為最小單位，而是以Cache Line為最小單位，稱(chēng)為緩存行。目前主流的Cache Line大小都是64字節(jié)，假設(shè)有一個(gè)64K字節(jié)的Cache，那這個(gè)Cache所能存放的Cache Line的個(gè)數(shù)就是1K個(gè)。

5. 寫(xiě)入策略

Cache的寫(xiě)入策略有兩種，分別是WriteThrough(直寫(xiě)模式)和WriteBack(回寫(xiě)模式)。直寫(xiě)模式：在數(shù)據(jù)更新時(shí)，將數(shù)據(jù)同時(shí)寫(xiě)入內(nèi)存和Cache，該策略操作簡(jiǎn)單，但是因?yàn)槊看味家獙?xiě)入內(nèi)存，速度較慢?；貙?xiě)模式：在數(shù)據(jù)更新時(shí)，只將數(shù)據(jù)寫(xiě)入到Cache中，只有在數(shù)據(jù)被替換出Cache時(shí)，被修改的數(shù)據(jù)才會(huì)被寫(xiě)入到內(nèi)存中，該策略因?yàn)椴恍枰獙?xiě)入到內(nèi)存中，所以速度較快。但數(shù)據(jù)僅寫(xiě)在了Cache中，Cache數(shù)據(jù)和內(nèi)存數(shù)據(jù)不一致，此時(shí)如果有其它CPU訪問(wèn)數(shù)據(jù)，就會(huì)讀到臟數(shù)據(jù)，出現(xiàn)bug，所以這里需要用到Cache的一致性協(xié)議來(lái)保證CPU讀到的是最新的數(shù)據(jù)。

6. 什么是Cache一致性呢?

多個(gè)CPU對(duì)某塊內(nèi)存同時(shí)讀寫(xiě)，就會(huì)引起沖突的問(wèn)題，被稱(chēng)為Cache一致性問(wèn)題。

有這樣一種情況：

a. CPU1讀取了一個(gè)字節(jié)offset，該字節(jié)和相鄰的數(shù)據(jù)就都會(huì)被寫(xiě)入到CPU1的Cache.

b. 此時(shí)CPU2也讀取相同的字節(jié)offset，這樣CPU1和CPU2的Cache就都擁有同樣的數(shù)據(jù)。

c. CPU1修改了offset這個(gè)字節(jié)，被修改后，這個(gè)字節(jié)被寫(xiě)入到CPU1的Cache中，但是沒(méi)有被同步到內(nèi)存中。

d. CPU2 需要訪問(wèn)offset這個(gè)字節(jié)數(shù)據(jù)，但是由于最新的數(shù)據(jù)并沒(méi)有被同步到內(nèi)存中，所以CPU2 訪問(wèn)的數(shù)據(jù)不是最新的數(shù)據(jù)。

這種問(wèn)題就被稱(chēng)為Cache一致性問(wèn)題，為了解決這個(gè)問(wèn)題大佬們?cè)O(shè)計(jì)了MESI協(xié)議，當(dāng)一個(gè)CPU1修改了Cache中的某字節(jié)數(shù)據(jù)時(shí)，那么其它的所有CPU都會(huì)收到通知，它們的相應(yīng)Cache就會(huì)被置為無(wú)效狀態(tài)，當(dāng)其他的CPU需要訪問(wèn)此字節(jié)的數(shù)據(jù)時(shí)，發(fā)現(xiàn)自己的Cache相關(guān)數(shù)據(jù)已失效，這時(shí)CPU1會(huì)立刻把數(shù)據(jù)寫(xiě)到內(nèi)存中，其它的CPU就會(huì)立刻從內(nèi)存中讀取該數(shù)據(jù)。

MESI協(xié)議是通過(guò)四種狀態(tài)的控制來(lái)解決Cache一致性的問(wèn)題：

M：代表已修改(Modified) 緩存行是臟的(dirty)，與主存的值不同。如果別的CPU內(nèi)核要讀主存這塊數(shù)據(jù)，該緩存行必須回寫(xiě)到主存，狀態(tài)變?yōu)楣蚕?S).
E：代表獨(dú)占(Exclusive) 緩存行只在當(dāng)前緩存中，但是干凈的(clean)--緩存數(shù)據(jù)同于主存數(shù)據(jù)。當(dāng)別的緩存讀取它時(shí)，狀態(tài)變?yōu)楣蚕?S);當(dāng)前寫(xiě)數(shù)據(jù)時(shí)，變?yōu)橐研薷?M)狀態(tài)。
S：代表共享(Shared) 緩存行也存在于其它緩存中且是干凈(clean)的。緩存行可以在任意時(shí)刻拋棄。
I：代表已失效(Invalidated) 緩存行是臟的(dirty)，無(wú)效的。

四種狀態(tài)的相容關(guān)系如下：

這里我們只需要知道它是通過(guò)這四種狀態(tài)的切換解決的Cache一致性問(wèn)題就好，具體狀態(tài)機(jī)的控制實(shí)現(xiàn)太繁瑣，就不多介紹了，這是狀態(tài)機(jī)轉(zhuǎn)換圖，是不是有點(diǎn)懵。

7. Cache與主存的映射關(guān)系?

直接映射

直接映射如圖所示，每個(gè)主存塊只能映射Cache的一個(gè)特定塊。直接映射是最簡(jiǎn)單的地址映射方式，它的硬件簡(jiǎn)單，成本低，地址轉(zhuǎn)換速度快，但是這種方式不太靈活，Cache的存儲(chǔ)空間得不到充分利用，每個(gè)主存塊在Cache中只有一個(gè)固定位置可存放，容易產(chǎn)生沖突，使Cache效率下降，因此只適合大容量Cache采用。

例如，如果一個(gè)程序需要重復(fù)引用主存中第0塊與第16塊，最好將主存第0塊與第16塊同時(shí)復(fù)制到Cache中，但由于它們都只能復(fù)制到Cache的第0塊中去，即使Cache中別的存儲(chǔ)空間空著也不能占用，因此這兩個(gè)塊會(huì)不斷地交替裝入Cache中，導(dǎo)致命中率降低。

直接映射方式下主存地址格式如圖，主存地址為s+w位，Cache空間有2的r次方行，每行大小有2的w次方字節(jié)，則Cache地址有w+r位。通過(guò)Line確定該內(nèi)存塊應(yīng)該在Cache中的位置，確定位置后比較標(biāo)記是否相同，如果相同則表示Cache命中，從Cache中讀取。

全相連映射

全相連映射如圖所示，主存中任何一塊都可以映射到Cache中的任何一塊位置上。

全相聯(lián)映射方式比較靈活，主存的各塊可以映射到Cache的任一塊中，Cache的利用率高，塊沖突概率低，只要淘汰Cache中的某一塊，即可調(diào)入主存的任一塊。但是，由于Cache比較電路的設(shè)計(jì)和實(shí)現(xiàn)比較困難，這種方式只適合于小容量Cache采用。

全相連映射的主存結(jié)構(gòu)就很簡(jiǎn)單啦，將CPU發(fā)出的內(nèi)存地址的塊號(hào)部分與Cache所有行的標(biāo)記進(jìn)行比較，如果有相同的，則Cache命中，從Cache中讀取，如果找不到，則沒(méi)有命中，從主存中讀取。

組相連映射

組相聯(lián)映射實(shí)際上是直接映射和全相聯(lián)映射的折中方案，其組織結(jié)構(gòu)如圖3-16所示。主存和Cache都分組，主存中一個(gè)組內(nèi)的塊數(shù)與Cache中的分組數(shù)相同，組間采用直接映射，組內(nèi)采用全相聯(lián)映射。也就是說(shuō)，將Cache分成u組，每組v塊，主存塊存放到哪個(gè)組是固定的，至于存到該組哪一塊則是靈活的。例如，主存分為256組，每組8塊，Cache分為8組，每組2塊。

主存中的各塊與Cache的組號(hào)之間有固定的映射關(guān)系，但可自由映射到對(duì)應(yīng)Cache組中的任何一塊。例如，主存中的第0塊、第8塊……均映射于Cache的第0組，但可映射到Cache第0組中的第0塊或第1塊;主存的第1塊、第9塊……均映射于Cache的第1組，但可映射到Cache第1組中的第2塊或第3塊。

常采用的組相聯(lián)結(jié)構(gòu)Cache，每組內(nèi)有2、4、8、16塊，稱(chēng)為2路、4路、8路、16路組相聯(lián)Cache。組相聯(lián)結(jié)構(gòu)Cache是前兩種方法的折中方案，適度兼顧二者的優(yōu)點(diǎn)，盡量避免二者的缺點(diǎn)，因而得到普遍采用。

組相連映射方式下的主存地址格式如圖，先確定主存應(yīng)該在Cache中的哪一個(gè)組，之后組內(nèi)是全相聯(lián)映射，依次比較組內(nèi)的標(biāo)記，如果有標(biāo)記相同的Cache，則命中，否則不命中。

在網(wǎng)上找到了三種映射方式下的主存格式對(duì)比圖，大家也可以看下：

8. Cache的替換策略?

Cache的替換策略想必大家都知道，就是LRU策略，即最近最少使用算法，選擇未使用時(shí)間最長(zhǎng)的Cache替換。

9. 如何巧妙利用CPU Cache編程?

const int row = 1024; 
const int col = 1024; 
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]; 
    } 
}

上面是兩段二維數(shù)組的遍歷方式，一種按行遍歷，另一種是按列遍歷，乍一看您可能認(rèn)為計(jì)算量沒(méi)有任何區(qū)別，但其實(shí)按行遍歷比按列遍歷速度快的多，這就是CPU Cache起到了作用，根據(jù)程序局部性原理，訪問(wèn)主存時(shí)會(huì)把相鄰的部分?jǐn)?shù)據(jù)也加載到Cache中，下次訪問(wèn)相鄰數(shù)據(jù)時(shí)Cache的命中率極高，速度自然也會(huì)提升不少。

平時(shí)編程過(guò)程中也可以多利用好程序的時(shí)間局部性和空間局部性原理，就可以提高CPU Cache的命中率，提高程序運(yùn)行的效率。

參考鏈接

https://cseweb.ucsd.edu/classes/fa14/cse240A-a/pdf/08/CSE240A-MBT-L15-Cache.ppt.pdf

http://www.ecs.csun.edu/~cputnam/Comp546/Putnam/Cache%20Memory.pdf

https://ece752.ece.wisc.edu/lect11-cache-replacement.pdf

http://www.ipdps.org/ipdps2010/ipdps2010-slides/session-22/2010IPDPS.pdf

https://faculty.tarleton.edu/agapie/documents/cs_343_arch/04_CacheMemory.pdf

https://www.cnblogs.com/bjlhx/p/10658938.html

https://zh.wikipedia.org/wiki/MESI%E5%8D%8F%E8%AE%AE

https://www.cnblogs.com/yanlong300/p/8986041.html

https://coolshell.cn/articles/20793.html

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