為什么要在CPU和DDR之間增加一個(gè)cache呢？

1， 簡(jiǎn)介

Cache被稱為高速緩沖存儲(chǔ)器（cache memory），是一種小容量高速的存儲(chǔ)器，屬于存儲(chǔ)子系統(tǒng)的一部分，存放程序常使用的指令和數(shù)據(jù)。對(duì)于做service開發(fā)的同學(xué)，可能很少關(guān)注過(guò)這個(gè)模塊，一般也不關(guān)心數(shù)據(jù)是在內(nèi)存，還是在cache里。畢竟大部分時(shí)候，上層的程序只要遵循一定的開發(fā)規(guī)范（比如局部性原理），就不會(huì)太影響cache的工作。但是對(duì)于底層開發(fā)的工程師，比如操作系統(tǒng)開發(fā)、固件開發(fā)、性能優(yōu)化和編譯器開發(fā)工程師，在做開發(fā)、性能優(yōu)化的時(shí)候，cache是需要重點(diǎn)關(guān)注的模塊，如果對(duì)cache的理解不夠深入，開發(fā)出來(lái)的程序不僅性能不好，并且可能會(huì)存在穩(wěn)定性問(wèn)題。

我們既然有了DDR，為什么還需要在CPU和DDR之間增加一個(gè)cache呢？主要是由于兩個(gè)原因：一是CPU和DDR的訪問(wèn)、讀寫速度相差很大，二是減少CPU與其他模塊爭(zhēng)搶訪存頻率。

DDR的性能雖然也在提升，但是與CPU的差距越來(lái)越大，當(dāng)前兩者的速度相差幾百倍，一條加載指令需要上百個(gè)時(shí)鐘周期，才能從DDR讀取數(shù)據(jù)到CPU的內(nèi)部寄存器，這會(huì)導(dǎo)致CPU停滯等待加載指令，嚴(yán)重影響了CPU的性能。CPU的運(yùn)行速度跟cache相差不大，并且程序運(yùn)行遵循著時(shí)間、空間的局限性。因此通過(guò)在CPU與DDR之間增加一個(gè)cache，就可以很大地緩解CPU與DDR之間的速度差距。你可能會(huì)想，既然cache的讀寫速度這么快，是不是可以直接替代DDR？想法是好的，不過(guò)現(xiàn)實(shí)比較殘酷，cache的成本是DDR的幾十倍，最主要的是cache的單位存儲(chǔ)的面積也要比DDR大，1G的cache面積有A4紙大小。因此不論從成本，還是芯片面積角度來(lái)看，基本上不能用cache替代DDR。

具有訪存需求的模塊不僅有CPU，還有GPU、DSP、DMA等模塊。這些模塊協(xié)同工作，存在很大概率的并行、競(jìng)爭(zhēng)訪問(wèn)DDR的時(shí)刻。在CPU與DDR之間增加cache，會(huì)減少CPU直接訪問(wèn)DDR的頻率，這樣對(duì)其他模塊訪問(wèn)DDR的速度提升有幫助。

其實(shí)在微架構(gòu)中，除了CPU與DDR之間的cache外，還存在著其他的一些cache。比如，用于虛擬地址與物理地址轉(zhuǎn)換的TLB（Table Lookup Buffer），用于指令流水線中的重排序緩沖區(qū)（Re-Order Buffer），用于指令亂序執(zhí)行的內(nèi)存重排緩沖區(qū)（Memory Ordering Buffer）等。本文主要談?wù)摰氖荂PU與DDR之間的cache。

Cache一般由集成在CPU內(nèi)部的SRAM（Static Random Access Memory）和Tag組成。在CPU第一次從DDR中讀取數(shù)據(jù)時(shí)，也會(huì)把這個(gè)數(shù)據(jù)緩存在cache里，當(dāng)CPU再次讀取時(shí)，直接從cache中取數(shù)據(jù)，從而大大提高讀寫的速度。CPU讀寫數(shù)據(jù)的時(shí)候，如果數(shù)據(jù)在cache中，稱為高速緩存命中（cache hit），如果數(shù)據(jù)不在cache中，稱為高速緩存未命中（cache miss）。如果程序的高速緩存命中率比較高，不僅會(huì)提升CPU性能，還會(huì)降低系統(tǒng)的功耗。

2， 框架

arm64體系結(jié)構(gòu)處理器框架

如上圖是一個(gè)經(jīng)典ARM64體系結(jié)構(gòu)處理器系統(tǒng)，其中包含了多級(jí)的cache。一個(gè)cluster CPU族包含了兩個(gè)CPU內(nèi)核，每個(gè)CPU都有自己的L1 cache及L2 cache，其中L1 cache分了L1I（Level 1 Instruction）、L1D（Level 1 Data）兩種。不同CPU共享L3 cache，L3 cache位于cluster內(nèi)。Cluster通過(guò)BUS與DDR、EMMC、SSD等建立連接，這樣CPU就可以訪問(wèn)到EMMC、SSD中的數(shù)據(jù)。在程序執(zhí)行時(shí)，會(huì)先將程序及數(shù)據(jù)，從SSD或者EMMC加載到內(nèi)存中，然后將內(nèi)存中的數(shù)據(jù)，加載到共享的 L3 Cache 中，再加載到每個(gè)核心獨(dú)有的 L2 Cache，最后才進(jìn)入到最快的 L1 Cache，之后才會(huì)被 CPU 讀取。

