What is cache?

CPU緩存（Cache Memory）位于CPU與內(nèi)存之間的臨時(shí)存儲(chǔ)器，它的容量比內(nèi)存小但交換速度快。在緩存中的數(shù)據(jù)是內(nèi)存中的一小部分，但這一小部分是短時(shí)間內(nèi)CPU即將訪問(wèn)的，當(dāng)CPU調(diào)用大量數(shù)據(jù)時(shí)，就可避開(kāi)內(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)存訪問(wèn)需要167個(gè)cycle，如果需要提升程序性能，減少CPU的memory訪問(wèn)至關(guān)重要。因此，需要采用容量小但是更快的存儲(chǔ)器（cache）。

為什么要有多級(jí)CPU Cache

隨著科技發(fā)展，熱點(diǎn)數(shù)據(jù)的體積越來(lái)越大，單純的增加一級(jí)緩存大小的性價(jià)比已經(jīng)很低了二級(jí)緩存就是一級(jí)緩存的緩沖器：一級(jí)緩存制造成本很高因此它的容量有限，二級(jí)緩存的作用就是存儲(chǔ)那些CPU處理時(shí)需要用到、一級(jí)緩存又無(wú)法存儲(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)存交互的過(guò)程

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í)緩存中也沒(méi)有的話，會(huì)繼續(xù)轉(zhuǎn)向L3 Cache、內(nèi)存(主存)和硬盤(pán)。

程序運(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的緩存單位大小來(lái)算，這個(gè)一級(jí)緩存所能存放的緩存?zhèn)€數(shù)就是512/64 = 8個(gè)。

查看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;

注意當(dāng)步長(zhǎng)在1到16范圍內(nèi)，循環(huán)運(yùn)行時(shí)間幾乎不變。但從16開(kāi)始，每次步長(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寫(xiě)機(jī)制

Cache寫(xiě)機(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（直寫(xiě)模式）在數(shù)據(jù)更新時(shí)，同時(shí)寫(xiě)入緩存Cache和后端存儲(chǔ)。此模式的優(yōu)點(diǎn)是操作簡(jiǎn)單；缺點(diǎn)是因?yàn)閿?shù)據(jù)修改需要同時(shí)寫(xiě)入存儲(chǔ)，數(shù)據(jù)寫(xiě)入速度較慢。

Write-back（回寫(xiě)模式）在數(shù)據(jù)更新時(shí)只寫(xiě)入緩存Cache。只在數(shù)據(jù)被替換出緩存時(shí)，被修改的緩存數(shù)據(jù)才會(huì)被寫(xiě)到后端存儲(chǔ)。此模式的優(yōu)點(diǎn)是數(shù)據(jù)寫(xiě)入速度快，因?yàn)椴恍枰獙?xiě)存儲(chǔ)；缺點(diǎn)是一旦更新后的數(shù)據(jù)未被寫(xiě)入存儲(chǔ)時(shí)出現(xiàn)系統(tǒng)掉電的情況，數(shù)據(jù)將無(wú)法找回。

cache 一致性

多個(gè)處理器對(duì)某個(gè)內(nèi)存塊同時(shí)讀寫(xiě)，會(huì)引起沖突的問(wèn)題，這也被稱為Cache一致性問(wèn)題。

Cache一致性問(wèn)題出現(xiàn)的原因是在一個(gè)多處理器系統(tǒng)中，多個(gè)處理器核心都能夠獨(dú)立地執(zhí)行計(jì)算機(jī)指令，從而有可能同時(shí)對(duì)某個(gè)內(nèi)存塊進(jìn)行讀寫(xiě)操作，并且由于我們之前提到的回寫(xiě)和直寫(xiě)的Cache策略，導(dǎo)致一個(gè)內(nèi)存塊同時(shí)可能有多個(gè)備份，有的已經(jīng)寫(xiě)回到內(nèi)存中，有的在不同的處理器核心的一級(jí)、二級(jí)Cache中。由于Cache緩存的原因，我們不知道數(shù)據(jù)寫(xiě)入的時(shí)序性，因而也不知道哪個(gè)備份是最新的。還有另外一個(gè)一種可能，假設(shè)有兩個(gè)線程A和B共享一個(gè)變量，當(dāng)線程A處理完一個(gè)數(shù)據(jù)之后，通過(guò)這個(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)更改，在未來(lái)的某個(gè)時(shí)刻將會(huì)寫(xiě)入內(nèi)存；E代表排除（exclusive），表示緩存的數(shù)據(jù)只被當(dāng)前的核心所緩存；S代表共享（shared），表示緩存的數(shù)據(jù)還被其他核心緩存；I代表無(wú)效（invalid），表示緩存中的數(shù)據(jù)已經(jīng)失效，即其他核心更改了數(shù)據(jù)。

