CACHE的一致性

Cache的一致性有這么幾個(gè)層面

1.一個(gè)CPU的icache和dcache的同步問題

2.多個(gè)CPU各自的cache同步問題

3.CPU與設(shè)備（其實(shí)也可能是個(gè)異構(gòu)處理器，不過在Linux運(yùn)行的CPU眼里，都是設(shè)備，都是DMA）的cache同步問題

先看一下ICACHE和DCACHE同步問題。由于程序的運(yùn)行而言，指令流的都流過icache，而指令中涉及到的數(shù)據(jù)流經(jīng)過dcache。所以對(duì)于自修改的代碼（Self-Modifying Code）而言，比如我們修改了內(nèi)存p這個(gè)位置的代碼（典型多見于JIT compiler），這個(gè)時(shí)候我們是通過store的方式去寫的p，所以新的指令會(huì)進(jìn)入dcache。但是我們接下來去執(zhí)行p位置的指令的時(shí)候，icache里面可能命中的是修改之前的指令。

所以這個(gè)時(shí)候軟件需要把dcache的東西clean出去，然后讓icache invalidate，這個(gè)開銷顯然還是比較大的。

但是，比如ARM64的N1處理器，它支持硬件的icache同步，詳見文檔：The Arm Neoverse N1 Platform: Building Blocks for the Next-Gen Cloud-to-Edge Infrastructure SoC

特別注意畫紅色的幾行。軟件維護(hù)的成本實(shí)際很高，還涉及到icache的invalidation向所有核廣播的動(dòng)作。

接下來的一個(gè)問題就是多個(gè)核之間的cache同步。下面是一個(gè)簡化版的處理器，CPU_A和B共享了一個(gè)L3，CPU_C和CPU_D共享了一個(gè)L3。實(shí)際的硬件架構(gòu)由于涉及到NUMA，會(huì)比這個(gè)更加復(fù)雜，但是這個(gè)圖反映層級(jí)關(guān)系是足夠了。

比如CPU_A讀了一個(gè)地址p的變量？CPU_B、C、D又讀，難道B,C,D又必須從RAM里面經(jīng)過L3,L2,L1再讀一遍嗎？這個(gè)顯然是沒有必要的，在硬件上，cache的snooping控制單元，可以協(xié)助直接把CPU_A的p地址cache拷貝到CPU_B、C和D的cache。

這樣A-B-C-D都得到了相同的p地址的棕色小球。

假設(shè)CPU B這個(gè)時(shí)候，把棕色小球?qū)懗杉t色，而其他CPU里面還是棕色，這樣就會(huì)不一致了：

這個(gè)時(shí)候怎么辦？這里面顯然需要一個(gè)協(xié)議，典型的多核cache同步協(xié)議有MESI和MOESI。MOESI相對(duì)MESI有些細(xì)微的差異，不影響對(duì)全局的理解。下面我們重點(diǎn)看MESI協(xié)議。

MESI協(xié)議定義了4種狀態(tài)：

M（Modified）:當(dāng)前cache的內(nèi)容有效，數(shù)據(jù)已被修改而且與內(nèi)存中的數(shù)據(jù)不一致，數(shù)據(jù)只在當(dāng)前cache里存在；類似RAM里面是棕色球，B里面是紅色球（CACHE與RAM不一致），A、C、D都沒有球。

E（Exclusive）：當(dāng)前cache的內(nèi)容有效，數(shù)據(jù)與內(nèi)存中的數(shù)據(jù)一致，數(shù)據(jù)只在當(dāng)前cache里存在；類似RAM里面是棕色球，B里面是棕色球（RAM和CACHE一致），A、C、D都沒有球。

S（Shared）：當(dāng)前cache的內(nèi)容有效，數(shù)據(jù)與內(nèi)存中的數(shù)據(jù)一致，數(shù)據(jù)在多個(gè)cache里存在。類似如下圖，在CPU A-B-C里面cache的棕色球都與RAM一致。

