Cache Memories — Part A

10 min readFeb 27, 2024

以下文章內容是閱讀 CMU csapp 的 Cache Memories 投影片的部分筆記（還沒讀完，不確定有沒有下篇），過程中參考了一些其他資料，會放在文章底部，都推薦看看。

筆記的方式是預設讀者已經知道什麼是 cache 了，所以有些部分會跳很快，筆記的順序也是按照我自己理解的方式紀錄的，歡迎討論 & 勘誤。

簡介

在電腦架構中，CPU 是主要負責運算的，在運算時會需要從 memory 中讀取資料到 CPU 中的 registers 裡，但 CPU 的運算速度很快，相較之下，從 memory 讀取資料的速度是很慢的，總不能讓 CPU 一直在那邊等待，這樣很浪費，解決的方式之一，就是在中間加上 cache 機制。Cache 通常會是一個較小但快速的裝置，我們可以把「比較常用」的資料先搬進 cache 中，再讓 CPU 來讀取，反之亦然，CPU 要寫資料回 memory 時，也可以先寫進 cache，再寫回 memory。

source: Computer Systems: A Programmer’s Perspective

Cache 中的結構

Cache 會分成一塊一塊，稱之為 cache line（或 block），例如 cache 總大小是 64 bytes，8 bytes 一塊的話，那就是會有 64/8 = 8 個 cache line。

這邊有個重要的事：當需要從記憶體中 load 資料進 cache 時，是一次讀進一個 cache line 大小的資料，也就是 cache line 是 cache 跟記憶體之間傳輸的最小單位，例如，雖然我們只是要讀取 0x0001 這個 byte 的資料，但仍須把 0x0000 ~ 0x0007 整個都載進（load） cache 裡。

Memory 遠大於 cache，所以不可能把 memory 中所有的資料都放進 cache裡，那應該要怎麼放呢？而當 CPU 要讀取某個 memory address 的資料時，會先去 cache 中查找看看這個資料是否存在，存在稱為 hit（命中），不存在就稱為 miss，那要怎麼查找呢？

Set-Associate Cache Organization

以下我們來舉個實際的例子，假設：

Cache 的資料總量是 4KB (cache size)
每個 cache line 的大小是 16B（單指 data 的部分）

由以上設定的數字可知，cache line 的數量是 4KB / 16B = 256 個

如果 memory address 是 32 bits，那會需要把 memory address 拆分成以下三個部分：

因為有 256 個 cache line，log 256 = 8，所以需要 8 bits 來紀錄這個資料可能存在哪一個 cache line，這個就是 index
因為每個 cache line 有 16B，log 16 = 4，所以需要 4 bits 來紀錄要讀取的這個 memory address 到底是在這個 cache line 中的哪個位置，這就是 offset
32–8–4 = 20 剩下的這 20 bits 就是 tag

而 cache 如下圖：

圖中每一個方塊就是一個 cache line，這裡面會有 flag（例如 valid flag, dirty flag…等），也會有一個空間在紀錄 tag，最後才是真正的 data。以我們舉例的數字來說，tag 的大小是 20 bits，data 是 16 Bytes。

讀操作

當 CPU 要讀某一個記憶體位址的資料時：

先將這個位址按照 20 bits + 8 bits + 4bits 拆好
用中間這個 8 bits (index) 找到對應的是哪一個 cache line
這塊 cache line 是 valid (valid bit = 1) 的且前 20 bits 去比對 tag 是對的，這就是 hit，反之為 miss
miss 的話，會先將此「塊」記憶體資料從 memory 中讀出來，放進 cache 中，注意這邊是「整塊」。

例如 CPU 要讀 0x0002，如果沒有命中，那會把整塊 0x0000 ~ 0x000F 都載進 cache
當 CPU 要讀的資料 miss，因此要從 memory 載入資料到 cache，如果算出來的那塊 cache line 裡面已經有資料了，且這塊資料的 dirty bit 也是 1 (表示這塊資料載入後有被變更過、髒掉惹)，那這塊 cache line 被新資料蓋掉前，要先寫回 memory 中。（如果 dirty bit 是 0，這塊資料自從載入後都沒有被更新過，那表示跟記憶中是一致的，那就直接蓋掉，不需要再寫回記憶體，節省一些寫操作） -> 這個作法是 write-back，上述的描述也表示，cache 中的資料只有在 cache line 要被替換或清空時，才會去更新回 memory，因此中間可能會有一段時間，cache 跟 memory 的資料是不一致的。

5. hit 的話：用最後的 4 bit 去找出這個位址的資料是在這個 cache line 中的哪一個位置（所以稱為 offset) -> 由 4. 可知，從 memory 載入資料進 cache 時，是整「塊」載入，以我們的範例來說，會一次載入 16 B 的資料，但 CPU 只要讀 0x0002 啊，所以就用 offset 去找出 0x0002 到底在這塊 cache line 中的哪裡。

