CPU Cache 是如何映射與尋址的？

CPU Cache 的組織結構

CPU Cache的組織結構：CPU Cache被劃分成多個組Set，每個Set中還可以有多個行Cache Line，需要注意的是 Cache Line 是 CPU Cache 中的基本緩存單位，也有人叫它塊（Block），也就是說它每次讀寫不是一個字節的去讀寫，而是以Cache Line爲單位，一塊塊地去讀取

一般主流的 CPU 的 Cache Line 大小是 64 Byte，當然也有其他大小，在 Cache 塊比較小的時候，這時的命中率很低，隨着塊大小的增加，空間局部性起作用，命中率會快速提高；如下圖：這種增加趨勢在某一個最佳塊大小處達到最大值。當到達頂峯以後，命中率隨着塊大小的增加反而會逐漸降低。因爲當塊大小非常大時，進入 Cache 中的許多數據可能根本用不上，同時隨着塊繼續增大，時間局部性會逐漸失去作用

而 CPU Line 又由有效標誌Valid、標誌Tag、數據塊Data這 3 個部分組成，其中 data 是真正要來緩存一片連續內存地址中的數據，而 tag 是用來查找 Cache Line 的標誌，存儲這片連續數據的公共地址，valid 表示當前緩存的數據是否有效，也可以用來協助查找 Cache Line

可以參考下圖：

Cache 與內存地址映射

我們知道高速緩存的速度要遠遠快於主存 (內存) 的速度，但 Cache 的容量卻是遠遠小於主存，相較於主存的價格，緩存則昂貴的多

另一方面 CPU Cache 是需要緩存內存中的數據，無論對 Cache 數據讀取還是寫入，CPU 都需要知道訪問的內存數據，對應於 Cache 上的哪個位置，而由於 Cache 容量不夠，無法做到 Cache 與內存地址一一對應

那麼 Cache 是如何與內存地址進行映射的？

其實CPU Cache主要有 3 種的實現方式：

  1. 直接映射 (direct-mapped)，也就是每個組Set只有一個Cache Line，選中 Set 之後不需要和 Set 中的每個 Line 進行比對

  2. 全相連映射 (fully associative)，即只有一個 Set，所以這個 Set 中包含所有的 Line

  3. 組相連映射 (set-associative)， 有多個 Set，每個 Set 有多個 Line；需要注意的是，組相連也會被稱爲路 Way，比如 6 路組相聯，表示每個 Set 有 6 個 Line

直接映射

直接映射會在內存塊和緩存塊之間建立起固定的映射關係，也就是內存中的某個塊總是映射到 Cache 的一特定塊上

在 Linux 內核中，並非總使用基於我們更熟悉的頁來當頁緩存。內核的早期版本使用了塊緩存，來加速文件系統，提高系統性能

我們這裏以 8 塊主存和 4 塊 (行) 爲例，具體如下圖所示：

通過上圖，我們可以發現 B0 塊和 B4 塊主存只能映射到 Cache 的第 0 塊，B3 塊和 B7 塊只能只能映射到 Cache 的第 3 塊，其他內存塊同理

其實相當於給主存空間按照Cache Line的大小 (也就是 Line 的行數) 來進行分區，每個內存塊編號需要與Cache Line的大小取模，得到固定的映射位置即區內編號，映射到與它區內編號相同的Cache Line上

可以發現直接映射的優點：查找效率高，硬件設備簡單，地址變換速度快，但是它也有缺點：由於每個主存塊只有一個固定位置可存放，即使 Cache 中別的 Line 空着也不能佔用，無法充分利用 Cache 空間，這樣衝突概率較大

如果衝突了，這多個內存塊會不斷地交替裝入固定的映射 Cache Line 中，導致緩存命中率降低，所以直接映射適合大容量 Cache

全相聯映射

全相聯映射 主存的數據可以放在任意一個 Cache line 中**，映射方式比較靈活，**Cache 的利用率高，塊衝突的概率低，因爲只有當所有的 Line 都被佔滿後纔會出現衝突