cache的局部性

程序在一段時(shí)間內(nèi)訪問(wèn)的數(shù)據(jù)通常具有局部性，比如對(duì)一維數(shù)組來(lái)說(shuō)，訪問(wèn)了地址x上的元素，那么以后訪問(wèn)地址x+1、x+2上元素的可能性就比較高；現(xiàn)在訪問(wèn)的數(shù)據(jù)，在不久之后再次被訪問(wèn)的可能性也比較高。局部性分為“時(shí)間局部性”和“空間局部性”，時(shí)間局部性是指當(dāng)前被訪問(wèn)的數(shù)據(jù)隨后有可能訪問(wèn)到；空間局部性是指當(dāng)前訪問(wèn)地址附近的地址可能隨后被訪問(wèn)。處理器通過(guò)在內(nèi)存和核心之間增加緩存以利用局部性增強(qiáng)程序性能，這樣可以用遠(yuǎn)低于緩存的價(jià)格換取接近緩存的速度。

• 時(shí)間局部性：

代碼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)在被重復(fù)使用，因此更有可能留在緩存中。這個(gè)重新排列的代碼在使用x[i]時(shí)顯示更好的時(shí)間局部性。

• 空間局部性：

一個(gè)矩陣乘法的例子：

代碼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)于代碼一的性能。

兩者實(shí)現(xiàn)上的差異：

代碼2的b[k,j]是按行訪問(wèn)的，所以存在良好的空間局部性，cache line被充分利用。代碼1中，b [k，j]由列訪問(wèn)。由于行的存儲(chǔ)矩陣，因此對(duì)于每個(gè)緩存行加載，只有一個(gè)元素用于遍歷。

cache替換策略

Cache工作原理要求它盡量保存最新數(shù)據(jù)，當(dāng)從主存向Cache傳送一個(gè)新塊，而Cache中可用位置已被占滿時(shí)，就會(huì)產(chǎn)生Cache替換的問(wèn)題。

常用的替換算法有下面三種。

1. LFU

LFU（Least Frequently Used，最不經(jīng)常使用）算法將一段時(shí)間內(nèi)被訪問(wèn)次數(shù)最少的那個(gè)塊替換出去。每塊設(shè)置一個(gè)計(jì)數(shù)器，從0開(kāi)始計(jì)數(shù)，每訪問(wèn)一次，被訪塊的計(jì)數(shù)器就增1。當(dāng)需要替換時(shí)，將計(jì)數(shù)值最小的塊換出，同時(shí)將所有塊的計(jì)數(shù)器都清零。這種算法將計(jì)數(shù)周期限定在對(duì)這些特定塊兩次替換之間的間隔時(shí)間內(nèi)，不能嚴(yán)格反映近期訪問(wèn)情況，新調(diào)入的塊很容易被替換出去。

1. 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)起來(lái)比較復(fù)雜，系統(tǒng)開(kāi)銷較大。這種算法保護(hù)了剛調(diào)入Cache的新數(shù)據(jù)塊，具有較高的命中率。LRU算法不能肯定調(diào)出去的塊近期不會(huì)再被使用，所以這種替換算法不能算作最合理、最優(yōu)秀的算法。但是研究表明，采用這種算法可使Cache的命中率達(dá)到90%左右。

1. 隨機(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)單，速度較快，命中率較高。