I（Invalid）：當(dāng)前cache無效。前面三幅圖里面cache沒有球的那些都是屬于這個(gè)情況。

然后它有個(gè)狀態(tài)機(jī)

這個(gè)狀態(tài)機(jī)比較難記，死記硬背是記不住的，也沒必要記，它講的cache原先的狀態(tài)，經(jīng)過一個(gè)硬件在本cache或者其他cache的讀寫操作后，各個(gè)cache的狀態(tài)會(huì)如何變遷。所以，硬件上不僅僅是監(jiān)控本CPU的cache讀寫行為，還會(huì)監(jiān)控其他CPU的。只需要記住一點(diǎn)：這個(gè)狀態(tài)機(jī)是為了保證多核之間cache的一致性，比如一個(gè)干凈的數(shù)據(jù)，可以在多個(gè)CPU的cache share，這個(gè)沒有一致性問題；但是，假設(shè)其中一個(gè)CPU寫過了，比如A-B-C本來是這樣：

然后B被寫過了：

這樣A、C的cache實(shí)際是過時(shí)的數(shù)據(jù)，這是不允許的。這個(gè)時(shí)候，硬件會(huì)自動(dòng)把A、C的cache invalidate掉，不需要軟件的干預(yù)，A、C其實(shí)變地相當(dāng)于不命中這個(gè)球了：

這個(gè)時(shí)候，你可能會(huì)繼續(xù)問，如果C要讀這個(gè)球呢？它目前的狀態(tài)在B里面是modified的，而且與RAM不一致，這個(gè)時(shí)候，硬件會(huì)把紅球clean，然后B、C、RAM變地一致，B、C的狀態(tài)都變化為S（Shared）：

這一系列的動(dòng)作雖然由硬件完成，但是對(duì)軟件而言不是免費(fèi)的，因?yàn)樗馁M(fèi)了時(shí)間。如果編程的時(shí)候不注意，引起了硬件的大量cache同步行為，則程序的效率可能會(huì)急劇下降。

為了讓大家直觀感受到這個(gè)cache同步的開銷，下面我們寫一個(gè)程序，這個(gè)程序有2個(gè)線程，一個(gè)寫變量，一個(gè)讀變量：

這個(gè)程序里，x和y都是cacheline對(duì)齊的，這個(gè)程序的thread1的寫，會(huì)不停地與thread2的讀，進(jìn)行cache同步。

它的執(zhí)行時(shí)間為：

$ time ./a.out 
real  0m3.614s
user  0m7.021s
sys0m0.004s

它在2個(gè)CPU上的userspace共運(yùn)行了7.021秒，累計(jì)這個(gè)程序從開始到結(jié)束的對(duì)應(yīng)真實(shí)世界的時(shí)間是3.614秒（就是從命令開始到命令結(jié)束的時(shí)間）。

如果我們把程序改一句話，把thread2里面的c = x改為c = y，這樣2個(gè)線程在2個(gè)CPU運(yùn)行的時(shí)候，讀寫的是不同的cacheline，就沒有這個(gè)硬件的cache同步開銷了：

它的運(yùn)行時(shí)間：

$ time ./b.out 
real  0m1.820s
user  0m3.606s
sys0m0.008s

現(xiàn)在只需要1.8秒，幾乎減小了一半。

感覺前面那個(gè)a.out，雙核的幫助甚至都不大。如果我們改為單核跑呢？

$ time taskset -c 0 ./a.out 
real  0m3.299s
user  0m3.297s
sys0m0.000s

它單核跑，居然只需要3.299秒跑完，而雙核跑，需要3.614s跑完。單核跑完這個(gè)程序，甚至比雙核還快，有沒有驚掉下巴？！！！因?yàn)閱魏死锩鏇]有cache同步的開銷。

