1. Cache的歷史

在科研領(lǐng)域，C. J. Conti等人于1968年在描述360/85和360/91系統(tǒng)性能差異時(shí)最早引入了高速緩存（cache）一詞。Alan Jay Smith于1982年的一篇論文中引入了空間局部性和時(shí)間局部性的概念。

Mark Hill在1987年發(fā)明了3C（Compulsory, Capacity, Conflict）沖突分類(lèi)。

最早介紹非阻塞緩存的論文之一來(lái)自David Kroft（1981年）。

1990年Norman Paul Jouppi在一篇論文中介紹了受害者緩存并研究了使用流緩沖器進(jìn)行預(yù)取的性能。

在工業(yè)領(lǐng)域，最早的有記載的緩存出現(xiàn)在IBM的360/85系統(tǒng)上。

Intel的x86架構(gòu)CPU從386開(kāi)始引入使用SRAM技術(shù)的主板緩存，大小從16KB到64KB不等。486引入兩級(jí)緩存。其中8KBL1緩存和CPU同片，而L2緩存仍然位于主板上，大小可達(dá)268KB。將二級(jí)緩存置于主板上在此后十余年間一直設(shè)計(jì)主流。但是由于SDRAM技術(shù)的引入，以及CPU主頻和主板總線(xiàn)頻率的差異不斷拉大，主板緩存在速度上的對(duì)內(nèi)存優(yōu)勢(shì)不斷縮水。因此，從Pentium Pro起，二級(jí)緩存開(kāi)始和處理器一起封裝，頻率亦與CPU相同（稱(chēng)為全速二級(jí)緩存）或?yàn)镃PU主頻的一半（稱(chēng)為半速二級(jí)緩存）。

AMD則從K6-III開(kāi)始引入三級(jí)緩存?；赟ocket 7接口的K6-III擁有64KB和256KB的同片封裝兩級(jí)緩存，以及可達(dá)2MB的三級(jí)主板緩存。
今天的CPU將三級(jí)緩存全部集成到CPU芯片上。

多核CPU通常為每個(gè)核配有獨(dú)享的一級(jí)和二級(jí)緩存，以及各核之間共享的三級(jí)緩存。

---

2. 什么是Cache?

在wikipedia上對(duì)cache的解釋：

In computing, a cache is a hardware or software component that stores data so future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation, or the duplicate of data stored elsewhere. A cache hit occurs when the requested data can be found in a cache, while a cache miss occurs when it cannot. Cache hits are served by reading data from the cache, which is faster than recomputing a result or reading from a slower data store; thus, the more requests can be served from the cache, the faster the system performs.

字面上理解就是，cache是一個(gè)硬件或軟件的組件用來(lái)存儲(chǔ)將來(lái)會(huì)請(qǐng)求到的數(shù)據(jù)，而且能讓數(shù)據(jù)獲取更快。因?yàn)槿缃窬彺娴母拍钜驯粩U(kuò)充，不僅在CPU和主內(nèi)存之間有Cache，而且在內(nèi)存和硬盤(pán)之間也有Cache（磁盤(pán)緩存），乃至在硬盤(pán)與網(wǎng)絡(luò)之間也有某種意義上的Cache──稱(chēng)為Internet臨時(shí)文件夾或網(wǎng)絡(luò)內(nèi)容緩存等。凡是位于速度相差較大的兩種硬件之間，用于協(xié)調(diào)兩者數(shù)據(jù)傳輸速度差異的結(jié)構(gòu)，均可稱(chēng)之為Cache。

• 硬件的cache：CPU cache，GPU cache，DSP；
• 軟件的cache：Disk Cache，Web Cache等。

圖1 什么是緩存

這里我們著重討論傳統(tǒng)的cache緩存：CPU的cache。不同的存儲(chǔ)技術(shù)有著不同的價(jià)格和性能的折中。不同存儲(chǔ)器訪(fǎng)問(wèn)時(shí)間差異很大，速度較快的技術(shù)每字節(jié)的成本要比速度較慢的技術(shù)高，而且容量小。金字塔存儲(chǔ)器層次結(jié)構(gòu)如下圖

圖2 CPU中的緩存金字塔

一般而言，高速緩存（cache）是一個(gè)小而快的存儲(chǔ)設(shè)備，它作為存儲(chǔ)在更大也更慢的設(shè)備中的數(shù)據(jù)對(duì)象的緩沖區(qū)域。使用高速緩存的過(guò)程成為緩存（caching）。cache的效率由命中率來(lái)衡量，一個(gè)好的cache效率通常在80%-95%的命中率。

---

3. 緩存命中和不命中

緩存命中

