這篇寫一下計(jì)算機(jī)系統(tǒng)中的緩存Cache應(yīng)用場(chǎng)景和實(shí)現(xiàn)方式介紹。

Memory hierarchy

在講緩存之前，首先要了解計(jì)算機(jī)中的內(nèi)存結(jié)構(gòu)層次Memory hierarchy。也就是下圖金字塔形狀的結(jié)構(gòu)。

從上到下，內(nèi)存層次結(jié)構(gòu)如下：

1. 寄存器：這是計(jì)算機(jī)中最快速的存儲(chǔ)區(qū)域。它們位于處理器內(nèi)，用于存儲(chǔ)即將被處理器執(zhí)行的指令和數(shù)據(jù)。

2. 高速緩存（Cache）：位于處理器和主內(nèi)存之間，用于存儲(chǔ)最近或頻繁訪問的數(shù)據(jù)和指令。高速緩存有多級(jí)（L1、L2、L3），其中L1最接近處理器且速度最快，但也最小。

3. 主內(nèi)存（RAM）：當(dāng)計(jì)算機(jī)運(yùn)行程序時(shí)，程序的代碼和數(shù)據(jù)被加載到主內(nèi)存中。

4. 硬盤驅(qū)動(dòng)器（HDD）或固態(tài)硬盤（SSD）：這些是非易失性的存儲(chǔ)設(shè)備，用于長(zhǎng)期存儲(chǔ)數(shù)據(jù)和程序。

5. 網(wǎng)絡(luò)存儲(chǔ)和云存儲(chǔ)：這些存儲(chǔ)設(shè)備位于本地計(jì)算機(jī)之外，數(shù)據(jù)通常通過網(wǎng)絡(luò)進(jìn)行訪問。

從上到下離CPU就越來越遠(yuǎn)，越往下的部分，容量往往越大，價(jià)格也越便宜；而越靠近CPU的部分，速度越快但是價(jià)格高且容量小。

Locality

局部性原理 (Locality of Reference) 是設(shè)計(jì)內(nèi)存層次結(jié)構(gòu)時(shí)需要考慮的重要因素，也是后面緩存為什么能夠起作用的原因。

• 時(shí)間局部性（Temporal Locality）：如果一個(gè)數(shù)據(jù)或指令在某個(gè)時(shí)間點(diǎn)被訪問，那么在未來的一段時(shí)間內(nèi)，這個(gè)數(shù)據(jù)或指令可能會(huì)被再次訪問。這是由于程序的執(zhí)行往往具有重復(fù)性，例如循環(huán)和遞歸。高速緩存就是基于時(shí)間局部性設(shè)計(jì)的，將最近訪問過的數(shù)據(jù)和指令存儲(chǔ)在快速訪問的緩存中。

• 空間局部性（Spatial Locality）：如果一個(gè)數(shù)據(jù)或指令被訪問，那么在未來的一段時(shí)間內(nèi)，其附近的數(shù)據(jù)或指令也可能會(huì)被訪問。這是由于程序的執(zhí)行通常具有連續(xù)性，例如順序執(zhí)行的指令和數(shù)組的元素。內(nèi)存管理系統(tǒng)會(huì)將整個(gè)塊（包含了訪問數(shù)據(jù)或指令的附近地址）加載到高速緩存或主內(nèi)存中，以利用空間局部性。

緩存Cache

如果我們把用過地址放在CPU里的存儲(chǔ)單元，或者說一個(gè)更接近CPU、更能快速獲取的地方，就有了我們廣義概念上的“Cache”了。雖然這個(gè)地方很小，但基于locality的原理，程序傾向于使用之前的地址或者之前地址附近地址，每次CPU像訪問數(shù)據(jù)，它都會(huì)優(yōu)先從cache里查找（因?yàn)殡x得更近），如果是那種多次反復(fù)需要的數(shù)據(jù)，就可以直接讓cache來提前處理了，提高數(shù)據(jù)獲取速度。

當(dāng)然，畢竟cache的位置有限，如果請(qǐng)求的數(shù)據(jù)沒有在cache里（這叫做cache miss），就只能把cache中的數(shù)據(jù)刪掉（比如最久沒用的那個(gè)），然后把新數(shù)據(jù)從下面更慢的內(nèi)存結(jié)構(gòu)中獲取后替換上去。

幾種Cache miss

Cache miss主要有以下三種：

1. 冷（強(qiáng)制）未命中（Cold or Compulsory Miss）
   冷未命中是因?yàn)榫彺骈_始時(shí)是空的，而這是對(duì)該塊的第一次引用。換句話說，這是無法避免的未命中，因?yàn)楫?dāng)你第一次訪問一個(gè)數(shù)據(jù)塊時(shí)，它不可能已經(jīng)在緩存中。

2. 容量未命中（Capacity Miss）
   當(dāng)活動(dòng)的緩存塊集合（工作集）大于緩存的容量時(shí)，就會(huì)發(fā)生容量未命中。即使數(shù)據(jù)塊之前已在緩存中，但由于緩存空間有限，可能已經(jīng)被其他更近期訪問的數(shù)據(jù)塊替換出去。

