好久沒有寫一些微觀方面的文章了,今天寫一篇關(guān)于CPU Cache相關(guān)的文章,這篇文章會講述一些多核 CPU 的系統(tǒng)架構(gòu)以及其原理,包括對程序性能上的影響,以及在進(jìn)行并發(fā)編程的時候需要注意到的一些問題。這篇文章我會盡量地寫簡單和通俗易懂一些,主要是講清楚相關(guān)的原理和問題,而對于一些細(xì)節(jié)和延伸閱讀我會在文章最好給出相關(guān)的資源。
本文比較長,主要分成這么幾個部分:基礎(chǔ)知識、緩存的命中、緩存的一致性、相關(guān)的代碼示例和延伸閱讀。
因?yàn)闊o論你寫什么樣的代碼都會交給CPU來執(zhí)行,所以,如果你想寫出性能比較高的代碼,這篇文章中的技術(shù)還是應(yīng)該認(rèn)真學(xué)習(xí)的。
基礎(chǔ)知識
首先,我們都知道現(xiàn)在的CPU多核技術(shù),都會有幾級緩存,老的CPU會有兩級內(nèi)存(L1和L2),新的CPU會有三級內(nèi)存(L1,L2,L3 ),如下圖所示:
其中:
L1緩分成兩種,一種是指令緩存,一種是數(shù)據(jù)緩存。L2緩存和L3緩存不分指令和數(shù)據(jù)。
L1和L2緩存在第一個CPU核中,L3則是所有CPU核心共享的內(nèi)存。
L1、L2、L3的越離CPU近就越小,速度也越快,越離CPU遠(yuǎn),速度也越慢。
再往后面就是內(nèi)存,內(nèi)存的后面就是硬盤。我們來看一些他們的速度:
L1 的存取速度: 4 個CPU時鐘周期
L2 的存取速度: 11 個CPU時鐘周期
L3 的存取速度: 39 個CPU時鐘周期
RAM內(nèi)存的存取速度 :107 個CPU時鐘周期
我們可以看到,L1的速度是RAM的27倍,但是L1/L2的大小基本上也就是KB級別的,L3會是MB級別的。例如: Intel Core i7-8700K ,是一個6核的CPU,每核上的L1是64KB(數(shù)據(jù)和指令各32KB),L2 是 256K,L3有12MB(我的蘋果電腦是 Intel Core i9-8950HK ,和Core i7-8700K的Cache大小一樣)。
于是我們的數(shù)據(jù)就從內(nèi)存向上,先到L3,再到L2,再到L1,最后到寄存器進(jìn)行CPU計算。為什么會設(shè)計成三層?這里有下面幾個方面的考慮:
一個方面是物理速度,如果你要更在的容量就需要更多的晶體管,除了芯片的體積會變大,更重要的是大量的晶體管會導(dǎo)致速度下降,因?yàn)樵L問速度和要訪問的晶體管的位置成反比,也就是當(dāng)信號路徑變長時,通信速度會變慢。這部分是物理問題。
另外一個問題是,多核技術(shù)中,數(shù)據(jù)的狀態(tài)需要在多個CPU中進(jìn)行同步,并且,我們可以看到,cache和RAM的速度差距太大,所以,多級不同尺寸的緩存有利于提高整體的性能。
這個世界永遠(yuǎn)是平衡的,一面變得有多光鮮,另一面也會變得有多黑暗。建立這么多級的緩存,一定就會引入其它的問題,這里有兩個比較重要的問題,
一個是比較簡單的緩存的命中率的問題。
另一個是比較復(fù)雜的緩存更新的一致性問題。
尤其是第二個問題,在多核技術(shù)下,這就很像分布式的系統(tǒng)了,要對多個地方進(jìn)行更新。
緩存的命中
在說明這兩個問題之前。我們需要要解一個術(shù)語 Cache Line。緩存基本上來說就是把后面的數(shù)據(jù)加載到離自己進(jìn)的地方,對于CPU來說,它是不會一個字節(jié)一個字節(jié)的加載的,因?yàn)檫@非常沒有效率,一般來說都是要一塊一塊的加載的,在CPU的緩存技術(shù)中,這個術(shù)語叫“Cache Line”(有的中文編譯成“緩存線”),一般來說,一個主流的CPU的Cache Line 是 64 Bytes(也有的CPU用32Bytes和128Bytes),也就是16個32位的整型。也就是說,CPU從內(nèi)存中撈數(shù)據(jù)上來的最小數(shù)據(jù)單位。
比如:Cache Line是最小單位(64Bytes),所以先把Cache分布多個Cache Line,比如:L1有32KB,那么,32KB/64B = 500 個 Cache Line。
一方面,緩存需要把內(nèi)存里的數(shù)據(jù)放到放進(jìn)來,英文叫 CPU Associativity。Cache的數(shù)據(jù)放置的策略決定了內(nèi)存中的數(shù)據(jù)塊會拷貝到CPU Cache中的哪個位置,因?yàn)镃ache的大小遠(yuǎn)遠(yuǎn)小于內(nèi)存,所以,需要有一種地址關(guān)聯(lián)的算法,能夠讓內(nèi)存中的數(shù)據(jù)可以被映射到cache中來。這個有點(diǎn)像內(nèi)存管理的方法。
基本上來說,我們會有如下的一些方法。
一種方法是,任何一個內(nèi)存地址的數(shù)據(jù)可以被緩存在任何一個Cache Line里,這種方法是最靈活的,但是,如果我們要知道一個內(nèi)存是否存在于Cache中,我們就需要進(jìn)行O(n)復(fù)雜度的Cache遍歷,這是很沒有效率的。
另一種方法,為了降低緩存搜索算法,我們需要使用像Hash Table這樣的數(shù)據(jù)結(jié)構(gòu),最簡單的hash table就是做“求模運(yùn)算”,比如:我們的L1 Cache有500個Cache Line,那么,公式:`(內(nèi)存地址 mod 500)x 64` 就可以直接找到所在的Cache地址的偏移了。但是,這樣的方式需要我們的程序?qū)?nèi)存地址的訪問要非常地平均,這成了一種非常理想的情況了。
為了避免上述的兩種方案的問題,于是就要容忍一定的hash沖突,也就出現(xiàn)了 N-Way 關(guān)聯(lián)。也就是把連續(xù)的N個Cache Line綁成一組,然后,先把找到相關(guān)的組,然后再在這個組內(nèi)找到相關(guān)的Cache Line。
那么,Cache的命中率會成為程序運(yùn)行性能非常關(guān)鍵的事,所以,了解上面的這些東西,會有利于我們知道在什么情況下有可以導(dǎo)致緩存的失效。
對于 N-Way 關(guān)聯(lián)我們?nèi)€例子,并多說一些細(xì)節(jié)(因?yàn)楹竺鏁玫剑?,Intel 大多數(shù)處理器的L1 Cache都是32KB,8-Way 組相聯(lián),Cache Line 是64 Bytes。于是,
32KB的可以分成,32KB / 64 = 512 條 Cache Line。
因?yàn)橛? Way,于是會每一Way 有 512 / 8 = 64 條 Cache Line。
于是每一路就有 64 x 64 = 4096 Byts 的內(nèi)存。
為了方便索引內(nèi)存地址,
Tag :每條 Cache Line 前都會有一個獨(dú)立分配的 24 bits來存的 tag,其就是內(nèi)存地址的前24bits
Index :內(nèi)存地址后續(xù)的6個bits則是在這一Way的是Cache Line 索引,2^6 = 64 剛好可以索引64條Cache Line
Offset :再往后的6bits用于表示在Cache Line 里的偏移量
如下圖所示:(更多的細(xì)節(jié)可以讀一下《 Cache: a place for concealment and safekeeping 》)
(圖片來自《 Cache: a place for concealment and safekeeping 》)
這意味著:
L1 Cache 可映射 36bits 的內(nèi)存地址,一共 2^36 = 64GB的內(nèi)存
因?yàn)橹灰^24bits相同就會被映射到同一個Way中,所以,每4096個地址會放在一Way中。
當(dāng)CPU要訪問一個內(nèi)存的時候,通過這個內(nèi)存的前24bits 和中間的6bits可以直接定位相應(yīng)的Cache Line。
此外,當(dāng)有數(shù)據(jù)沒有命中緩存的時候,CPU就會以最小為Cache Line的單元向內(nèi)存更新數(shù)據(jù)。當(dāng)然,CPU并不一定只是更新64Bytes,因?yàn)樵L問主存是在是太慢了,所以,一般都會多更新一些。好的CPU會有一些預(yù)測的技術(shù),如果找到一種pattern的話,就會預(yù)先加載更多的內(nèi)存,包括指令也可以預(yù)加載。這叫 Prefetching 技術(shù) (參看,Wikipedia 的 Cache Prefetching 和 紐約州立大學(xué)的 Memory Prefetching )。比如,你在for-loop訪問一個連續(xù)的數(shù)組,你的步長是一個固定的數(shù),內(nèi)存就可以做到prefetching。(注:指令也是以預(yù)加載的方式執(zhí)行,參看本站的《 代碼執(zhí)行的效率 》中的第三個示例)
緩存的一致性
對于主流的CPU來說,緩存的寫操作基本上是兩種策略(參看本站《 緩存更新的套路 》),
一種是Write Back,寫操作只要在cache上,然后再flush到內(nèi)存上。
一種是Write Through,寫操作同時寫到cache和內(nèi)存上。
為了提高寫的性能,一般來說,主流的CPU(如:Intel Core i7/i9)采用的是Write Back的策略,因?yàn)橹苯訉憙?nèi)存實(shí)在是太慢了。
好了,現(xiàn)在問題來了,如果有一個數(shù)據(jù) x 在 CPU 第0核的緩存上被更新了,那么其它CPU核上對于這個數(shù)據(jù) x 的值也要被更新,這就是緩存一致性的問題。(當(dāng)然,對于我們上層的程序我們不用關(guān)心CPU多個核的緩存是怎么同步的,這對上層都是透明的)
一般來說,在CPU硬件上,會有兩種方法來解決這個問題。
Directory 協(xié)議 。這種方法的典型實(shí)現(xiàn)是要設(shè)計一個集中式控制器,它是主存儲器控制器的一部分。其中有一個目錄存儲在主存儲器中,其中包含有關(guān)各種本地緩存內(nèi)容的全局狀態(tài)信息。當(dāng)單個CPU Cache 發(fā)出讀寫請求時,這個集中式控制器會檢查并發(fā)出必要的命令,以在主存和CPU Cache之間或在CPU Cache自身之間進(jìn)行數(shù)據(jù)同步和傳輸。
Snoopy 協(xié)議 。這種協(xié)議更像是一種數(shù)據(jù)通知的總線型的技術(shù)。CPU Cache通過這個協(xié)議可以識別其它Cache上的數(shù)據(jù)狀態(tài)。如果有數(shù)據(jù)共享的話,可以通過廣播機(jī)制將共享數(shù)據(jù)的狀態(tài)通知給其它CPU Cache。這個協(xié)議要求每個CPU Cache 都可以 “窺探” 數(shù)據(jù)事件的通知并做出相應(yīng)的反應(yīng)。
因?yàn)镈irectory協(xié)議是一個中心式的,會有性能瓶頸,而且會增加整體設(shè)計的復(fù)雜度。而Snoopy協(xié)議更像是微服務(wù)+消息通訊,所以,現(xiàn)在基本都是使用Snoopy的總線的設(shè)計。
這里,我想多寫一些細(xì)節(jié),因?yàn)檫@種微觀的東西,不自然就就會更分布式系統(tǒng)相關(guān)聯(lián),在分布式系統(tǒng)中我們一般用Paxos/Raft這樣的分布式一致性的算法。而在CPU的微觀世界里,則不必使用這樣的算法,原因是因?yàn)镃PU的多個核的硬件不必考慮網(wǎng)絡(luò)會斷會延遲的問題。所以,CPU的多核心緩存間的同步的核心就是要管理好數(shù)據(jù)的狀態(tài)就好了。
這里介紹幾個狀態(tài)協(xié)議,先從最簡單的開始,MESI協(xié)議,這個協(xié)議跟那個著名的足球運(yùn)動員梅西沒什么關(guān)系,其主要表示緩存數(shù)據(jù)有四個狀態(tài):Modified(已修改), Exclusive(獨(dú)占的),Shared(共享的),Invalid(無效的)。
這些狀態(tài)的狀態(tài)機(jī)如下所示:
下面是個示例(如果你想看一下動畫演示的話,這里有一個網(wǎng)頁( MESI Interactive Animations ),你可以進(jìn)行交互操作,這個動畫演示中使用的Write Through算法):
當(dāng)前操作CPU0CPU1Memory說明1) CPU0 read(x)x=1 (E)x=1只有一個CPU有 x 變量,
所以,狀態(tài)是 Exclusive2) CPU1 read(x)x=1 (S)x=1(S)x=1有兩個CPU都讀取 x 變量,
所以狀態(tài)變成 Shared3) CPU0 write(x,9)x= 9 (M)x=1(I)x=1變量改變,在CPU0中狀態(tài)
變成 Modified,在CPU1中
狀態(tài)變成 Invalid4) 變量 x 寫回內(nèi)存x=9 (M)X=1(I)x=9目前的狀態(tài)不變5) CPU1 read(x)x=9 (S)x=9(S)x=9變量同步到所有的Cache中,
狀態(tài)回到Shared
MESI 這種協(xié)議在數(shù)據(jù)更新后,會標(biāo)記其它共享的CPU緩存的數(shù)據(jù)拷貝為Invalid狀態(tài),然后當(dāng)其它CPU再次read的時候,就會出現(xiàn) cache misses 的問題,此時再從內(nèi)存中更新數(shù)據(jù)。可見,從內(nèi)存中更新數(shù)據(jù)意味著20倍速度的降低。我們能不直接從我隔壁的CPU緩存中更新?是的,這就可以增加很多速度了,但是狀態(tài)控制也就變麻煩了。還需要多來一個狀態(tài):Owner(宿主),用于標(biāo)記,我是更新數(shù)據(jù)的源。于是,現(xiàn)了 MOESI 協(xié)議
MOESI協(xié)議的狀態(tài)機(jī)和演示我就不貼了,我們只需要理解MOESI協(xié)議允許 CPU Cache 間同步數(shù)據(jù),于是也降低了對內(nèi)存的操作,性能是非常大的提升,但是控制邏輯也非常復(fù)雜。
順便說一下,與 MOESI 協(xié)議類似的一個協(xié)議是 MESIF ,其中的 F 是 Forward,同樣是把更新過的數(shù)據(jù)轉(zhuǎn)發(fā)給別的 CPU Cache 但是,MOESI 中的 Owner 狀態(tài) 和MESIF 中的 Forward 狀態(tài)有一個非常大的不一樣—— 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)主要是針對 CPU L3 Cache 設(shè)計的(前面我們說過,L3是所有CPU核心共享的)。(相關(guān)的比較可以參看 StackOverlow上這個問題的答案 )
程序性能
了解了我們上面的這些東西后,我們來看一下對于程序的影響。
示例一
首先,假設(shè)我們有一個64M長的數(shù)組,設(shè)想一下下面的兩個循環(huán):
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;
按我們的想法來看,第二個循環(huán)要比第一個循環(huán)少4倍的計算量,其應(yīng)該也是要快4倍的。但實(shí)際跑下來并不是, 在我的機(jī)器上,第一個循環(huán)需要127毫秒,第二個循環(huán)則需要121毫秒,相差無幾 。這里最主要的原因就是 Cache Line,因?yàn)镃PU會以一個Cache Line 64Bytes最小時單位加載,也就是16個32bits的整型,所以,無論你步長是2還是8,都差不多。而后面的乘法其實(shí)是不耗CPU時間的。
示例二
我們再來看一個與緩存命中率有關(guān)的代碼,我們以一定的步長 increment 來訪問一個連續(xù)的數(shù)組。
for (int i = 0; i 《 10000000; i++) { for (int j = 0; j 《 size; j += increment) { memory[j] += j; }}
我們測試一下,在下表中, 表頭是步長,也就是每次跳多少個整數(shù),而縱向是這個數(shù)組可以跳幾次(你可以理解為要幾條Cache Line),于是表中的任何一項代表了這個數(shù)組有多少,而且步長是多少。比如:橫軸是 512,縱軸是4,意思是,這個數(shù)組有 4*512 = 2048 個長度,訪問時按512步長訪問,也就是訪問其中的這幾項: [0, 512, 1024, 1536] 這四項。
表中同的項是,是循環(huán)1000萬次的時間,單位是“微秒”(除以1000后是毫秒)
| count | 1 | 16 | 512 | 1024 |------------------------------------------| 1 | 17539 | 16726 | 15143 | 14477 || 2 | 15420 | 14648 | 13552 | 13343 || 3 | 14716 | 14463 | 15086 | 17509 || 4 | 18976 | 18829 | 18961 | 21645 || 5 | 23693 | 23436 | 74349 | 29796 || 6 | 23264 | 23707 | 27005 | 44103 || 7 | 28574 | 28979 | 33169 | 58759 || 8 | 33155 | 34405 | 39339 | 65182 || 9 | 37088 | 37788 | 49863 |156745 || 10 | 41543 | 42103 | 58533 |215278 || 11 | 47638 | 50329 | 66620 |335603 || 12 | 49759 | 51228 | 75087 |305075 || 13 | 53938 | 53924 | 77790 |366879 || 14 | 58422 | 59565 | 90501 |466368 || 15 | 62161 | 64129 | 90814 |525780 || 16 | 67061 | 66663 | 98734 |440558 || 17 | 71132 | 69753 |171203 |506631 || 18 | 74102 | 73130 |293947 |550920 |
我們可以看到,從[9,1024] 以后,時間顯注上升。包括[17,512] 和 [18,512] 也顯注上升。這是因?yàn)?,我機(jī)器的 L1 Cache 是 32KB, 8 Way 的,前面說過,8 Way的一個組有64個Cache Line,也就是4096個字節(jié),而1024個整型正好是 4096 Bytes,所以,一旦過了這個界,每個步長都無法命中 L1 Cache,每次都是 Cache Miss,所以,導(dǎo)致訪問時間一下子就上升了。而 [16, 512]也是一樣的,其中的幾步開始導(dǎo)致L1 Cache開始失效。
示例三
接下來,我們再來看個示例。下面是一個二維數(shù)組的兩種遍歷方式,一個逐行遍歷,一個是逐列遍歷,這兩種方式在理論上來說,尋址和計算量都是一樣的,執(zhí)行時間應(yīng)該也是一樣的。
const int row = 1024;const int col = 512int 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]; }}//逐列遍歷int sum_col=0;for(int c=0; c《col; c++) { for(int r=0; r《row; r++){ sum_col += matrix[r]; }}
然而,并不是,在我的機(jī)器上,得到下面的結(jié)果。
逐行遍歷:0.081ms
逐列遍歷:1.069ms
執(zhí)行時間有十幾倍的差距。其中的原因,就是逐列遍歷對于CPU Cache 的運(yùn)作方式并不友好,所以,付出巨大的代價。
示例四
接下來,我們來看一下多核下的性能問題,參看如下的代碼。兩個線程在操作一個數(shù)組的兩個不同的元素(無需加鎖),線程循環(huán)1000萬次,做加法操作。在下面的代碼中,我高亮了一行,就是 p2 指針,要么是 p[1] ,或是 p[18] ,理論上來說,無論訪問哪兩個數(shù)組元素,都應(yīng)該是一樣的執(zhí)行時間。
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);
然而,并不是,在我的機(jī)器上執(zhí)行下來的結(jié)果是:
對于 p[0] 和 p[1] :560ms
對于 p[0] 和 p[30] :104ms
這是因?yàn)?p[0] 和 p[1] 在同一條 Cache Line 上,而 p[0] 和 p[30] 則不可能在同一條Cache Line 上 ,CPU的緩沖最小的更新單位是Cache Line,所以, 這導(dǎo)致雖然兩個線程在寫不同的數(shù)據(jù),但是因?yàn)檫@兩個數(shù)據(jù)在同一條Cache Line上,就會導(dǎo)致緩存需要不斷進(jìn)在兩個CPU的L1/L2中進(jìn)行同步,從而導(dǎo)致了5倍的時間差異 。
示例五
接下來,我們再來看一下另外一段代碼:我們想統(tǒng)計一下一個數(shù)組中的奇數(shù)個數(shù),但是這個數(shù)組太大了,我們希望可以用多線程來完成,這個統(tǒng)計。下面的代碼中,我們?yōu)槊恳粋€線程傳入一個 id ,然后通過這個 id 來完成對應(yīng)數(shù)組段的統(tǒng)計任務(wù)。這樣可以加快整個處理速度。
int total_size = 16 * 1024 * 1024; //數(shù)組長度int* test_data = new test_data[total_size]; //數(shù)組int nthread = 6; //線程數(shù)(因?yàn)槲业臋C(jī)器是6核的)int result[nthread]; //收集結(jié)果的數(shù)組void thread_func (int id) { result[id] = 0; int chunk_size = total_size / nthread + 1; int start = id * chunk_size; int end = min(start + chunk_size, total_size); for ( int i = start; i 《 end; ++i ) { if (test_data[i] % 2 != 0 ) ++result[id]; }}
然而,在執(zhí)行過程中,你會發(fā)現(xiàn),6個線程居然跑不過1個線程。因?yàn)楦鶕?jù)上面的例子你知道 result[] 這個數(shù)組中的數(shù)據(jù)在一個Cache Line中,所以,所有的線程都會對這個 Cache Line 進(jìn)行寫操作,導(dǎo)致所有的線程都在不斷地重新同步 result[] 所在的 Cache Line,所以,導(dǎo)致 6 個線程還跑不過一個線程的結(jié)果。這叫 False Sharing。
優(yōu)化也很簡單,使用一個線程內(nèi)的變量。
void thread_func (int id) { result[id] = 0; int chunk_size = total_size / nthread + 1; int start = id * chunk_size; int end = min(start + chunk_size, total_size); int c = 0; //使用臨時變量,沒有cache line的同步了 for ( int i = start; i 《 end; ++i ) { if (test_data[i] % 2 != 0 ) ++c; } result[id] = c;}
我們把兩個程序分別在 1 到 32 個線程上跑一下,得出的結(jié)果畫一張圖如下所示:
上圖中,我們可以看到,灰色的曲線就是第一種方法,橙色的就是第二種(用局部變量的)方法。當(dāng)只有一個線程的時候,兩個方法相當(dāng),而且第二種方法還略差一點(diǎn),但是在線程數(shù)增加的時候的時候,你會發(fā)現(xiàn),第二種方法的性能提高的非??臁V钡降竭_(dá)6個線程的時候,開始變得穩(wěn)定(前面說過,我的CPU是6核的)。而第一種方法無論加多少線程也沒有辦法超過第二種方法。因?yàn)榈谝环N方法不是CPU Cache 友好的。
-
寄存器
+關(guān)注
關(guān)注
31文章
5325瀏覽量
120054 -
cpu
+關(guān)注
關(guān)注
68文章
10829瀏覽量
211198 -
晶體管
+關(guān)注
關(guān)注
77文章
9641瀏覽量
137876
發(fā)布評論請先 登錄
相關(guān)推薦
評論