下一個(gè)cache同步的重大問題，就是設(shè)備與CPU之間。如果設(shè)備感知不到CPU的cache的話（下圖中的紅色數(shù)據(jù)流向不經(jīng)過cache），這樣，做DMA前后，CPU就需要進(jìn)行相關(guān)的cacheclean和invalidate的動(dòng)作，軟件的開銷會(huì)比較大。

這些軟件的動(dòng)作，若我們?cè)贚inux編程的時(shí)候，使用的是streaming DMA APIs的話，都會(huì)被類似這樣的API自動(dòng)搞定：

dma_map_single()
dma_unmap_single()
dma_sync_single_for_cpu()
dma_sync_single_for_device()
dma_sync_sg_for_cpu()
dma_sync_sg_for_device()

如果是使用的dma_alloc_coherent() API呢，則設(shè)備和CPU之間的buffer是cache一致的，不需要每次DMA進(jìn)行同步。對(duì)于不支持硬件cache一致性的設(shè)備而言，很可能dma_alloc_coherent()會(huì)把CPU對(duì)那段DMA buffer的訪問設(shè)置為uncachable的。

這些API把底層的硬件差異封裝掉了，如果硬件不支持CPU和設(shè)備的cache同步的話，延時(shí)還是比較大的。那么，對(duì)于底層硬件而言，更好的實(shí)現(xiàn)方式，應(yīng)該仍然是硬件幫我們來搞定。比如我們需要修改總線協(xié)議，延伸紅線的觸角：

當(dāng)設(shè)備訪問RAM的時(shí)候，可以去snoop CPU的cache：

如果做內(nèi)存到外設(shè)的DMA，則直接從CPU的cache取modified的數(shù)據(jù)；

如果做外設(shè)到內(nèi)存的DMA，則直接把CPU的cache invalidate掉。

這樣，就實(shí)現(xiàn)硬件意義上的cache同步。當(dāng)然，硬件的cache同步，還有一些其他方法，原理上是類似的。注意，這種同步仍然不是免費(fèi)的，它仍然會(huì)消耗bus cycles的。實(shí)際上，cache的同步開銷還與距離相關(guān)，可以說距離越遠(yuǎn)，同步開銷越大，比如下圖中A、B的同步開銷比A、C小。

對(duì)于一個(gè)NUMA服務(wù)器而言，跨NUMA的cache同步開銷顯然是要比NUMA內(nèi)的同步開銷大。

意識(shí)到CACHE的編程

通過上一節(jié)的代碼，讀者應(yīng)該意識(shí)到了cache的問題不處理好，程序的運(yùn)行性能會(huì)急劇下降。所以意識(shí)到cache的編程，對(duì)程序員是至關(guān)重要的。

從CPU流水線的角度講，任何的內(nèi)存訪問延遲都可以簡化為如下公式：

Average Access Latency = Hit Time + Miss Rate × Miss Penalty

cache miss會(huì)導(dǎo)致CPU的stall狀態(tài)，從而影響性能。現(xiàn)代CPU的微架構(gòu)分了frontend和backend。frontend負(fù)責(zé)fetch指令給backend執(zhí)行，backend執(zhí)行依賴運(yùn)算能力和Memory子系統(tǒng)（包括cache）延遲。

backend執(zhí)行中訪問數(shù)據(jù)導(dǎo)致的cache miss會(huì)導(dǎo)致backend stall，從而降低IPC（instructions per cycle）。減小cache的miss，實(shí)際上是一個(gè)軟硬件協(xié)同設(shè)計(jì)的任務(wù)。比如硬件方面，它支持預(yù)取prefetch，通過分析cache miss的pattern，硬件可以提前預(yù)取數(shù)據(jù)，在流水線需要某個(gè)數(shù)據(jù)前，提前先取到cache，從而CPU流水線跑到需要它的時(shí)候，不再miss。當(dāng)然，硬件不一定有那么聰明，也許它可以學(xué)會(huì)一些簡單的pattern。但是，對(duì)于復(fù)雜的無規(guī)律的數(shù)據(jù)，則可能需要軟件通過預(yù)取指令，來暗示CPU進(jìn)行預(yù)取。