在系統(tǒng)設(shè)計(jì)時(shí)，需要在cache的性能和成本（芯片面積）之間做tradeoff，由于程序運(yùn)行遵循著局部性原理，因此現(xiàn)在CPU都采用了多級(jí)cache設(shè)計(jì)方案。越靠近CPU的cache，速度越快，成本越高，容量越小，越遠(yuǎn)離CPU的存儲(chǔ)模塊，速度越慢，成本越低、容量越大。不同存儲(chǔ)器的訪問(wèn)速度、成本對(duì)比如下圖：

不同存儲(chǔ)器成本、性能對(duì)比

2.1 cache和MMU的關(guān)系

Cache和MMU基本上都是一起使用的，會(huì)同時(shí)開啟或同時(shí)關(guān)閉。因?yàn)镸MU頁(yè)表中的entry屬性，控制著內(nèi)存的權(quán)限和cache緩存的策略。CPU在訪問(wèn)DDR的時(shí)候用的地址是虛擬地址（Virtual Address，VA），經(jīng)過(guò)MMU將VA映射成物理地址（Physucal Address，PA），然后使用物理地址查詢高速緩存，這種高速緩存稱為物理高速緩存。物理高速緩存在的缺點(diǎn)主要是，CPU查詢TLB或MMU后才能訪問(wèn)cache，增加了流水線的延時(shí)。物理高速緩存的工作流程如下：

物理高速緩存的工作流程

CPU使用虛擬地址尋址高速緩存，這種高速緩存稱為虛擬高速緩存。CPU在尋址時(shí)，先把虛擬地址發(fā)送到高速緩存，若在高速緩存里找到所需數(shù)據(jù)，就不再訪問(wèn)TLB和DDR。虛擬高速緩存的工作流程如下：

虛擬高速緩存的工作流程

2.2 L1、L2、L3 cache

1）cache分級(jí)的原因

L1、L2、L3 cache主要是由SRAM及tag組成的，其中L1 cache采用的是分離緩存方式：L1I（Level 1 Instruction）、L1D（Level 1 Data）cache。L2、L3 cache采用的卻是統(tǒng)一緩存的方式，沒有將數(shù)據(jù)、指令分開存儲(chǔ)。從上面各存儲(chǔ)器的訪問(wèn)延時(shí)對(duì)比來(lái)看，L1、L2、L3存在一定差異，但是成本相近，為什么要做成這種多級(jí)緩存形式，不直接將L1 cache做大，然后去掉L2、L3？

不采用一級(jí)cache的原因，一方面是：cache做地太大會(huì)影響讀寫速度。如果要更大的容量，就需要更多的晶體管，這不僅帶來(lái)芯片的面積變大，還會(huì)導(dǎo)致速度下降。因?yàn)樵L問(wèn)速度和要訪問(wèn)的晶體管信號(hào)線的長(zhǎng)度成反比。也就是說(shuō)當(dāng)晶體管數(shù)增加后，信號(hào)路徑會(huì)變長(zhǎng)，讀寫存在大延遲，從而影響讀寫速度。另一方面，多級(jí)不同尺寸的緩存有利于提高整體的性能。尤其是對(duì)于CPU存在私有的L1、L2 cache，會(huì)減少對(duì)L3 cache的訪問(wèn)競(jìng)爭(zhēng)。

L1、L2、L3 cache的區(qū)別是什么呢？L1是為了更快的速度訪問(wèn)，而優(yōu)化過(guò)的。它用了更多、更復(fù)雜、更大的晶體管，從而更加昂貴和更加耗電。L2是為提供更大的容量?jī)?yōu)化的，用了更少、更簡(jiǎn)單的晶體管，從而相對(duì)便宜和省電。L3相對(duì)L2的優(yōu)化也是類似的道理。在相同的制程、工藝中，單位面積可以放入晶體管的數(shù)目是確定的，這些晶體管如果都給L1，則容量太少，Cache命中率（Hit Rate）嚴(yán)重降低，功耗上升太快。如果都給L2、L3，容量大了，但延遲提高了一個(gè)數(shù)量級(jí)。如何平衡L1、L2和L3，用固定的晶體管數(shù)目達(dá)成最好的性能、最低的功耗、最小的成本，這是一種平衡的藝術(shù)。

2）cache命中率與大小的關(guān)系

對(duì)于L2、L3一般比L1要大，但是比DDR還是小了很多，L2、L3是不是可以更大？其實(shí)這跟上面講述的L1不能做的太大的原因類似，主要是成本、面積、速度限制了L2、L3不能做的太大。L2、L3也是基于SRAM實(shí)現(xiàn)的，一個(gè)存儲(chǔ)單元需要6個(gè)晶體管，再加上tag電路，至少需要幾十個(gè)晶體管，另外命中率并不是隨著L2、L3的增加一直大幅度增加的。命中率和各級(jí)cache大小的關(guān)系如下：

