系列文章 : 資訊工程自學筆記

這些內容在課本的 ch 5.3, ch 5.4。
學習 direct mapped, x-way set associative, full associative 的差異。

現在假設

• 一個系統的 address space 是 5 bits，也就是說 address 會是 0b00000 ~ 0b11111。
• 假設這個快取有 8 個 block ( 也就是 2 的 3 次方 )

當我們取用低位的三個 bits 作為 index 的時候，會發現每一個 address 最終都只會進到同一個 block。

例如說

• 00000 永遠都會在 index 為 000 的 block
• 00001 永遠都會在 index 為 001 的 block

這種一個 address 只會落在一個 block 的方式，就叫做 direct mapped。

Q: 為什麼 index 要取低位，而不是高位呢 ?
假如我們取位址的高三位，就會變成

• `000`00
• `000`01
• `000`10
• `000`11

這四個位址都會指向同一個 cache block，變成相鄰的位置會搶奪同樣的資源，另外根據 Spatial Locality 的假設，當我們取用某個位址的時候，很快的就會取用相鄰的位址。

於是取高位的位址作為 cache index，會讓我們短時間內不斷的 cache miss。取低位址的話，就可以解決這個問題，在 spatial locality 的前提下，會有更好的 cache hit rate。

假如我們取用 00`001`，藉著又需要取用 10`001` 的時候，因為這兩個位址使用到同樣的 block，所以必須要把 00`001` 挪出 cache 才行。

可這時候，我們要怎麼知道 `001` 這一個 cache block，存的到底是 address : 00`001` 還是 address : 10`001` 呢 ? 這時候我們就需要 `label`。

• address : [00][001]
  • label : 00
  • index : 001
• address : [10][001]
  • label : 10
  • index : 001

於是我們可以藉由 `label`，得知當前的 cache block 到底是存 [00][001] 還是 [10][001] 了!

-----
-----

那我們該怎麼知道當前的 cache block 有沒有資料呢 ? 這時候可以看 cache block 裡面的 `valid bit`

• valid bit == 1 : 表示當前的 block 有資料
• valid bit == 0 : 表示當前的 block 沒有資料

-----
-----

這邊統整一下簡化版的 cache 會有哪些東西

• index : 索引，讓我們可以找到相對應的 cache block
• V : valid bit，表示當年的 cache block 裡面有沒有資料
• Tag : 標籤，讓我們可以分別這個 cache block 對應到的是哪個 address 的資料
• Data : 資料。

-----
-----

剛剛提到的 direct mapped，代表每個 address 都會去固定的一個 cache block。那能不能讓某個特定 address ( e.g. `00101` ) 可以被分配到多個可能的 cache block 呢 ?

假如某個特定 address ( e.g. `00101` ) 被分配到...

• 2 個可能的 cache block，就叫做 two-way set associative
• 4 個可能的 cache block，就叫做 four-way set associative
• … 以此類推

假如某個特定 address 可以被丟到任意一個 cache block，則被稱為 `full associative`

-----
-----

假設情況與剛剛相同

• 一個系統的 address space 是 5 bits，也就是說 address 會是 0b00000 ~ 0b11111。
• 假設這個快取有 8 個 block ( 也就是 2 的 3 次方 )

但是我們再額外加上一個條件

• 現在的 cache 是 two-way set associative

如下圖，我們可以發現， index 從原本的 8 變成 4 了。

於是會有下列情況

• 0b[000][00]
  • 會被分配到 set 0b`00`
  • set 0b`00` 有兩個 cache block，這兩個 cache block 都有可能會被 0b[000][00] 使用
  • tag 會是 [000]
• 0b[000][10]
  • 會被分配到 set 0b`10` ( set 2 )
  • set 0b`10` 有兩個 cache block，這兩個 cache block 都有可能會被 0b[000][10] 使用
  • tag 會是 [000]
• 0b[111][10]
  • 會被分配到 set 0b`10` ( set 2 )
  • set 0b`10` 有兩個 cache block，這兩個 cache block 都有可能會被 0b[111][10] 使用
  • tag 會是 [111]

-----
-----

假設情況與剛剛也差不多

• 一個系統的 address space 是 5 bits，也就是說 address 會是 0b00000 ~ 0b11111。
• 假設這個快取有 8 個 block ( 也就是 2 的 3 次方 )

我們再額外加上一個條件

• 現在的 cache 是 `four-way set associative`

於是會有下列情況

• 0b[0000][0]
  • 會被分配到 set 0b`0`
  • set 0b`0` 有 4 個 cache block，這 4 個 cache block 都有可能會被 0b[0000][0] 使用
  • tag 會是 [0000]
• 0b[0001][0]
  • 會被分配到 set 0b`0`
  • set 0b`0` 有 4 個 cache block，這 4 個 cache block 都有可能會被 0b[0001][0] 使用
  • tag 會是 [0001]
• 0b[1111][0]
  • 會被分配到 set 0b`0`
  • set 0b`0` 有 4 個 cache block，這 4 個 cache block 都有可能會被 0b[1111][0] 使用
  • tag 會是 [1111]

-----
-----

假設情況與剛剛也差不多

• 一個系統的 address space 是 5 bits，也就是說 address 會是 0b00000 ~ 0b11111。
• 假設這個快取有 8 個 block ( 也就是 2 的 3 次方 )

我們再額外加上一個條件

• 現在的 cache 是 `fully set associative`

於是會有下列情況

• 0b[00000]
  • 這 8 個 cache block 都有可能會被 0b[00000] 使用
  • tag 會是 [00000]
• 0b[00010]
  • 這 8 個 cache block 都有可能會被 0b[00010] 使用
  • tag 會是 [00010]
• 0b[11110]
  • 這 8 個 cache block 都有可能會被 0b[11110] 使用
  • tag 會是 [11110]