1 Cache名詞解釋
- 命中（hit）： CPU要訪問的數據在Cache中有緩存
- 缺失（miss）： CPU要訪問的數據在Cache中沒有緩存
- Cache Size：Cache的大小，代表Cache可以緩存最大數據的大小
- Cache Line：Cache會被平均分成很多相等的塊，每一個塊大小稱之為Cache Line Size；Cache Line是Cache和主存之間數據傳輸的最小單位。當CPU試圖load一個字節數據的時候，如果Cache缺失，那么Cache控制器會從主存中一次性的load一個Cache Line大小的數據到Cache中。例如，Cache Line大小是8字節。CPU即使讀取一個Byte，在Cache 出現miss后，Cache會從主存中load 8字節填充整個Cache Line。
Cache Size 為 64 Bytes的Cache舉兩個例子：
- 將64 Bytes平均分成64塊，那么Cache Line就是1字節，總共64行Cache Line
- 將64 Bytes平均分成8塊，那么Cache Line就是8字節，總共8行Cache Line
現在的硬件設計中，一般Cache Line的大小是4-128 Byts。會有如下兩個問題：
- Cache如何判斷是否命中
- 這個值為什么不是更低，低至1字節，這樣就可以更加靈活的映射，從而沒有刷新整個cache line的開銷
- 這個值為什么不是更高或者更低
- 為什么一次要讀取整個Cache Line
將在后文中進行解釋說明。
2 多級Cache之間的配合工作
當CPU試圖從某地址load數據時，下圖為只有兩級Cache的系統舉例：
- 從L1 Cache中查詢是否命中，如果命中則把數據返回給CPU（藍色實線）
- L1 Cache缺失，則繼續從L2 Cache中查找。當L2 Cache命中時，數據會返回給L1 Cache以及CPU（綠色實線&綠色虛線）
- L2 Cache也缺失，需要從主存中load數據，將數據返回給L2 Cache、L1 Cache及CPU（紅色實線&紅色虛線）
這種多級Cache的工作方式稱之為inclusive Cache。某一地址的數據可能存在多級緩存中。與Inclusive Cache對應的是Exclusive Cache，這種Cache保證某一地址的數據緩存只會存在于多級Cache其中一級。也就是說，任意地址的數據不可能同時在L1和L2 Cache中緩存。
3 直接映射緩存（Direct Mapped Cache）
3.1 舉例1
以一個Cache Size 為 128 Bytes 并且Cache Line是 16 Bytes的Cache為例。首先把這個Cache想象成一個數組，數組總共8個元素，每個元素大小是 16 Bytes，如下圖：
現在考慮一個問題，CPU從0x0654地址讀取一個字節，由于Cache大小相對于主存來說，是非常小的。所以Cache只能緩存主存中極小一部分數據。如何根據地址在有限大小的Cache中查找數據呢？現在硬件采取的做法是對地址進行散列（可以理解成地址取模操作）。
3.2 命中與缺失
經過如下計算：
- 假設地址總線是16位，目標地址為0x0654，轉換為二進制為
0000,0110,0101,0100 - Offset：由于每個Cache Line中有16 Byte，所以地址最低4位，即為每一個Cache Line中的偏移Offset，標記在這個Cache Line中的具體位置是哪個字節，舉例中為
0100，即為圖中地址段的藍色背景部分 - Index：由于一共有8個Cache Line，所以地址除去最低4位的后3位，即為不同Cache Line的索引Index，標記具體在整個Cache 中的那一個Cache Line，舉例中為
101，即為圖中地址段的綠色背景部分
如果兩個不同的地址，其地址的Index部分完全一樣，這兩個地址經過硬件散列之后都會找到同一個Cache Line。所以，根據地址確定到Cache Line之后，只代表所需要訪問的目標地址中存儲的對應數據可能存在這個Cache Line中，但是該Cache Line也有可能存儲其他地址對應的數據。
所以，獨立于Data Array，又引入Tag Array區域，Tag Array和Data Array中的每一個Cache Line都有著一一對應關系。每一個Cache Line都對應唯一一個tag，tag中保存的是整個地址位寬去除index和offset使用的bit剩余部分（如上圖地址粉色背景部分）。tag、index和offset三者組合就可以唯一確定一個地址了。
因此，根據地址中index位找到Cache Line后，取出當前Cache Line對應的tag，然后和目標地址的tag進行比較，如果相等，這說明Cache命中。如果不相等，說明當前Cache Line存儲的是其他地址的數據，這就是Cache缺失。
在上述圖中，我們看到tag的值是0,0000,1100，和地址中的tag部分相等，因此在本次訪問會命中。
我們可以從圖中看到tag旁邊還有一個valid bit，這個bit用來表示Cache Line中數據是否有效（例如：1代表有效；0代表無效）。當系統剛啟動時，Cache中的數據都應該是無效的，因為還沒有緩存任何數據。Cache控制器可以根據valid bit確認當前Cache Line數據是否有效。所以，上述比較tag確認Cache Line是否命中之前還會檢查valid bit是否有效。只有在有效的情況下，比較tag才有意義。如果無效，直接判定Cache缺失。
此時回答，前文提出的第二個問題：這個值為什么不是更低，低至1字節，這樣就可以更加靈活的映射，從而避免了因為部分所需要的數據而刷新整個Cache Line的開銷
由于tag的引入。這樣會導致硬件成本的上升，將兩種情況進行對比：
- 原本Cache Line 設置為16 Byte：每16 Byte對應一個tag，需要8個tag
- 假設Cache Line設置為1 Byte：需要128個Tag同時每一個Tag的長度也會更長，因為Offest縮短了
因此可以發現這樣做占用了很多內存。需要注意：tag也是Cache的一部分，但是談到Cache size的時候并不考慮tag占用的內存部分。
上面的例子中，總結如下：Cache Size是128 Byte并且Cache Line size是16 Byte，共計8個Cache Line。
- offset：4bit
- index：3bit
- tag：9bits（假設地址寬度是16 bit）
3.3 直接映射緩存的優缺點
- 優點1：直接映射緩存在硬件設計上會更加簡單
- 優點2：因為優點1，所以成本上也會較低
根據直接映射緩存的工作方式，可以計算出不同主存地址段和對應的Cache
| 地址段 | Cahce Line Index |
|---|---|
| 0x0000-0x000F，0x0080-0x008F，… | 0 |
| 0x0010-0x001F，0x0090-0x009F，… | 1 |
| 0x0020-0x002F，0x00A0-0x00AF，… | 2 |
| 0x0030-0x003F，0x00B0-0x00BF，… | 3 |
| 0x0040-0x004F，0x00C0-0x00CF，… | 4 |
| 0x0050-0x005F，0x00D0-0x00DF，… | 5 |
| 0x0060-0x006F，0x00E0-0x00EF，… | 6 |
| 0x0070-0x007F，0x00F0-0x00FF，… | 7 |
可以看到，地址0x0000-0x007F地址（0x0000-0x000F~0x0070-0x007F）處對應的數據可以覆蓋整個Cache。0x0080-0x00FF地址的數據也同樣是覆蓋整個Cache。
現在思考一個問題，如果一個程序試圖依次訪問地址0x0000、0x0080、0x0100，Cache中的數據會發生什么呢？首先應該明白0x0000、0x0080、0x0100地址中index部分是一樣的。因此，這3個地址對應的Cache Line是同一個。所以，當訪問0x0000地址時，Cache會缺失，然后數據會從主存中加載到Cache中第0行Cache Line。當我們訪問0x0080地址時，依然索引到Cache中第0行Cache Line，由于此時Cache Line中存儲的是地址0x0000地址對應的數據，所以此時依然會Cache缺失。然后從主存中加載0x0080地址數據到第一行Cache Line中。同理，繼續訪問0x0100地址，依然會Cache缺失。這就相當于每次訪問數據都要從主存中讀取，所以Cache的存在并沒有對性能有什么提升。訪問0x0080地址時，就會把0x00地址緩存的數據替換。這種現象叫做Cache顛簸（Cache thrashing）。針對這個問題，在后面的文章中引入多路組相連緩存優化規避這一問題。