由以上操作可知：

系統剛啟動時、cache 都是空的，valid flag 都是 0
資料剛從 memory 載進 cache 時，dirty flag 也是 0 (尚未修改過、還沒髒掉)

寫操作

當 CPU 要對某一個記憶體位址進行寫操作時：

跟讀操作一樣，先把要寫的記憶體位址摻拆成 tag + index + offset
用 index 找到是哪一塊 cache line
valid & tag 是對的 => hit，反之 miss
hit 的情況: 把 CPU 要寫的資料更新到這塊 cache line，把 dirty bit 設定成 1
miss 的情況: 從記憶體中，把有這個記憶體位址的那「塊」資料寫進 cache 中，然後更新 cache、設定 dirty (就跟 hit 一樣了)

=> 如果 cache line 是 valid 但 tag 不同，表示這塊記憶體有其他資料，這時候如果 dirty bit 也設定了，那表示 cache 中的這塊資料有更新過（髒了），一樣蓋掉前要把當前 cache 中的資料更新回 memory。

映射與 Eviction

可以理解 memory 通常遠大於 cache，不可能把 memory 全部放進 cache 裡，那要怎麼放？有三種方式：

Direct Mapped Cache

給定一個 memory address，就能確定是哪一個 cache line，應該能聯想到可以用 mod 去算。當有 N 個 cache line，那某個特定的 memory address A 在 cache 的位置的就是 A mod N。

又，cache line 是 memory 到 CPU 之間的最小傳輸單位，當一個 cache line 的大小是 16 Bytes 時，那給定的 address A 對應到的 cache 位置會是 (A/16) mod N。

前文中所列出的讀寫操作就是 Direct Mapped Cache 的情況下。這種映射方式的 Eviction 也很單純，因為一個 address 就是對應到某個特定的 cache line，如果這個特定 cache line 不命中，那就是逐出（eviction）、替換。

優點: 簡單、容易運算 (硬體設計成本低)

缺點: 容易發生衝突，會經常需要替換 cache (cache thrashing 顛頗)

Fully Associative Cache

給定一個 memory address，有可能被放在任何一個 cache line 中。

要知道這個 memory address 的資料有沒有被快取在 cache 中，就只能遍歷整個 cache。

可以理解，這個方式查找的延遲會很高（雖然可能最不顛頗）。

E-way Set Associate Cache

E 個 cache line 作為一組 (set)，cache 按照 set 等分劃分。注意: 這邊 memory address 的拆分方式就會跟上述的內容略有不同。

以 E = 2 來說（2-way Set-Associate），就是每一個 set 會有兩個 cache line 。所以 Direct Mapped 其實就是 E = 1 (一個 set 一個 cache line)，而 Fully Associate Cache 就是 E = N (所有的 cache line 一個 set）

這個機制下，memory address 依舊被拆成 tag + index + offset，只是這個 index 是對應到哪個 set，而不再是單一的 cache line。

透過 index 找到這個 memory address 對應的那個 set 之後，一樣要比對 valid bit 跟 tag，只是這時候要比對兩個 cache line 的 valid bit 跟 tag。有比對到，那就是 hit，一樣再用 offset 去找到這一個 cache line 中真正資料的位置。

如果比對不到或是 invalid（也就是 miss了），因為現在不再是每個 cache line 單兵作戰了，是一整個 set，那就看這個 set 中有沒有空位，有就放進去。如果這個 set 中沒有空位，那就要判斷要從這個 set 中選擇哪一個位置來替換 (Eviction)，例如使用 LRU (Least-Recently-Used，最近最少使用）來替換掉最後一次訪問時間最遠的那一行。

到這邊，應該可以知道，E-way Associate Cache 就是介於 Direct Mapped 跟 Fully Associate 之間，盡可能取兩邊優點，讓查找有效率、但又必較不要顛頗。

思考題

理解了上述的 cache 機制後，那就可以來想想以下兩個問題：

為什麽用 memory address 的中間段來做 index?
以下兩段程式碼，哪一個比較好？為什麼？

// Code A
int arr[10][128];
for(int i = 0; i < 10; i++) {
    for(int j = 0; j < 128; j++) {
        arr[i][j] = 1;
    }
}
// Code B
int arr[10][128];
for(int i = 0; i < 128; i++) {
    for(int j = 0; j < 10; j++) {
        arr[j][i] = 1;
    }
}

References

CMU CSAPP Cache Memories https://www.cs.cmu.edu/~213/lectures/10-cache-memories.pdf
Cache的基本原理 https://zhuanlan.zhihu.com/p/102293437
CPU快取 https://zh.wikipedia.org/zh-tw/CPU%E7%BC%93%E5%AD%98