但是另一方面，訪問緩存時，每次都要和全部 Line 中的內存進行比較，速度低延遲高是它無法避免的缺點，因此適合於小容量 Cache 採用

組相聯映射

組相聯映射是直接映射和全相聯映射的折中方案，吸取 2 者的優點，儘量避免 2 者的缺點，組間採用直接映射，組內採用全相聯映射，即主存塊存放到哪個組 Set 是固定的，存到 Set 內哪一個Cache Line是靈活隨意的

當查找緩存時，不再需要全部進行遍歷，只需先查到 cache 的組號，然後在那一組內，進行小範圍遍歷。這樣衝突概率較小，同時命中率較高，所以這種方式在現代的處理器中得到了廣泛的應用

Cache 尋址方式

通過前文的閱讀，相信大家都對 CPU Cache 的組織結構和 Cache 與內存地址映射方式有所瞭解，而 Intel 多數處理器的 L1 Cache 都是32KB，8-Way 組相聯，Cache Line 是 64 Byte，我們以這個參數爲例，來看看 Cache 是如何尋址的？

因爲 Cache Line 是最小單位（64Bytes），所以可以得出Cache Line的條數 = 32KB /64=512，每一Way的Cache Line條數 = 512 / 8 = 64(也就是每一個Set的Cache Line條數)

那麼我們可以得到，每一Set的內存大小 = 64 x 64 = 4096B=4KB，是不是很熟悉，這不正是一個內存頁 page 的大小嘛！本文前面用塊來劃分內存，和頁一樣都是內存劃分的方式，在操作系統中，頁是固定大小的存儲單元，而塊是可變大小的存儲單元

首先我們得知道內存地址如何被分解？內存地址被分成了 3 部分：tag, set index和block offset

  1. tag：與 Cache Line 中的 tag 匹配, 內存地址的前 24bit

  2. set index：set 索引，用來尋找定位 Set，內存地址中間的 6 個 bit，正好能查詢 2^6=64 個 line

  3. block offset：塊偏移量，用來尋找 Cache Line 裏 data 中的內存數據，內存地址最後 6 位

那麼 Cache 尋址的具體方式，我們可以將其分爲 3 個步驟：

  1. 先根據 set index 來找到對應的 Set

  2. 接着根據 tag 在上一步步找到的 set 中找到對應的Cache Line, 如果找到且對應的有效位valid爲 1，表示緩存命中，反之無論其中的 tag 和Cache Line 裏的數據內容是什麼，CPU 都不會管這些數據，而是會直接訪問主存，重新加載數據 (當然這裏涉及到緩存一致性的問題，比較複雜，先挖個坑，本文暫不講解)，那如果沒找到，說明當前發生 cache 缺失，即 cache miss

  3. 最後根據block offset在上一步找到的 Cache Line 的 data 中找到對應內存的數據

筆者這裏再吐血畫了張圖，幫助大家更加直觀瞭解 Cache 尋址的具體方式

VIVT、VIPT、PIPT(補充)

最後再介紹一下幾個概念，就是 Cache 尋址時，可以根據物理地址，也可以根據虛擬地址，或者二者結合起來查找

  1. VIVT（Virtually Indexed, Virtually Tagged ）表示 index 和 tag 都是採用虛擬地址

  2. VIPT（Virtually Indexed, Physically Tagged ）表示 index 採用虛擬地址，tag 採用物理地址，一般用於L1 Cache

  3. PIPT（Physically Indexed, Physically Tagged ）表示 index 採用物理地址，tag 採用物理地址，一般用於L2 Cache

尾語

本文先後介紹了 CPU Cache 的組織結構，Cache 與內存‍地址映射的 3 種方式，以組相聯 Cache 來講解 Cache 的尋址方式，畫圖太耗心神了，先到這了，後面我們繼續更新 Cache 的緩存一致性，提高代碼性能等難點

參考資料：

《Cache: a place for concealment and safekeeping》

https://blog.csdn.net/qq_38768922/article/details/78737284

http://staff.ustc.edu.cn/~hdrq/jsjzcyl/text/chapter5/sec3/part4/r1.htm

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Ogs8o7eNlflC5Z5i2WnTAw

猜你喜歡