局部性原理
一個(gè)編寫良好的計(jì)算機(jī)程序，它們傾向于引用鄰近于其他最近引用過的數(shù)據(jù)項(xiàng)的數(shù)據(jù)項(xiàng)，或者最近引用過的數(shù)據(jù)項(xiàng)本身，我們稱這種程序具有良好的局部性。這種傾向性，我們稱之為局部性原理，是一個(gè)持久的概念，對(duì)于硬件和軟件系統(tǒng)的設(shè)計(jì)和性能都有著極大的影響。
在一個(gè)具有良好時(shí)間局部性的程序中，被引用過一次的存儲(chǔ)器在不遠(yuǎn)的將來會(huì)被再次引用。在一個(gè)具有良好空間局部性的程序中，如果一個(gè)存儲(chǔ)器位置被引用了一次，那么程序很可能在不遠(yuǎn)的將來引用附近的一個(gè)存儲(chǔ)器的位置。
在硬件層，局部性原理允許計(jì)算機(jī)設(shè)計(jì)者通過引入稱為高速緩存存儲(chǔ)器的小而快速的存儲(chǔ)器來保存最近被引用的指令和數(shù)據(jù)項(xiàng)，從而提高對(duì)主存的訪問速度。在操作系統(tǒng)級(jí)，局部性原理允許系統(tǒng)使用主存作為虛擬地址空間最近被引用塊的高速緩存。
Cache
cache，中譯名高速緩沖存儲(chǔ)器，其作用是為了更好的利用局部性原理，減少CPU訪問主存的次數(shù)。簡(jiǎn)單地說，CPU正在訪問的指令和數(shù)據(jù)，其可能會(huì)被以后多次訪問到，或者是該指令和數(shù)據(jù)附近的內(nèi)存區(qū)域，也可能會(huì)被多次訪問。因此，第一次訪問這一塊區(qū)域時(shí)，將其復(fù)制到cache中，以后訪問該區(qū)域的指令或者數(shù)據(jù)時(shí)，就不用再?gòu)闹鞔嬷腥〕觥?/p>
下圖顯示了典型的計(jì)算機(jī)或者服務(wù)器組成中存儲(chǔ)的層次結(jié)構(gòu)。
從上圖中也可以看出Cache彌補(bǔ)了CPU與內(nèi)存之間的巨大訪問速度差異，而SCM彌補(bǔ)了內(nèi)存和磁盤之間的巨大訪問速度差異。
Cache組成
現(xiàn)代CPU大多數(shù)都采用多級(jí)緩存機(jī)制，常見是3級(jí)緩存機(jī)制，即L1 Cache,L2 Cache,L3 Cache。L1 Cache緊連著CPU，L2 Cache接著L1 Cache，L3 Cache連接著L2 Cache和內(nèi)存。
下圖是Power9 CPU的一個(gè)示意圖，可以看出L1 Cache/L2 Cache/L3 Cache的分布。
其中L1 Cache是在每個(gè)Core的內(nèi)部。
L1 Cache
L1 Cache是比較特殊的，因?yàn)樗钟蓴?shù)據(jù)緩存L1 Data Cache俗稱D-Cache和指令緩存L1 Instruction Cache俗稱I-Cache組成。其中I-Cache還承擔(dān)著分支預(yù)取的功能，尤其在類似循環(huán)操作的時(shí)候，提前把下一個(gè)指令放到I-Cache中，這時(shí)I-Cache看起來很像Input-Cache。
Inclusive Cache vs Non-Inclusive Cache
為了讓問題簡(jiǎn)單化，只考慮L1 Cache和L2 Cache。
Inclusive Cache
簡(jiǎn)單說來，如果L2 Cache（low level cache）包含所有L1 Cache(high level cache)中的數(shù)據(jù)，那么把L2 Cache叫做L1 Cache的Inclusive Cache(全包含Cache)。
上圖L2 Cache是Inclusive Cache，如果Y在L2 Cache中不再存在，L2 Cache會(huì)通知L1 Cache，把Y也刪除。
Non-Inclusive Cache
簡(jiǎn)單說來，如果L2 Cache(low level cache)，只包含L1 Cache(high level cache)中沒有的數(shù)據(jù)，那么把L2 Cache叫做L1 Cache的Non-Inclusive Cache(非包含Cache)。
上圖L2 cache是Non-Inclusive Cache。L2 Cache只有L1 Cache中沒有的數(shù)據(jù)。
Inclusive Cache多了一個(gè)“Back Invalidation”，很多時(shí)候，Inclusive Cache會(huì)慢一點(diǎn)。
一個(gè)典型的代表是Intel Skylake對(duì)于L3 Cache的修改，將其從之前的Inclusive Cache修改為Non-Inclusive Cache。
Cache Line
cache line：每次內(nèi)存和CPU緩存之間交換數(shù)據(jù)都是固定大小，cache line就表示這個(gè)固定的長(zhǎng)度。
cache set：一個(gè)或多個(gè)cache line組成cache set,也叫cache row。
Cache Hit/Cache Miss
cache hit：緩存命中，查找的地址在cache中。
cache miss：緩存未命中，查找的地址不在cache中。
hit rate：命中率，cache hit/（cache hit+cache miss）
Cache分配策略
Cache Allocation Policy是指我們什么情況下應(yīng)該為數(shù)據(jù)分配cache line。cache分配策略分為讀和寫兩種情況。
讀分配(read allocation)
當(dāng)CPU讀數(shù)據(jù)時(shí)，發(fā)生cache缺失，這種情況下都會(huì)分配一個(gè)cache line緩存從主存讀取的數(shù)據(jù)。默認(rèn)情況下，cache都支持讀分配。
寫分配(write allocation)
當(dāng)CPU寫數(shù)據(jù)發(fā)生cache缺失時(shí)，才會(huì)考慮寫分配策略。當(dāng)我們不支持寫分配的情況下，寫指令只會(huì)更新主存數(shù)據(jù)，然后就結(jié)束了。當(dāng)支持寫分配的時(shí)候，我們首先從主存中加載數(shù)據(jù)到cache line中（相當(dāng)于先做個(gè)讀分配動(dòng)作），然后會(huì)更新cache line中的數(shù)據(jù)。
Cache更新策略
Cache Update Policy是指當(dāng)發(fā)生cache命中時(shí)，寫操作應(yīng)該如何更新數(shù)據(jù)。cache更新策略分成兩種：寫直通和回寫。
寫直通(write through)
當(dāng)CPU執(zhí)行store指令并在cache命中時(shí)，我們更新cache中的數(shù)據(jù)并且更新主存中的數(shù)據(jù)。cache和主存的數(shù)據(jù)始終保持一致。
寫回(write back)
當(dāng)CPU執(zhí)行store指令并在cache命中時(shí)，我們只更新cache中的數(shù)據(jù)。并且每個(gè)cache line中會(huì)有一個(gè)bit位記錄數(shù)據(jù)是否被修改過，稱之為dirty bit。我們會(huì)將dirty bit置位。主存中的數(shù)據(jù)只會(huì)在cache line被替換或者顯示的clean操作時(shí)更新。因此，主存中的數(shù)據(jù)可能是未修改的數(shù)據(jù)，而修改的數(shù)據(jù)躺在cache中。cache和主存的數(shù)據(jù)可能不一致。
緩存映射Cache Mapping
很明顯，Cache的大小遠(yuǎn)小于內(nèi)存的大小，那么Cache和內(nèi)存之間如何進(jìn)行映射即Cache地址怎樣去對(duì)應(yīng)內(nèi)存中的地址呢？使用的機(jī)制就是緩存映射Cache Mapping。
在講述常見的緩存映射機(jī)制前，需要復(fù)習(xí)一下Cache Line的概念。
將cache平均分成相等的很多塊，每一個(gè)塊大小稱之為cache line，其大小是cache line size。例如一個(gè)64 Bytes大小的cache。如果我們將64 Bytes平均分成64塊，那么cache line就是1字節(jié)，總共64行cache line。如果我們將64 Bytes平均分成8塊，那么cache line就是8字節(jié)，總共8行cache line?，F(xiàn)在的硬件設(shè)計(jì)中，一般cache line的大小是4-128字節(jié)。常見的如x86的Cache Line為64字節(jié)，而ARM和Power9的Cache Line為128字節(jié)。
有一點(diǎn)需要注意，cache line是cache和主存之間數(shù)據(jù)傳輸?shù)淖钚挝?。什么意思呢？?dāng)CPU試圖load一個(gè)字節(jié)數(shù)據(jù)的時(shí)候，如果cache缺失，那么cache控制器會(huì)從主存中一次性的load cache line大小的數(shù)據(jù)到cache中。例如，cache line大小是64字節(jié)。CPU即使讀取一個(gè)byte，在cache缺失后，cache會(huì)從主存中l(wèi)oad 64字節(jié)填充整個(gè)cache line。
直接映射緩存Direct Mapped Cache
假設(shè)Cache的大小為64字節(jié)，Cache Line的大小為8字節(jié)，那么整個(gè)Cache就分成了64/8=8 Line。假設(shè)內(nèi)存大小為512字節(jié)，同樣按照Cache的大小將其分成512/64=8 block，每一份叫做一個(gè)塊(block)，每個(gè)block里面也是按照Cache Line的大小分為64/8=8 Line。將每個(gè)block的第一個(gè)Line和Cache中的第一個(gè)Line對(duì)應(yīng)起來，以此類推，這種方法就叫做Direct Mapped Cache。下圖是Direct Mapped Cache的示例。
直接映射緩存在硬件設(shè)計(jì)上會(huì)更加簡(jiǎn)單，因此成本上也會(huì)較低。但是直接映射緩存存在一個(gè)稱為“Cache顛簸(Cache Thrashing)”的問題，舉個(gè)例子，如果我們恰好要訪問內(nèi)存中每個(gè)block的第一個(gè)Line，由于它們都被映射到了Cache的第一個(gè)Line，所以每次都不會(huì)命中，而是不停從內(nèi)存中加載到Cache中，此時(shí)，Cache對(duì)于性能提升就毫無幫助。
組相聯(lián)緩存Set Associative Cache
依然假設(shè)Cache大小是64字節(jié)，Cache Line大小是8字節(jié)，內(nèi)存大小是512字節(jié)。
在解釋組相聯(lián)緩存之前，還需要了解Way（路）的概念。
將Cache平均分為幾份，每一份就叫做一組（Set）。而每一個(gè)Set里面包含幾個(gè)Cache Line，可以稱為幾路（Way）。
假設(shè)將Cache平均分為4份，也就是4組，那么每一組就是64/4=16字節(jié)。每一組包含16/8=2 Line即2個(gè)Cache Line，就是2路，命名為way-0，way-1。而此時(shí)內(nèi)存劃分block時(shí)，需要保證每個(gè)block里面包含的Line數(shù)等于Cache的組數(shù)4。相當(dāng)于劃分為512/(4*8)=16 block，每個(gè)block包含4個(gè)Cache Line。
主存中的各塊與Cache的組號(hào)之間有固定的映射關(guān)系，但可自由映射到對(duì)應(yīng)Cache組中的任何一路。例如，主存中的第0塊、第4塊……均映射于Cache的第0組，但可映射到Cache第0組中的way-0或way-1；主存的第1塊、第5塊……均映射于Cache的第1組，但可映射到Cache第1組中的way-0或way-1。
常采用的組相聯(lián)結(jié)構(gòu)Cache，每組內(nèi)有2、4、8、16路，稱為2路、4路、8路、16路組相聯(lián)Cache。
全相聯(lián)緩存Full Associative Cache
全相聯(lián)緩存，將整個(gè)Cache看做一個(gè)組（set），也就是不再分組，其實(shí)是組相聯(lián)緩存的特殊情況。在全相聯(lián)緩存中，任意地址的數(shù)據(jù)可以緩存在任意的cache line中。所以，這可以最大程度的降低cache顛簸的頻率。但是硬件成本上也是更高。
組相聯(lián)結(jié)構(gòu)Cache是直接映射和全相聯(lián)映射的折中方案，適度兼顧二者的優(yōu)點(diǎn)，盡量避免二者的缺點(diǎn)，因而得到普遍采用。
最后，是個(gè)小測(cè)試：
Que-1:A computer has a 256 KByte,4-way set associative,write back data cache with the block size of 32 Bytes.The processor sends 32-bit addresses to the cache controller.Each cache tag directory entry contains,in addition,to address tag,2 valid bits,1 modified bit and 1 replacement bit.The number of bits in the tag field of an address is
(A)11
(B)14
(C)16
(D)27
Answer:(C)
Explanation:https://www.geeksforgeeks.org/gate-gate-cs-2012-question-54/
Que-2:Consider the data given in previous question.The size of the cache tag directory is
(A)160 Kbits
(B)136 bits
(C)40 Kbits
(D)32 bits
Answer:(A)
Explanation:https://www.geeksforgeeks.org/gate-gate-cs-2012-question-55/
Que-3:An 8KB direct-mapped write-back cache is organized as multiple blocks,each of size 32-bytes.The processor generates 32-bit addresses.The cache controller maintains the tag information for each cache block comprising of the following.
1 Valid bit
1 Modified bit
As many bits as the minimum needed to identify the memory block mapped in the cache.What is the total size of memory needed at the cache controller to store meta-data(tags)for the cache?
(A)4864 bits
(B)6144 bits
(C)6656 bits
(D)5376 bits
Answer:(D)
Explanation:https://www.geeksforgeeks.org/gate-gate-cs-2011-question-43/
參考鏈接：
https://www.hardwaretimes.com/difference-between-l1-l2-and-l3-cache-what-is-cpu-cache/
https://www.geeksforgeeks.org/cache-memory-in-computer-organization/
https://zhuanlan.zhihu.com/p/102293437