命中率和cache大小關(guān)系

為方便分析，我們假設(shè)L1維持在50%~60%的命中率（實(shí)際上95%左右）。從圖中可以看出，隨著L2容量的快速增加，開始時(shí)整體命中率也會(huì)快速提高，這表明提高L2容量，對(duì)提升整體命中率效用很明顯。但隨后L2的命中率，在容量增加到64KB后，隨著容量增加，命中率增長(zhǎng)趨緩，而整體命中率也同時(shí)趨緩。增加同樣的晶體管，而受益卻越來(lái)越少，個(gè)人理解這跟運(yùn)行程序的訪存特點(diǎn)有關(guān)，就是說(shuō)當(dāng)訪存的頻次、大小等確定后，開始L2容量增加，整體命中率也會(huì)增加，但是一旦達(dá)到一個(gè)臨界點(diǎn)后，就算再增加容量，命中率的提升也是很有限的。因此在做CPU cache大小設(shè)計(jì)的時(shí)候，一定要建立在業(yè)務(wù)訪存特點(diǎn)的基礎(chǔ)之上，不然要么造成成本浪費(fèi)，要么造成性能不足。

3）為什么L1 cache采用分離緩存的方式，而L2、L3采用統(tǒng)一緩存的形式？

為什么L1采用了分離緩存的方式，分了L1I和L1D？主要原因如下：

原因一：避免取指令單元和取數(shù)據(jù)單元競(jìng)爭(zhēng)訪問(wèn)緩存：在CPU中，取指令和取數(shù)據(jù)指令是由兩個(gè)不同的單元完成的，也就是說(shuō)在流水線控制中取指和訪存是分開的。如果使用統(tǒng)一緩存，當(dāng)CPU使用超前控制或流水線控制（并行執(zhí)行）的控制方式時(shí)，會(huì)存在取指令操作和取數(shù)據(jù)操作，同時(shí)爭(zhēng)用同一個(gè)緩存的情況，這會(huì)降低CPU運(yùn)行效率。

原因二：內(nèi)存中數(shù)據(jù)和指令是相對(duì)聚集的，分離緩存能提高命中率：在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，內(nèi)存中的指令和數(shù)據(jù)并不是隨機(jī)分布的，而是相對(duì)聚集地分開存儲(chǔ)的。因此，CPU Cache中也采用分離緩存的策略，這更符合DDR內(nèi)存中數(shù)據(jù)的組織形式，從而提高cache命中率。

為什么L2、L3采用了統(tǒng)一緩存的方式？主要原因如下：

原因一：CPU直接跟L1 cache打交道，L1采用分離緩存后，已經(jīng)解決了取指令單元和取數(shù)據(jù)單元的競(jìng)爭(zhēng)訪問(wèn)緩存問(wèn)題，所以L2是否使用分離緩存，影響不大。

原因二：當(dāng)緩存容量較大時(shí)，分離緩存無(wú)法動(dòng)態(tài)調(diào)節(jié)分離比例，不能最大化發(fā)揮緩存容量的利用率。例如數(shù)據(jù)緩存滿了，但是指令緩存還有空閑，而L2使用統(tǒng)一緩存，則能夠保證最大化利用緩存空間。

4）L3 cache為多核共享的，能不能放在片外？

集成在芯片內(nèi)部的緩存稱為片內(nèi)緩存，放在在芯片外部的緩存稱為片外緩存。開始由于芯片工藝的限制，片內(nèi)緩存不可能很大，不然芯片會(huì)非常大，因此 L2 / L3 緩存都是設(shè)計(jì)在板子上，而不是在芯片內(nèi)的。后來(lái)，隨著芯片制作工藝的提升，L2 / L3 才逐漸集成到 CPU 芯片內(nèi)部。片內(nèi)緩存優(yōu)于片外緩存的主要原因如下：

原因一：片內(nèi)緩存物理距離更短：片內(nèi)緩存與取指令單元和取數(shù)據(jù)單元的物理距離更短，延遲更小，訪問(wèn)速度更快。

原因二：片內(nèi)緩存不占用系統(tǒng)總線：片內(nèi)緩存使用獨(dú)立的CPU片內(nèi)總線，可以減輕系統(tǒng)總線的負(fù)擔(dān)。

5）多級(jí)cache替換策略

多級(jí)cache的替換策略設(shè)計(jì)有很多種方式，可以根據(jù)一個(gè)cache的內(nèi)容，是否同時(shí)存在于其他級(jí)cache來(lái)分類，即Cache inclusion policy。如果低級(jí)別cache中的所有cache line，也存在于較高級(jí)別cache中，則稱高級(jí)別cache包含（inclusive）低級(jí)別cache。如果高級(jí)別的cache，僅包含低級(jí)別cache不存在的cache line，則稱高級(jí)別的cache不包含（exclusive）較低級(jí)別的cache。如果高級(jí)cache的內(nèi)容，既不嚴(yán)格包含，也不排除低級(jí)cache，則稱為非包含非排他（non-inclusive non-exclusive，NINE）cache。

