快取記憶體 (Cache Memories)

Overview Table

6.4 快取記憶體的由來 (p.650-651)

早期系統的記憶體階層只有三層:CPU registers、main memory、disk。隨著 CPU 與主記憶體速度差距擴大,設計者在 register file 與主記憶體之間插入小型 SRAM 快取:

• L1 cache:存取約 4 clock cycles,速度接近暫存器
• L2 cache:介於 L1 與主記憶體之間,約 10 cycles
• L3 cache:介於 L2 與主記憶體之間,約 50 cycles

CPU chip
+---------------------------------+
|  Register file                  |
|  +-------+        +-----+       |
|  | Cache |<------>| ALU |       |
|  | mems  |        +-----+       |
|  +-------+                      |
|      |                          |    System bus      Memory bus
|  +---------------+              |   +------------+   +--------+
|  | Bus interface |<-------------+-->| I/O bridge |<->|  Main  |
|  +---------------+              |   +------------+   | memory |
+---------------------------------+                    +--------+

6.4.1 通用快取組織 (S, E, B, m) (p.651-653)

位址有 $m$ 位元,共 $M=2^m$ 個位址。快取組織成 $S=2^s$ 個 cache set;每個 set 有 $E$ 條 cache line;每條 line 含一個 $B=2^b$ bytes 的 data block、1 個 valid bit(標示此 line 是否含有意義資訊)、$t=m-(b+s)$ 個 tag bits(唯一識別存放在該 line 的區塊)。

• 快取容量 $C=S\times E\times B$,不含 tag bits 與 valid bit 等 overhead
• 快取像一個雜湊函數極簡單的 hash table:只靠檢查位址位元即可定位資料
• set index bits(視為 unsigned 整數)決定字組「必須」放在哪個 set;tag bits 決定 set 內哪條 line(若有);block offset bits 給出字組在 B-byte 區塊內的起始位移

位址分割 (m 位元):
 m-1                                    0
 +-----------+-------------+------------+
 |  t bits   |   s bits    |   b bits   |
 |   Tag     |  Set index  | Blk offset |
 +-----------+-------------+------------+

快取結構:
            +-------+-----+----------------+
  Set 0:    | Valid | Tag | 0 | 1 |...|B-1 |  \
            +-------+-----+----------------+   E lines
            | Valid | Tag | 0 | 1 |...|B-1 |  /  per set
            +-------+-----+----------------+
  Set 1:    |  ...                         |
            +------------------------------+     S = 2^s sets
  Set S-1:  |  ...                         |
            +------------------------------+

參數速查表 (Figure 6.26, p.653)

6.4.2 Direct-Mapped Cache ($E=1$) (p.653-660)

每個 set 恰好一條 line,是最容易實作與理解的類別。判定 hit/miss 並取出字組的流程分三步:

CPU 送出位址 A
      |
      v
(1) Set selection: 取中間 s bits 當 unsigned index 選 set
      |
      v
(2) Line matching: valid bit == 1 且 line tag == 位址 tag ?
      |                       |
     Yes                      No
      |                       v
      v                  Cache miss --> 向下層取 block,存入該 set
(3) Word selection:            (E=1 時替換策略 trivial:直接覆蓋現有 line)
    block offset 指出字組在 block 內的起始 byte --> 回傳給 CPU

• Line matching:命中 iff valid bit 已設 且 tag 相符;兩者任一不成立即 miss
• Word selection:把 block 視為 byte 陣列,offset 是索引;例如 offset ${100}_2$ 表示字組從 block 的 byte 4 開始(假設 4-byte 字組)
• Line replacement:direct-mapped 的替換策略是 trivial 的——新抓進來的 line 直接取代現有 line

實例模擬:$(S,E,B,m)=(4,1,2,4)$ (p.655-657)

4 組、每組 1 line、每 block 2 bytes、4 位元位址(假設字組為 1 byte)。列舉整個位址空間並分割位元後可觀察到:

• tag + index 串接唯一識別記憶體中的每個 block(block 0 = 位址 0,1;block 1 = 位址 2,3 …)
• 8 個 memory block 對 4 個 set:多個 block 映射到同一 set(block 0 與 4 都到 set 0)
• 映射到同一 set 的 block 由 tag 區別(block 0 tag=0,block 4 tag=1)

讀取序列示範(初始所有 valid bit = 0):

Conflict Miss 與 Thrashing (p.658-660)

Conflict miss:快取整體空間足夠,卻因交替引用映射到同一 set 的 block 而反覆互相驅逐。Thrashing 泛指快取反覆載入又驅逐同一批 block 的情形。

典型案例 dotprod:float x[8]、y[8] 連續放置(x 從位址 0、y 從 32),block 16 bytes、2 sets(C = 32 bytes)時,每個 x[i] 與 y[i] 映射到相同 set——第一次讀 x[0] miss 載入 x[0]-x[3],接著讀 y[0] miss 又把它覆蓋掉,如此往復,每次引用都是 conflict miss。

• 程式存取大小為 2 的冪次 的陣列時特別容易發生
• 即使空間局部性良好、快取容量足夠,仍可能全部 miss;thrashing 常拖慢 2~3 倍
• 修法:在陣列尾端加 B bytes 的 padding(如 float x[8] 改 float x[12]),使 x[i] 與 y[i] 落在不同 set,消除 thrashing

