[[343372]]

本文轉載自微信公眾號「程序喵大人」，作者程序喵大人 。轉載本文請聯(lián)系程序喵大人公眾號。

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

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

 

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

1. 什么是CPU Cache?

如圖所示：

 

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

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

 

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

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

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

 

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

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

 

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

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

 

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

CPU多級緩存架構大體如下：

 

L1 Cache是最離CPU最近的，它容量最小，速度最快，每個CPU都有L1 Cache，見上圖，其實每個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共享的，可以把它理解為速度更快，容量更小的內存。

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

 

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

4. Cache Line?

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

5. 寫入策略

Cache的寫入策略有兩種，分別是WriteThrough(直寫模式)和WriteBack(回寫模式)。直寫模式：在數(shù)據(jù)更新時，將數(shù)據(jù)同時寫入內存和Cache，該策略操作簡單，但是因為每次都要寫入內存，速度較慢?；貙懩Ｊ剑涸跀?shù)據(jù)更新時，只將數(shù)據(jù)寫入到Cache中，只有在數(shù)據(jù)被替換出Cache時，被修改的數(shù)據(jù)才會被寫入到內存中，該策略因為不需要寫入到內存中，所以速度較快。但數(shù)據(jù)僅寫在了Cache中，Cache數(shù)據(jù)和內存數(shù)據(jù)不一致，此時如果有其它CPU訪問數(shù)據(jù)，就會讀到臟數(shù)據(jù)，出現(xiàn)bug，所以這里需要用到Cache的一致性協(xié)議來保證CPU讀到的是最新的數(shù)據(jù)。

6. 什么是Cache一致性呢?

多個CPU對某塊內存同時讀寫，就會引起沖突的問題，被稱為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中，但是沒有被同步到內存中。

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

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

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

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

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

 

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

 

7. Cache與主存的映射關系?

直接映射

 

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

 

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

 

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

全相連映射

 

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

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

 

全相連映射的主存結構就很簡單啦，將CPU發(fā)出的內存地址的塊號部分與Cache所有行的標記進行比較，如果有相同的，則Cache命中，從Cache中讀取，如果找不到，則沒有命中，從主存中讀取。

組相連映射

 

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

主存中的各塊與Cache的組號之間有固定的映射關系，但可自由映射到對應Cache組中的任何一塊。例如，主存中的第0塊、第8塊……均映射于Cache的第0組，但可映射到Cache第0組中的第0塊或第1塊;主存的第1塊、第9塊……均映射于Cache的第1組，但可映射到Cache第1組中的第2塊或第3塊。

 

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

 

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

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

 

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ù)組的遍歷方式，一種按行遍歷，另一種是按列遍歷，乍一看您可能認為計算量沒有任何區(qū)別，但其實按行遍歷比按列遍歷速度快的多，這就是CPU Cache起到了作用，根據(jù)程序局部性原理，訪問主存時會把相鄰的部分數(shù)據(jù)也加載到Cache中，下次訪問相鄰數(shù)據(jù)時Cache的命中率極高，速度自然也會提升不少。

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

參考鏈接

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

https://www.cnblogs.com/jokerjason/p/10711022.html

http://cenalulu.github.io/linux/all-about-cpu-cache/

https://my.oschina.net/fileoptions/blog/1630855

https://www.pianshen.com/article/9557956769/

https://blog.csdn.net/weixin_42649617/article/details/105092395