cache預(yù)取

比如在ARM處理器上就有一條指令叫pld，prefetch可以用pld指令：

static inline void prefetch(const void *ptr)
{
        __asm__ __volatile__(
                "pld	%a0"
                :: "p" (ptr));
}

眼見為實(shí)，我們隨便從Linux內(nèi)核里面找一個(gè)commit：

因?yàn)槲覀儚腤iFi收到了一個(gè)skb，我們很快就要訪問這個(gè)skb里面的數(shù)據(jù)來進(jìn)行packet的分類以及交給IP stack處理了，不如我們先prefetch一下，這樣后面等需要訪問這個(gè)skb->data的時(shí)候，流水線可以直接命中cache，從而不打斷。

預(yù)取的原理有點(diǎn)類似今天星期五，咱們?cè)谏虾ffice，下周一需要北京分公司的人來上海office開會(huì)。于是，我們通知北京office的人周末坐飛機(jī)過來，這樣周一開會(huì)的時(shí)候就不必等他們了。不預(yù)取的情況下，會(huì)議開始后，再等北京的人飛過來，會(huì)導(dǎo)致stall狀態(tài)。

任何東西最終還是要落實(shí)到代碼，talk is cheap，show me the code。下面這個(gè)是經(jīng)典的二分查找法代碼，這個(gè)代碼是網(wǎng)上抄的。

特別留意ifdef DO_PREFETCH包著的代碼，它提前預(yù)取了下次的中間值。我們來對(duì)比下，不預(yù)取和預(yù)取情況下，這個(gè)同樣的代碼執(zhí)行時(shí)間的差異。先把cpufreq的影響盡可能關(guān)閉掉，設(shè)置為performance:

barry@barry-HP-ProBook-450-G7:~$ sudo cpupower frequency-set 
--governor performance
Setting cpu: 0
Setting cpu: 1
Setting cpu: 2
Setting cpu: 3
Setting cpu: 4
Setting cpu: 5
Setting cpu: 6
Setting cpu: 7

然后我們來對(duì)比差異：

開啟prefetch執(zhí)行時(shí)間大約10s, 不prefetch的情況下，11.6s執(zhí)行完成，性能提升大約14%，所以周末坐飛機(jī)太重要了！

現(xiàn)在我們來通過基于perf的pmu-tools（下載地址：https://github.com/andikleen/pmu-tools)，對(duì)上面的程序進(jìn)行topdown分析，分析的時(shí)候，為了盡可能減小其他因子的影響，我們把程序通過taskset運(yùn)行到CPU0。

先看不prefetch的情況，很明顯，程序是backend_bound的，其中DRAM_Bound占比大，達(dá)到75.8%。

開啟prefetch的情況呢？程序依然是backend_bound的，其中，backend bound的主體依然是DRAM_Bound，但是比例縮小到了60.7%。

DRAM_Bound主要對(duì)應(yīng)cycle_activity.stalls_l3_miss事件，我們通過perf stat來分別進(jìn)行搜集：

我們看到，執(zhí)行prefetch情況下，指令的條數(shù)明顯多了，但是它的insn per cycle變大了，所以總的時(shí)間cycles反而減小。其中最主要的原因是cycle_activity.stalls_l3_miss變小了很多次。

這個(gè)時(shí)候，我們可以進(jìn)一步通過錄制mem_load_retired.l3_miss來分析究竟代碼哪里出了問題，先看noprefetch情況：

焦點(diǎn)在main函數(shù)：

繼續(xù)annotate一下：

明顯問題出在array[mid] < key這句話這里。做prefetch的情況下呢？

main的占比明顯變小了（99.93% -> 80.00%）：

繼續(xù)annotate一下：

熱點(diǎn)被分散了，預(yù)取緩解了Memory_Bound的情況。