3. 沖突未命中（Conflict Miss）
   前兩個(gè)都比較好理解，這個(gè)沖突未命中比較復(fù)雜，我用通俗的語(yǔ)言講大概是這樣：比如我們教室有三排學(xué)生，每排都有一個(gè)椅子當(dāng)作cache，那么我們cache一共有3個(gè)，學(xué)生有3排。這個(gè)時(shí)候如果規(guī)定每排學(xué)生只能用對(duì)應(yīng)的一把椅子，就會(huì)發(fā)生conflict miss。比如第一排第一個(gè)同學(xué)有了一個(gè)行為，他被存儲(chǔ)在了第一個(gè)椅子上；這個(gè)時(shí)候第一排第二個(gè)同學(xué)又有一個(gè)行為，我們只會(huì)用第二個(gè)同學(xué)去換下第一個(gè)同學(xué)——即使這個(gè)時(shí)候還有兩把椅子是空的。當(dāng)最后再次訪問第一個(gè)同學(xué)時(shí)，你會(huì)發(fā)現(xiàn)明明第一個(gè)同學(xué)之前訪問過，明明cache里有空位，但就是在cache里找不到他，這種情況下的miss就叫做conflict miss。

Cache的參數(shù)和大小表示

高速緩存（Cache）的總大小可以由以下三個(gè)參數(shù)描述：

• S：緩存的集數(shù)（Set）。
• E：每個(gè)集中的線數(shù)（Line），也就是每個(gè)集中的緩存塊數(shù)量（Cache blocks per set）。
• B：每個(gè)緩存塊的大?。⊿ize of each block）。

而Cache set就等于 S × E × B。

?Cache的結(jié)構(gòu)看起來這么麻煩，如何存儲(chǔ)數(shù)據(jù)呢？對(duì)于一個(gè)數(shù)據(jù)，如cache會(huì)根據(jù)它的地址來劃分和存儲(chǔ)。

如上圖所示，通常地址會(huì)被劃分成3部分：塊偏移量（block offset）、集索引（set index）和標(biāo)簽（tag）。

• 塊偏移量（Block Offset）：這部分的位數(shù)取決于每個(gè)cache塊（或行）的大小。例如，如果一個(gè)塊的大小是16字節(jié)，那么塊偏移量就需要4位（因?yàn)?^4 = 16），用于確定一個(gè)字節(jié)在其塊中的位置。

• 集索引（Set Index）：這部分的位數(shù)取決于cache的集數(shù)。例如，如果有64個(gè)集，集索引就需要6位（因?yàn)?^6 = 64），用于確定一個(gè)塊應(yīng)該存儲(chǔ)在哪個(gè)集中。

• 標(biāo)簽（Tag）：地址中剩下的位被用作標(biāo)簽，用于在cache查找過程中區(qū)分不同的內(nèi)存塊。

所以對(duì)于一個(gè)地址，大致的查找流程是這樣的：首先進(jìn)行地址分割，就像上面說的那樣分成三部分；其次拿著集索引去cache中找到對(duì)應(yīng)的集，拿到了這個(gè)集（可以理解成圖里的一整行藍(lán)色背景，包含很多l(xiāng)ine），我們查找所有l(wèi)ine（通常會(huì)并行查找來提高速度），找到那個(gè)line，which有效位（valid bit）是1以及tag標(biāo)簽和地址劃分出來的tag部分一樣，如果找到了，則使用塊偏移量從這個(gè)集中取出所需的數(shù)據(jù)。

再舉個(gè)例子，在上面這個(gè)圖中，?block塊大小是8，因此我們需要3個(gè)位作為block offset，這里offset是100也就是4，那么數(shù)據(jù)到時(shí)候會(huì)從第4位開始，也就是圖中綠色塊部分；集的個(gè)數(shù)不知道，集索引的位數(shù)也不確定，但這里0...01不管中間幾個(gè)0，都是1，表示對(duì)應(yīng)第一個(gè)集。在剩下的部分就是兩個(gè)紅色部分的tag比較了。

用這句話來檢查一下你是否理解：這里雖然得到的塊偏移量是4，但是你可以發(fā)現(xiàn)我們把4往后的部分也都放在cache里了（綠色部分）。因?yàn)檫@樣的話如果下次訪問這個(gè)同樣的地址+1，按找那套流程算下來其實(shí)直接就對(duì)應(yīng)塊偏移量為5的部分，直接就在cache里了！這就是cache對(duì)Spatial Locality也友好的地方——不止是之前訪問過的我有，之前訪問過的鄰居我也有！

Cache的寫操作

當(dāng)我們討論寫操作（write operations）在緩存系統(tǒng)中的行為時(shí)，我們需要考慮兩種基本的情況：寫命中（write hit）和寫未命中（write miss）。在處理這兩種情況時(shí)，有幾種常見的策略：