Inclusive Policy cache：CPU對(duì)數(shù)據(jù)A進(jìn)行讀取操作時(shí)，若A在L1 cache中找到，則從L1 cache中讀取數(shù)據(jù)，并返回給CPU。若A未在L1 cache中找到，但存在L2 cache中，則從L2 cache中提取該數(shù)據(jù)所在cache line，并將其填充到L1中。若一個(gè)cache line從L1 cache中被逐出，則L2 cache不做操作。若在L1或L2中均未找到想要的數(shù)據(jù)，則從L3中尋找，找到后會(huì)填充到L2、L1，若未在L3中找到，則從DDR中以cache line為單位取出該數(shù)據(jù)，并將其填充到L1、L2、L3中。若有來(lái)自L2的逐出，L2會(huì)向L1發(fā)送invalidation，以便遵循“Inclusive Policy”。

為了保持inclusion，需要滿足：

無(wú)論set的數(shù)量多少，L2 way的數(shù)量都必須大于或等于 L1 way的數(shù)量。

無(wú)論 L2 way的數(shù)量多少，L2 set的數(shù)量必須大于或等于 L1 set的數(shù)量。

Exclusive Policy cache：CPU對(duì)數(shù)據(jù)A進(jìn)行讀取操作時(shí)，若A在L1中找到，則從 L1 中讀取數(shù)據(jù)并返回給CPU。若未在L1中找到，但存在L2中，則將該A數(shù)據(jù)所在的cache line從L2移動(dòng)到L1。若一個(gè)cache line從L1中被逐出，則被逐出的cache line將被放置到L2中。這是L2 填充的唯一方式。若在L1、L2中都未找到A數(shù)據(jù)，則將其從L3中取出，并填充到L1，若在L3中也未找到，則在主存中取出，并填充到L1中。

NINE（non-inclusive non-exclusive）Policy：CPU對(duì)數(shù)據(jù)A進(jìn)行讀取操作時(shí)，若A在L1中找到，則從L1中讀取數(shù)據(jù)并返回給CPU。若在L1中未找到，但存在L2中，則從L2中提?。◤?fù)制）該數(shù)據(jù)對(duì)應(yīng)的cache line，并放置到L1中。若一個(gè)cache line從L1中被逐出，則L2不做操作，這與inclusive policy相同。若在L1、L2中都沒找到該A數(shù)據(jù)，則從L3中查找，若L3中找到該數(shù)據(jù)，將該數(shù)據(jù)所在cache line取出，并填充到L1、L2，若L3中沒找到，從主存中取出該數(shù)據(jù)對(duì)應(yīng)的cache line，填充到L1、L2、L3。

三種數(shù)據(jù)關(guān)系策略的比較：

inclusive policy的優(yōu)點(diǎn)：在每個(gè)處理器都有私有cache 時(shí)，如果存在cache miss，則檢查其他處理器私有cache，以查找該cache line。如果L2 cache包含L1 cache，并且在L1 cache中miss，則不需要再大面積搜索L2 cache。這意味著與exclusive cache和 NINE cache相比，inclusive cache的miss 延遲更短。

inclusive policy的缺點(diǎn)：cache的內(nèi)存容量由L3 cache決定的。exclusive cache的容量是層次結(jié)構(gòu)中，所有cache的總?cè)萘?。如果L3 cache較小，則在inclusive cache中浪費(fèi)的cache容量更多。

盡管exclusive cache具有更多的內(nèi)存容量，但相比NINE cache，它需要占用更多的帶寬，因?yàn)長(zhǎng)1 cache 逐出時(shí)，會(huì)將逐出數(shù)據(jù)填充到L2、L3 cache。

3， cache的工作原理

3.1 cache的存儲(chǔ)單元

Cache的存儲(chǔ)部分是由SRAM實(shí)現(xiàn)的，cache的存儲(chǔ)單元就是SRAM的存儲(chǔ)單元，SRAM存儲(chǔ)單元由6個(gè)三極管組成，如下圖所示：

SRAM的存儲(chǔ)單元

寫入“1”的過(guò)程如下（寫入數(shù)據(jù)“0”的過(guò)程類似）：

先將某一組地址值輸入到行、列譯碼器中，選中特定的單元，如上圖所示。

使寫使能信號(hào)WE有效，將要寫入的數(shù)據(jù)“1”，通過(guò)寫入電路變成“1”和“0”后，分別加到選中單元的兩條位線BL、BLB上。

選中單元的WL=1，晶體管N6、N5打開，把BL、BLB上的信號(hào)分別送到Q、QB點(diǎn)，從而使Q=1，QB=0，這樣數(shù)據(jù)“1”就被鎖存在晶體管P2、P3、N3、N4構(gòu)成的鎖存器中。

讀“1”的過(guò)程如下（讀取數(shù)據(jù)“0”的過(guò)程類似）：

通過(guò)譯碼器選中某列位線對(duì)BL、BLB進(jìn)行預(yù)充電到電源電壓VDD。

