當(dāng)前位置:首頁 > 公眾號精選 > CPP開發(fā)者
[導(dǎo)讀]↓推薦關(guān)注↓大家好,今天給大家分享一篇關(guān)于Cache的硬核的技術(shù)文,基本上關(guān)于Cache的所有知識點(diǎn)都可以在這篇文章里看到。關(guān)于Cache這方面內(nèi)容圖比較多,不想自己畫了,所以圖都來自《ComputerArchitecture:AQuantitativeApproach》。這是一...

推薦關(guān)注↓


大家好,今天給大家分享一篇關(guān)于 Cache 的硬核的技術(shù)文,基本上關(guān)于Cache的所有知識點(diǎn)都可以在這篇文章里看到。


關(guān)于 Cache 這方面內(nèi)容圖比較多,不想自己畫了,所以圖都來自《Computer Architecture : A Quantitative Approach》。


這是一本體系架構(gòu)方面的神書,推薦大家看一下。


本文主要內(nèi)容如下,基本涉及了Cache的概念,工作原理,以及保持一致性的入門內(nèi)容。



1、為什么需要 Cache

1.1 為什么需要 Cache

我們首先從一張圖來開始講為什么需要 Cache.



上圖是 CPU 性能和 Memory 存儲器訪問性能的發(fā)展。


我們可以看到,隨著工藝和設(shè)計(jì)的演進(jìn),CPU 計(jì)算性能其實(shí)發(fā)生了翻天覆地的變化,但是DRAM存儲性能的發(fā)展沒有那么快。


所以造成了一個問題,存儲限制了計(jì)算的發(fā)展。


容量與速度不可兼得。


如何解決這個問題呢?可以從計(jì)算訪問數(shù)據(jù)的規(guī)律入手。


我們隨便貼段代碼:


for (j = 0; j < 100; j = j 1)
for( i = 0; i < 5000; i = i 1)
x[i][j] = 2 * x[i][j];
可以看到,由于大量循環(huán)的存在,我們訪問的數(shù)據(jù)其實(shí)在內(nèi)存中的位置是相近的。


換句專業(yè)點(diǎn)的話說,我們訪問的數(shù)據(jù)有局部性。


我們只需要將這些數(shù)據(jù)放入一個小而快的存儲中,這樣就可以快速訪問相關(guān)數(shù)據(jù)了。


總結(jié)起來,Cache是為了給CPU提供高速存儲訪問,利用數(shù)據(jù)局部性而設(shè)計(jì)的小存儲單元。


1.2 實(shí)際系統(tǒng)中的 Cache

我們展示一下實(shí)際系統(tǒng)中的 Cache 。



如上圖所示,整個系統(tǒng)的存儲架構(gòu)包括了 CPU 的寄存器,L1/L2/L3 CACHE,DRAM 和硬盤。


數(shù)據(jù)訪問時先找寄存器,寄存器里沒有找 L1 Cache, L1 Cache 里沒有找 L2 Cache 依次類推,最后找到硬盤中。


同時,我們可以看到,速度與存儲容量的折衷關(guān)系。容量越小,訪問速度越快!


其中,一個概念需要搞清楚。



CPU 和 Cache 是 word 傳輸?shù)?,?Cache 到主存是以塊傳輸?shù)?,一塊大約 64Byte 。


現(xiàn)有 SOC 中的 Cache 一般組成如下。


1.3 Cache 的分類

Cache按照不同標(biāo)準(zhǔn)分類可以分為若干類。


  • 按照數(shù)據(jù)類型劃分:I-Cache與D-Cache。其中I-Cache負(fù)責(zé)放置指令,D-Cache負(fù)責(zé)方式數(shù)據(jù)。兩者最大的不同是D-Cache里的數(shù)據(jù)可以寫回,I-Cache是只讀的。


  • 按照大小劃分:分為small Cache和large Cache。沒路組(后文組相連介紹)<4KB叫small Cache, 多用于L1 Cache, 大于4KB叫l(wèi)arge Cache。多用于L2及其他Cache.


  • 按照位置劃分:Inner Cache和Outer Cache。一般獨(dú)屬于CPU微架構(gòu)的叫Inner Cache, 例如上圖的L1 L2 CACHE。不屬于CPU微架構(gòu)的叫outer Cache.


  • 按照數(shù)據(jù)關(guān)系劃分:Inclusive/exclusive Cache: 下級Cache包含上級的數(shù)據(jù)叫inclusive Cache。不包含叫exclusive Cache。舉個例子,L3 Cache里有L2 Cache的數(shù)據(jù),則L2 Cache叫exclusive Cache。


