一、存儲器與局部性原理

1. 局部性原理

基礎概念：

• 時間局部性：一個存儲單元被訪問后，短時間內可能再次被訪問（例如循環變量）。
• 空間局部性：一個存儲單元被訪問后，其附近單元可能在短時間內被訪問（例如數組連續訪問）。

通俗理解：

• 時間局部性：程序反復訪問同一數據，如循環中的變量 sum。
• 空間局部性：程序訪問連續存儲的數據，如數組按存儲順序訪問。

例題：程序訪問局部性分析

• 背景：數組按行優先存儲，比較兩個求和程序段。
  • 程序段A（行優先訪問）：
    • 訪問順序與存儲順序一致，空間局部性優秀，Cache命中率高。
  • 程序段B（列優先訪問）：
    • 訪問順序與存儲順序不一致，空間局部性差，Cache命中率低。
  • 變量sum分析：
    • 時間局部性：優秀（每次循環都訪問 sum）。
    • 空間局部性：無意義（單個變量不涉及相鄰單元）。

---

二、Cache工作原理

類比說明：

• 主存：像超市，存儲所有數據，訪問慢。
• Cache：像儲物柜，存放高頻數據，訪問快。
• 優勢：利用局部性原理預存數據，避免頻繁訪問主存，提升效率。
• 性能關鍵：Cache命中率，訪問速度：Cache > 主存 > 外存。

1. Cache與主存結構關系

• 結構對應：
  • Cache分為行，每行大小等于主存的一個塊。
  • 主存塊頻繁訪問時被復制到Cache行。
• 容量差異：
  • Cache容量遠小于主存，僅存儲高頻數據副本，出于成本和需求考慮。

2. Cache地址結構

• 地址組成：
  • Cache地址：行號（高位） + 塊內地址（低位）。
  • 例：16行×16單元的Cache，地址8位（高4位行號，低4位塊內地址）。
  • 二進制地址 0010 0001：高4位 0010（行號2），低4位 0001（塊內偏移1）。
• 設計思想：
  • n位地址表示2?種含義。
  • Cache行數2? → 行號占c位；每行2?單元 → 塊內地址占b位。

3. 主存地址特點

• 地址結構：
  • 主存地址：塊號（高位，t位，2?塊） + 塊內地址（低位，b位，與Cache一致）。
  • 主存塊數2? >> Cache行數2?，t > c。
• 地址長度差異：
  • 主存地址比Cache地址長，高位（塊號）位數多，塊內地址位數相同。
• 映射問題：
  • 主存地址不含Cache行號，需通過映射方式確定Cache位置。

4. 有效位

• 功能：
  • 每個Cache行有有效位，標識該行是否存儲有效主存塊副本。
  • 初始化：系統啟動時有效位為0（無效）。
  • 數據裝入：主存塊復制到Cache后有效位設為1。
  • 淘汰：有效位置0，實現邏輯刪除。
• 特點：
  • Cache行內多個存儲單元共享1個有效位。
  • 主存塊無有效位，僅為Cache設計。

5. CPU訪問Cache流程

• 目的：通過主存地址訪問Cache獲取數據。
• 命中流程：
  • 主存地址的塊在Cache中：
    1. 讀取Cache行數據。
    2. 傳送至CPU。
    3. 結束訪存。
• 缺失流程：
  • 主存地址的塊不在Cache中：
    1. 從主存讀取整個塊。
    2. 尋找Cache空閑行（若無空閑，觸發淘汰）。
    3. 復制主存塊到Cache。
    4. 傳送目標單元數據至CPU。
  • 局部性原理：整塊調入利用空間局部性。
• 性能指標：
  • 命中率：命中次數/總訪問次數。
  • 訪問時間：命中時（T_c：Cache訪問+判斷），未命中時（T_c + T_m：Cache判斷+主存讀取）。

6. 平均訪問時間（AMAT）

• 公式：
  • AMAT = p * T_c + (1-p) * (T_m + T_c) = T_c + (1-p) * T_m
  • p：命中率，T_c：Cache訪問時間，T_m：缺失代價（主存讀取+傳輸）。
• 定義：AMAT = 命中時間 + 缺失率 × 缺失代價。

例題：命中率計算

• 條件：總訪存1000次，缺失50次。
• 計算：
  • 命中次數 = 1000 - 50 = 950。
  • 命中率 = 950/1000 = 95%。
• 答案：95%。

---

三、Cache映射方式

1. 直接映射

• 原理：主存塊固定映射到特定Cache行。
• 地址劃分：
  • 主存地址：tag（t-c位） + Cache行號（c位） + 塊內地址（b位）。
  • Cache地址：行號（c位） + **塊內地址（b主存地址：tag（t-c位） + Cache行號（c位） + 塊內地址（b位）。
  • Cache地址：行號（c位） + 塊內地址（b位）。