在存儲(chǔ)器層次結(jié)構(gòu)中，假設(shè)層次從上到下是增序排列，假設(shè)一個(gè)k值，當(dāng)程序需要第k+1層的某個(gè)數(shù)據(jù)對(duì)象d時(shí)，它首先在第k層的一塊中查找d，如果d剛好緩存在k層中，就是緩存命中(cache hit).

2. 緩存不命中

當(dāng)在k層找不到數(shù)據(jù)d時(shí)，我們就稱(chēng)k層緩存不命中(cache miss)。當(dāng)發(fā)生緩存不命中的時(shí)候，第k層緩存從第k+1層緩存中取出包含d的那個(gè)塊，如果k層緩存滿(mǎn)了，就會(huì)覆蓋現(xiàn)有的塊。
覆蓋一個(gè)現(xiàn)存的塊的過(guò)程稱(chēng)為替換(replacing)或驅(qū)逐(evicting)這個(gè)塊。被驅(qū)逐的塊稱(chēng)為犧牲(victim)塊。關(guān)于替換哪個(gè)具體的塊是由替換策略來(lái)控制的。比如隨機(jī)替換策略，或最少最近被使用策略(LRU)。

緩存不命中的種類(lèi)

• 強(qiáng)制不命中或冷不命中：這種不命中是由于緩存是空的，它通常是短暫的，不會(huì)在反復(fù)訪(fǎng)問(wèn)存儲(chǔ)器的過(guò)程中出現(xiàn)。
• 沖突不命中：這種緩存是由于放置策略引起的。如下圖所示，如果程序請(qǐng)求0，然后8，然后0，然后8，就會(huì)出現(xiàn)每次都不命中

圖3

• 容量不命中：當(dāng)工作集的大小超過(guò)了緩存的大小的時(shí)候，不能處理這個(gè)工作集，就會(huì)發(fā)生容量不命中。

高速緩存存儲(chǔ)器(SRAM)層級(jí)

• L1（一級(jí)緩存）：一般與處理器同片封裝，訪(fǎng)問(wèn)速度幾乎和寄存器一樣快，通常是2-4個(gè)時(shí)鐘周期，大小為8KB-128KB
• L2（二級(jí)緩存）：可以在chip中也可以在外部，訪(fǎng)問(wèn)速度大約是是10個(gè)時(shí)鐘周期，大小為64KB-8MB
• L3（三級(jí)緩存）：在chip外部被多核處理器共享，訪(fǎng)問(wèn)速度大約是30～40個(gè)時(shí)鐘周期，大小為4MB-128MB
• L4（四級(jí)緩存）：cc-NUMA集群系統(tǒng)的遠(yuǎn)程cache，大小比L3緩存大（大于512MB).

---

4. 高速緩存結(jié)構(gòu)

一般而言，高速緩存的結(jié)構(gòu)可以用元組(S, E, B, m)來(lái)表示，緩存大小C=B×E×S。如下圖所示，每個(gè)存儲(chǔ)器有m位，一個(gè)機(jī)器的高速緩存是一個(gè)有S個(gè)高速緩存組（cache set）的數(shù)組，每個(gè)組包含E行高速緩存行（cache line），每個(gè)行由一個(gè)B字節(jié)的數(shù)據(jù)塊，一個(gè)有效位（valid bit）表示這個(gè)行是否有有意義的信息，t個(gè)（t=m-(b+s)）標(biāo)志位（用于標(biāo)識(shí)存儲(chǔ)在這個(gè)高速緩存塊中的位置）組成。

圖4

高速緩存確定一個(gè)請(qǐng)求是否命中，然后取出被請(qǐng)求的字的過(guò)程分為3步：

- 組選擇

- 行匹配

- 字抽取

人們根據(jù)E(每個(gè)組的行數(shù))的不同把高速緩存分成不同類(lèi)，主要有

1. 直接映射高速緩存(Direct Mapped cache)

每個(gè)組只有一行的高速緩存為直接映射高速緩存。

圖5

直接映射緩存的操作：

1）組選擇：根據(jù)s位組索引位選擇出組；2）行匹配：確定是否有字w的拷貝存儲(chǔ)在組的高速緩存行中，當(dāng)設(shè)置了有效位，并且行中的標(biāo)記與w的地址中的標(biāo)記相匹配的時(shí)候，我們認(rèn)為這一行包含w的一個(gè)拷貝。因?yàn)槊總€(gè)組只有一行，所以很快就可以完成。如果找到了就是命中，反之不命中。 3）如果不命中要進(jìn)行行替換 4）取出數(shù)據(jù)塊

2. 組相聯(lián)高速緩存(Set Associative cache)

我們知道，直接映射高速緩存會(huì)造成沖突不命中，原因是每個(gè)組織有一行。那么組相聯(lián)高速緩存則是1圖6

3. 全相聯(lián)高速緩存(Fully Associative cache)