2、Cache的工作原理

要講清楚 Cache 的工作原理,需要回答 4 個問題:


  • 數(shù)據(jù)如何放置


  • 數(shù)據(jù)如何查詢


  • 數(shù)據(jù)如何被替換


  • 如果發(fā)生了寫操作,Cache如何處理


2.1 數(shù)據(jù)如何放置

這個問題也好解決。我們舉個簡單的栗子來說明問題。


假設(shè)我們主存中有 32 個塊,而我們的 Cache 一共有 8 個 Cache 行( 一個 Cache 行放一行數(shù)據(jù))。


假設(shè)我們要把主存中的塊 12 放到 Cache 里。


那么應(yīng)該放到 Cache 里什么位置呢?


三種方法:


  • 全相連(Fully associative)??梢苑旁贑ache的任何位置。


  • 直接映射(Direct mapped)。只允許放在Cache的某一行。比如12 mod 8


  • 組相連(set associative)。可以放在Cache的某幾行。例如2路組相連,一共有4組,所以可以放在0,1位置中的一個。


可以看到,全相連和直接映射是Cache組相連的兩種極端情況。


不同的放置方式主要影響有兩點(diǎn):


1、組相連組數(shù)越大,比較電路就越大,但Cache利用率更高,Cache miss發(fā)生的概率小。2、組相連數(shù)目變小,Cache經(jīng)常發(fā)生替換,但是比較電路比較小。


這也好理解,內(nèi)存中的塊在Cache中可放置的位置多,自然找起來就麻煩。


2.2 如何在Cache中找數(shù)據(jù)

其實(shí)找數(shù)據(jù)就是一個比對過程,如下圖所示。



我們地址都以 Byte 為單位的。


但主存于Cache之間的數(shù)據(jù)交換單位都是塊(block,現(xiàn)代Cache一般一個block大約64Byte)。所以地址對最后幾位是block offset。


由于我們采用了組相連,則還有幾個比特代表的是存儲到了哪個組。


組內(nèi)放著若干數(shù)據(jù),我們需要比較Tag, 如果組內(nèi)有Tag出現(xiàn),則說明我們訪問的數(shù)據(jù)在緩存中,可以開心的使用了。


比如舉個 2 路組相連的例子,如下圖所示。



T表示Tag。直接比較Tag,就能得知是不是命中了。如果命中了,則根據(jù)index(組號)將對應(yīng)的塊取出來即可。


如上圖所示。用index選出位于組相連的哪個組。然后并行的比較Tag, 判斷最后是不是在Cache中。上圖是2路組相連,也就是說兩組并行比較。


那如果不在緩存中呢?這就涉及到另一個問題。


不在緩存中如何替換 Cache ?


2.3 如何替換Cache中的數(shù)據(jù)

Cache中的數(shù)據(jù)如何被替換的?這個就比較簡單直接。



  • 隨機(jī)替換。如果發(fā)生Cache miss里隨機(jī)替換掉一塊。


  • Least recently used. LRU。最近使用的塊最后替換。


  • First in, first out (FIFO), 先進(jìn)先出。


實(shí)際上第一個不怎么使用,LRU 和 FIFO 根據(jù)實(shí)際情況選擇即可。


Cache 在什么時候數(shù)據(jù)會被替換內(nèi)?也有幾種策略。


  • 不在本 Cache 替換。如果Cache miss了,直接轉(zhuǎn)發(fā)訪問地址到主存,取到的數(shù)據(jù)不會寫到Cache.


  • 在讀MISS時替換。如果讀的時候Cache里沒有該數(shù)據(jù),則從主存讀取該數(shù)據(jù)后寫入Cache。


  • 在寫MISS時替換。如果寫的時候Cache里沒有該數(shù)據(jù),則將本數(shù)據(jù)調(diào)入Cache再寫。


2.4 如果發(fā)生了寫操作怎么辦

Cache畢竟是個臨時緩存。


如果發(fā)生了寫操作,會造成Cache和主存中的數(shù)據(jù)不一致。如何保證寫數(shù)據(jù)操作正確呢?


也有三種策略。


  • 通寫:直接把數(shù)據(jù)寫回Cache的同時寫回主存。極其影響寫速度。



  • 回寫:先把數(shù)據(jù)寫回Cache, 然后當(dāng)Cache的數(shù)據(jù)被替換時再寫回主存。



  • 通寫隊(duì)列:通寫與回寫的結(jié)合。先寫回一個隊(duì)列,然后慢慢往主存儲寫。如果多次寫同一個數(shù)據(jù),直接寫這個隊(duì)列。避免頻繁寫主存。


