title: CPU Cache
date: 2019-11-17 20:20:30
keywords: cache "CPU cache" "三級緩存" 緩存映射 cache原理 多級cache TLB
Linux的CPU cache
一． CPU 與 Memory 內存之間的三級緩存的實現(xiàn)原理
1.1 cache 存在的原理
??引入 Cache 的理論基礎是程序局部性原理坊罢，包括時間局部性和空間局部性。時間局部性原理即最近被CPU訪問的數(shù)據，短期內CPU 還要訪問（時間）棒拂；空間局部性即被CPU訪問的數(shù)據附近的數(shù)據，CPU短期內還要訪問（空間）哟绊。因此如果將剛剛訪問過的數(shù)據緩存在一個速度比主存快得多的存儲中北救，那下次訪問時，可以直接從這個存儲中取诅妹，其速度可以得到數(shù)量級的提高罚勾。
??CPU緩存是（Cache Memory）位于CPU與內存之間的臨時存儲器，它的容量比內存小但交換速度快吭狡。在緩存中的數(shù)據是內存中的一小部分尖殃，但這一小部分是短時間內CPU即將訪問的，當CPU調用大量數(shù)據時划煮，就可避開內存直接從緩存中調用送丰，從而加快讀取速度。
??在CPU中加入緩存是一種高效的解決方案弛秋，是對于存儲器件成本更低器躏，速度更快這兩個互相矛盾的目標的一個最優(yōu)解決方案牵现，這樣整個內存儲器（緩存+內存）就變成了既有緩存的高速度，又有內存的大容量的存儲系統(tǒng)了邀桑。緩存對CPU的性能影響很大瞎疼，主要是因為CPU的數(shù)據交換順序和CPU與緩存間的帶寬引起的。
下圖是一個典型的存儲器層次結構壁畸，我們可以看到一共使用了三級緩存
各級存儲訪問延遲的對比
1.2 cpu 三級cache
??介于CPU和主存儲器間的高速小容量存儲器贼急，由靜態(tài)存儲芯片SRAM組成，容量較小但比主存DRAM技術更加昂貴而快速捏萍， 接近于CPU的速度太抓。CPU往往需要重復讀取同樣的數(shù)據塊， Cache的引入與緩存容量的增大令杈，可以大幅提升CPU內部讀取數(shù)據的命中率走敌，從而提高系統(tǒng)性能。通常由高速存儲器逗噩、聯(lián)想存儲器掉丽、地址轉換部件异雁、替換部件等組成捶障。如圖所示。
- 聯(lián)想存儲器：根據內容進行尋址的存儲器（馮氏模型中是按照地址進行尋址纲刀，但在高速存儲器中往往只存有部分信息项炼，此時需要根據內容進行檢索）
- 地址轉換部件：通過聯(lián)想存儲器建立目錄表以實現(xiàn)快速地址轉換。命中時直接訪問Cache示绊；未命中時從內存讀取放入Cache
- 替換部件：在緩存已滿時按一定策略進行數(shù)據塊替換锭部，并修改地址轉換部件
??早期采用外部（Off-chip）Cache，不做在CPU內而是獨立設置一個Cache∶婧郑現(xiàn)在采用片內（On-chip）Cache拌禾，將Cache和CPU作在一個芯片上，且采用多級Cache盆耽，同時使用L1 Cache和L2 Cache蹋砚，甚至有L3 Cache。
- 一般L1 Cache都是分立Cache摄杂，分為數(shù)據緩存和指令緩存坝咐，可以減少訪存沖突引起的結構冒險，這樣多條指令可以并行執(zhí)行析恢；內置墨坚；其成本最高，對CPU的性能影響最大
多級Cache的情況下，L1 Cache的命中時間比命中率更重要 - 一般L2 Cache都是聯(lián)合Cache泽篮，這樣空間利用率高
沒有L3 Cache的情況下盗尸，L2 Cache的命中率比命中時間更重要（缺失時需從主存取數(shù)，并要送L1和L2 cache）
- L3 Cache多為外置帽撑，在游戲和服務器領域有效泼各；但對很多應用來說，總線改善比設置L3更加有利于提升系統(tǒng)性能
??上圖顯示了最簡單的緩存配置亏拉。它對應著最早期使用CPU cache的系統(tǒng)的架構扣蜻。CPU內核不再直接連接到主內存。所有的數(shù)據加載和存儲都必須經過緩存及塘。CPU核心與緩存之間的連接是一種特殊的快速連接莽使。在一個簡化的表示中，主存和高速緩存連接到系統(tǒng)總線笙僚，該系統(tǒng)總線也可用于與系統(tǒng)的其他組件進行通信芳肌。我們引入了系統(tǒng)總線（現(xiàn)代叫做“FSB”）。
引入緩存后不久肋层，系統(tǒng)變得更加復雜亿笤。高速緩存和主存之間的速度差異再次增大，使得另一個級別的高速緩存不得不被添加進來槽驶，它比第一級高速緩存更大且更慢责嚷。出于經濟原因鸳兽，僅增加第一級緩存的大小不是一種選擇掂铐。今天，甚至有機器在生產環(huán)境中使用了三級緩存揍异。帶有這種處理器的系統(tǒng)如圖下所示全陨。隨著單個CPU的內核數(shù)量的增加，未來的緩存級別數(shù)量可能會增加≈灾溃現(xiàn)在已經出現(xiàn)了擁有四級cache的處理器了辱姨。
??上圖展示了三級緩存的結構。L1d是一級數(shù)據cache戚嗅，L1i是一級指令cache雨涛。請注意，這只是一個示意圖; 現(xiàn)實中的數(shù)據流從core到主存的過程中不需要經過任何更高級別的cache懦胞。CPU設計人員有很大的自由來設計cache的接口替久。對于程序員來說，這些設計選擇是不可見的躏尉。
另外蚯根，我們有擁有多個core的處理器，每個core可以有多個“線程”胀糜。核心和線程之間的區(qū)別在于颅拦，獨立的核心具有所有硬件資源的獨立的副本蒂誉，早期的多核處理器，甚至具有單獨的第二級緩存而沒有第三級緩存距帅。核心可以完全獨立運行右锨，除非它們在同一時間使用相同的資源，例如與外部的連接碌秸。另一方面陡蝇，線程們共享幾乎所有的處理器資源哮肚。英特爾的線程實現(xiàn)只為線程提供單獨的寄存器登夫，甚至是有限的，還有一些寄存器是共享的允趟。
一個現(xiàn)代CPU的完整概貌如圖所示恼策。
- i-cache和d-cache都是32KB、8路潮剪、4個時鐘周期涣楷；
- L2 cache：256KB 、8路抗碰、11個時鐘周期狮斗。
- 所有核共享的L3 cache：8MB、16路弧蝇、30~40個時鐘周期碳褒。
- Core i7中所有cache的塊大小都是64B
1.3 cpu cache與TLB的聯(lián)系
??由于cache中對應的都是主存地址，即物理地址看疗，在cqu查看具體數(shù)據是否在cache中時沙峻，如果CPU傳送過來的地址時一個虛擬地址，需要將其轉換成實際物理地址再到cache中去尋找两芳。Cache的實現(xiàn)需要TLB的幫助摔寨。可以說TLB命中是Cache命中的基本條件怖辆。TLB不命中是复，會更新TLB項，這個代價非常大竖螃，Cache命中的好處基本都沒有了淑廊。在TLB命中的情況下，物理地址才能夠被選出斑鼻，Cache的命中與否才能夠達成蒋纬。
1.3.1 TLB的概述
??TLB是一個內存管理單元用于改進虛擬地址到物理地址轉換速度的緩存。TLB是位于內存中的頁表的cache，如果沒有TLB蜀备，則每次取數(shù)據都需要兩次訪問內存,即查頁表獲得物理地址和取數(shù)據关摇。
1.3.2 TLB的原理
??當cpu對數(shù)據進行讀請求時,CPU根據虛擬地址(前20位)到TLB中查找.TLB中保存著虛擬地址(前20位)和頁框號的對映關系,如果匹配到虛擬地址就可以迅速找到頁框號(頁框號可以理解為頁表項),通過頁框號與虛擬地址后12位的偏移組合得到最終的物理地址.
??如果沒在TLB中匹配到虛擬地址,就出現(xiàn)TLB丟失,需要到頁表中查詢頁表項,如果不在頁表中,說明要讀取的內容不在內存,需要到磁盤讀取.
??TLB是MMU中的一塊高速緩存,也是一種Cache.在分頁機制中,TLB中的數(shù)據和頁表的數(shù)據關聯(lián),不是由處理器維護,而是由OS來維護,TLB的刷新是通過裝入處理器中的CR3寄存器來完成.如果MMU發(fā)現(xiàn)在TLB中沒有命中,它在常規(guī)的頁表查找后,用找到的頁表項替換TLB中的一個條目.
1.3.3 TLB的刷新原則
??當進程進行上下文切換時重新設置cr3寄存器,并且刷新tlb.
有兩種情況可以避免刷tlb.
第一種情況是使用相同頁表的進程切換.
第二種情況是普通進程切換到內核線程.
lazy-tlb(懶惰模式)的技術是為了避免進程切換導致tlb被刷新.
當普通進程切換到內核線程時,系統(tǒng)進入lazy-tlb模式,切到普通進程時退出該模式.
1.3.4 cache的概念
??cache是為了解決處理器與慢速DRAM(慢速DRAM即內存)設備之間巨大的速度差異而出現(xiàn)的。cache屬于硬件系統(tǒng),linux不能管理cache.但會提供flush整個cache的接口.
cache分為一級cache,二級cache,三級cache等等.一級cache與cpu處于同一個指令周期.
1.3.5 Cache的存取單位(Cache Line)
??CPU從來不從DRAM直接讀/寫字節(jié)或字,從CPU到DRAM的每次讀或寫的第一步都要經過L1 cache,每次以整數(shù)行讀或寫到DRAM中.Cache Line是cache與DRAM同步的最小單位.典型的虛擬內存頁面大小為4KB,而典型的Cache line通常的大小為32或64字節(jié).
??CPU 讀/寫內存都要通過Cache,如果數(shù)據不在Cache中,需要把數(shù)據以Cache Line為單位去填充到Cache,即使是讀/寫一個字節(jié).CPU 不存在直接讀/寫內存的情況,每次讀/寫內存都要經過Cache.
1.3.6 Cache的工作模式
- 數(shù)據回寫(write-back):這是最高性能的模式,也是最典型的,在回寫模式下,cache內容更改不需要每次都寫回內存,直到一個新的 cache要刷新或軟件要求刷新時,才寫回內存.
- 寫通過(write-through):這種模式比回寫模式效率低,因為它每次強制將內容寫回內存,以額外地保存cache的結果,在這種模式寫耗時,而讀和回寫模一樣快,這都為了內存與cache相一致而付出的代價.
- 預取 (prefectching):一些cache允許處理器對cache line進行預取,以響應讀請求,這樣被讀取的相鄰內容也同時被讀出來,如果讀是隨機的,將會使CPU變慢,預取一般與軟件進行配合以達到最高性能.
二. 各級緩存中數(shù)據的包含關系
2.1 整個緩存和主存間
??緩存里有的數(shù)據，主存中一定存在。
2.2 各級緩存之間
??一級緩存中還分數(shù)據緩存（data cache站刑，d-cache）和指令緩存（instruction cache，i-cache）宪睹。二者分別用來存放數(shù)據和執(zhí)行這些數(shù)據的指令，而且兩者可以同時被cpu訪問蚕钦，所以一級cache間數(shù)據時獨立的亭病。
??一級沒有的數(shù)據二級可能有也可能沒有。因為一級緩存miss會接著訪問二級緩存嘶居。
??一級有二級一定有罪帖，三級也一定有。因為一級的數(shù)據從二級中讀上來的邮屁。在一級缺失二級命中時發(fā)生整袁。
??二級沒有的數(shù)據三級可能有也可能沒有。因為二級確實會接著訪問三級緩存佑吝。找不到會繼續(xù)訪問主存坐昙。
??二級有的數(shù)據三級一定有。在二級缺失三級命中時芋忿，數(shù)據會從三級緩存提到二級緩存炸客。
??三級沒有的數(shù)據，主存可能有也可能沒有盗飒。三級緩存缺失嚷量，會訪問主存，主存也缺失就要從外存訪問數(shù)據了逆趣。
??三級緩存有的數(shù)據主存一定有。因為在三級缺失主存命中時嗜历，數(shù)據會從主存提到三級緩存中來宣渗。
三. 各級緩存的大小設置
??一級緩存就是指CPU第一層級的高速緩存，主要是為了緩存指令和緩存數(shù)據梨州，一級緩存的容量對CPU性能影響非常大痕囱，但是因為成本太高，所以一般容量特別小暴匠，也就256KB左右鞍恢。
??二級緩存是CPU第二層級的高速緩存，對于CPU來說，二級緩存容量越大越好帮掉，它是直接影響CPU性能的弦悉，CPU每個核心都會有自己的緩存，一個CPU的二級緩存容量是所有核心二級緩存容量的總和蟆炊。
??三級緩存就是CPU第三層級的高速緩存稽莉，主要是為了降低與內存進行數(shù)據傳輸時的延遲問題，三級緩存與一二級不同涩搓，三級緩存只有一個污秆，它是所有核心共享，所以在CPU參數(shù)中可以看到昧甘，三級緩存相對于其他兩級緩存來說都很大良拼。
??由于緩存的設置與OS無關且透明，所以對于不同的體系架構下不同的處理器對待緩存區(qū)域的處理和方式都不同充边，不同的處理器也有不同的緩存設置值将饺。從主流的處理器cache大小來看，一般一個cache line的大小都是固定的64B左右痛黎，這是經過經驗得到的比較合理的大小予弧，一般一級cache大小在數(shù)十KB左右，二級cache大小在數(shù)十到數(shù)百KB左右湖饱，而L3 cache大小在數(shù)MB左右掖蛤。
四. 各級緩存之間的數(shù)據放置與數(shù)據淘汰策略
??由于三級cache一般來說是運用于擁有多核的處理器，對于單核處理器來說二級cache就能夠足夠保持夠高的cache命中率井厌。所以一般的三級cache一般只針對于多核處理器蚓庭。L1和L2級cache是處理器核所單獨的內容。L1又可以看成是L2的cache仅仆。L2可以看成是L3級cache的cache器赞。所以我們分兩個部分討論數(shù)據放置與數(shù)據淘汰策略。
4.1 各級cache之間數(shù)據放置方式
??各級cache間的數(shù)據放置策略主要有三種墓拜。直接相連映射港柜，全相聯(lián)映射和組相聯(lián)映射。將一個主存塊存儲到唯一的一個Cache行咳榜。對應的大小都是一個cache line的大小夏醉，一般來說是64B。
4.1.1直接相連映射
??多對一的映射關系涌韩，但一個主存塊只能拷貝到cache的一個特定行位置上去畔柔。cache的行號i和主存的塊號j有如下函數(shù)關系：i=j mod m（m為cache中的總行數(shù)）。
- 優(yōu)點：硬件簡單臣樱，容易實現(xiàn)
- 缺點：命中率低靶擦， Cache的存儲空間利用率低
4.1.2全相聯(lián)映射
??可以將一個主存塊存儲到任意一個Cache行腮考。
主存的一個塊直接拷貝到cache中的任意一行上
- 優(yōu)點：命中率較高，Cache的存儲空間利用率高
- 缺點：線路復雜玄捕，成本高踩蔚，速度低
4.1.3組相聯(lián)映射
??可以將一個主存塊存儲到唯一的一個Cache組中任意一個行。
將cache分成u組桩盲，每組v行寂纪，主存塊存放到哪個組是固定的，至于存到該組哪一行是靈活的赌结，即有如下函數(shù)關系：cache總行數(shù)m＝u×v 組號q＝j mod u
??組間采用直接映射捞蛋，組內為全相聯(lián)。硬件較簡單柬姚，速度較快拟杉，命中率較高。是現(xiàn)代處理器中一般所常用的映射方式量承。
4.2 數(shù)據淘汰策略
??Cache工作原理要求它盡量保存最新數(shù)據搬设，當從主存向Cache傳送一個新塊，而Cache中可用位置已被占滿時撕捍，就會產生Cache替換的問題拿穴。
常用的替換算法有下面三種。
4.2.1 LFU
??LFU（Least Frequently Used忧风，最不經常使用）算法將一段時間內被訪問次數(shù)最少的那個塊替換出去默色。每塊設置一個計數(shù)器，從0開始計數(shù)狮腿，每訪問一次腿宰，被訪塊的計數(shù)器就增1。當需要替換時缘厢，將計數(shù)值最小的塊換出吃度，同時將所有塊的計數(shù)器都清零。
這種算法將計數(shù)周期限定在對這些特定塊兩次替換之間的間隔時間內贴硫，不能嚴格反映近期訪問情況椿每，新調入的塊很容易被替換出去。
4.2.2 LRU
??LRU（Least Recently Used夜畴，近期最少使用）算法是把CPU近期最少使用的塊替換出去拖刃。這種替換方法需要隨時記錄Cache中各塊的使用情況，以便確定哪個塊是近期最少使用的塊贪绘。每塊也設置一個計數(shù)器，Cache每命中一次央碟，命中塊計數(shù)器清零税灌，其他各塊計數(shù)器增1均函。當需要替換時，將計數(shù)值最大的塊換出菱涤。
??LRU算法相對合理苞也，但實現(xiàn)起來比較復雜，系統(tǒng)開銷較大粘秆。這種算法保護了剛調入Cache的新數(shù)據塊如迟，具有較高的命中率。LRU算法不能肯定調出去的塊近期不會再被使用攻走，所以這種替換算法不能算作最合理殷勘、最優(yōu)秀的算法。但是研究表明昔搂，采用這種算法可使Cache的命中率達到90%左右玲销。
4.2.3 隨機替換
??最簡單的替換算法是隨機替換。隨機替換算法完全不管Cache的情況摘符，簡單地根據一個隨機數(shù)選擇一塊替換出去贤斜。隨機替換算法在硬件上容易實現(xiàn)，且速度也比前兩種算法快逛裤。缺點則是降低了命中率和Cache工作效率瘩绒。
五. 整個緩存結構的訪問流程
5.1 查找命中
??處理器微架構訪問Cache的方法與訪問主存儲器有類似之處。主存儲器使用地址編碼方式带族，微架構可以地址尋址方式訪問這些存儲器锁荔。Cache也使用了類似的地址編碼方式，微架構也是使用這些地址操縱著各級Cache炉菲，可以將數(shù)據寫入Cache堕战，也可以從Cache中讀出內容。只是這一切微架構針對Cache的操作并不是簡單的地址訪問操作拍霜。為簡化起見嘱丢，我們忽略各類Virtual Cache，討論最基礎的Cache訪問操作祠饺，并借此討論CPU如何使用TLB完成虛實地址轉換越驻，最終完成對Cache的讀寫操作。
??Cache的存在使得CPU Core的存儲器讀寫操作略微顯得復雜道偷。CPU Core在進行存儲器方式時缀旁，首先使用EPN(Effective Page Number)進行虛實地址轉換，并同時使用CLN(Cache Line Number)查找合適的Cache Block勺鸦。這兩個步驟可以同時進行并巍。在使用Virtual Cache時，還可以使用虛擬地址對Cache進行尋址换途。為簡化起見懊渡，我們并不考慮Virtual Cache的實現(xiàn)細節(jié)刽射。
??EPN經過轉換后得到VPN，之后在TLB中查找并得到最終的RPN(Real Page Number)剃执。如果期間發(fā)生了TLB Miss誓禁，將帶來一系列的嚴重的系統(tǒng)懲罰，我們只討論TLB Hit的情況肾档，此時將很快獲得合適的RPN摹恰，并依此得到PA(Physical Address)。
??在多數(shù)處理器微架構中怒见，Cache由多行多列組成俗慈，使用CLN進行索引最終可以得到一個完整的Cache Block。但是在這個Cache Block中的數(shù)據并不一定是CPU Core所需要的速种。因此有必要進行一些檢查姜盈，將Cache Block中存放的Address與通過虛實地址轉換得到的PA進行地址比較(Compare Address)。如果結果相同而且狀態(tài)位匹配配阵，則表明Cache Hit馏颂。此時微架構再經過Byte Select and Align部件最終獲得所需要的數(shù)據。如果發(fā)生Cache Miss棋傍，CPU需要使用PA進一步索引主存儲器獲得最終的數(shù)據救拉。
??由上文的分析，我們可以發(fā)現(xiàn)瘫拣，一個Cache Block由預先存放的地址信息亿絮，狀態(tài)位和數(shù)據單元組成。一個Cache由多個這樣的Cache Block組成麸拄，在不同的微架構中派昧，可以使用不同的Cache Block組成結構。我們首先分析單個Cache Block的組成結構拢切。單個Cache Block由Tag字段蒂萎，狀態(tài)位和數(shù)據單元組成，如圖所示淮椰。
??其中Data字段存放該Cache Block中的數(shù)據五慈，在多數(shù)處理器微架構中，其大小為32或者64字節(jié)主穗。Status字段存放當前Cache Block的狀態(tài)泻拦，在多數(shù)處理器系統(tǒng)中，這個狀態(tài)字段包含MESI忽媒，MOESI或者MESIF這些狀態(tài)信息争拐，在有些微架構的Cache Block中，還存在一個L位晦雨，表示當前Cache Block是否可以鎖定陆错。許多將Cache模擬成SRAM的微架構就是利用了這個L位灯抛。有關MOESIFL這些狀態(tài)位的說明將在下文中詳細描述金赦。在多核處理器和復雜的Cache Hierarchy環(huán)境下音瓷，狀態(tài)信息遠不止MOESIF。
??RAT(Real Address Tag)記錄在該Cache Block中存放的Data字段與那個地址相關夹抗，在RAT中存放的是部分物理地址信息绳慎，雖然在一個CPU中物理地址可能有40，46或者48位漠烧，但是在Cache中并不需要存放全部地址信息杏愤。因為從Cache的角度上看，CPU使用的地址被分解成為了若干段已脓，如圖所示珊楼。
??這個地址也可以理解為CPU訪問Cache使用的地址，由多個數(shù)據段組成度液。首先需要說明的是Cache Line Index字段厕宗。這一字段與Cache Line Number類似，CPU使用該字段從Cache中選擇一個或者一組Entry堕担。
??Bank和Byte字段之和確定了單個Cache的Data字段長度已慢，通常也將這個長度稱為Cache 行長度，上圖所示的微架構中的Cache Block長度為64字節(jié)霹购。目前多數(shù)支持DDR3 SDRAM的微架構使用的Cache Block長度都是64字節(jié)佑惠。部分原因是由于DDR3 SDRAM的一次Burst Line為8，一次基本Burst操作訪問的數(shù)據大小為64字節(jié)齐疙。
??在處理器微架構中膜楷，將地址為Bank和Byte兩個字段出于提高Cache Block訪問效率的考慮。Multi-Bank Mechanism是一種常用的提高訪問效率的方法贞奋，采用這種機制后赌厅，CPU訪問Cache時，只要不是對同一個Bank進行訪問忆矛，即可并發(fā)執(zhí)行察蹲。Byte字段決定了Cache的端口位寬，在現(xiàn)代微架構中催训，訪問Cache的總線位寬為64位或者為128位洽议。
??剩余的字段即為Real Address Tag，這個字段與單個Cache中的Real Address Tag的字段長度相同漫拭。CPU使用地址中的Real Address Tag字段與Cache Block的對應字段和一些狀態(tài)位進行聯(lián)合比較亚兄，判斷其訪問數(shù)據是否在Cache中命中
5.2 cache 不命中
??如果cache miss,就去下一級cache或者主存中去查找數(shù)據，并將查找到的數(shù)據采用上面的數(shù)據淘汰策略將數(shù)據替換到cache中采驻。
5.3 cache和主存數(shù)據一致性保持
??由于在發(fā)生cache miss時會產生數(shù)據替換审胚，在運行過程中緩存的數(shù)據也可能會被修改匈勋。所以需要一個策略來保持數(shù)據在緩存和主存間的一致性。
Cache寫機制分為write through和write back兩種膳叨。
Write-through（直寫模式）在數(shù)據更新時洽洁，同時寫入緩存Cache和主存存儲。此模式的優(yōu)點是操作簡單菲嘴；缺點是因為數(shù)據修改需要同時寫入存儲饿自，數(shù)據寫入速度較慢。
Write-back（回寫模式）在數(shù)據更新時只寫入緩存Cache龄坪。只在數(shù)據被替換出緩存時昭雌，被修改的緩存數(shù)據才會被寫到后端存儲。此模式的優(yōu)點是數(shù)據寫入速度快健田，因為不需要寫存儲烛卧；缺點是一旦更新后的數(shù)據未被寫入存儲時出現(xiàn)系統(tǒng)掉電的情況，數(shù)據將無法找回妓局。