全相聯(lián)高速緩存的條件是E=C/B，也就是緩存只有一組，組中包含E行。這樣的相聯(lián)完全免去了索引的使用

圖7

---

5. 緩存策略

在緩存的讀寫(xiě)操作中，有不同的策略來(lái)指導(dǎo)操作的順序以及位置。

1. 替換策略

上文提到，覆蓋一個(gè)現(xiàn)存的塊的時(shí)候會(huì)使用替換策略，替換策略有很多種，主要有：

LRU - Least Recently Used
通常用于組相聯(lián)高速緩存，會(huì)有一個(gè)age counter（替換index）與每個(gè)數(shù)組S相關(guān)。這個(gè)counter最大值就是S，當(dāng)一個(gè)set被訪(fǎng)問(wèn)到，那么比它低的counter就被置為0，其他set自增1。舉個(gè)例子，有4個(gè)set的緩存，原本的counter值是0-3-2-1，如果第三個(gè)被訪(fǎng)問(wèn)到了，那么counter的值是1-3-0-2。

FIFO - First-In First-Out
先進(jìn)先出策略，通常用于組相聯(lián)高速緩存。

LFU – Least Frequently Used
很高效的算法，但很耗資源，通常不用。

Round-robin
用于全相聯(lián)高速緩存。有一個(gè)指針指向?qū)⒁惶鎿Q的行，當(dāng)行被替換，指針就會(huì)自增1，指針是環(huán)形的。

Random
隨機(jī)策略，用于全相聯(lián)高速緩存。每個(gè)時(shí)序Round-robin就要更新，而不是每個(gè)替換操作。

2. 回寫(xiě)策略

cache的回寫(xiě)策略決定怎么把cache的數(shù)據(jù)寫(xiě)到內(nèi)存的位置中去。有兩種基本的策略：

• 寫(xiě)回（write back）
  寫(xiě)回是指，僅當(dāng)一個(gè)緩存塊需要被替換回內(nèi)存時(shí)，才將其內(nèi)容寫(xiě)入內(nèi)存。如果緩存命中，則總是不用更新內(nèi)存。為了減少內(nèi)存寫(xiě)操作，緩存塊通常還設(shè)有一個(gè)臟位（dirty bit），用以標(biāo)識(shí)該塊在被載入之后是否發(fā)生過(guò)更新。如果一個(gè)緩存塊在被置換回內(nèi)存之前從未被寫(xiě)入過(guò)，則可以免去回寫(xiě)操作。寫(xiě)回的優(yōu)點(diǎn)是節(jié)省了大量的寫(xiě)操作。這主要是因?yàn)?#xff0c;對(duì)一個(gè)數(shù)據(jù)塊內(nèi)不同單元的更新僅需一次寫(xiě)操作即可完成。這種內(nèi)存帶寬上的節(jié)省進(jìn)一步降低了能耗，因此頗適用于嵌入式系統(tǒng)。
• 寫(xiě)通（write through）
  寫(xiě)通是指，每當(dāng)緩存接收到寫(xiě)數(shù)據(jù)指令，都直接將數(shù)據(jù)寫(xiě)回到內(nèi)存。如果此數(shù)據(jù)地址也在緩存中，則必須同時(shí)更新緩存。由于這種設(shè)計(jì)會(huì)引發(fā)造成大量寫(xiě)內(nèi)存操作，有必要設(shè)置一個(gè)緩沖來(lái)減少硬件沖突。這個(gè)緩沖稱(chēng)作寫(xiě)緩沖器（Write buffer），通常不超過(guò)4個(gè)緩存塊大小。不過(guò)，出于同樣的目的，寫(xiě)緩沖器也可以用于寫(xiě)回型緩存。
  寫(xiě)通較寫(xiě)回易于實(shí)現(xiàn)，并且能更簡(jiǎn)單地維持?jǐn)?shù)據(jù)一致性。

6. 如何編寫(xiě)高速緩存友好的代碼

當(dāng)明白了高速緩存的原理后，我們?cè)诰幊痰倪^(guò)程中應(yīng)該試著去編寫(xiě)高速緩存友好的代碼。什么樣的代碼算是高速緩存友好的代碼？局部性比較好的程序往往有更高的緩存命中率，而緩存命中率更高，代碼運(yùn)行的速度就更快。確保代碼高速緩存友好的方法有：

讓最常見(jiàn)的情況運(yùn)行得快。
程序通常大部分時(shí)間都在少量的核心函數(shù)上，而核心函數(shù)大部分時(shí)間都花在循環(huán)上面，讓這些循環(huán)執(zhí)行得快一點(diǎn)是我們需要關(guān)注的地方。