6.4.3 Set Associative Cache ($1<E<C/B$) (p.660-662)

Direct-mapped 的 conflict miss 源自「每 set 恰一 line」的限制;set associative cache 放寬此限制,每 set 持有多條 line。每 set 有 E 條 line 者稱 E-way set associative cache。

• Set selection:與 direct-mapped 完全相同(set index bits 選 set)
• Line matching:較複雜——set 中任一條 line 都可能存放映射到該 set 的任何 block,必須搜尋 set 內每條 line,找 valid 且 tag 相符者。可把每個 set 想成小型 associative memory:key = tag 與 valid bit 的串接,value = block 內容(相對地,傳統記憶體以位址為輸入回傳該位址的值)
• Word selection:同前,block offset 選出字組起始 byte

Miss 時的替換 (line replacement):

• set 內有空 line(invalid)→ 優先填入
• 無空 line → 需選一條驅逐,並希望 CPU 短期內不會再引用它;策略包括:
  • 隨機 (random):最簡單
  • LFU (least frequently used):替換過去某時間窗內引用次數最少者
  • LRU (least recently used):替換最久未被存取者
• 精巧策略需額外時間與硬體;越往階層下方,miss penalty 越貴,越值得投資好的替換策略
• 程式設計者很難在程式碼中利用替換策略的知識,故書中不深入細節

6.4.4 Fully Associative Cache ($E=C/B$) (p.662-664)

整個快取只有單一 set,包含全部 line。

Fully associative 位址分割(沒有 set index 欄位):
 m-1                          0
 +---------------+------------+
 |    Tag        | Blk offset |
 +---------------+------------+

• Set selection:trivial——永遠選 set 0;位址只分成 tag + block offset
• Line matching / word selection:與 set associative 相同,差別只在規模(要對所有 line 平行比對 tag)
• 因為電路必須平行搜尋大量 tag,又大又快的 associative cache 難以且昂貴地建造 → 只適合小型快取,例如虛擬記憶體系統中快取 page table entries 的 TLB(見 09-Virtual-Memory/03-Address-Translation-and-TLB)

三種組織比較

6.4.5 寫入的議題 (p.666-667)

讀取單純:hit 直接回傳;miss 則向下層抓 block、存入某條 line(可能驅逐 valid line)、再回傳。寫入則有兩個獨立的決策點:

• 典型配對:write-through + no-write-allocate;write-back + write-allocate
• 越往階層下方,傳輸時間越長,越傾向 write-back;虛擬記憶體(以主記憶體快取磁碟 block)一律 write-back。隨邏輯密度提升,write-back 的複雜度不再是障礙,現代系統各層都漸採 write-back
• 寫入最佳化細節因系統而異、常是專有且文件不全

6.4.6 真實快取階層剖析:Intel Core i7 (p.667-668)

快取不只放程式資料,也放指令:

• i-cache:只放指令;通常唯讀,因此較簡單
• d-cache:只放程式資料
• unified cache:指令與資料混放

現代處理器採分離的 i-cache 與 d-cache,理由:CPU 可同時讀一個指令字與一個資料字;兩者可針對不同存取模式分別最佳化(不同 block size、associativity、容量);且資料存取不會與指令存取互造 conflict miss——代價是可能增加 capacity miss。

Processor package (Core i7, 4 cores)
+------------------------------------------------------+
| Core 0                            Core 3              |
| +------+                          +------+            |
| | Regs |                          | Regs |            |
| +------+                          +------+            |
| +---------+ +---------+    ...    +---------+ +-----+ |
| |L1 dcache| |L1 icache|           |L1 dcache| |L1 ic| |
| +---------+ +---------+           +---------+ +-----+ |
| +--------------------+            +------------------+|
| |  L2 unified cache  |            | L2 unified cache ||
| +--------------------+            +------------------+|
| +--------------------------------------------------+ |
| |      L3 unified cache (shared by all cores)       | |
| +--------------------------------------------------+ |
+------------------------------------------------------+
                          |
                    Main memory

• L1/L2 為每核心私有,L3 由所有核心共享;所有 SRAM 快取都在 CPU 晶片內

6.4.7 快取參數對效能的影響 (p.667-669)

效能量測指標:

• Miss rate = #misses / #references
• Hit rate = $1-\text{miss rate}$
• Hit time:命中時把字組送達 CPU 的時間(含 set selection、line identification、word selection);L1 約數個 cycles
• Miss penalty:因 miss 而需要的額外時間;L1 miss 由 L2 服務約 10 cycles、由 L3 約 50 cycles、由主記憶體約 200 cycles

各參數的質性取捨(精確最佳化需在真實 benchmark 上大量模擬,超出本書範圍):

• E 的選擇本質上是 hit time vs miss penalty 的取捨:傳統上追求時脈的高效能系統,L1 用較低關聯度(miss penalty 只有幾個 cycles),下層用較高關聯度(miss penalty 高);Core i7 的 L1/L2 為 8-way、L3 為 16-way

Exam/Test Patterns

Related Notes

• 06-Memory-Hierarchy/01-Storage-Technologies
• 06-Memory-Hierarchy/02-Locality-and-Memory-Hierarchy
• 06-Memory-Hierarchy/04-Cache-Friendly-Code-and-Memory-Mountain
• 09-Virtual-Memory/03-Address-Translation-and-TLB
• 05-Program-Optimization/04-Limiting-Factors-and-Memory-Performance