避免false sharing

前面我們提到過，數(shù)據(jù)如果在一個(gè)cacheline，被多核訪問的時(shí)候，多核間運(yùn)行的cache一致性協(xié)議，會(huì)導(dǎo)致cacheline在多核間的同步。這個(gè)同步會(huì)有很大的延遲，是工程里著名的false sharing問題。

比如下面一個(gè)結(jié)構(gòu)體

structs
{
inta;
intb;
}

如果1個(gè)線程讀寫a，另外一個(gè)線程讀寫b，那么兩個(gè)線程就有機(jī)會(huì)在不同的核，于是產(chǎn)生cacheline同步行為的來回顛簸。但是，如果我們把a(bǔ)和b之間padding一些區(qū)域，就可以把這兩個(gè)纏繞在一起的人拉開：

struct s
{
    int a;
charpadding[cacheline_size-sizeof(int)];
    int b;
}

因此，在實(shí)際的工程中，我們經(jīng)常看到有人對(duì)數(shù)據(jù)的位置進(jìn)行移位，或者在2個(gè)可能引起false sharing的數(shù)據(jù)間填充數(shù)據(jù)進(jìn)行padding。這樣的代碼在內(nèi)核不甚枚舉，我們隨便找一個(gè)：

它特別提到在tw_count后面60個(gè)字節(jié)（L1_CACHE_BYTES - sizeof(atomic_t)）的padding，從而避免false sharing：

下面這個(gè)則是通過移動(dòng)結(jié)構(gòu)體內(nèi)部成員的位置，相關(guān)數(shù)據(jù)的cacheline分開的：

這個(gè)改動(dòng)有明顯的性能提升，最高可達(dá)9.9%。代碼里面也有明顯地注釋，usage和parent原先靠地太近，一個(gè)頻繁寫，一個(gè)頻繁讀。移開了2邊互相不打架了：

把理論和代碼能對(duì)上的感覺真TNND爽。無論是996,還是007,都必須留些時(shí)間來思考，來讓理論和實(shí)踐結(jié)合，否則，就變成漫無目的的內(nèi)卷，這樣一定會(huì)卷輸?shù)摹?nèi)卷并不可悲，可悲的是卷不贏別人。

1. 什么是CPU Cache？

如圖所示：

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

2. 為什么要有Cache？為什么要有多級(jí)Cache？

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

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

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

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

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

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

那CPU訪問各個(gè)Cache的速度如何呢？

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

CPU多級(jí)緩存架構(gòu)大體如下：

L1 Cache是最離CPU最近的，它容量最小，速度最快，每個(gè)CPU都有L1 Cache，見上圖，其實(shí)每個(gè)CPU都有兩個(gè)L1 Cache，一個(gè)是L1D Cache，用于存取數(shù)據(jù)，另一個(gè)是L1I Cache，用于存取指令。

L2 Cache容量較L1大，速度較L1較慢，每個(gè)CPU也都有一個(gè)L2 Cache。L2 Cache制造成本比L1 Cache更低，它的作用就是存儲(chǔ)那些CPU需要用到的且L1 Cache miss的數(shù)據(jù)。

L3 Cache容量較L2大，速度較L2慢，L3 Cache不同于L1 Cache和L2 Cache，它是所有CPU共享的，可以把它理解為速度更快，容量更小的內(nèi)存。

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

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

4. Cache Line？

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

5. 寫入策略