• 1 寫命中（Write Hit）：當(dāng)我們?cè)噲D寫入的數(shù)據(jù)已在緩存中時(shí)，我們有兩種基本策略：

  • 寫直達(dá)（Write-Through）：這種策略立即將更改寫入到主存儲(chǔ)器和緩存中。這種策略的優(yōu)點(diǎn)是它保持了主存儲(chǔ)器和緩存中的數(shù)據(jù)一致性，但缺點(diǎn)是每次寫操作都需要訪問主存儲(chǔ)器，這可能會(huì)帶來較大的性能開銷。

  • 寫回（Write-Back）：這種策略僅將更改寫入到緩存中，并將緩存行標(biāo)記為"dirty"（通過設(shè)置一個(gè)"dirty bit"）。只有當(dāng)緩存行被替換出緩存時(shí)，更改才會(huì)被寫回到主存儲(chǔ)器。這里的dirty bit就是替換時(shí)用來判斷的，如果是1，那么就需要把整個(gè)緩存行（包含2^b字節(jié)的數(shù)據(jù)塊）寫回（write-back）到主內(nèi)存。這種策略的優(yōu)點(diǎn)是減少了對(duì)主存儲(chǔ)器的訪問次數(shù)，從而提高了性能。但是，這也可能會(huì)導(dǎo)致主存儲(chǔ)器與緩存之間的數(shù)據(jù)不一致。

• 2 寫未命中（Write Miss）：當(dāng)我們?cè)噲D寫入的數(shù)據(jù)不在緩存中時(shí)，我們有兩種基本策略：

  • 不寫分配（No-Write-Allocate）：這種策略直接將數(shù)據(jù)寫入主存儲(chǔ)器，而不將其加載到緩存中。這種策略適用于不希望單次寫操作污染緩存的情況。

  • 寫分配（Write-Allocate）：這種策略在寫入數(shù)據(jù)之前，先將相關(guān)的緩存行加載到緩存中，再將新的寫操作應(yīng)用到這個(gè)緩存行。如果預(yù)計(jì)將來會(huì)有更多對(duì)同一位置的寫操作，這種策略可能會(huì)很有用。

在實(shí)際的系統(tǒng)中，可能會(huì)組合使用這些策略。比如，一種常見的組合是使用寫直達(dá)和不寫分配策略，這種組合可以保持?jǐn)?shù)據(jù)的一致性，而且適合處理散列的、非連續(xù)的寫操作。另一種常見的組合是使用寫回和寫分配策略，這種組合可以減少對(duì)主存儲(chǔ)器的訪問次數(shù)，從而提高性能，尤其是在處理連續(xù)的、集中的寫操作時(shí)。

小結(jié)

這篇文章寫了下cache的概念以及讀寫過程中的讀取策略。cache的緩存命中是非常有用和關(guān)鍵的，可以為程序或許數(shù)據(jù)節(jié)省下非常多時(shí)間。一個(gè)有趣的觀點(diǎn)是，99%的命中率可能比97%的命中率好兩倍。比如假設(shè)緩存命中的時(shí)間為1個(gè)周期，未命中的懲罰為100個(gè)周期。那么：

• 對(duì)于97%的命中率，平均訪問時(shí)間為：1個(gè)周期（命中時(shí)間） + 0.03（未命中率） * 100個(gè)周期（未命中懲罰） = 4個(gè)周期。
• 對(duì)于99%的命中率，平均訪問時(shí)間為：1個(gè)周期（命中時(shí)間） + 0.01（未命中率） * 100個(gè)周期（未命中懲罰） = 2個(gè)周期。

因此，盡管兩者的命中率只相差2%，但是平均訪問時(shí)間卻差了一倍。

所以對(duì)于程序員來說，盡量寫出“緩存友好”的代碼也是能很好提升程序的效率。通過理解緩存的工作方式，我們可以編寫出更有效地利用緩存的代碼，一些常見方式有：

• 重復(fù)引用變量：這是好的（利用時(shí)間局部性Temporal Locality）：如果一個(gè)變量被反復(fù)引用，它可能會(huì)留在緩存中，這樣每次引用都會(huì)命中緩存，從而提高性能。

• 使用跨度為1的引用模式：這是好的（利用空間局部性Spatial Locality）。如果你的代碼按順序訪問數(shù)據(jù)（例如，遍歷數(shù)組），那么緩存系統(tǒng)可能會(huì)預(yù)先加載你即將訪問的數(shù)據(jù)，從而提高緩存命中率。這就是為什么我們一行一行地遍歷二維數(shù)組要比一列一列地遍歷快很多，因?yàn)閿?shù)組在內(nèi)存中是按行存儲(chǔ)，緩存可以幫助我們提前加載到接下來的數(shù)據(jù)。

結(jié)束！文章來源地址http://www.zghlxwxcb.cn/news/detail-608554.html

到了這里，關(guān)于計(jì)算機(jī)內(nèi)存中的緩存Cache Memories的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！