如何利用CPU Cache寫出高性能代碼？看這些圖就夠了！

時間：2020-09-28 11:48:29

關(guān)鍵字：代碼 C語言

手機(jī)看文章

掃描二維碼
隨時隨地手機(jī)看文章

[導(dǎo)讀]我們平時編寫的代碼最后都會交給CPU來執(zhí)行，如何能巧妙利用CPU寫出性能比較高的代碼呢？看完這篇文章您可能會有所收獲。

	世界就像個巨大的馬戲團(tuán)，它讓你興奮，卻讓我惶恐，因?yàn)槲抑郎鲇肋h(yuǎn)是——有限溫存，無限辛酸。 ——卓別林

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

先提出幾個問題，之后我們逐個擊破：

初入寶地：什么是CPU Cache？

連類比事：為什么要有Cache？為什么要有多級Cache？

挑燈細(xì)覽：Cache的大小和速度如何？

追本溯源：什么是Cache Line？

旁枝末葉：什么是Cache一致性？

觸類旁通：Cache與主存的映射關(guān)系如何？

更上一層：如何巧妙利用CPU Cache編程？

1. 什么是CPU Cache？

如圖所示：

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

2. 為什么要有Cache？為什么要有多級Cache？

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

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

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

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

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

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

那CPU訪問各個Cache的速度如何呢？

如圖所示，級別越低的高速緩存，CPU訪問的速度越快。

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

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

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

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

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

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

4. Cache Line？

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

5. 寫入策略

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

6. 什么是Cache一致性呢？

多個CPU對某塊內(nèi)存同時讀寫，就會引起沖突的問題，被稱為Cache一致性問題。

有這樣一種情況：

a. CPU1讀取了一個字節(jié)offset，該字節(jié)和相鄰的數(shù)據(jù)就都會被寫入到CPU1的Cache. b. 此時CPU2也讀取相同的字節(jié)offset，這樣CPU1和CPU2的Cache就都擁有同樣的數(shù)據(jù)。 c. CPU1修改了offset這個字節(jié)，被修改后，這個字節(jié)被寫入到CPU1的Cache中，但是沒有被同步到內(nèi)存中。 d. CPU2 需要訪問offset這個字節(jié)數(shù)據(jù)，但是由于最新的數(shù)據(jù)并沒有被同步到內(nèi)存中，所以CPU2 訪問的數(shù)據(jù)不是最新的數(shù)據(jù)。

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

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

■ M：代表已修改（Modified）緩存行是臟的（dirty），與主存的值不同。如果別的CPU內(nèi)核要讀主存這塊數(shù)據(jù)，該緩存行必須回寫到主存，狀態(tài)變?yōu)楣蚕恚?/span>S）.

■ E：代表獨(dú)占（Exclusive）緩存行只在當(dāng)前緩存中，但是干凈的（clean）--緩存數(shù)據(jù)同于主存數(shù)據(jù)。當(dāng)別的緩存讀取它時，狀態(tài)變?yōu)楣蚕恚?/span>S）；當(dāng)前寫數(shù)據(jù)時，變?yōu)橐研薷模?/span>M）狀態(tài)。

■ S：代表共享（Shared）緩存行也存在于其它緩存中且是干凈（clean）的。緩存行可以在任意時刻拋棄。

■ I：代表已失效（Invalidated）緩存行是臟的（dirty），無效的。

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

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

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

直接映射

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

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

直接映射方式下主存地址格式如圖，主存地址為s+w位，Cache空間有2的r次方行，每行大小有2的w次方字節(jié)，則Cache地址有w+r位。通過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)就很簡單啦，將CPU發(fā)出的內(nèi)存地址的塊號部分與Cache所有行的標(biāo)記進(jìn)行比較，如果有相同的，則Cache命中，從Cache中讀取，如果找不到，則沒有命中，從主存中讀取。

組相連映射

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

主存中的各塊與Cache的組號之間有固定的映射關(guān)系，但可自由映射到對應(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塊，稱為2路、4路、8路、16路組相聯(lián)Cache。組相聯(lián)結(jié)構(gòu)Cache是前兩種方法的折中方案，適度兼顧二者的優(yōu)點(diǎn)，盡量避免二者的缺點(diǎn)，因而得到普遍采用。

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

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

8. Cache的替換策略？

Cache的替換策略想必大家都知道，就是LRU策略，即最近最少使用算法，選擇未使用時間最長的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ì)算量沒有任何區(qū)別，但其實(shí)按行遍歷比按列遍歷速度快的多，這就是CPU Cache起到了作用，根據(jù)程序局部性原理，訪問主存時會把相鄰的部分?jǐn)?shù)據(jù)也加載到Cache中，下次訪問相鄰數(shù)據(jù)時Cache的命中率極高，速度自然也會提升不少。

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

參考鏈接