為什么要有CPU Cache
CPU的處理速度和內(nèi)存的訪問速度差距越來越大涝焙，甚至可以達到上萬倍坠韩。
當(dāng)處理器發(fā)出內(nèi)存訪問請求時距潘，會先查看緩存內(nèi)是否有請求數(shù)據(jù)。如果存在（命中）只搁，則不經(jīng)訪問內(nèi)存直接返回該數(shù)據(jù)音比；如果不存在（失效），則要先把內(nèi)存中的相應(yīng)數(shù)據(jù)載入緩存氢惋，再將其返回處理器洞翩。
緩存之所以有效稽犁，主要是因為程序運行時對內(nèi)存的訪問呈現(xiàn)局部性（Locality）特征。這種局部性既包括空間局部性（Spatial Locality）骚亿，也包括時間局部性（Temporal Locality）已亥。有效利用這種局部性，緩存可以達到極高的命中率来屠。
為什么要有多級CPU Cache
熱點數(shù)據(jù)的體積越來越大虑椎，單純的增加一級緩存大小的性價比已經(jīng)很低了。
因此俱笛，就慢慢出現(xiàn)了在一級緩存(L1 Cache)和內(nèi)存之間又增加一層訪問速度和成本都介于兩者之間的二級緩存(L2 Cache)捆姜。
此外，又由于程序指令和程序數(shù)據(jù)的行為和熱點分布差異很大迎膜，因此L1 Cache也被劃分成
- L1i (i for instruction)
- L1d (d for data)
什么是Cache Line
Cache Line可以簡單的理解為CPU Cache中的最小緩存單位娇未。
目前主流的CPU Cache的Cache Line大小都是 64Bytes。
假設(shè)我們有一個 512Bytes 的一級緩存星虹，那么按照 64Bytes 的緩存單位大小來算零抬，這個一級緩存所能存放的緩存?zhèn)€數(shù)就是512/64 = 8個。具體參見下圖：
了解Cache Line的概念對我們程序猿有什么幫助宽涌？ 我們來看下面這個C語言中常用的循環(huán)優(yōu)化例子下面兩段代碼中平夜，第一段代碼在C語言中總是比第二段代碼的執(zhí)行速度要快。
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
int num;
//code
arr[i][j] = num;
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
int num;
//code
arr[j][i] = num;
}
}
CPU Cache 是如何存放數(shù)據(jù)的
緩存設(shè)計的一個關(guān)鍵決定是確保每個主存塊(chunk)能夠存儲在任何一個Cache Line里卸亮，或者只是其中一些Cache Line忽妒。
我們先來嘗試回答一下那么這個問題：
假設(shè)我們有一塊4MB的區(qū)域用于緩存，每個緩存對象的唯一標(biāo)識是它所在的物理內(nèi)存地址兼贸。每個緩存對象大小是64Bytes段直，所有可以被緩存對象的大小總和（即物理內(nèi)存總大小）為4GB溶诞。那么我們該如何設(shè)計這個緩存鸯檬？
最簡單的思想：
把Cache設(shè)計成一個Hash數(shù)組。內(nèi)存地址的Hash值作為數(shù)組的Index螺垢，緩存對象的值作為數(shù)組的Value喧务。每次存取時，都把地址做一次Hash然后找到Cache中對應(yīng)的位置操作即可枉圃。 這樣的設(shè)計方式在高等語言中很常見功茴，也顯然很高效。因為Hash值的計算雖然耗時(10000個CPU Cycle左右)孽亲，但是相比程序中其他操作（上百萬的CPU Cycle）來說可以忽略不計坎穿。而對于CPU Cache來說，本來其設(shè)計目標(biāo)就是在幾十CPU Cycle內(nèi)獲取到數(shù)據(jù)。如果訪問效率是百萬Cycle這個等級的話玲昧，還不如到Memory直接獲取數(shù)據(jù)犯祠。當(dāng)然，更重要的原因是在硬件上要實現(xiàn)Memory Address Hash的功能在成本上是非常高的酌呆。
為什么Cache不能做成Fully Associative
Fully Associative 字面意思是全關(guān)聯(lián)衡载。
在CPU Cache中的含義是：如果在一個Cache集內(nèi)，任何一個內(nèi)存地址的數(shù)據(jù)可以被緩存在任何一個Cache Line里隙袁，那么我們成這個cache是Fully Associative痰娱。
從定義中我們可以得出這樣的結(jié)論：給到一個內(nèi)存地址，要知道他是否存在于Cache中菩收，需要遍歷所有Cache Line并比較緩存內(nèi)容的內(nèi)存地址梨睁。而Cache的本意就是為了在盡可能少得CPU Cycle內(nèi)取到數(shù)據(jù)。那么想要設(shè)計一個快速的Fully Associative的Cache幾乎是不可能的娜饵。
每個內(nèi)存塊能夠被映射到任意一個緩存槽坡贺。操作效果上相當(dāng)于一個散列表。
直接映射緩存會引發(fā)沖突——當(dāng)多個值競爭同一個緩存槽箱舞，它們將相互驅(qū)逐對方遍坟，導(dǎo)致命中率暴跌。另一方面晴股，完全關(guān)聯(lián)緩存過于復(fù)雜愿伴，并且硬件實現(xiàn)上昂貴。
為什么Cache不能做成Direct Mapped
和Fully Associative完全相反电湘，使用Direct Mapped模式的Cache給定一個內(nèi)存地址隔节，就唯一確定了一條Cache Line。
設(shè)計復(fù)雜度低且速度快寂呛。那么為什么Cache不使用這種模式呢怎诫？
讓我們來想象這么一種情況：一個擁有 1M L2 Cache的32位CPU，每條Cache Line的大小為 64Bytes贷痪。
那么整個L2Cache被劃為了 1M/64=16384 條Cache Line幻妓。
我們?yōu)槊織lCache Line從0開始編上號。同時32位CPU所能管理的內(nèi)存地址范圍是 2^32=4G呢诬，那么Direct Mapped模式下涌哲，內(nèi)存也被劃為 4G/16384=256K 的小份胖缤。也就是說每256K的內(nèi)存地址共享一條Cache Line尚镰。
被映射到同一 Cache Line 上的兩個內(nèi)存塊是不能同時換入緩存的。
但是哪廓，這種模式下每條Cache Line的使用率如果要做到接近100%狗唉，就需要操作系統(tǒng)對于內(nèi)存的分配和訪問在地址上也是近乎平均的。而與我們的意愿相反涡真，為了減少內(nèi)存碎片和實現(xiàn)便捷分俯，操作系統(tǒng)更多的是連續(xù)集中的使用內(nèi)存肾筐。這樣會出現(xiàn)的情況就是0-1000號這樣的低編號Cache Line由于內(nèi)存經(jīng)常被分配并使用，而16000號以上的Cache Line由于內(nèi)存鮮有進程訪問缸剪，幾乎一直處于空閑狀態(tài)吗铐。這種情況下，本來就寶貴的1M二級CPU緩存杏节，使用率也許50%都無法達到唬渗。
什么是N-Way Set Associative N路組相聯(lián)
為了避免以上兩種設(shè)計模式的缺陷，N-Way Set Associative緩存就出現(xiàn)了奋渔。
他的原理是把一個緩存按照N個Cache Line作為一組（set）镊逝，緩存按組劃為等分。
這樣一個64位系統(tǒng)的內(nèi)存地址在 4MB 二級緩存中就劃成了三個部分（見下圖）：
另 N=16嫉鲸，即16路撑蒜。
- 低位
6bit表示在Cache Line中的偏移量（Cache Line Offset） - 中間
12bit表示Cache組號（Set Index） - 高位
46bit就是內(nèi)存地址的唯一id。
這樣的設(shè)計相較前兩種設(shè)計有以下兩點好處：
- 給定一個內(nèi)存地址可以唯一對應(yīng)一個set玄渗，對于set中只需遍歷16個元素就可以確定對象是否在緩存中（Full Associative中比較次數(shù)隨內(nèi)存大小線性增加）
- 每
2^18(256K)*16(way)=4M的連續(xù)熱點數(shù)據(jù)才會導(dǎo)致一個set內(nèi)的conflict（Direct Mapped中512K的連續(xù)熱點數(shù)據(jù)就會出現(xiàn)conflict）
為什么N-Way Set Associative的Set段是從低位而不是高位開始的：
由于內(nèi)存的訪問通常是大片連續(xù)的座菠，或者是因為在同一程序中而導(dǎo)致地址接近的（即這些內(nèi)存地址的高位都是一樣的）。所以如果把內(nèi)存地址的高位作為set index的話藤树，那么短時間的大量內(nèi)存訪問都會因為set index相同而落在同一個set index中辈灼，從而導(dǎo)致cache conflicts使得L2, L3 Cache的命中率低下，影響程序的整體執(zhí)行效率也榄。
了解N-Way Set的概念后巡莹，我們不難得出以下結(jié)論：2^(6Bits <Cache Line Offset> + 12Bits <Set Index>) = 2^18 = 256K。即在連續(xù)的內(nèi)存地址中每 256K 都會出現(xiàn)一個處于同一個Cache Set中的緩存對象甜紫。
因此Cache Line對應(yīng)的物理地址凡是以262,144字節(jié)(4096*64)的倍數(shù)區(qū)分的降宅，將競爭同一個Cache Line。
Cache淘汰策略
常見的淘汰策略主要有LRU和Random兩種囚霸。通常意義下LRU對于Cache的命中率會比Random更好腰根，所以CPU Cache的淘汰策略選擇的是LRU。當(dāng)然也有些實驗顯示在Cache Size較大的時候Random策略會有更高的命中率拓型。
Cache寫操作
為了和下級存儲（如內(nèi)存）保持?jǐn)?shù)據(jù)一致性额嘿，就必須把數(shù)據(jù)更新適時傳播下去。這種傳播通過回寫來完成劣挫。一般有兩種回寫策略：
寫回（Write back）：
寫回是指册养，僅當(dāng)一個緩存塊需要被替換回內(nèi)存時，才將其內(nèi)容寫入內(nèi)存压固。如果緩存命中球拦，則總是不用更新內(nèi)存。為了減少內(nèi)存寫操作，緩存塊通常還設(shè)有一個臟位（dirty bit）坎炼，用以標(biāo)識該塊在被載入之后是否發(fā)生過更新愧膀。如果一個緩存塊在被置換回內(nèi)存之前從未被寫入過，則可以免去回寫操作谣光。
寫回的優(yōu)點是節(jié)省了大量的寫操作檩淋。這主要是因為，對一個數(shù)據(jù)塊內(nèi)不同單元的更新僅需一次寫操作即可完成萄金。這種內(nèi)存帶寬上的節(jié)省進一步降低了能耗狼钮，因此頗適用于嵌入式系統(tǒng)。寫通（Write through）：
寫通是指捡絮，每當(dāng)緩存接收到寫數(shù)據(jù)指令熬芜，都直接將數(shù)據(jù)寫回到內(nèi)存。如果此數(shù)據(jù)地址也在緩存中福稳，則必須同時更新緩存涎拉。由于這種設(shè)計會引發(fā)造成大量寫內(nèi)存操作，有必要設(shè)置一個緩沖來減少硬件沖突的圆。這個緩沖稱作寫緩沖器（Write buffer）鼓拧，通常不超過4個緩存塊大小。不過越妈，出于同樣的目的季俩，寫緩沖器也可以用于寫回型緩存。
寫通較寫回易于實現(xiàn)梅掠，并且能更簡單地維持?jǐn)?shù)據(jù)一致性酌住。
