# Associativity Structures

如同 Hash map 一樣，我們希望某個 cache index 對到的空間可以放兩個或多個 block 的資料，這種技巧叫做 Associativity Structures。

<iframe src="https://drive.google.com/file/d/1BLpOmtVQMWgFU1-_CUItnjOWahuMANVj/preview" height="580"></iframe>

- 1-Way Assoc
- 就是之前的 Direct Mapped，一個 Cache 地址只能放一個 block
- 2-Way Assoc
- 如同其名，一個 Cache 地址可以放兩個 block
- 所以可以自行延伸出 N-Way Assoc，一個 Cache 地址可以放 N 個 block
- Fully Assoc
- 整個 cache 就只有一個 set，這樣就不用算 Cache index 了
- 因此全部的資料都放在同一個 set 裡面
- 另一個別名叫做 Full Mapped

:::warning
要注意一件事情，通常進行不同 Assoc 進行比較的時候，**是要固定 Cache 大小的**。
因此如果從 1-Way 變成 2-Way，要注意 set 數會只剩一半。
:::

## 比較

這裡來比較 1-Way Assoc、2-Way Assoc 跟 Fully Assoc 的差異。

假設現在 Cache **只有 4 個 Block 的容量**，現在要從記憶體中讀取資料，並且用以下的「Block Address」序列來依序讀取資料：

- 0 8 0 6 8

> 別忘記我們是將記憶體中的「Block Address」進行模除運算後才找到對應的 Cache index

- 1-Way Assoc：要模除 4，因為一個 set 只能放 1 個 block
- 模除後的 Index：0 0 0 2 0
- 全部的操作都是 Miss，包含讀取新資料也是 Miss
- 例如第 3 個 0，他是要讀取 Block Address 0 的資料，可是在那之前就被 Block Address 8 給覆蓋掉了
- 2-Way Assoc：要模除 2，因為一個 set 可以放 2 個 block 所以 index 砍半
- 模除後的 Index：0 0 0 0 0
- 只有一個 1 Hit：第三個 0 讀取的時候沒有 miss
- 因為這裡採用了 2-Way，所以就不會被前一個 Block Address 8 的資料給覆蓋掉
- 可是後來因為讀取了 Block Address 6 的資料，**所以會把最先讀進來的 Block Address 8 的資料給覆蓋掉**
- 因此導致最後一次的讀取是 Miss
- Fully Assoc，要模除 1，因為一個 set 可以放 4 個 block，Index 剩 1 個
- 模除後的 Index：0 0 0 0 0 (其實也不用模除就是了...)
- 因為一個 set 可以放 4 個 Block 的資料，除了第一次放入是 miss，後續讀取都是 hit
- 所以總共有兩個 Hit

:::warning
要注意 2-Way 中的**取代原則**，這裡是採用 **LRU / Least Recently Used**，因為 Block Address 0 的有被使用一次，而 Block Address 8 則沒有，因此他會比較優先被替換掉。

LRU 的話會有特別的硬體負責相關的紀錄；還有其他的原則，像是 **FIFO** 或是 **Random**，這部分也是一門學問。
:::

## 電路結構

下面以 4-Way 的電路作介紹：

<iframe src="https://drive.google.com/file/d/1CAiTdoza84F72HXHj_RpUO6s0uDeeV5u/preview" height="580"></iframe>

- 這是個 256 Sets 的 Cache，所以 Cache index 是 8 個 bit
- 每個 Block 是 4 Bytes 寬，所以 Block Offset 是 2 個 bit

可以看到跟上周一樣的電路結構，不過現在一個 Set 裡面有 4 個 Block 的資料。

順序上是先將該 Set 的資料全部讀出來，然後用 Cache tag 進行檢驗的結果作為 MUX 的 Selection bit，來決定要輸出誰。

# Tag Size

情境：