預(yù)充電結(jié)束后，再通過(guò)行譯碼器選中某行，則某一存儲(chǔ)單元被選中。

由于其中存放的是“1”，則WL=1、Q=1、QB=0。晶體管N4、N5導(dǎo)通，有電流經(jīng)N4、N5到地，從而使BLB電位下降，BL、BLB間電位產(chǎn)生電壓差，當(dāng)電壓差達(dá)到一定值后打開靈敏度放大器，對(duì)電壓進(jìn)行放大，再送到輸出電路，讀出數(shù)據(jù)。

3.2 高速緩存的映射方式

CPU訪問(wèn)DDR前，都會(huì)先對(duì)cache進(jìn)行操作，無(wú)論對(duì)Cache數(shù)據(jù)檢查、讀取還是寫入，CPU都需要知道訪問(wèn)的內(nèi)存數(shù)據(jù)，對(duì)應(yīng)于Cache上的哪個(gè)位置，這就是內(nèi)存地址與 Cache 地址的映射問(wèn)題。由于內(nèi)存塊和緩存塊的大小分別是固定的，所以在映射的過(guò)程中，我們只需要考慮 “內(nèi)存塊索引 - 緩存塊索引” 之間的映射關(guān)系，而具體訪問(wèn)的是塊內(nèi)的哪一個(gè)字，則使用相同的偏移在塊中尋找。

目前，主要有 3 種映射方案：

直接相聯(lián)映射（Direct Mapped Cache）：固定的映射關(guān)系；

全相聯(lián)映射（Fully Associative Cache）：靈活的映射關(guān)系；

組相聯(lián)映射（N-way Set Associative Cache）：前兩種方案的折中方法。

接下來(lái)，我們分別以內(nèi)存有32個(gè)內(nèi)存塊，CPU Cache有8個(gè)緩存塊為例講解這3種映射方案。

1） 直接相聯(lián)映射

直接相聯(lián)映射的策略：在內(nèi)存塊和緩存塊之間建立起固定的映射關(guān)系，一個(gè)內(nèi)存塊總是映射到同一個(gè)緩存塊上。直接映射是三種映射方式中最簡(jiǎn)單的。我們通過(guò)以下圖來(lái)了解直接相聯(lián)映射，其中cache塊跟內(nèi)存塊大小相等，大小為cache line。

直接相聯(lián)映射

具體方式如下：

將內(nèi)存塊索引對(duì) Cache 塊個(gè)數(shù)取模，得到固定的映射位置。例如11號(hào)內(nèi)存塊映射的位置就是11 % 8 = 3，對(duì)應(yīng)3號(hào)Cache塊。

取模后，多個(gè)內(nèi)存塊會(huì)映射到同一個(gè)緩存塊上，這會(huì)產(chǎn)生塊沖突，所以需要在Cache塊上，增加一個(gè)組標(biāo)記（TAG），標(biāo)記當(dāng)前緩存塊存儲(chǔ)的是哪一個(gè)內(nèi)存塊的數(shù)據(jù)。其實(shí)，組標(biāo)記就是內(nèi)存塊索引的高位，而 Cache 塊索引就是內(nèi)存塊索引的低4位（8個(gè)字塊需要4位）；

由于初始狀態(tài)Cache塊中的數(shù)據(jù)是空的，也是無(wú)效的。為了標(biāo)識(shí)Cache塊中的數(shù)據(jù)，是否已經(jīng)從內(nèi)存中讀取，需要在Cache塊上增加一個(gè)有效位（Valid bit）。如果有效位為1，則CPU可以直接讀取 Cache 塊上的內(nèi)容，否則需要先從內(nèi)存讀取內(nèi)存塊，并填入Cache塊，再將有效位改為 1。

2） 全相聯(lián)映射

對(duì)于直接映射存在2個(gè)問(wèn)題：

問(wèn)題1，緩存利用不充分：每個(gè)內(nèi)存塊只能映射到固定的位置上，即使Cache上有空閑位置也不會(huì)使用。

問(wèn)題2，塊沖突率高：直接映射會(huì)頻繁出現(xiàn)塊沖突，影響緩存命中率。

為了改進(jìn)直接相聯(lián)映射的缺點(diǎn)，全相聯(lián)映射的策略是：允許內(nèi)存塊映射到任何一個(gè)Cache塊上。這種方式能夠充分利用 Cache 的空間，塊沖突率也更低，但是所需要的電路結(jié)構(gòu)物更復(fù)雜，成本更高。

全相聯(lián)映射

具體方式如下：

當(dāng)Cache塊上有空閑位置時(shí)，使用空閑位置。

當(dāng)Cache被占滿時(shí)，則替換出一個(gè)舊的塊騰出空閑位置。

由于一個(gè)Cache塊會(huì)映射所有內(nèi)存塊，因此組標(biāo)記TAG需要擴(kuò)大到與主內(nèi)存塊索引相同的位數(shù)，而且映射的過(guò)程需要沿著Cache從頭到尾匹配Cache塊的TAG標(biāo)記。

3） 組相聯(lián)映射

