What is cache?
CPU緩存(Cache Memory)位于CPU與內(nèi)存之間的臨時(shí)存儲(chǔ)器,它的容量比內(nèi)存小但交換速度快。在緩存中的數(shù)據(jù)是內(nèi)存中的一小部分,但這一小部分是短時(shí)間內(nèi)CPU即將訪問的,當(dāng)CPU調(diào)用大量數(shù)據(jù)時(shí),就可避開內(nèi)存直接從緩存中調(diào)用,從而加快讀取速度。
在CPU中加入緩存是一種高效的解決方案,這樣整個(gè)內(nèi)存儲(chǔ)器(緩存+內(nèi)存)就變成了既有緩存的高速度,又有內(nèi)存的大容量的存儲(chǔ)系統(tǒng)了。緩存對(duì)CPU的性能影響很大,主要是因?yàn)镃PU的數(shù)據(jù)交換順序和CPU與緩存間的帶寬引起的。
下圖是一個(gè)典型的存儲(chǔ)器層次結(jié)構(gòu),我們可以看到一共使用了三級(jí)緩存:
Why should I care about cache?
從延遲上看,做一次乘法一般只要三個(gè)周期,而做一次CPU的內(nèi)存訪問需要167個(gè)cycle,如果需要提升程序性能,減少CPU的memory訪問至關(guān)重要。因此,需要采用容量小但是更快的存儲(chǔ)器(cache)。
為什么要有多級(jí)CPU Cache
隨著科技發(fā)展,熱點(diǎn)數(shù)據(jù)的體積越來越大,單純的增加一級(jí)緩存大小的性價(jià)比已經(jīng)很低了二級(jí)緩存就是一級(jí)緩存的緩沖器:一級(jí)緩存制造成本很高因此它的容量有限,二級(jí)緩存的作用就是存儲(chǔ)那些CPU處理時(shí)需要用到、一級(jí)緩存又無法存儲(chǔ)的數(shù)據(jù)。
同樣道理,三級(jí)緩存和內(nèi)存可以看作是二級(jí)緩存的緩沖器,它們的容量遞增,但單位制造成本卻遞減。另外需要注意的是,L3 Cache和L1,L2 Cache有著本質(zhì)的區(qū)別。,L1和L2 Cache都是每個(gè)CPU core獨(dú)立擁有一個(gè),而L3 Cache是幾個(gè)Cores共享的,可以認(rèn)為是一個(gè)更小但是更快的內(nèi)存。
使用dmidecode命令查看cache size:
cpu與cache 內(nèi)存交互的過程
CPU接收到指令后,它會(huì)最先向CPU中的一級(jí)緩存(L1 Cache)去尋找相關(guān)的數(shù)據(jù),然一級(jí)緩存是與CPU同頻運(yùn)行的,但是由于容量較小,所以不可能每次都命中。這時(shí)CPU會(huì)繼續(xù)向下一級(jí)的二級(jí)緩存(L2 Cache)尋找,同樣的道理,當(dāng)所需要的數(shù)據(jù)在二級(jí)緩存中也沒有的話,會(huì)繼續(xù)轉(zhuǎn)向L3 Cache、內(nèi)存(主存)和硬盤。
程序運(yùn)行時(shí)可以使用perf工具觀察cache-miss的rate。
什么是cache line
Cache Line可以簡(jiǎn)單的理解為CPU Cache中的最小緩存單位。內(nèi)存和高速緩存之間或高速緩存之間的數(shù)據(jù)移動(dòng)不是以單個(gè)字節(jié)或甚至word完成的。相反,移動(dòng)的最小數(shù)據(jù)單位稱為緩存行,有時(shí)稱為緩存塊。目前主流的CPU Cache的Cache Line大小都是64Bytes。假設(shè)我們有一個(gè)512字節(jié)的一級(jí)緩存,那么按照64B的緩存單位大小來算,這個(gè)一級(jí)緩存所能存放的緩存?zhèn)€數(shù)就是512/64 = 8個(gè)。
查看cache line大小:
cat /sys/devices/system/cpu/cpu1/cache/index0/coherency_line_size
cache line的影響:
for(inti=0;i
注意當(dāng)步長(zhǎng)在1到16范圍內(nèi),循環(huán)運(yùn)行時(shí)間幾乎不變。但從16開始,每次步長(zhǎng)加倍,運(yùn)行時(shí)間減半。由于16個(gè)整型數(shù)占用64字節(jié)(一個(gè)緩存行),for循環(huán)步長(zhǎng)在1到16之間必定接觸到相同數(shù)目的緩存行:即數(shù)組中所有的緩存行。當(dāng)步長(zhǎng)為32,我們只有大約每?jī)蓚€(gè)緩存行接觸一次,當(dāng)步長(zhǎng)為64,只有每四個(gè)接觸一次。
cache寫機(jī)制
Cache寫機(jī)制分為write through和write back兩種。
Write-through- Write is done synchronously both to the cache and to the backing store.
Write-back (or Write-behind) - Writing is done only to the cache. A modified cache block is written back to the store, just before it is replaced.
Write-through(直寫模式)在數(shù)據(jù)更新時(shí),同時(shí)寫入緩存Cache和后端存儲(chǔ)。此模式的優(yōu)點(diǎn)是操作簡(jiǎn)單;缺點(diǎn)是因?yàn)閿?shù)據(jù)修改需要同時(shí)寫入存儲(chǔ),數(shù)據(jù)寫入速度較慢。
Write-back(回寫模式)在數(shù)據(jù)更新時(shí)只寫入緩存Cache。只在數(shù)據(jù)被替換出緩存時(shí),被修改的緩存數(shù)據(jù)才會(huì)被寫到后端存儲(chǔ)。此模式的優(yōu)點(diǎn)是數(shù)據(jù)寫入速度快,因?yàn)椴恍枰獙懘鎯?chǔ);缺點(diǎn)是一旦更新后的數(shù)據(jù)未被寫入存儲(chǔ)時(shí)出現(xiàn)系統(tǒng)掉電的情況,數(shù)據(jù)將無法找回。
cache 一致性
多個(gè)處理器對(duì)某個(gè)內(nèi)存塊同時(shí)讀寫,會(huì)引起沖突的問題,這也被稱為Cache一致性問題。
Cache一致性問題出現(xiàn)的原因是在一個(gè)多處理器系統(tǒng)中,多個(gè)處理器核心都能夠獨(dú)立地執(zhí)行計(jì)算機(jī)指令,從而有可能同時(shí)對(duì)某個(gè)內(nèi)存塊進(jìn)行讀寫操作,并且由于我們之前提到的回寫和直寫的Cache策略,導(dǎo)致一個(gè)內(nèi)存塊同時(shí)可能有多個(gè)備份,有的已經(jīng)寫回到內(nèi)存中,有的在不同的處理器核心的一級(jí)、二級(jí)Cache中。由于Cache緩存的原因,我們不知道數(shù)據(jù)寫入的時(shí)序性,因而也不知道哪個(gè)備份是最新的。還有另外一個(gè)一種可能,假設(shè)有兩個(gè)線程A和B共享一個(gè)變量,當(dāng)線程A處理完一個(gè)數(shù)據(jù)之后,通過這個(gè)變量通知線程B,然后線程B對(duì)這個(gè)數(shù)據(jù)接著進(jìn)行處理,如果兩個(gè)線程運(yùn)行在不同的處理器核心上,那么運(yùn)行線程B的處理器就會(huì)不停地檢查這個(gè)變量,而這個(gè)變量存儲(chǔ)在本地的Cache中,因此就會(huì)發(fā)現(xiàn)這個(gè)值總也不會(huì)發(fā)生變化。
為了正確性,一旦一個(gè)核心更新了內(nèi)存中的內(nèi)容,硬件就必須要保證其他的核心能夠讀到更新后的數(shù)據(jù)。目前大多數(shù)硬件采用的策略或協(xié)議是MESI或基于MESI的變種:
M代表更改(modified),表示緩存中的數(shù)據(jù)已經(jīng)更改,在未來的某個(gè)時(shí)刻將會(huì)寫入內(nèi)存;
E代表排除(exclusive),表示緩存的數(shù)據(jù)只被當(dāng)前的核心所緩存;
S代表共享(shared),表示緩存的數(shù)據(jù)還被其他核心緩存;
I代表無效(invalid),表示緩存中的數(shù)據(jù)已經(jīng)失效,即其他核心更改了數(shù)據(jù)。
cache的局部性
程序在一段時(shí)間內(nèi)訪問的數(shù)據(jù)通常具有局部性,比如對(duì)一維數(shù)組來說,訪問了地址x上的元素,那么以后訪問地址x+1、x+2上元素的可能性就比較高;現(xiàn)在訪問的數(shù)據(jù),在不久之后再次被訪問的可能性也比較高。局部性分為“時(shí)間局部性”和“空間局部性”,時(shí)間局部性是指當(dāng)前被訪問的數(shù)據(jù)隨后有可能訪問到;空間局部性是指當(dāng)前訪問地址附近的地址可能隨后被訪問。處理器通過在內(nèi)存和核心之間增加緩存以利用局部性增強(qiáng)程序性能,這樣可以用遠(yuǎn)低于緩存的價(jià)格換取接近緩存的速度。
時(shí)間局部性:
代碼1:
for(loop=0;loop<10;?loop++)?{ ????for?(i=0;?i
代碼2:
for(i=0;i
代碼2的性能優(yōu)于代碼1,x的元素現(xiàn)在被重復(fù)使用,因此更有可能留在緩存中。這個(gè)重新排列的代碼在使用x[i]時(shí)顯示更好的時(shí)間局部性。
空間局部性:
一個(gè)矩陣乘法的例子:
代碼1:
fori=1..n forj=1..n fork=1..n c[i,j]+=a[i,k]*b[k,j]
代碼2:
fori=1..n fork=1..n forj=1..n c[i,j]+=a[i,k]*b[k,j]
代碼2的性能優(yōu)于代碼一的性能。
兩者實(shí)現(xiàn)上的差異:
代碼2的b[k,j]是按行訪問的,所以存在良好的空間局部性,cache line被充分利用。代碼1中,b [k,j]由列訪問。由于行的存儲(chǔ)矩陣,因此對(duì)于每個(gè)緩存行加載,只有一個(gè)元素用于遍歷。
cache替換策略
Cache工作原理要求它盡量保存最新數(shù)據(jù),當(dāng)從主存向Cache傳送一個(gè)新塊,而Cache中可用位置已被占滿時(shí),就會(huì)產(chǎn)生Cache替換的問題。
常用的替換算法有下面三種。
LFU
LFU(Least Frequently Used,最不經(jīng)常使用)算法將一段時(shí)間內(nèi)被訪問次數(shù)最少的那個(gè)塊替換出去。每塊設(shè)置一個(gè)計(jì)數(shù)器,從0開始計(jì)數(shù),每訪問一次,被訪塊的計(jì)數(shù)器就增1。當(dāng)需要替換時(shí),將計(jì)數(shù)值最小的塊換出,同時(shí)將所有塊的計(jì)數(shù)器都清零。這種算法將計(jì)數(shù)周期限定在對(duì)這些特定塊兩次替換之間的間隔時(shí)間內(nèi),不能嚴(yán)格反映近期訪問情況,新調(diào)入的塊很容易被替換出去。
LRU
LRU(Least Recently Used,近期最少使用)算法是把CPU近期最少使用的塊替換出去。這種替換方法需要隨時(shí)記錄Cache中各塊的使用情況,以便確定哪個(gè)塊是近期最少使用的塊。每塊也設(shè)置一個(gè)計(jì)數(shù)器,Cache每命中一次,命中塊計(jì)數(shù)器清零,其他各塊計(jì)數(shù)器增1。當(dāng)需要替換時(shí),將計(jì)數(shù)值最大的塊換出。LRU算法相對(duì)合理,但實(shí)現(xiàn)起來比較復(fù)雜,系統(tǒng)開銷較大。這種算法保護(hù)了剛調(diào)入Cache的新數(shù)據(jù)塊,具有較高的命中率。LRU算法不能肯定調(diào)出去的塊近期不會(huì)再被使用,所以這種替換算法不能算作最合理、最優(yōu)秀的算法。但是研究表明,采用這種算法可使Cache的命中率達(dá)到90%左右。
隨機(jī)替換
最簡(jiǎn)單的替換算法是隨機(jī)替換。隨機(jī)替換算法完全不管Cache的情況,簡(jiǎn)單地根據(jù)一個(gè)隨機(jī)數(shù)選擇一塊替換出去。隨機(jī)替換算法在硬件上容易實(shí)現(xiàn),且速度也比前兩種算法快。缺點(diǎn)則是降低了命中率和Cache工作效率。
cache的映射
主存與cache的地址映射方式有全相聯(lián)方式、直接方式和組相聯(lián)方式三種。
直接映射:將一個(gè)主存塊存儲(chǔ)到唯一的一個(gè)Cache行。
多對(duì)一的映射關(guān)系,但一個(gè)主存塊只能拷貝到cache的一個(gè)特定行位置上去。cache的行號(hào)i和主存的塊號(hào)j有如下函數(shù)關(guān)系:i=j mod m(m為cache中的總行數(shù))。
優(yōu)點(diǎn):硬件簡(jiǎn)單,容易實(shí)現(xiàn)。缺點(diǎn):命中率低, Cache的存儲(chǔ)空間利用率低。
全相聯(lián)映射:將一個(gè)主存塊存儲(chǔ)到任意一個(gè)Cache行。
主存的一個(gè)塊直接拷貝到cache中的任意一行上。
優(yōu)點(diǎn):命中率較高,Cache的存儲(chǔ)空間利用率高。缺點(diǎn):線路復(fù)雜,成本高,速度低。
組相聯(lián)映射:將一個(gè)主存塊存儲(chǔ)到唯一的一個(gè)Cache組中任意一個(gè)行。
將cache分成u組,每組v行,主存塊存放到哪個(gè)組是固定的,至于存到該組哪一行是靈活的,即有如下函數(shù)關(guān)系:cache總行數(shù)m=u×v 組號(hào)q=j(luò) mod u
組間采用直接映射,組內(nèi)為全相聯(lián)。硬件較簡(jiǎn)單,速度較快,命中率較高。
審核編輯:彭靜
-
cpu
+關(guān)注
關(guān)注
68文章
10698瀏覽量
209329 -
內(nèi)存
+關(guān)注
關(guān)注
8文章
2902瀏覽量
73534 -
Cache
+關(guān)注
關(guān)注
0文章
128瀏覽量
28188
原文標(biāo)題:CPU中cache那些事,太重要了!
文章出處:【微信號(hào):嵌入式情報(bào)局,微信公眾號(hào):嵌入式情報(bào)局】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論