Cache的寫入策略有兩種，分別是WriteThrough（直寫模式）和WriteBack（回寫模式）。 直寫模式：在數(shù)據(jù)更新時(shí)，將數(shù)據(jù)同時(shí)寫入內(nèi)存和Cache，該策略操作簡單，但是因?yàn)槊看味家獙懭雰?nèi)存，速度較慢。 回寫模式：在數(shù)據(jù)更新時(shí)，只將數(shù)據(jù)寫入到Cache中，只有在數(shù)據(jù)被替換出Cache時(shí)，被修改的數(shù)據(jù)才會(huì)被寫入到內(nèi)存中，該策略因?yàn)椴恍枰獙懭氲絻?nèi)存中，所以速度較快。但數(shù)據(jù)僅寫在了Cache中，Cache數(shù)據(jù)和內(nèi)存數(shù)據(jù)不一致，此時(shí)如果有其它CPU訪問數(shù)據(jù)，就會(huì)讀到臟數(shù)據(jù)，出現(xiàn)bug，所以這里需要用到Cache的一致性協(xié)議來保證CPU讀到的是最新的數(shù)據(jù)。

6. 什么是Cache一致性呢？

多個(gè)CPU對(duì)某塊內(nèi)存同時(shí)讀寫，就會(huì)引起沖突的問題，被稱為Cache一致性問題。

有這樣一種情況：

a.CPU1讀取了一個(gè)字節(jié)offset，該字節(jié)和相鄰的數(shù)據(jù)就都會(huì)被寫入到CPU1的Cache. b.此時(shí)CPU2也讀取相同的字節(jié)offset，這樣CPU1和CPU2的Cache就都擁有同樣的數(shù)據(jù)。 c.CPU1修改了offset這個(gè)字節(jié)，被修改后，這個(gè)字節(jié)被寫入到CPU1的Cache中，但是沒有被同步到內(nèi)存中。 d.CPU2 需要訪問offset這個(gè)字節(jié)數(shù)據(jù)，但是由于最新的數(shù)據(jù)并沒有被同步到內(nèi)存中，所以CPU2 訪問的數(shù)據(jù)不是最新的數(shù)據(jù)。

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

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

■M：代表已修改（Modified） 緩存行是臟的（dirty），與主存的值不同。如果別的CPU內(nèi)核要讀主存這塊數(shù)據(jù)，該緩存行必須回寫到主存，狀態(tài)變?yōu)楣蚕恚⊿）.

■E：代表獨(dú)占（Exclusive） 緩存行只在當(dāng)前緩存中，但是干凈的（clean）--緩存數(shù)據(jù)同于主存數(shù)據(jù)。當(dāng)別的緩存讀取它時(shí)，狀態(tài)變?yōu)楣蚕恚⊿）；當(dāng)前寫數(shù)據(jù)時(shí)，變?yōu)橐研薷模∕）狀態(tài)。

■S：代表共享（Shared） 緩存行也存在于其它緩存中且是干凈（clean）的。緩存行可以在任意時(shí)刻拋棄。

■I：代表已失效（Invalidated） 緩存行是臟的（dirty），無效的。

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

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

7. Cache與主存的映射關(guān)系？

直接映射

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

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

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

全相連映射

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

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

全相連映射的主存結(jié)構(gòu)就很簡單啦，將CPU發(fā)出的內(nèi)存地址的塊號(hào)部分與Cache所有行的標(biāo)記進(jìn)行比較，如果有相同的，則Cache命中，從Cache中讀取，如果找不到，則沒有命中，從主存中讀取。

組相連映射

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

主存中的各塊與Cache的組號(hào)之間有固定的映射關(guān)系，但可自由映射到對(duì)應(yīng)Cache組中的任何一塊。例如，主存中的第0塊、第8塊……均映射于Cache的第0組，但可映射到Cache第0組中的第0塊或第1塊；主存的第1塊、第9塊……均映射于Cache的第1組，但可映射到Cache第1組中的第2塊或第3塊。

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

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

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

8. Cache的替換策略？

Cache的替換策略想必大家都知道，就是LRU策略，即最近最少使用算法，選擇未使用時(shí)間最長的Cache替換。

9. 如何巧妙利用CPU Cache編程？

constintrow=1024;
constintcol=1024;
intmatrix[row][col];


//按行遍歷
intsum_row=0;
for(intr=0;r

	

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

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

	    責(zé)任編輯：彭菁