組相聯(lián)映射結(jié)合了直接相聯(lián)映射和全相聯(lián)映射的優(yōu)點(diǎn)，組相聯(lián)映射的策略是：將Cache分為多組，每個(gè)內(nèi)存塊固定映射到一個(gè)分組中，又允許映射到組內(nèi)的任意Cache塊。顯然，組相聯(lián)的分組為1時(shí)，就等于全相聯(lián)映射，而分組等于Cache塊個(gè)數(shù)時(shí)，就等于直接映射。

組相聯(lián)映射

3.3 cache的基本結(jié)構(gòu)

Cache的基本結(jié)構(gòu)如下圖所示：

cache的基本結(jié)構(gòu)

地址：以32位為例，CPU訪問(wèn)cache時(shí)的地址編碼，分為3個(gè)部分：偏移量（offset）域、索引（index）域和標(biāo)記（tag）域。

高速緩存行：高速緩存中最小的訪問(wèn)單元，包含一小段DDR中的數(shù)據(jù)。常見的高速緩存行大小是32字節(jié)或64字節(jié)。

索引（index）：高速緩存地址編碼的一部分，用于索引和查找地址在高速緩存行的哪一組中。

組（set）：由相同索引的高速緩存行組成。

路（way）：在組相聯(lián)的高速緩存中，高速緩存分成大小相同的幾個(gè)塊。如上每一路由四個(gè)緩存行組成。

標(biāo)記（tag）：高速緩存地址編碼的一部分，通常是高速緩存地址的高位部分，用于盤點(diǎn)高速緩存行中的數(shù)據(jù)地址，是否和處理器尋找的地址一致。

偏移量（offset）：高速緩存行中的偏移量。CPU可以按字節(jié)或字來(lái)尋址高速緩存行的內(nèi)容。

CPU訪問(wèn)高速緩存的流程如下：

CPU對(duì)訪問(wèn)高速緩存時(shí)的地址進(jìn)行編碼。根據(jù)索引域來(lái)查找組。對(duì)于組相聯(lián)的高速緩存，一個(gè)組里有多個(gè)緩存行的候選者。比如上圖，有一個(gè)4路組相聯(lián)的高速緩存，一個(gè)組里有4個(gè)高速緩存行候選者。

在4個(gè)高速緩存行候選者中，通過(guò)組標(biāo)記域進(jìn)行比對(duì)。若組標(biāo)記域相同則說(shuō)明命中高速緩存行。

通過(guò)偏移量域來(lái)尋址高速緩存行對(duì)應(yīng)的數(shù)據(jù)。

3.4 cache的體系結(jié)構(gòu)

高速緩存可以設(shè)計(jì)成，通過(guò)虛擬地址或者物理地址來(lái)訪問(wèn)，這在處理器設(shè)計(jì)時(shí)就確定下來(lái)了。高速緩存可以分成如下3類：

VIVT（Virtual Index Virtual Tag）：使用虛擬地址的索引域和虛擬地址的標(biāo)記域，相當(dāng)于虛擬高速緩存。

PIPT（Physical Index Physical Tag）：使用物理地址的索引域和物理地址的標(biāo)記域，相當(dāng)于物理高速緩存。

VIPT（Virtual Index Physical Tag）：使用虛擬地址的索引域和物理地址的標(biāo)記域。

在當(dāng)前ARM架構(gòu)中，L1 cache都是VIPT的，也就是當(dāng)有一個(gè)虛擬地址送進(jìn)來(lái)，MMU在開始進(jìn)行地址翻譯的時(shí)候，Virtual Index就可以去L1 cache中查詢了，MMU查詢和L1 cache的index查詢是同時(shí)進(jìn)行的。如果L1 Miss了，則再去查詢L2，L2還找不到則再去查詢L3。注意在ARM架構(gòu)中，僅僅L1是VIPT，L2和L3都是PIPT。我們看看VIPT的工作過(guò)程：

CPU輸出的虛擬地址會(huì)同時(shí)發(fā)送到TLB和高速緩存。TLB是一個(gè)用于存儲(chǔ)虛擬地址到物理地址的轉(zhuǎn)換的小緩存，處理器先使用有效頁(yè)幀號(hào)（Effective Page Number，EPN），在TLB中查找最終的實(shí)際頁(yè)幀號(hào)（Real Page Number，RPN）。如果期間發(fā)生TLB未命中（TLB miss），將會(huì)帶來(lái)一系列嚴(yán)重的系統(tǒng)懲罰，處理器需要查詢頁(yè)表。假設(shè)發(fā)生TLB命中（TLB hit），就會(huì)很快獲得合適的RPN，并得到相應(yīng)的物理地址。

同時(shí)，處理器通過(guò)高速緩存編碼地址的索引（index）域，可以很快找到高速緩存行對(duì)應(yīng)的組。但是這里的高速緩存行中的數(shù)據(jù)，不一定是處理器所需要的，因此有必要進(jìn)行一些檢查，將高速緩存行中存放的標(biāo)記域和通過(guò)虛實(shí)地址轉(zhuǎn)換得到的物理地址的標(biāo)記域進(jìn)行比較，如果相同并且狀態(tài)位匹配，就會(huì)發(fā)生高速緩存命中，處理器通過(guò)字節(jié)選擇與對(duì)齊（byte select and align）部件，就可以獲取所需要的數(shù)據(jù)。如果發(fā)生高速緩存未命中，處理器需要用物理地址進(jìn)一步訪問(wèn)主存儲(chǔ)器，來(lái)獲得最終的數(shù)據(jù)，數(shù)據(jù)也會(huì)填充到相應(yīng)的高速緩存行中。