在每個(gè)循環(huán)內(nèi)部緩存不命中率數(shù)量小。
舉個(gè)經(jīng)典的二維數(shù)據(jù)相加求和的例子：

int colsarray(int a[M][N]) {int i,j,sum=0;for(j = 0; j<N; j++)for(i = 0; i<M; i++)sum += a[i][j];return sum; }

這個(gè)程序中內(nèi)循環(huán)遍歷行，外循環(huán)遍歷列，一列一列地掃描過(guò)來(lái)，而由于緩存從內(nèi)存中抓取的幾乎都是同行不同列的數(shù)據(jù)，這樣如果a[i][0]失效，從內(nèi)存中抓取的數(shù)據(jù)實(shí)際上包括了a[i][0]-a[i][7](假定使用32字節(jié)大小的緩存塊，每個(gè)整型值占四字節(jié)),這樣后面7次循環(huán)緩存都可以命中。大大提高了緩存命中率。那么可以得到大概3/4的命中率。

如果只是做個(gè)小改動(dòng),把內(nèi)外循環(huán)交換一下，那么就是一列一列地掃描過(guò)來(lái)，命中率大大降低。

int colsarray(int a[M][N]) {int i,j,sum=0;for(i = 0; i<M; i++)for(j = 0; j<N; j++)sum += a[i][j];return sum; }

在實(shí)際的運(yùn)行過(guò)程中，第一種的程序比第二種快2倍。

7. 緩存隔離方法

同一臺(tái)服務(wù)器上的CPU數(shù)量在近幾年一直在增加，32核->48核->72核，為了提高資源使用率，同一臺(tái)機(jī)器上會(huì)同時(shí)運(yùn)行很多應(yīng)用，在同一個(gè)物理CPU的不同邏輯CPU上或者某個(gè)CPU package上不同物理CPU運(yùn)行的應(yīng)用會(huì)共享LLC(Last level cache)，這樣一個(gè)batch應(yīng)用如果需要大量的讀寫(xiě)LLC，會(huì)占據(jù)大部分LLC，導(dǎo)致LS(Latency Sensitive)應(yīng)用在讀取數(shù)據(jù)時(shí)產(chǎn)生cache miss,對(duì)于LS應(yīng)用來(lái)說(shuō)，batch應(yīng)用會(huì)是一個(gè)noisy neighbor。

Intel在CPU微架構(gòu)Haswell開(kāi)始引入RDT（Resource Director Technology）技術(shù),其中有一個(gè)功能是Cache Allocation Technology (CAT)，可以通過(guò)設(shè)置給不同的core分配不同的cache way，做到cache資源隔離?？梢哉J(rèn)為CAT使得LLC變成了一種支持QoS（Quality of Service）的資源，操作系統(tǒng)或者容器軟件可以限制應(yīng)用只能使用為其劃分的部分cache區(qū)域，為不同應(yīng)用劃分的cache區(qū)域可以重疊。該功能在分配cache line時(shí)起作用，比如讀取數(shù)據(jù)到cache的時(shí)候。不同的cache區(qū)域是通過(guò)CLOS（Class of Service）標(biāo)記來(lái)區(qū)分的，每個(gè)CLOS有一個(gè)CBM（Cache Bit Mask）。CBM是一個(gè)連續(xù)的bits，定義了每個(gè)cache區(qū)域可用的cache大小。

CAT可以在cloud和container環(huán)境下，更好的分配管理具有大LLC的高性能服務(wù)器。比如具有72個(gè)core的服務(wù)器上，需要同時(shí)運(yùn)行web服務(wù)器，數(shù)據(jù)庫(kù)和Map Reduce任務(wù)等?？梢酝ㄟ^(guò)cache的分區(qū)隔離，使不同應(yīng)用同時(shí)達(dá)到更好的資源共享效果。
因?yàn)镃AT支持在應(yīng)用運(yùn)行時(shí)動(dòng)態(tài)修改cache的分區(qū)，可以配合上層監(jiān)控系統(tǒng)更好的優(yōu)化LS的性能同時(shí)最小化對(duì)batch應(yīng)用的影響。

一個(gè)典型的例子就是解決之前提到的noisy neighbor。在container環(huán)境下，一個(gè)運(yùn)行在container里面的streaming應(yīng)用不停的讀寫(xiě)數(shù)據(jù)導(dǎo)致大量的LLC占用，會(huì)導(dǎo)致同機(jī)器上另外一個(gè)container里運(yùn)行的LS需要的數(shù)據(jù)被evict出LLC，從而導(dǎo)致LS應(yīng)用性能下降。

通過(guò)英特爾? 資源調(diào)配技術(shù)優(yōu)化資源利用?www.intel.cn

有興趣可以查閱Intel Software Developer Manual的第17.17節(jié)。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的4路组相连cache设计_浅谈 Cache的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。