CPU Cache是如何映射與尋址的？-魔扣目錄

CPU Cache的組織結構
Cache與內存地址映射
- 直接映射
- 全相聯映射
- 組相聯映射
Cache尋址方式
VIVT、VIPT、PIPT(補充)
尾語
往期推薦

哈嘍，大家好，我是呼嚕嚕，在上一篇文章我們介紹了突破計算機性能瓶頸的利器CPU Cache，今天我們來聊聊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種的實現方式：

直接映射(direct-mApped)，也就是每個組Set只有一個Cache Line，選中Set之后不需要和Set中的每個Line進行比對
全相連映射(fully associative)，即只有一個Set，所以這個Set中包含所有的Line
組相連映射(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

tag：與Cache Line中的tag匹配,內存地址的前24bit
set index：set索引，用來尋找定位Set，內存地址中間的6個bit，正好能查詢2^6=64個line
block offset：塊偏移量，用來尋找Cache Line里data中的內存數據，內存地址最后6位

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

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

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

VIVT、VIPT、PIPT(補充)

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

VIVT（Virtually Indexed, Virtually Tagged ）表示index和tag都是采用虛擬地址
VIPT（Virtually Indexed, Physically Tagged ）表示index采用虛擬地址，tag采用物理地址，一般用于L1 Cache
PIPT（Physically Indexed, Physically Tagged ）表示index采用物理地址，tag采用物理地址，一般用于L2 Cache