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