- Cache size 為 4K 個 Blocks 的大小，一個 block 有 4 個 word(16 bytes)，32 bit 的 Address：
- 所以 Bytes offset 是 4 bit。
- 可以知道 tag + index 必定有 32 - 4 = 28 個 bits

接著我們來探討不同 Assoc 對 Tag size 的影響。

- 1-Way Assoc
- Cache size 有 4K 個 Blocks，所以總共有 4K 個 Sets，所以 index 需要 12 個 bits
- 因此 tag 有 16 個 bits
- 所以 tag 總共佔了 16 × 4K = 64K bits
- 2-Way Assoc
- Cache size 有 4K 個 Blocks，所以總共有 2K 個 Sets，所以 index 需要 11 個 bits
- 因此 tag 有 17 個 bits
- 所以 tag 總共佔了 17 × 2 × 2K = 68K bits
- Fully Assoc
- Cache size 有 4K 個 Blocks，總共只有 1 個 Set，所以 index 要 0 個 bit
- 因此 tag 有 28 個 bits
- 所以 tag 總共佔了 28 × 4K × 1 = 112K bits

# Cache Control

講了這麼多跟 Cache 有關的內容，現在要講如何處理 Cache 的控制電路。

下面是三個層級之間的概念架構圖：

<iframe src="https://drive.google.com/file/d/1uBhwZIKy2EVRB8UA869FUrfChy_A7BIn/preview" height="580"></iframe>

>老師說 low end CPU 通常會共用 write 跟 read 的 bus

這裡的情境是：

- Direct-mapped, write-back, write allocate
- write-back 就是只寫到 Cache，並且要設置 Dirty bit
- write allocate 就是發生 write miss 時會把資料拿進 Cache 裡面
- 可以複習上一周的內容
- Block size：4 words (16 bytes)
- Cache size：16 KB (1024 blocks)
- 32-bit address
- Valid bit and dirty bit per block
- Blocking cache
- CPU 會等到存取完成才做下一步

設計 Cache Control 的方法就是先畫出 FSM，也就是狀態圖：

<iframe src="https://drive.google.com/file/d/11Iw6LiXUc7EEO05QHMKKt9EIG-bbw4DS/preview" height="580"></iframe>

- Idle → Compare Tag
- 當 CPU 發送一個 Valid request 時
- Idle ← Compare Tag
- 有兩種 request 情形
- 如果是 read ，並且資料是 Valid 並且是 Hit
- 設置 Valid Bit 跟 Cache Tag
- 如果是 write，沒有發生 write miss
- 設置 Dirty bit
- 滿足條件的話就標示 Cache ready 以及 Cache Hit
- Compare Tag → Write-Back
- 如果 Request 是 read，但是發生了 read miss，並且資料是 dirty 的
- 需要先將資料寫回記憶體
- 並且要等到資料寫好，所以會有個 Memory not ready 的指向自己箭頭
- Memory Ready 的話就可以前往 Allocate 狀態了
- Compare Tag → Allocate
- 如果 Request 是 read，但是發生了 read miss，不過資料是 clean 的
- 那麼就可以直接去拿資料了
- 並且也會有個 Memory not ready 的指向自己箭頭
- 別忘記由於這裡是 Write-Allocate，所以 write miss 跟 read miss 一樣，遇到 dirty 要先寫回

上面狀態圖中的 Cache Ready 跟 Memory Ready 就是概念架構圖中的 Ready。

有了 FSM 後就可以轉成電路圖了，例如下圖：

<iframe src="https://drive.google.com/file/d/1MQITf5pKNbrhRTJ5V806Nnyq5BemvS3o/preview" height="580"></iframe>

通常這個轉換的工作都有軟體可以幫忙；而最後電路可以透過 PLA 或是 ROMs 的方式做出來。

總之概念就是只要畫出 FSM 後就可以弄出電路來。

# L2 Cache

現在的電腦就我們所知，都會有 2 到 3 層的 Cache，尤其近年來 L3 快取挺普遍的。