3、Cache一致性

Cache 一致性是 Cache 中遇到的比較坑的一個問題。


什么原因需要 Cache 處理一致性呢?


主要是多核系統(tǒng)中,假如core 0讀了主存儲的數(shù)據(jù),寫了數(shù)據(jù)。core 1也讀了主從的數(shù)據(jù)。這個時候core 1并不知道數(shù)據(jù)已經(jīng)被改動了,也就是說,core 1 Cache中的數(shù)據(jù)過時了,會產(chǎn)生錯誤。


Cache一致性的保證就是讓多核訪問不出錯。



Cache一致性主要有兩種策略。


策略一:基于監(jiān)聽的一致性策略

這種策略是所有Cache均監(jiān)聽各Cache的寫操作,如果一個Cache中的數(shù)據(jù)被寫了,有兩種處理辦法。


寫更新協(xié)議:某個Cache發(fā)生寫了,就索性把所有Cache都給更新了。


寫失效協(xié)議:某個Cache發(fā)生寫了,就把其他Cache中的該數(shù)據(jù)塊置為無效。


策略 1 由于監(jiān)聽起來成本比較大,所以只應(yīng)用于極簡單的系統(tǒng)中。


策略二:基于目錄的一致性策略

這種策略是在主存處維護(hù)一張表。記錄各數(shù)據(jù)塊都被寫到了哪些Cache, 從而更新相應(yīng)的狀態(tài)。一般來講這種策略采用的比較多。又分為下面幾個常用的策略。


  • SI: 對于一個數(shù)據(jù)塊來講,有share和invalid兩種狀態(tài)。如果是share狀態(tài),直接通知其他Cache, 將對應(yīng)的塊置為無效。


  • MSI:對于一個數(shù)據(jù)塊來講,有share和invalid,modified三種狀態(tài)。其中modified狀態(tài)表表示該數(shù)據(jù)只屬于這個Cache, 被修改過了。當(dāng)這個數(shù)據(jù)被逐出Cache時更新主存。這么做的好處是避免了大量的主從寫入。同時,如果是invalid時寫該數(shù)據(jù),就要保證其他所有Cache里該數(shù)據(jù)的標(biāo)志位不為M,負(fù)責(zé)要先寫回主存儲。


  • MESI:對于一個數(shù)據(jù)來講,有4個狀態(tài)。modified, invalid, shared, exclusive。其中exclusive狀態(tài)用于標(biāo)識該數(shù)據(jù)與其他Cache不依賴。要寫的時候直接將該Cache狀態(tài)改成M即可。


我們著重講講 MESI。圖中黑線:CPU的訪問。紅線:總線的訪問,其他Cache的訪問。



當(dāng)前狀態(tài)時I狀態(tài)時,如果發(fā)生處理器讀操作 prrd。


  • 如果其他Cache里有這份數(shù)據(jù),如果其他Cache里是M態(tài),先 把M態(tài)寫回主存再讀。否則直接讀。最終狀態(tài)變?yōu)镾。


  • 其他Cache里沒這個數(shù)據(jù),直接變到E狀態(tài)。


當(dāng)前狀態(tài)為S態(tài)。


  • 如果發(fā)生了處理器讀操作,仍然在S態(tài)。


  • 如果發(fā)生了處理器寫操作,則跳轉(zhuǎn)到M狀態(tài)。


  • 如果其他Cache發(fā)生了寫操作,跳到I態(tài)。


當(dāng)前狀態(tài)E態(tài)


  • 發(fā)生了處理器讀操作還是E。


  • 發(fā)生了處理器寫操作變成M。


  • 如果其他Cache發(fā)生了讀操作,變到S狀態(tài)。


當(dāng)前狀態(tài)M態(tài)


  • 發(fā)生了讀操作依舊是M態(tài)。


  • 發(fā)生了寫操作依舊是M態(tài)。


  • 如果其他Cache發(fā)生了讀操作,則將數(shù)據(jù)寫回主存儲,變換到S態(tài)。


4、總結(jié)

Cache 在計(jì)算機(jī)體系架構(gòu)中有非常重要的地位,本文講了 Cache中最主要的內(nèi)容,具體細(xì)節(jié)可以再根據(jù)某個點(diǎn)深入研究。


作者:桔里貓



- EOF -


本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時聯(lián)系本站刪除。
關(guān)閉
關(guān)閉