VIPT高速緩存體系結(jié)構(gòu)

3.5 cache的替換策略

在使用直接相聯(lián)映射的 Cache 中，由于每個(gè)主內(nèi)存塊都與某個(gè)Cache塊有直接映射關(guān)系，因此不存在替換策略。而使用全相聯(lián)映射或組相聯(lián)映射的Cache，由于主內(nèi)存塊與Cache塊沒有固定的映射關(guān)系，當(dāng)新的內(nèi)存塊需要加載到Cache中時(shí)，且Cache塊沒有空閑位置，則需要替換到Cache塊上的數(shù)據(jù)。此時(shí)就存在替換策略的問(wèn)題。

常見cache中數(shù)據(jù)的替換策略如下，cache中數(shù)據(jù)的替換以cache line為單位：

隨機(jī)法：使用一個(gè)隨機(jī)數(shù)生成器，隨機(jī)地選擇要被替換的 Cache 塊。優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，缺點(diǎn)是沒有利用 “局部性原理”，無(wú)法提高緩存命中率。

FIFO先進(jìn)先出法：記錄各個(gè)Cache塊的加載事件，最早調(diào)入的塊最先被替換。缺點(diǎn)同樣是沒有利用 “局部性原理”，無(wú)法提高緩存命中率。

LRU最近最少使用法：記錄各個(gè)Cache塊的使用情況，最近最少使用的塊最先被替換。這種方法相對(duì)比較復(fù)雜，也有類似的簡(jiǎn)化方法，即記錄各個(gè)塊最近一次使用時(shí)間，最久未訪問(wèn)的最先被替換。與前 2 種策略相比，LRU策略利用了 “局部性原理”，平均緩存命中率更高。

多級(jí)cache的替換策略，在上面的“多級(jí)cache替換策略”里說(shuō)明了常見的三種替換策略：Inclusive Policy cache，Exclusive Policy cache，NINE（non-inclusive non-exclusive）Policy。接下來(lái)以DynamIQ架構(gòu)中的cortex-A710的L1、L2 cache的替換策略為例，做分析。

我們先看一下DynamIQ架構(gòu)中的cache中新增的幾個(gè)概念：

(1) Strictly inclusive: 對(duì)應(yīng)Inclusive Policy cache，所有存在于L1 cache的數(shù)據(jù)，必然也存在L2 cache中。

(2) Weakly inclusive: 對(duì)應(yīng)NINE（non-inclusive non-exclusive）Policy，當(dāng)miss的時(shí)候，數(shù)據(jù)會(huì)被同時(shí)緩存到L1和L2，但在之后，L2中的數(shù)據(jù)可能會(huì)被替換。

(3) Fully exclusive: 對(duì)應(yīng)Exclusive Policy cache，當(dāng)miss的時(shí)候，數(shù)據(jù)只會(huì)緩存到L1。L1中的數(shù)據(jù)會(huì)逐出到L2。

其實(shí)inclusive/exclusive屬性描述的是 L1和L2之間的替換策略，這部分是硬件定死的，軟件不可更改。

根據(jù)ARMV9 cortex-A710 trm手冊(cè)中的描述，查看該core的cache類型如下：

L1 I-cache和L2之間是 weakly inclusive的，當(dāng)發(fā)生I-cache發(fā)生miss時(shí)，數(shù)據(jù)緩存到L1 I-cache的時(shí)候，也會(huì)被緩存到L2 Cache中，當(dāng)L2 Cache被替換時(shí)，L1 I- cache不會(huì)被替換。

L1 D-cache和L2之間是 strictly inclusive的，當(dāng)發(fā)生D-cache發(fā)生miss時(shí)，數(shù)據(jù)緩存到L1 D-cache的時(shí)候，也會(huì)被緩存到L2 Cache中，當(dāng)L2 Cache被替換時(shí)，L1 D-cache也會(huì)跟著被替換。

dynamIQ 架構(gòu)中 L1和L2之間的替換策略，是由core的inclusive/exclusive的硬件特性決定的，軟無(wú)法更改。core cache之間的替換策略，是由SCU(或DSU)執(zhí)行的MESI協(xié)議中定義的，軟件也無(wú)法更改。多cluster之間的緩存一致性，由 CCI/CMN 來(lái)執(zhí)行維護(hù)，沒有使用MESI協(xié)議。在L1 data cache TAG中，有記錄MESI相關(guān)比特。將一個(gè)core內(nèi)的cache看做是一個(gè)整體，core與core之間的緩存一致性，就由DSU執(zhí)行MESI協(xié)議來(lái)維護(hù)，因此L1D遵從MESI協(xié)議。對(duì)于L1I cache來(lái)說(shuō)，都是只讀的，cpu不會(huì)改寫L1I中的數(shù)據(jù)，所以也就不需要硬件維護(hù)多核之間緩存的不一致。