會需要 L2 快取的原因是根據下面的公式：

$$
\begin{align}
\text{Total CPI} &= \frac{\text{CPU execution clock cycles + Memory stall clock cycles}}{\text{Total Instructions}}\\
&= \text{CPI} + \frac{\text{Memory stall clock cycles}}{\text{Total Instructions}}\\
&= \text{CPI} + \frac{\text{# Memory accesses × Miss rate × Miss penalty}}{\text{Total Instructions}}\\
&= \text{CPI} + \text{Miss rate × Miss penalty}\\
\end{align}
$$

:::info
這裡是混合式的 Cache，所以每個 Instructions 都是一筆 Memory Access。
:::

可知如果只有 L1 快取，一旦 Miss 就會動到 Memory 的 Penalty，那可是很貴的。
聰明的架構師就想到，既然一層不夠，那就兩層。

## 情境模擬

- Base CPI = 1.0
- L1 Cache miss rate = 2%
- Clock Rate = 5GHz = 0.2 ns per cycle
- Memory Access time = 100 ns，包含 miss handling
- L1 Miss Penalty **to main memory** = 100 / 0.2 = 500 cycle

如果今天只有 L1 快取，那麼 Total CPI 就會是 1 + 2% × 500 = 11.0。

:::warning
CPU cycle 又稱 **hit time**
:::

但是當我們引進 L2 快取：

- 5 ns access time
- L1 Miss Penalty **to L2 Cache**= 5 / 0.2 = 25 cycle
- ==global miss rate== = 0.5%

那麼 Total CPI 就會是 1 + 2% × 25 + ==0.5%== × 500 = 4.0。

:::warning
上面的公式其實可以改寫成：
1 + 2% × 25 + 0.5% × 500 = 1 + 2%(25 + 25% × 500)
- 25% 叫做 **L1 Local miss rate in L2**
- 乘開來後的 0.5% 叫做 **CPU global miss rate in L2**
- 所以 **CPU global miss rate in L1** 就是一開始給的 2%
:::

## 設計目的

如果要避免 Miss，那為何不將 L1 快取弄得很大？原因是因為 L1 快取負責跟 CPU 接洽，所以他的 **Hit Time** 也是很重要的。

如果為了降低 Miss 而將 L1 弄得很大，結果反而讓 ==Hit time== 變很長，那麼也不是我們想要的，所以才有了 L2 快取的產生。

而 L2 快取的設計目的跟 L1 相比之下， ==Hit time== 就沒有那麼重要，會著重處理 Miss，所以可以：

- 有更大的 Cache 大小
- 更大的 associativity
- 更大的 Block Size

這裡跟上周提到的 [Combined 跟 Split Cache](https://hackmd.io/xnZnH9ZXT1yJfCaXqwflHw?view#Split-cache-vs-Combined-cache) 一樣：

- L1 追求的快還要更快：==低 Hit Time==。
- L2 則是追求低 Miss Rate：==高 Hit Time==。

# Cache Friendly

老師說 Programmer 會分為以下等級：

- 會寫程式：基礎
- 進行時間優化的：進階
- 會寫 Cache Friendly 的：專家

所謂的 Cache Friendly，就是寫程式的時候要**想到 Locality，以及善用 Locality**。

例如下面的 Radix Sort 跟 Quick Sort，雖然 Radix Sort 在數量大的時候有著較低的 Instruction 量(左圖)，但是實際跑出來的結果卻有較多的 Clock Cycle(右圖)。

<iframe src="https://drive.google.com/file/d/1tiELh0axcLuvrNi8Os7ilx4cODeLAtR-/preview" height="380"></iframe>

而原因就是在於 Radix Sort 的 Cache Misses 比 Quick Sort 大：

<iframe src="https://drive.google.com/file/d/1gy5x52uPq_NSJZIH1rssKkV-5t55zz0X/preview" height="480"></iframe>

也就是說在該實驗中的 Radix Sort 比較不具有 Cache Friendly 的特性。

# Software Optimization via Blocking / DGEMM

在計算矩陣乘法時可以使用所謂的 Blocking 技巧，善用 Locality 做出 Cache Friendly 的 Code。

下面是在計算兩個方陣 A 跟 B 的矩陣乘法

// 假設 C 矩陣都先初始化為 0
for (int i = 0; i < n; ++i){
    for (int j = 0; j < n; ++j){
        double cij = C[i+j*n]; /* cij = C[i][j] */
        for( int k = 0; k < n; k++ )
            cij += A[i+k*n] * B[k+j*n]; /* cij += A[i][k]*B[k][j] */
        C[i+j*n] = cij; /* C[i][j] = cij */
    }
}

在這樣的算法中，Cache 存取的次數是 $2N^3+N^2$，也就是內層的 `cij += A[i+k*n] * B[k+j*n]` 部分跟 `cij = C[i+j*n]` 的部分。

在最糟的情形，每次的存取都是 Miss，所以 Miss 次數就是 $2N^3+N^2$。

- 首先 `cij = C[i+j*n]` 的部分確定是拿取寫入只會發生一次，所以 Miss 次數確定有 $N^2$ 次
- 至於 `cij += A[i+k*n] * B[k+j*n]` 的部分
- 假設 `A[i+k*n]` 大小很大，雖然第一次讀取時拿進 Cache 裡面，但是它佔滿了 Cache
- 並且 Cache 又剛好只放的下他
- 因此換到下一個 `A[i+k*n]` 就會被替換掉。

但其實最糟的情形不一定會發生，因為通常記憶體中一個 Block 可能可以放入多個 `A[i+k*n]`，而且不同的 `A[i+k*n]` 也不一定會在同個 Block，藉由 Block Address 算出的 Cache index 可能也會不同。

總之為了避免發生被替換掉，聰明的設計師們想到說，那就確保計算某個區域內的資料量大小剛好是 Cache 的大小，這樣就不會發生替換這件事了。

void do_block(int n, int si, int sj, int sk,double *A, double *B, double *C){
for (int i = si; i < si + BLOCKSIZE; i ++) {
    for (int j = sj; j < sj + BLOCKSIZE; j++) {
        double cij = C[i+j*n]; /* cij = C[i][j] */
        for (int k = sk; k < sk + BLOCKSIZE; k++) {
            cij += A[i+k*n] * B[k+j*n]; /* cij += A[i][k]*B[k][j] */
        }
        //C[i+j*n] = cij; /* C[i][j] = cij */
        C[i+j*n] += cij; // 應該是 += 不是 =
    }
}
}
void dgemm(size_t n, double *A, double *B, double *C){
for (int sj = 0; sj < n; sj += BLOCKSIZE) {
    for (int si = 0; si < n; si += BLOCKSIZE) {
        for (int sk = 0; sk < n; sk += BLOCKSIZE) {
            do_block(n, si, sj, sk, A, B, C);
        }
    }
}
}

這份程式碼可以看到的特點是，我們一次只取 A 跟 B 當中的 `BLOCKSIZE × BLOCKSIZE` 的區域進行計算，也就是說可以確保要經過每一個 `BLOCKSIZE` 才會發生 Miss。

因此 Miss 次數就可以從 $2N^3+N^2$ 降到 $\frac{2N^3}{BLOCKSIZE}+N^2$ 次。

> 對 A 跟 B 兩個方陣來說，原本是 $N^3$ 次存取都會發生 Miss，現在則是要經過一個 Block 大小的次數後才會發生 Miss，因此次數從 $N^3$ 變成 $\frac{N^3}{BLOCKSIZE}$，而因為有 A 跟 B 兩個方陣，所以次數要乘以 2

---

## 回顧

- Associativity
- L2 Cache & formula