• 映射方法：
  • 主存塊號取模Cache行數，得Cache行號。
  • tag位：主存塊號與Cache行號的差（t-c位）。
• 命中判斷：
  • 比較主存地址tag與Cache行tag。
  • 檢查有效位是否為1。
• 缺失處理：
  • 讀取主存塊到Cache。
  • 更新tag位和有效位。
  • 數據送回CPU。

例題：地址劃分計算

• 條件：主存容量是Cache的4096倍，Cache有64塊，直接映射。
• 解題：
  • Cache行數：2? = 64 → 行號6位。
  • 主存塊數：64 × 4096 = 21? → 塊號18位。
  • tag位：18 - 6 = 12位。
  • 映射表大小：(tag位12 + 有效位1) × 64 = 832位。
• 答案：832位。
• 易錯點：tag位存在于主存地址和Cache行，需計入有效位。

2. 全相聯映射

• 特點：主存塊可存入任意Cache行。
• 地址結構：
  • 主存地址：tag（t位，主存塊號） + 塊內地址（b位）。
  • 無Cache行號，需全行比較。
• tag作用：標識主存塊位置。

3. 組相聯映射

• 原理：
  • Cache分為組，組間直接映射，組內全相聯。
  • 主存塊映射到固定組，組內任意行。
• 地址解析：
  • 主存地址：tag + 組號（g位） + 塊內地址（b位）。
  • 組數2?，組內行數（路數）決定關聯度。
• 例題：主存地址tag計算
  • 條件：Cache 128KB，每行16B，8路組相聯，主存地址1234567H，字節編址。
  • 解題：
    • 總行數：128KB / 16B = 21? / 2? = 213。
    • 組數：213 / 8 = 21? → 組號10位。
    • 塊內地址：16B = 2?字節 → 4位。
    • 主存地址：7位16進制 = 28位二進制。
    • tag位：28 - 10 - 4 = 14位。
  • 答案：tag位14位。
  • 易錯點：字節編址影響塊內地址，路數影響組號位數。

---

四、關聯度與比較器

1. 關聯度

• 定義：主存塊可映射的Cache位置數。
  • 直接映射：關聯度1（固定1行）。
  • 全相聯：關聯度=Cache行數（任意行）。
  • 組相聯：關聯度=組路數（組內任意行）。

2. 命中率與時間

• 命中率：直接映射最低，全相聯最高。
• 命中時間：直接映射最短（1比較），全相聯最長（全行比較）。

3. 比較器

• 功能：比較tag位，位數等于tag位數。
• 數量：
  • 直接映射：1個（精確定位）。
  • 全相聯：Cache行數個（全行比較）。
  • 組相聯：路數個（組內比較）。

---

五、Cache替換算法

1. LRU（最近最少用）

• 原理：替換近期最少使用的塊。
• 實現：
  • 每行有LRU計數器，計數值高表示最少使用。
  • 命中：訪問行計數器清0，其他低于其值的加1。
  • 未命中有空間：新行計數器置0，其他加1。
  • 未命中無空間：淘汰最大計數行，新行置0，其他加1。
• 計數器位數：?log?(組路數)?。

2. 其他算法

• FIFO：淘汰最早裝入的塊。
• LFU：淘汰引用次數最少的塊。
• 隨機替換：隨機選擇。

---

六、Cache一致性

1. 寫命中

• 全寫法（直寫）：
  • 同時更新Cache和主存。
  • 優勢：一致性強。
  • 劣勢：每次寫訪問主存，速度慢。
• 回寫法：
  • 只更新Cache，替換時寫回主存。
  • 控制位：臟位（1位），標記是否修改。
  • 優勢：減少主存訪問。
  • 劣勢：需額外存儲臟位。

2. 寫不命中

• 寫分配法：
  • 更新主存并裝入Cache。
  • 常與回寫法配合，提高后續命中率。
• 非寫分配法：
  • 僅更新主存，不裝入Cache。
  • 常與全寫法配合，簡單但后續可能不命中。

3. 方法搭配

• 回寫法+寫分配法：效率高，符合Cache設計。
• 回寫法+非寫分配：效率低，數據不裝入Cache。
• 全寫法：搭配寫分配或非寫分配，效率相當，因始終寫主存。

---

七、總結

• 局部性原理是Cache設計基礎，時間局部性和空間局部性決定數據預存策略。
• Cache工作依賴地址映射（直接、組相聯、全相聯）、有效位和替換算法（如LRU）。
• 命中率與時間：高關聯度提升命中率，但增加比較時間。
• 一致性：全寫法保證強一致性，回寫法+寫分配法效率更高。
• 例題解析：
  • 命中率：95%（950/1000）。
  • 直接映射地址劃分：832位（12位tag+1位有效位×64行）。
  • 組相聯tag計算：14位（128KB，16B/行，8路）。