3.6 高速緩存分配策略

cache的分配策略是指我們什么情況下應(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ù)。

1）寫操作時(shí)，cache更新策略

一條存儲(chǔ)器讀寫指令，通過(guò)取指、譯碼、發(fā)射和執(zhí)行等一系列操作之后，會(huì)到達(dá)LSU（Load Store Unit）。LSU是指令流水線中的一個(gè)執(zhí)行部件，連接指令流水線和高速緩存，包括加載隊(duì)列（load queue）和存儲(chǔ)隊(duì)列（store queue）。存儲(chǔ)器讀寫指令通過(guò)LSU后，會(huì)到達(dá)L1控制器，L1控制器先發(fā)起探測(cè)（probe）操作。對(duì)于讀操作，發(fā)起高速緩存讀探測(cè)操作，并帶回?cái)?shù)據(jù)。對(duì)于寫操作，發(fā)起高速緩存寫探測(cè)操作。發(fā)起寫探測(cè)操作前，需要準(zhǔn)備好待寫的高速緩存行。探測(cè)操作返回時(shí)，會(huì)帶回?cái)?shù)據(jù)，存儲(chǔ)器寫指令獲得最終數(shù)據(jù)，并進(jìn)行提交操作后，才會(huì)將數(shù)據(jù)寫入，這個(gè)寫入可以采用直寫（write through）模式，或者回寫（write back）模式。

在探測(cè)過(guò)程中，對(duì)于寫操作，若沒有找到相應(yīng)的高速緩存行，就出現(xiàn)寫未命中（write miss）。否則就出現(xiàn)寫命中（write bit）。對(duì)于寫未命中的處理策略是寫分配（write allocate），L1控制器將分配一個(gè)新的高速緩存行，之后和獲取的數(shù)據(jù)合并，然后寫入L1D。

若寫未命中，存在兩種不同的策略：

寫分配（write allocate）策略：先把要寫的數(shù)據(jù)加載到高速緩存中，然后修改高速緩存的內(nèi)容。

不寫分配（no write allocate）策略：不分配高速緩存，而直接把內(nèi)容寫入內(nèi)存。

若寫命中，存在兩種不同的策略：

直寫模式：進(jìn)行寫操作時(shí)，數(shù)據(jù)同時(shí)寫入當(dāng)前的高速緩存，下一級(jí)高速緩存，或主存儲(chǔ)器中，cache和主存的數(shù)據(jù)始終保持一致。。直寫模式可以降低高速緩存一致性實(shí)現(xiàn)的難度，缺點(diǎn)是消耗比較多的總線帶寬，性能比回寫模式差。

回寫模式：在進(jìn)行寫操作時(shí)，數(shù)據(jù)直接寫入當(dāng)前高速緩存，而不會(huì)繼續(xù)傳遞，當(dāng)該高速緩存被替換出去時(shí)，被改寫的數(shù)據(jù)才會(huì)更新到下一級(jí)高速緩存，或主存中。該策略增加了高速緩存一致性的實(shí)現(xiàn)難度，但是可有效減少總線帶寬的需求。每個(gè)cache line中會(huì)有一個(gè)bit位記錄數(shù)據(jù)是否被修改過(guò)，稱之為dirty bit。我們會(huì)在數(shù)據(jù)寫到cache中后，將dirty bit置位。主存中的數(shù)據(jù)只會(huì)在cache line被替換或者顯式的clean操作時(shí)更新。因此，主存中的數(shù)據(jù)可能是未修改的數(shù)據(jù)，而修改的數(shù)據(jù)躺在cache中。cache和主存的數(shù)據(jù)可能不一致。此模式的優(yōu)點(diǎn)是，數(shù)據(jù)寫入速度快，因?yàn)椴恍枰獙懘鎯?chǔ)。缺點(diǎn)是，一旦更新后的數(shù)據(jù)，未被寫入存儲(chǔ)時(shí)，出現(xiàn)系統(tǒng)掉電的情況，數(shù)據(jù)將無(wú)法找回。

無(wú)論是Write-through還是Write-back都可以使用寫缺失的兩種方式之一。只是通常Write-back采用Write allocate方式，而Write-through采用No-write allocate方式。因?yàn)槎啻螌懭胪痪彺鏁r(shí)，Write allocate配合Write-back可以提升性能，而對(duì)于Write-through則沒有幫助。

2）讀操作時(shí)，cache更新策略

對(duì)于讀操作，若高速緩存命中，那么直接從高速緩存中獲取數(shù)據(jù)。若未命中高速緩存，存在如下兩種策略：

讀分配（read allocate）策略：先把數(shù)據(jù)加載到高速緩存中，然后將數(shù)據(jù)返回給CPU。

讀直通（read through）策略：不經(jīng)過(guò)高速緩存，直接從內(nèi)存中讀取數(shù)據(jù)。

審核編輯：劉清