cache在計(jì)算機(jī)組織結(jié)構(gòu)中很重要，理解cache對(duì)編寫(xiě)性能友好的程序很有幫助。
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)自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主頻和主板總線頻率的差異不斷拉大腕巡，主板緩存在速度上的對(duì)內(nèi)存優(yōu)勢(shì)不斷縮水。因此血筑，從Pentium Pro起绘沉，二級(jí)緩存開(kāi)始和處理器一起封裝，頻率亦與CPU相同（稱為全速二級(jí)緩存）或?yàn)镃PU主頻的一半（稱為半速二級(jí)緩存）豺总。
AMD則從K6-III開(kāi)始引入三級(jí)緩存车伞。基于Socket 7接口的K6-III擁有64KB和256KB的同片封裝兩級(jí)緩存园欣，以及可達(dá)2MB的三級(jí)主板緩存帖世。
今天的CPU將三級(jí)緩存全部集成到CPU芯片上休蟹。
多核CPU通常為每個(gè)核配有獨(dú)享的一級(jí)和二級(jí)緩存沸枯，以及各核之間共享的三級(jí)緩存。
2. 什么是Cache
字面上理解就是赂弓，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──稱為Internet臨時(shí)文件夾或網(wǎng)絡(luò)內(nèi)容緩存等杨耙。凡是位于速度相差較大的兩種硬件之間赤套，用于協(xié)調(diào)兩者數(shù)據(jù)傳輸速度差異的結(jié)構(gòu)，均可稱之為Cache珊膜。
- 硬件的cache：CPU cache容握，GPU cache，DSP（數(shù)字信號(hào)處理器）车柠；
-
軟件的cache：Disk Cache剔氏，Web Cache，數(shù)據(jù)庫(kù)的Cache等竹祷。
image.png
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).
顯然從k層讀取數(shù)據(jù)是要比k+1層速度快很多的吹菱。
緩存不命中
當(dāng)在k層找不到數(shù)據(jù)d時(shí)巍虫，我們就稱k層緩存不命中(cache miss)。當(dāng)發(fā)生緩存不命中的時(shí)候鳍刷，第k層緩存從第k+1層緩存中取出包含d的那個(gè)塊占遥，如果k層緩存滿了，就會(huì)覆蓋現(xiàn)有的塊输瓜。
覆蓋一個(gè)現(xiàn)存的塊的過(guò)程稱為替換(replacing)或驅(qū)逐(evicting)這個(gè)塊瓦胎。被驅(qū)逐的塊稱為犧牲(victim)塊。關(guān)于替換哪個(gè)具體的塊是由替換策略來(lái)控制的尤揣。比如隨機(jī)替換策略搔啊，或最少最近被使用策略(LRU)。
緩存不命中的種類
-
強(qiáng)制不命中或冷不命中：這種不命中是由于緩存是空的北戏，它通常是短暫的负芋，不會(huì)在反復(fù)訪問(wèn)存儲(chǔ)器的過(guò)程中出現(xiàn)。
image.png
image.png
-
沖突不命中：這種緩存是由于放置策略引起的嗜愈。如下圖所示旧蛾，放置如果程序請(qǐng)求0，然后8蠕嫁，然后0锨天，然后8，在k層緩存中對(duì)這兩個(gè)塊的每次引用都不會(huì)命中剃毒，即便k層有4個(gè)緩存塊
image.png - 容量不命中：當(dāng)工作集的大小超過(guò)了緩存的大小的時(shí)候病袄，不能處理這個(gè)工作集，就會(huì)發(fā)生容量不命中赘阀。
高速緩存存儲(chǔ)器(SRAM)層級(jí)
- L1（一級(jí)緩存）：一般與處理器同片封裝益缠，訪問(wèn)速度幾乎和寄存器一樣快，通常是2-4個(gè)時(shí)鐘周期基公，大小為8KB-128KB
- L2（二級(jí)緩存）：可以在chip中也可以在外部幅慌，訪問(wèn)速度大約是是10個(gè)時(shí)鐘周期，大小為64KB-8MB
- L3（三級(jí)緩存）：在chip外部被多核處理器共享酌媒，訪問(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è)高速緩存塊中的位置）組成。
假設(shè)我們有這樣一個(gè)系統(tǒng),它有一個(gè)CPU云茸、一個(gè)寄存器文件是目、一個(gè)L1高速緩存和一個(gè)主存。當(dāng)CPU執(zhí)行一條讀內(nèi)存字w的指令,它向L1高速緩存請(qǐng)求這個(gè)字标捺。如果L1高速緩存有w的一個(gè)緩存的副本,那么就得到L1高速緩存命中,高速緩存會(huì)很快抽取出,并將它返回給CPU懊纳。否則就是緩存不命中,當(dāng)L1高速緩存向主存請(qǐng)求包含w的塊的一個(gè)副本時(shí),CPU必須等待。當(dāng)被請(qǐng)求的塊最終從內(nèi)存到達(dá)時(shí),L1高速緩存將這個(gè)塊存放在它的一個(gè)高速緩存行里,從被存儲(chǔ)的塊中抽取出字w,然后將它返回CPU亡容。高速緩存確定一個(gè)請(qǐng)求是否命中嗤疯，然后抽取出被請(qǐng)求的字的過(guò)程分為：
- 組選擇
- 行匹配
- 字抽取
人們根據(jù)E(每個(gè)組的行數(shù))的不同把高速緩存分成不同類，主要有
（1） 直接映射高速緩存(Direct Mapped cache)
組選擇
行匹配
字選擇
行替換
總結(jié)來(lái)說(shuō)就是以下步驟：
- 組選擇：根據(jù)s位組索引位選擇出組闺兢；
- 行匹配：確定是否有字w的拷貝存儲(chǔ)在組的高速緩存行中茂缚，當(dāng)設(shè)置了有效位，并且行中的標(biāo)記與w的地址中的標(biāo)記相匹配的時(shí)候屋谭，我們認(rèn)為這一行包含w的一個(gè)拷貝脚囊。因?yàn)槊總€(gè)組只有一行，所以很快就可以完成戴而。如果找到了就是命中凑术，反之不命中翩蘸。
- 如果不命中要進(jìn)行行替換
- 取出數(shù)據(jù)塊
一個(gè)示例
沖突不命中
中間位索引的意義
（2） 組相聯(lián)高速緩存(Set Associative cache)
組選擇
同直接映射高速緩存的組選擇過(guò)程所意。
行匹配和字選擇
行替換
關(guān)于行替換更多詳細(xì)內(nèi)容后面替換策略部分會(huì)講解
（3）全相聯(lián)高速緩存(Fully Associative cache)
全相聯(lián)高速緩存的條件是E=C/B，也就是緩存只有一組催首，組中包含E行扶踊。這樣的相聯(lián)完全免去了索引的使用
組選擇
行匹配和字選擇
（4）三種方式的性能總結(jié)
每次CUP所訪問(wèn)的單元在cache中，則命中郎任，命中的概率為p秧耗，命中時(shí)CPU在cache中直接存取信息，所用時(shí)間開(kāi)銷(xiāo)稱為命中時(shí)間舶治，其值為cache訪問(wèn)時(shí)間分井，缺失時(shí)需要從主存讀取一個(gè)主存塊，同時(shí)將所需信息送入CPU霉猛，所用時(shí)間開(kāi)銷(xiāo)稱為主存訪問(wèn)時(shí)間
與cache訪問(wèn)時(shí)間
之和
CPU在cache-主存的平均訪問(wèn)時(shí)間為：
由于程序訪問(wèn)的局部性特點(diǎn)尺锚，cache命中率p在80%以上甚至接近于1，即便主存訪問(wèn)時(shí)間遠(yuǎn)大于cache訪問(wèn)時(shí)間惜浅，然而最終平均訪問(wèn)時(shí)間接近于cache的訪問(wèn)時(shí)間
在以上基礎(chǔ)上瘫辩，對(duì)三種映射方式作出總結(jié)：
- 直接映射的優(yōu)點(diǎn)是容易實(shí)現(xiàn)，命中時(shí)間短，但當(dāng)多個(gè)塊映射到同一cache行時(shí)伐厌，訪問(wèn)又引發(fā)不停地抖動(dòng)時(shí)承绸，即便別的cache行都空閑，也會(huì)引起頻繁的調(diào)進(jìn)調(diào)出挣轨，也就導(dǎo)致了命中率較低
- 全相聯(lián)映射下军熏，只要有空閑cache行，就不會(huì)引發(fā)沖突卷扮，因而塊沖突概率低羞迷，但時(shí)間開(kāi)銷(xiāo)和原件開(kāi)銷(xiāo)大，實(shí)現(xiàn)困難画饥，只適合小容量的cache
- 組相聯(lián)映射結(jié)合前兩者的優(yōu)點(diǎn)衔瓮，沖突概率比直接映射低，同時(shí)在開(kāi)銷(xiāo)上比全相聯(lián)映射小抖甘，速度也很快
5. 緩存策略
在緩存的讀寫(xiě)操作中热鞍，有不同的策略來(lái)指導(dǎo)操作的順序以及位置。
（1）替換策略
當(dāng)新的一個(gè)主存塊復(fù)制到cache時(shí)衔彻，cache對(duì)應(yīng)的組（如果有的話）包含的行可能已經(jīng)被全部占滿薇宠，此時(shí)必須淘汰掉一個(gè)cache行。直接映射的行替換因?yàn)橹挥幸恍屑瓒睿灾苯犹鎿Q就可以了澄港，但另外兩種映射的行替換有以下幾種方式：
-
FIFO - First-In First-Out：先進(jìn)先出算法，總是選擇最早裝入cache的緩存行將其替換柄沮。其算法實(shí)現(xiàn)方便回梧，但不能正確反映程序的訪問(wèn)局部性，通常用于組相聯(lián)高速緩存祖搓。
image.png -
LRU - Least Recently Used：最近最少用算法狱意，總是選擇近期最少使用的緩存行，可以正確反映程序的訪問(wèn)局部性拯欧，這個(gè)緩存算法將最近使用的條目存放到靠近緩存頂部的位置详囤。當(dāng)一個(gè)新條目被訪問(wèn)時(shí)，LRU將它放置到緩存的頂部镐作。當(dāng)緩存達(dá)到極限時(shí)藏姐，較早之前訪問(wèn)的條目將從緩存底部開(kāi)始被移除。這里會(huì)使用到昂貴的算法该贾，而且它需要記錄“年齡位”來(lái)精確顯示條目是何時(shí)被訪問(wèn)的羔杨。此外，當(dāng)一個(gè)LRU緩存算法刪除某個(gè)條目后靶庙，“年齡位”將隨其他條目發(fā)生改變问畅。通常用于組相聯(lián)高速緩存娃属。
image.png
-
LFU – Least Frequently Used:最不經(jīng)常使用算法，這個(gè)緩存算法使用一個(gè)計(jì)數(shù)器來(lái)記錄條目被訪問(wèn)的頻率护姆。通過(guò)使用LFU緩存算法矾端，最低訪問(wèn)數(shù)的條目首先被移除。這個(gè)方法并不經(jīng)常使用卵皂，因?yàn)樗鼰o(wú)法對(duì)一個(gè)擁有最初高訪問(wèn)率之后長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)的條目緩存負(fù)責(zé)秩铆。
image.png - Random：隨機(jī)策略算法，從候選行中隨機(jī)選取一個(gè)替換掉灯变，與使用情況無(wú)關(guān)殴玛，其性能一般，但代價(jià)很低添祸。
以上幾種替換策略也會(huì)應(yīng)用在數(shù)據(jù)庫(kù)的緩存比如Redis中滚粟，對(duì)以上算法實(shí)現(xiàn)的java代碼展示，見(jiàn)
（2） 回寫(xiě)策略
cache的回寫(xiě)策略決定怎么把cache的數(shù)據(jù)寫(xiě)到內(nèi)存的位置中去刃泌。當(dāng)發(fā)生回寫(xiě)時(shí)凡壤，由于cache的內(nèi)容是部分主存塊的副本，因此當(dāng)CPU進(jìn)行寫(xiě)操作需要對(duì)cache中的內(nèi)容進(jìn)行更新耙替，就要考慮cache和主存的數(shù)據(jù)一致性問(wèn)題亚侠，此外以下情況也會(huì)出現(xiàn)一致性問(wèn)題：
- 當(dāng)多個(gè)設(shè)備都允許訪問(wèn)主存時(shí)。例如磁盤(pán)類的高速I(mǎi)/O設(shè)備可以通過(guò)DMA方式直接與主存交換數(shù)據(jù)俗扇，如果cache中的內(nèi)容被CPU修改而主存塊沒(méi)有更新硝烂，則從主存?zhèn)魉偷絀/O設(shè)備的內(nèi)容就無(wú)效；同樣的铜幽，當(dāng)I/O設(shè)備修改了主存塊的內(nèi)容滞谢，則對(duì)應(yīng)（如果有的話）cache行的內(nèi)容將就無(wú)效
- 當(dāng)多個(gè)CPU都帶有各自的cache而共享主存時(shí)。在多CPU系統(tǒng)啥酱，如果某個(gè)CPU修改了自身cache的內(nèi)容爹凹，則對(duì)應(yīng)的主存塊和其他CPU對(duì)應(yīng)的cache行的內(nèi)容都變?yōu)闊o(wú)效
未解決一致性問(wèn)題厨诸，通常采用如下兩種寫(xiě)操作方式：
- 通寫(xiě)（write through）
通寫(xiě)是指镶殷，每當(dāng)CPU執(zhí)行寫(xiě)操作時(shí)，若寫(xiě)命中微酬，則同時(shí)寫(xiě)cache和主存绘趋，若寫(xiě)不命中，則分為兩種方式：寫(xiě)分配法颗管，更新主存陷遮，同時(shí)將更新的主存塊放入cache中；非寫(xiě)分配法垦江，僅更新主存帽馋，不對(duì)cache做操作。前者開(kāi)銷(xiāo)更大，但也充分利用了空間局部性绽族。
由于通寫(xiě)會(huì)引發(fā)造成大量寫(xiě)內(nèi)存操作姨涡，有必要設(shè)置一個(gè)緩沖來(lái)減少硬件沖突。這個(gè)緩沖稱作寫(xiě)緩沖器（Write buffer）吧慢，采用FIFO隊(duì)列涛漂，通常不超過(guò)4個(gè)緩存塊大小。在寫(xiě)操作不頻繁發(fā)生時(shí)性能不錯(cuò)检诗，但在寫(xiě)操作頻繁發(fā)生時(shí)則會(huì)因?yàn)閷?xiě)緩沖飽和而發(fā)生阻塞匈仗。
通寫(xiě)較寫(xiě)回易于實(shí)現(xiàn)，并且能更簡(jiǎn)單地維持?jǐn)?shù)據(jù)一致性逢慌。
- 回寫(xiě)（write back）
回寫(xiě)是指悠轩，僅當(dāng)寫(xiě)不命中，也就是一個(gè)緩存塊需要被替換回內(nèi)存時(shí)攻泼，才將其內(nèi)容寫(xiě)入內(nèi)存哗蜈。如果寫(xiě)命中，則總是不用更新內(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)椋瑢?duì)一個(gè)數(shù)據(jù)塊內(nèi)不同單元的更新僅需一次寫(xiě)操作即可完成焰望。這種內(nèi)存帶寬上的節(jié)省進(jìn)一步降低了能耗骚亿，因此頗適用于嵌入式系統(tǒng)。
但由于回寫(xiě)沒(méi)法同步更新cache和主存的內(nèi)容熊赖，所以有內(nèi)容不一致的潛在隱患来屠，需要其他同步機(jī)制保證存儲(chǔ)信息的一致性。
- 總結(jié)
對(duì)試圖編寫(xiě)對(duì)高速緩存友好的程序來(lái)說(shuō),我們建議在心里采用一個(gè)使用寫(xiě)回和寫(xiě)分配的高速緩存的模型震鹉。這樣建議有幾個(gè)原因俱笛。通常,由于較長(zhǎng)的傳送時(shí)間,存儲(chǔ)器層次結(jié)構(gòu)中較低層的緩存更可能使 用寫(xiě)回,而不是通寫(xiě)。例如,虛擬內(nèi)存系統(tǒng)(用主存作為存儲(chǔ)在磁盤(pán)上的塊的緩存)只使用寫(xiě)回传趾。但是由于邏輯電路密度的提高,寫(xiě)回的高復(fù)雜性也越來(lái)越不成為阻礙了,我們?cè)诂F(xiàn)代系統(tǒng)的所有層次上都能看到寫(xiě)回緩存迎膜。所以這種假設(shè)符合當(dāng)前的趨勢(shì)。使用寫(xiě)回寫(xiě)分配方法的另一個(gè)原因是,它與處理讀的方式相對(duì)稱,因?yàn)閷?xiě)回寫(xiě)分配試圖利用局部性浆兰。 因此,我們可以在高層次上開(kāi)發(fā)我們的程序,展示良好的空間和時(shí)間局部性,而不是試圖為某一個(gè)存儲(chǔ)器系統(tǒng)進(jìn)行優(yōu)化磕仅。
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ù)量小。在其他條件（加載和存儲(chǔ)的次數(shù)）相同的情況下溶诞，不命中率較低的循環(huán)運(yùn)行的更快鸯檬。
舉個(gè)經(jīng)典的二維數(shù)據(jù)相加求和的例子：
int colsarray(int a[M][N])
{
int i,j,sum=0;
for(i = 0; i<N; i++)
for(j = 0; j<M; j++)
sum += a[i][j];
return sum;
}
這個(gè)程序中內(nèi)循環(huán)遍歷行，外循環(huán)遍歷列螺垢，一列一列地掃描過(guò)來(lái)喧务，而由于緩存從內(nèi)存中抓取的幾乎都是同行不同列的數(shù)據(jù)，在接下來(lái)的循環(huán)中幾乎沒(méi)法被重負(fù)利用枉圃。如果只是做個(gè)小改動(dòng),把內(nèi)外循環(huán)交換一下
int rowsarray(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;
}
這樣如果a[i][0]失效功茴，從內(nèi)存中抓取的數(shù)據(jù)實(shí)際上包括了a[i][0]-a[i]7,這樣后面7次循環(huán)緩存都可以命中。大大提高了緩存命中率孽亲。在實(shí)際的運(yùn)行過(guò)程中坎穿，第二種的程序比第一種快2倍。
