Chapter 5 — 記憶體階層架構期末考筆記

🎯

§5.1 Locality 原則與記憶體階層

Principle of Locality · Memory Hierarchy

Principle of Locality（局部性原理）

⏱ Temporal Locality（時間局部性）

最近被存取的資料很快還會再被存取
例：迴圈中的指令、感應變數

📍 Spatial Locality（空間局部性）

最近存取位址附近的資料也很快會被存取
例：循序指令、陣列元素

Memory Hierarchy（記憶體階層）

所有資料都存在磁碟（最大最慢最便宜）
把最近存取及附近的資料複製到更小的 DRAM → Main Memory
再把更最近的資料複製到 SRAM → Cache Memory（附在 CPU）
CPU Registers → L1 Cache → L2/L3 Cache → DRAM → Disk

基本術語

術語	說明
Block / Line	資料複製的基本單位，可能是多個 words
Hit	所需資料在上層存在 → Hit ratio = hits / accesses
Miss	所需資料不在上層 → 從下層複製一整個 Block
Miss Penalty	從下層取資料所花的時間
Miss Ratio	1 – Hit ratio

💾

§5.2 記憶體技術

SRAM · DRAM · Flash · Disk

各類記憶體比較

類型	存取時間	$/GB	特性
SRAM	0.5 – 2.5 ns	$2000–$5000	快、貴、用於 Cache
DRAM	50 – 70 ns	$20–$75	電容存儲，需定期 refresh，用於 Main Memory
Flash	~100× 比磁碟快	介於 DRAM 與 Disk	非揮發性，寫入次數有限制
Disk	5 – 20 ms	$0.20–$2	慢、便宜、大容量

⚠️ Ideal Memory：我們想要 SRAM 的速度 + Disk 的容量與低成本 → 這就是為什麼需要 Memory Hierarchy！

DRAM 技術細節

資料存成電容的電荷，用單一電晶體存取
必須定期 refresh（讀取後寫回，以一整 row 為單位）
DDR DRAM：在 clock 的上升與下降緣都傳輸資料（Double Data Rate）
QDR DRAM：分開的 DDR 輸入與輸出

Flash Storage 重點

NOR flash：可隨機讀寫，用於嵌入式系統的指令記憶體
NAND flash：密度更高，以區塊為單位存取，更便宜，用於 USB、SD 卡等
Flash bits 在寫入數千次後會壞掉 → 需要 Wear Leveling（把資料分散到使用較少的區塊）

磁碟存取時間計算（重要！）

平均讀取時間 = Seek Time + Rotational Latency + Transfer Time + Controller Overhead
旋轉延遲 = ½ × (1 rotation time)；例如 15000 rpm → 1 rot = 4ms → 平均 2ms

範例：512B sector, 15,000rpm, 4ms seek, 100MB/s transfer, 0.2ms overhead
= 4ms (seek) + 2ms (rotational) + 0.005ms (transfer) + 0.2ms (controller)
= 6.2ms

⚡

§5.3 Cache 基礎

Direct Mapped · Tags · Write Policy

Direct Mapped Cache

每個 memory block 只有一個固定的 cache 位置
對應規則：(Block address) mod (# Blocks in cache)
# Blocks 必須是 2 的次方，所以用低位元的 address bits 當 index

Address 分解（超重要！）

欄位	用途	位元數來源
Tag	辨識是哪個 block（高位元）	32 – Index bits – Offset bits
Index	決定放在 cache 哪個 set	log₂(# sets)
Offset	在 block 內的位元組偏移	log₂(block size in bytes)

範例：64 blocks, 16 bytes/block, address 1200
Block address = 1200 / 16 = 75
Cache index = 75 mod 64 = 11
Offset = 4 bits (log₂16), Index = 6 bits (log₂64), Tag = 22 bits

Valid Bit 與 Tag

Valid bit：1 = 有效資料，0 = 空的（初始全為 0）
Tag：只需存 address 的高位元，判斷是否為目標 block
Hit 條件：valid bit = 1 且 tag 相符

Block Size 考量

較大的 block → 利用 spatial locality → 降低 miss rate
但 fixed-size cache 下，更大的 block → 更少的 blocks → 競爭增加 → miss rate 反升
更大的 miss penalty
解法：Early restart & Critical-word-first

Cache Miss 處理

Hit：CPU 正常繼續執行
Miss：暫停 pipeline → 從下層取整個 block → 再繼續
Instruction cache miss：重新取指令
Data cache miss：完成資料存取

Write 策略（很常考！）

✍️ Write-Through

寫入時同時更新 cache 和 memory
Cache 和 memory 永遠一致
缺點：每次寫入都要存取 memory，很慢
解法：Write Buffer（暫存待寫資料，讓 CPU 繼續）

🔄 Write-Back

只更新 cache，暫時不更新 memory
用 Dirty bit 標記哪些 block 被修改過
Dirty block 被替換時才寫回 memory
可搭配 Write Buffer 讓替換更有效率

Write Miss 時的 Write Allocation

Allocate on miss：先把 block 從 memory 取到 cache，再寫入
Write around：不取 block，直接寫到 memory（程式通常會整塊初始化再讀）
Write-back 通常搭配 Allocate on miss

實例：Intrinsity FastMATH

嵌入式 MIPS，12 stage pipeline，Split cache（I-cache + D-cache 分開）
各 16KB，256 blocks × 16 words/block
SPEC2000 miss rates：I-cache 0.4%，D-cache 11.4%，加權平均 3.2%

📊

§5.4 Cache 效能量測與改善

AMAT · Associativity · Multilevel Cache

Cache 效能公式（超重要！）

CPU time = (Program exec cycles + Memory stall cycles) × Clock cycle time

Memory stall cycles = (Mem accesses / Program) × Miss rate × Miss penalty
= (Instructions / Program) × (Misses / Instruction) × Miss penalty

範例：I-cache miss rate=2%, D-cache miss rate=4%, Miss penalty=100 cycles, Base CPI=2, Load/Store=36%
I-cache miss cycles = 0.02 × 100 = 2 per instruction
D-cache miss cycles = 0.36 × 0.04 × 100 = 1.44 per instruction
Actual CPI = 2 + 2 + 1.44 = 5.44（理想 CPU 快 2.72×）

AMAT（Average Memory Access Time）

AMAT = Hit time + Miss rate × Miss penalty

範例：1ns clock, hit=1 cycle, miss penalty=20 cycles, miss rate=5%
AMAT = 1 + 0.05 × 20 = 2ns（= 2 cycles per instruction）

⚠️ 注意：CPU 效能提升時（更快的 clock），miss penalty 的影響會更大！設計時不能忽視 cache 行為。

Associativity（關聯度）

類型	放置方式	比較器數量	特性
Direct Mapped	只有 1 個選擇	1	最簡單最快，衝突 miss 多
n-way Set Associative	同一 set 內有 n 個選擇	n	平衡效能與複雜度
Fully Associative	可放在任何位置	# entries	miss rate 最低，硬體最貴

Set index：(Block address) mod (# Sets in cache)
64KB D-cache, 16-word blocks 的模擬：1-way 10.3% → 2-way 8.6% → 4-way 8.3% → 8-way 8.1%（邊際效益遞減）

Replacement Policy（替換政策）

LRU（Least Recently Used）：換掉最久沒用的；2-way 容易，4-way 還可以，超過就太難了
Random：在高關聯度時效果接近 LRU，實作較簡單
Direct mapped：沒有選擇，直接換

Multilevel Cache（多層 Cache）

L1 Cache（Primary）：最小最快，接在 CPU 旁邊；設計重點：最小化 hit time
L2 Cache：服務 L1 miss；比 L1 大慢，但比 DRAM 快；設計重點：最低 miss rate（避免存取 main memory）
有些高端系統還有 L3 Cache

範例：Base CPI=1, clock=4GHz, miss rate=2%, DRAM=100ns
只有 L1：Miss penalty = 400 cycles → CPI = 1 + 0.02×400 = 9

加上 L2（5ns access, global miss rate=0.5%）：
L1 miss with L2 hit penalty = 20 cycles
L1 miss with L2 miss penalty = 400 cycles
CPI = 1 + 0.02×20 + 0.005×400 = 3.4（快了 9/3.4 = 2.6×）

Software 優化：Cache Blocking（DGEMM）

矩陣乘法（DGEMM）直接迭代：column-major array 會有大步距，spatial locality 差
Blocking（分塊）：把矩陣切成 BLOCKSIZE × BLOCKSIZE 的小塊，讓每塊資料在被替換前盡量被重複使用
目標：在 cache 容量內最大化資料重用次數

🛡️

§5.5 可靠記憶體階層（ECC）

Dependability · Hamming Code · SEC/DEC

可靠性指標

指標	說明
MTTF	Mean Time To Failure（平均無故障時間）
MTTR	Mean Time To Repair（平均修復時間）
MTBF	MTTF + MTTR
Availability	MTTF / (MTTF + MTTR)

Hamming SEC Code（Single Error Correction）

Hamming distance：兩個 bit pattern 之間不同 bits 的數量
Min distance = 2：可偵測 single bit error（如 parity code）
Min distance = 3：可更正 single bit error，偵測 2-bit error
Parity bits 放在 2 的次方位置（位置 1, 2, 4, 8...）
解碼時：parity bits 的值組合 = 指出哪個 bit 出錯（0000 = 無錯誤）

SEC/DEC（加上 Double Error Detection）

在整個 word 加一個額外的 parity bit（pn）→ Hamming distance = 4
H even + pn even：無錯誤
H odd + pn odd：可更正的 single bit error
H even + pn odd：pn 本身出錯
H odd + pn even：double error，無法更正
注意：ECC DRAM 使用 SEC/DEC，每 64 bits 資料用 8 bits 保護

🖥️

§5.6 Virtual Machines

VMM · Virtualization · Timer

Virtual Machine 概念

Host 電腦模擬 guest OS 和機器資源
優點：隔離、安全、資源共享
效能有損耗，但現代高效能 CPU 可接受
例：IBM VM/370、VMWare、Microsoft Virtual PC

Virtual Machine Monitor (VMM)

把虛擬資源對應到實體資源（memory, I/O devices, CPUs）
Guest code 在 user mode 執行，遇到特權指令或受保護資源時 trap 到 VMM
VMM 處理真實 I/O 裝置，為 guest 模擬虛擬 I/O 裝置

Timer Virtualization 範例

VMM 攔截 timer interrupt → 選擇下一個 VM 執行
若 VM 需要 timer，VMM 模擬一個 virtual timer

ISA 支援需求

所有實體資源只能透過特權指令存取（含 page tables, interrupt controls, I/O registers）
x86 等現代 ISA 正在加強 virtualization 支援

🗺️

§5.7 Virtual Memory & TLB

Page Table · TLB · Page Fault

Virtual Memory 概念

把 Main Memory 當作 Disk 的 Cache 使用
由 CPU hardware + OS 共同管理
每個程式有自己的私有虛擬位址空間，受到保護
VM 的 "block" 稱為 Page
VM 的 "miss" 稱為 Page Fault

Page Table

以 virtual page number 為 index 的陣列
每個 PTE（Page Table Entry）存：physical page number + status bits（referenced, dirty...）
若 page 不在 memory：PTE 指向 disk 上的 swap space 位置
CPU 有 page table register 指向目前的 page table
使用 Fully Associative 放置（任何 virtual page 可對應任何 physical page）→ 降低 page fault rate

Page Fault 處理（OS 負責）

用 faulting virtual address 找到 PTE
在磁碟上找到對應的 page
選擇要替換的 page（若 dirty 則先寫回磁碟）
把 page 讀入 memory，更新 page table
讓 process 恢復執行（從 faulting instruction 重新開始）

Page fault penalty：數百萬個 clock cycles（很痛），所以要最小化 page fault rate
寫入策略：只能用 Write-Back（disk 寫入需要數百萬 cycles，write-through 不切實際）
用 Dirty bit 記錄 page 是否被修改
替換政策：LRU 近似（用 Reference bit，OS 定期清零）

TLB（Translation Look-aside Buffer）

每次位址轉換都要存取 page table（在 memory），太慢了
TLB = CPU 內的 PTE cache（快取 Page Table Entries）
典型規格：16–512 PTEs，hit 0.5–1 cycle，miss 10–100 cycles，miss rate 0.01%–1%

TLB Hit（最常見）

直接從 TLB 取到 physical address，速度極快

TLB Miss

Page 在 memory 中但 PTE 不在 TLB → 從 memory 載入 PTE 到 TLB，再重試（by hardware 或 software）

若 page 不在 memory → TLB miss → Page fault → OS 處理
TLB 使用 Fully Associative 或 small set-associative

Memory Protection

Page table 和其他 state 只能在 supervisor mode（kernel mode）存取
System call exception（MIPS 的 syscall）進入 kernel mode

🔄

§5.8 記憶體階層統一框架 & 3C Misses

Block Placement · Replacement · Write Policy · Sources of Misses

各層級通用的四個問題

問題	Cache	Virtual Memory
Block 放哪？	Direct / n-way / Fully associative	Fully associative（任何 virtual page）
怎麼找到？	Index + tag 比較	Page table lookup（無需比較）
替換誰？	LRU or Random	LRU 近似（reference bit）
寫入策略？	Write-through 或 Write-back	只能 Write-back

3C Miss 分類（超重要！）

❄️ Compulsory Miss（Cold Start Miss）

第一次存取某個 block → 一定會 miss，無法避免

📦 Capacity Miss

Cache 太小，裝不下所有需要的 blocks → 被替換掉的 block 之後又需要

⚔️ Conflict Miss（Collision Miss）

在 non-fully associative cache 中，多個 blocks 競爭同一個 set → 在 fully associative cache 中這些 miss 不會發生

Cache Design Trade-offs 表格

設計改變	對 Miss Rate 的影響	負面效果
增大 cache size	↓ capacity misses	可能增加 access time
增加 associativity	↓ conflict misses	可能增加 access time
增大 block size	↓ compulsory misses	增大 miss penalty；過大時因 pollution 反而↑ miss rate

🤖

§5.9 用 FSM 控制 Cache

Finite State Machine · Cache Controller

範例 Cache 特性

Direct-mapped, write-back, write allocate
Block size: 4 words（16 bytes），Cache size: 16 KB（1024 blocks）
32-bit byte addresses，每個 block 有 valid bit 和 dirty bit
Blocking cache：CPU 等待直到存取完成
Address 分解：Tag 18 bits + Index 10 bits + Offset 4 bits

FSM 控制的概念

用 Finite State Machine（有限狀態機）來排序控制步驟
State 以 binary 編碼，存在暫存器中
Next state = f(current state, current inputs)
Control outputs = f(current state)

🔗

§5.10 Cache Coherence

Multiprocessor · Snooping · Memory Consistency

Cache Coherence 問題

當多個 CPU 共享同一個實體位址空間，且各有自己的 cache，寫入一個 cache 後，其他 CPU 的 cache 就過時了

時間	事件	CPU A cache	CPU B cache	Memory
0	-	-	-	0
1	A 讀 X	0	-	0
2	B 讀 X	0	0	0
3	A 寫 X=1	1	0 (舊!)	1

Coherence 的正式定義

P 寫 X 後 P 讀 X（中間無其他寫入）→ 讀到剛寫的值
P1 寫 X 後（夠久之後）P2 讀 X → 讀到剛寫的值
P1 寫 X、P2 寫 X → 所有 processor 看到相同的寫入順序

Coherence Protocols

👁 Snooping Protocol

每個 cache 監聽（snoop）bus 上的讀寫
簡單，適用於共享 bus 的多處理器

📋 Directory-based Protocol

用一個 directory 記錄每個 block 被哪些 cache 持有
適用於更大規模的多處理器系統

Invalidating Snooping Protocol（重要！）

某個 cache 要寫入某 block 時，先在 bus 上廣播 Invalidate 訊息
其他 cache 把該 block 標記為 invalid
之後其他 CPU 讀取時 cache miss → 從擁有該 block 的 cache 取得更新值

CPU 動作	Bus 動作	A cache	B cache	Memory
A 讀 X	Cache miss for X	0	-	0
B 讀 X	Cache miss for X	0	0	0
A 寫 X=1	Invalidate for X	1	(invalid)	0
B 讀 X	Cache miss for X	1	1	1

Memory Consistency

假設：寫入完成 = 所有 processor 都看到了；processor 不重新排序 writes
結果：P 先寫 X 再寫 Y → 所有看到新 Y 的 processor 也能看到新 X
Processors 可以 reorder reads，但不能 reorder writes

🔬

§5.13 ARM Cortex-A8 & Intel Core i7 實例

Multilevel On-Chip Caches · 2-Level TLB · Non-blocking Cache

Multilevel On-Chip Caches 比較表（ARM Cortex-A8 vs Intel Nehalem/Core i7）

特性	ARM Cortex-A8	Intel Nehalem (Core i7)
L1 cache 組織	Split I/D cache	Split I/D cache（per core）
L1 cache 大小	32 KiB each	32 KiB each per core
L1 associativity	4-way (I), 4-way (D)	4-way (I), 8-way (D)
L1 replacement	Random	Approximated LRU
L1 block size	64 bytes	64 bytes
L1 write policy	Write-back, Write-allocate(?)	Write-back, No-write-allocate
L1 hit time	1 clock cycle	4 clock cycles, pipelined
L2 cache 組織	Unified (I+D)	Unified per core
L2 cache 大小	128 KiB – 1 MiB	256 KiB
L2 associativity	8-way set associative	8-way set associative
L2 replacement	Random(?)	Approximated LRU
L2 block size	64 bytes	64 bytes
L2 write policy	Write-back, Write-allocate(?)	Write-back, Write-allocate
L2 hit time	11 clock cycles	10 clock cycles
L3 cache 組織	—	Unified, shared
L3 cache 大小	—	8 MiB
L3 associativity	—	16-way set associative
L3 block size	—	64 bytes
L3 write policy	—	Write-back, Write-allocate
L3 hit time	—	35 clock cycles

2-Level TLB 組織比較表

特性	ARM Cortex-A8	Intel Core i7
Virtual address	32 bits	48 bits
Physical address	32 bits	44 bits
Page size	Variable: 4, 16, 64 KiB, 1, 16 MiB	Variable: 4 KiB, 2/4 MiB
L1 TLB	Fully associative, 32 entries, round robin；I/D 各一；miss by hardware	4-way set assoc, LRU；I-TLB 128 entries (small), 7/thread (large)；D-TLB 64 entries (small), 32 (large)
L2 TLB	—	4-way set assoc, LRU, 512 entries；miss by hardware

Supporting Multiple Issue（多發射支援）

兩者都用 multi-banked cache，允許每個 cycle 多次存取（前提：無 bank conflict）
Core i7 特有 cache 優化：
- Return requested word first：先把 CPU 需要的 word 送出去，不用等整個 block 載入完
- Non-blocking cache（Hit under miss / Miss under miss）：cache miss 時不完全暫停，可繼續服務其他不相依的存取
- Data prefetching：預先把即將需要的資料載入 cache

⚡

§5.14 Going Faster: Cache Blocking & Matrix Multiply

DGEMM · Subword Parallelism · Blocking

進階 DGEMM 優化

結合兩種技術：Cache Blocking（§5.4 已介紹）+ Subword Parallelism（SIMD）
Subword parallelism：一次對多個資料執行相同運算（如 AVX 指令集一次處理多個 double）
兩者合用可大幅提升矩陣乘法的效能

核心概念：先用 blocking 確保資料在 cache 裡被充分重用，再用 SIMD 讓每次運算處理更多資料 → 雙管齊下榨乾 CPU 效能。

⚠️

§5.15 Fallacies and Pitfalls（常見錯誤與陷阱）

Byte vs Word · AMAT · Segments · VMM

Pitfall 1：Byte vs. Word Addressing 混淆

32-byte direct-mapped cache，4-byte blocks：
Byte address 36 → Block 36/4=9，9 mod 8 = block 1
Word address 36 → Block 36，36 mod 8 = block 4

⚠️ 考試陷阱：搞清楚題目給的是 byte address 還是 word address！

Pitfall 2：忽略 Memory System 對程式碼的影響

以行（row）還是以列（column）迭代陣列，效能差異極大
大步距（large stride）存取 → 空間局部性差 → 大量 cache miss
Compiler 優化和演算法設計都需考慮 memory access pattern

Pitfall 3：多核心共享 L2/L3 的 Conflict Miss

若共享 cache 的 associativity 低於 core 數 → 大量 conflict miss
核心數越多 → 需要更高的 associativity

Pitfall 4：用 AMAT 評估 Out-of-Order Processor

AMAT 沒考慮 non-blocked accesses 的效果
Out-of-order CPU 在 cache miss 期間可繼續執行其他指令
正確做法：用 system simulation

Pitfall 5：用 Segments 擴展位址範圍

如 Intel 80286 的 segment 機制：segment 不一定夠大、位址運算複雜
現代做法用 virtual memory 取代

Pitfall 6：在不支援虛擬化的 ISA 上實作 VMM

若 ISA 有非特權指令可存取硬體資源，VMM 就無法正確攔截
解法：擴充 ISA 加入 virtualization 支援，或要求 guest OS 不使用問題指令

🎓

§5.16 Concluding Remarks（結語）

Big Picture · Key Takeaways

核心思想總結

快的記憶體小，大的記憶體慢 → 我們想要又快又大的記憶體
Caching 給了我們這個幻覺，透過 locality 原理讓常用資料留在快的地方
Memory Hierarchy：L1 ↔ L2 ↔ … ↔ DRAM ↔ Disk
Memory system 設計對多處理器系統尤其關鍵（cache coherence 問題）

一句話總結整章：利用 Locality 原理，透過分層的 Cache 架構，讓程式看起來好像有很大又很快的記憶體——這就是 Memory Hierarchy 的精髓。

作業練習題

三份作業完整題目與解題

💡 點擊每個小題的 「看答案」 按鈕來顯示解答，自己先想想再看！

第一次作業

Exercise 5.1 · 5.3 · 5.6 — Locality、Direct Mapped Cache、Cache 效能

Exercise 5.1 — Matrix Locality（C 語言，row-major）

for (I = 0; I < 8; I++)
for (J = 0; J < 8000; J++)
A[I][J] = B[I][0] + A[J][I];
// row-major 儲存，32-bit integers，16-byte cache blocks

5.1.1

一個 16-byte 的 cache block 可以存幾個 32-bit integer？

看答案

16 bytes ÷ 4 bytes/integer = 4 個

5.1.2

哪些變數的存取具有 temporal locality（時間局部性）？

看答案

B[I][0]：內層迴圈 J 跑 8000 次，每次都存取同一個 B[I][0] → 強烈 temporal locality
I, J（迴圈變數）：每次迭代都存取 → temporal locality

5.1.3

哪些變數的存取具有 spatial locality（空間局部性）？

看答案

A[I][J]：row-major 下 J 遞增 = 連續記憶體 → ✅ spatial locality
A[J][I]：J 遞增但 I 固定，row-major 下是跨 row → 大步距 → ✗ spatial locality
B[I][0]：每次同位置，算 temporal，非 spatial

同樣的程式改成 Matlab（column-major）：

for I = 1:8
  for J = 1:8000
    A(I,J) = B(I,0) + A(J,I);
  end
end

5.1.4

存一列 8000 個 32-bit integers 需要幾個 16-byte cache blocks？

看答案

8000 × 4 bytes = 32,000 bytes；32,000 ÷ 16 = 2,000 個 cache blocks

5.1.5

Matlab (column-major) 下，哪些變數具有 temporal locality？

看答案

B(I,0)：同 C 版本，內層 J 迴圈重複存取 → temporal locality
I, J（迴圈變數）→ temporal locality

5.1.6

Matlab (column-major) 下，哪些變數具有 spatial locality？

看答案

Column-major 下：
A(J,I)：J 遞增 = 同 column 依序存取 = 連續記憶體 → ✅ spatial locality
A(I,J)：I 固定、J 遞增在 column-major 下是跨 column → ✗ spatial locality

Exercise 5.3 — Direct-Mapped Cache 結構計算

32-bit address：Tag [31–10] = 22 bits，Index [9–5] = 5 bits，Offset [4–0] = 5 bits

5.3.1

Cache block size 是多少 words？

看答案

Offset = 5 bits → block size = 2⁵ = 32 bytes = 8 words（每 word 4 bytes）

5.3.2

Cache 有幾個 entries？

看答案

Index = 5 bits → 2⁵ = 32 entries

5.3.3

Total bits / Data storage bits 的比值是多少？

看答案

每個 entry：1 valid bit + 22 tag bits + 256 data bits = 279 bits
Total = 32 × 279 = 8,928 bits；Data = 32 × 256 = 8,192 bits
Ratio = 8,928 / 8,192 ≈ 1.09

接下來從 power-on 開始，依序存取以下 byte addresses：

存取順序	0	4	16	132	232	160	1024	30	140	3100	180	2180

5.3.4

共有幾個 blocks 被 replaced（替換）？

看答案

先算每個 address 的 index（bits[9:5]）和 tag（bits[31:10]）：

Address	Index	Tag	Hit/Miss	Replace?
0	0	0	Miss	No（空）
4	0	0	Hit	—
16	0	0	Hit	—
132	4	0	Miss	No（空）
232	7	0	Miss	No（空）
160	5	0	Miss	No（空）
1024	0	1	Miss	✅ Yes（踢掉 tag=0）
30	0	0	Miss	✅ Yes（踢掉 tag=1）
140	4	0	Hit	—
3100	12	3	Miss	No（空）
180	5	0	Hit	—
2180	4	2	Miss	✅ Yes（踢掉 tag=0）

Replaced = 3 次

5.3.5

Hit ratio 是多少？

看答案

Hits：4, 16, 140, 180 共 4 次；總共 12 次存取
Hit ratio = 4/12 ≈ 33.3%

5.3.6

列出 cache 最終狀態（格式：<index, tag, data>）

看答案

<0, 0, Mem[0–31]>
<4, 2, Mem[2176–2207]>
<5, 0, Mem[160–191]>
<7, 0, Mem[224–255]>
<12, 3, Mem[3072–3103]>

Exercise 5.6 — Cache 效能計算（P1 vs P2）

Main memory = 70ns，Memory accesses = 36% of instructions
P1: L1=2KiB, miss rate=8%, hit time=0.66ns | P2: L1=4KiB, miss rate=6%, hit time=0.90ns

5.6.1

以 L1 hit time 作為 cycle time，P1 和 P2 各自的 clock rate 是多少？

看答案

P1: 1/0.66ns = 1.52 GHz
P2: 1/0.90ns = 1.11 GHz

5.6.2

P1 和 P2 各自的 AMAT 是多少？

看答案

AMAT = Hit time + Miss rate × Miss penalty
P1: 0.66 + 0.08 × 70 = 6.26 ns
P2: 0.90 + 0.06 × 70 = 5.10 ns

5.6.3

Base CPI = 1，P1 和 P2 各自的 Total CPI 是多少？哪個較快？

看答案

Miss penalty（cycles）= memory time / cycle time
P1 penalty = 70/0.66 ≈ 106 cycles；stall = 0.36 × 0.08 × 106 ≈ 3.05 → CPI = 4.05
P2 penalty = 70/0.90 ≈ 77.8 cycles；stall = 0.36 × 0.06 × 77.8 ≈ 1.68 → CPI = 2.68
P2 較快

幫 P1 加上 L2 cache：

L2 Size = 1MiB，L2 local miss rate = 95%，L2 hit time = 5.62ns

5.6.4

P1 加上 L2 後的 AMAT 是多少？比沒有 L2 好還是差？

看答案

AMAT = L1 hit + L1 miss rate × (L2 hit + L2 miss rate × Memory)
= 0.66 + 0.08 × (5.62 + 0.95 × 70) = 0.66 + 0.08 × 72.12 = 6.43 ns
比只有 L1 的 6.26ns 還差 → 更差！ L2 miss rate 太高（95%），加了反而拖慢

5.6.5

P1 加上 L2 後的 Total CPI 是多少？

看答案

L2 hit penalty = 5.62/0.66 ≈ 8.5 cycles；L2 miss penalty = 70/0.66 ≈ 106 cycles
stall = 0.36 × 0.08 × (8.5 + 0.95×106) = 0.36 × 0.08 × 109.2 ≈ 3.14
CPI = 4.14

5.6.6

P1(+L2) vs P2，哪個更快？要讓較慢的追上較快的，需要什麼條件？

看答案

P1+L2 CPI ≈ 4.14 vs P2 CPI ≈ 2.68 → P2 仍更快
P1 要追上 P2（目標 CPI=2.68）：
1 + 0.36 × miss_rate × (8.5 + 0.95×106) = 2.68
miss_rate ≈ 4.27%（P1 的 L1 miss rate 要降到約 4.27%）

第二次作業

Exercise 5.8 · 5.12 · 5.14 — MTTF/可靠性、Page Table 設計、Shadow vs NPT

Exercise 5.8 — MTTF / MTTR / Availability

MTTF = 3 years，MTTR = 1 day

5.8.1

計算 MTBF

看答案

MTBF = MTTF + MTTR = 3×365 + 1 = 1096 days

5.8.2

計算 Availability

看答案

Availability = MTTF / MTBF = 1095 / 1096 ≈ 99.91%

5.8.3

MTTR → 0 時，availability 會怎樣？這是現實情況嗎？

看答案

Availability → 100%。不現實——修復永遠需要一定時間。

5.8.4

MTTR 非常大時（裝置很難修），availability 會怎樣？

看答案

Availability → 0%。是，修不好的裝置可用性極低。

Exercise 5.12 — Page Table 空間與時間優化

Virtual Address = 43 bits，Physical DRAM = 16 GiB，Page Size = 4 KiB，PTE Size = 4 bytes

5.12.1

Single-level page table 需要幾個 PTE？要佔多少 physical memory？

看答案

Page offset = log₂(4KiB) = 12 bits → VPN = 43 - 12 = 31 bits
PTEs = 2³¹ ≈ 2 Giga 個
Physical memory = 2³¹ × 4 bytes = 8 GiB（超誇張）

5.12.2

用 multilevel page table 需要幾層？TLB miss 時需幾次 memory reference？

看答案

每個 page table page 可放 4KiB/4B = 1024 = 2¹⁰ 個 PTEs → 每層 index 10 bits
VPN = 31 bits → ⌈31/10⌉ = 4 層（分 10+10+10+1 bits）
TLB miss 時需 4 次 memory references（每層各一次）

5.12.3

Inverted page table 需幾個 PTE？TLB miss 時 common case 和 worst case 各幾次 memory reference？

看答案

Physical pages = 16GiB / 4KiB = 2²² → 4M 個 PTEs（以物理頁為索引，比 single-level 小很多）
Hash table：Common case = 1 次（hash 直接命中）；Worst case = hash chain 長度次（全部 collision）

以下是一個 4-entry TLB 的內容：

Entry	Valid	VA Page	Modified	Protection	PA Page
1	1	140	1	RW	30
2	0	40	0	RX	34
3	1	200	1	RO	32
4	1	280	0	RW	31

5.12.4

什麼情況下 Entry 2 的 valid bit 會被設成 0？

看答案

① 該 PTE 從 TLB 被 evict（容量不足）
② Context switch 時 OS flush TLB
③ 該 page 被 invalidated（如 page unmapped 或 page fault 後）

5.12.5

指令對 VA page 30 執行寫入時會發生什麼事？Software-managed TLB 何時比 hardware-managed TLB 快？

看答案

VA page 30 不在 TLB → TLB miss → 查 page table → 載入 PTE 到 TLB → 重試寫入
Software TLB 較快的情況：page table 結構複雜（如 inverted page table），hardware walker 無法直接處理，software handler 可自訂優化路徑

5.12.6

指令對 VA page 200 執行寫入時會發生什麼事？

看答案

Entry 3：VA=200，protection=RO（Read Only）
→ 寫入 RO page → Protection fault！OS 攔截，通常會終止程序或送出 SIGSEGV

Exercise 5.14 — Shadow Page Table vs Nested Page Table (NPT)

Shadow paging：software 在 hypervisor 複製 guest page table，攔截修改保持同步
NPT：hardware 支援 VA→PA 和 PA→MA 兩層 page table，pure hardware walk

5.14.1

以下操作在 shadow page table 和 NPT 下各會怎樣？
(1) Create process (2) TLB miss (3) Page fault (4) Context switch

看答案

操作	Shadow Page Table	Nested Page Table
Create process	Hypervisor 建立 shadow PT，overhead 高	只需建立 guest PT，overhead 低
TLB miss	查 shadow PT（已整合 VA→MA），1 層 walk，快	走兩層 PT（VA→PA→MA），memory ref 多
Page fault	需同步更新 guest PT 和 shadow PT，複雜	只更新 guest PT，NPT 自動處理
Context switch	切換到對應 VM 的 shadow PT	切換 guest PT + NPT pointer，TLB flush

5.14.2

x86 4-level page table，native vs nested page table 的 TLB miss 各需幾次 memory reference？

看答案

Native：4 levels = 4 次
NPT：每個 guest PT level 在 walk 時，guest 的每個 PTE address 本身也需要經過 NPT 的 4 層 walk。
計算：4 guest levels × 5（4 NPT levels + 1）+ 1 final data = 最多 24 次 memory references

5.14.3

TLB miss rate、TLB miss latency、page fault rate、page fault handler latency，各對哪種方案更重要？

看答案

Shadow PT：Page fault rate & page fault handler latency 最重要（每次 page fault 要同步兩份 PT，超貴）
NPT：TLB miss rate & TLB miss latency 最重要（TLB miss 時需走兩層 PT，memory access 暴增）

已知參數：

TLB misses = 0.2 / 1000 instructions，NPT TLB miss latency = 200 cycles
Page faults = 0.001 / 1000 instructions，Shadow page fault overhead = 30,000 cycles

5.14.4

Native CPI = 1，使用 shadow page table 和 NPT 的 CPI 各是多少？

看答案

Shadow PT：overhead 主要來自 page fault
CPI = 1 + (0.001/1000) × 30,000 = 1 + 0.03 = 1.03
NPT：overhead 主要來自 TLB miss
CPI = 1 + (0.2/1000) × 200 = 1 + 0.04 = 1.04

5.14.5

有哪些技術可以減少 Shadow Paging 的 overhead？

看答案

① 使用更大的 page（superpage），減少 page fault 次數
② Lazy synchronization（延遲同步 shadow PT）
③ 增大 TLB size，減少 TLB miss 進而減少 shadow PT 被查詢的頻率

5.14.6

有哪些技術可以減少 NPT 的 overhead？

看答案

① 增大 TLB size，降低 TLB miss rate
② 使用 superpage，減少 PT levels
③ Hardware TLB prefetching
④ 增加 TLB associativity

第三次作業

Exercise 5.16 · 5.17 · 5.18 — Write Buffer FSM、Cache Coherence、CMP Cache 設計

Exercise 5.16 — Write Buffer FSM 設計

Cache：direct-mapped, write-back, write-allocate（參考 Figure 5.40）
在此基礎上加入一個容量 1 block 的 write buffer。
Write buffer 的作用：dirty miss 時，不用等 writeback 完才讀新 block，先把 dirty block 丟進 write buffer，立刻 fetch 新 block；dirty block 再慢慢寫回 memory。

5.16.1

Write buffer 正在把 dirty block writeback 到 memory 時，CPU 發出一個 cache hit 的請求，應該怎麼處理？

看答案

Cache hit 不需要存取 memory，直接從 cache 服務 CPU。
CPU 不需要等，write buffer 繼續在背景 writeback，兩者並行。

5.16.2

Write buffer 正在 writeback 時，CPU 發出一個 cache miss 的請求，應該怎麼處理？

看答案

Cache miss 需要存取 memory bus 來 fetch 新 block，但 bus 正被 write buffer 佔用。
CPU 需要等，直到 write buffer 完成 writeback 釋放 bus，才能開始 fetch。

5.16.3

設計一個支援 write buffer 的 FSM，說明各狀態及轉換條件。

看答案

State 0：Idle（等待 CPU 請求）
  → Hit：State 0（直接服務）
  → Miss，block not dirty：State 1（fetch）
  → Miss，block dirty：State 2（把 dirty block → write buffer，同時開始 fetch）

State 1：Fetching（從 memory 取新 block，write buffer 空閒）
  → Fetch 完成：State 0

State 2：Fetching + Write Buffer Busy（fetch 新 block 同時 write buffer 有 dirty block 待寫）
  → CPU hit 請求：繼續 State 2（cache hit 不需要 bus，直接服務）
  → CPU miss 請求：繼續 State 2（需要 bus 但忙，等待）
  → Fetch 完成：State 3（開始 writeback）

State 3：Writing Back（把 write buffer 的 dirty block 寫回 memory）
  → Writeback 完成，無 pending miss：State 0
  → Writeback 完成，有 pending miss：State 1（開始 fetch）

Exercise 5.17 — Cache Coherence & Memory Consistency

X[0] = X[1] = 0（初始，同一個 cache block X）
P1: X[0]++; X[1] = 3; | P2: X[0] = 5; X[1] += 2;

5.17.1

正確的 coherence protocol 下，X[0] 和 X[1] 有哪些可能的最終值組合？
若 protocol 不保證 coherence，再列出至少一個額外可能的值。

看答案

Coherent 下可能的值（X[0], X[1]）：
• P1全先：X[0]=1→P2寫5，X[1]=3→P2+=2=5 → (5, 5)
• P2全先：X[0]=5→P1++=6，X[1]=2→P1=3 → (6, 3)
• 交錯：P1寫X[0]=1，P2覆寫X[0]=5，P1寫X[1]=3，P2讀X[1]=3+2=5 → (5, 5)
• 交錯：P2寫X[0]=5，P1++=6，P2寫X[1]+=2=2，P1=3 → (6, 3)
→ 結合所有合法交錯：(5,5), (6,3), (5,3), (6,5)

不 coherent 下額外可能：
P2 看不到 P1 的 X[0]=1 就讀了舊值 → 如 (1, 2) 或 (1, 5)

5.17.2

以 Snooping protocol 為例，列出一個合法的操作序列（以得到其中一種結果為例）。

看答案

以 P1 先執行為例，最終結果 (5, 5)：
1. P1 讀 X[0]（miss）→ 廣播讀取，取得 block，X[0]=0
2. P1 寫 X[0]=1（hit）→ 廣播 Invalidate，P2 的 copy 失效
3. P2 讀 X[0]（miss，因被 invalidate）→ 取得 X[0]=1
4. P2 寫 X[0]=5 → 廣播 Invalidate
5. P1 寫 X[1]=3 → 廣播 Invalidate
6. P2 讀 X[1]（miss）→ 取得 X[1]=3
7. P2 寫 X[1]=3+2=5
最終：X[0]=5, X[1]=5

5.17.3

執行以上讀寫操作，best-case 和 worst-case 各需要幾次 cache miss？

看答案

Best case（2 misses）：block 本來就在兩個 cache 中，只有寫入時的 invalidate 造成對方 miss，P1 寫 X[0] invalidate P2 → P2 再讀時 miss (1)，P1 寫 X[1] invalidate P2 → P2 再讀時 miss (2)
Worst case（4 misses）：P1 讀 X[0] miss (1)，P2 讀 X[0] miss (2)（被 invalidate），P1 讀 X[1] miss (3)，P2 讀 X[1] miss (4)

Memory consistency 部分（A=B=0 初始，不同 cache blocks）：

P1: A=1; B=2; A+=2; B++;　（最終 A=3, B=3）
P2: C=B; D=A;

5.17.4

在保證 consistency 的情況下，C 和 D 有哪些可能的值組合？

看答案

Consistency 保證：P2 看到的 B 和 A 必須符合 P1 的寫入順序（看到比較新的 B，就不能看到比 B 更舊版本對應的 A）
合法的 (C, D) 組合：
(0,0), (0,1), (0,3), (2,1), (2,3), (3,3)

5.17.5

若不保證 consistency，額外可能出現哪些 (C,D) 值？

看答案

如 (3, 0)（看到最新 B=3 但 A=0，違反寫入順序）或 (2, 0)

5.17.6

哪種 write policy + write allocation 組合，最能讓 coherence protocol 實作變簡單？

看答案

Write-through + No write-allocate 最簡單：
每次寫入直接寫到 memory，memory 永遠是最新值；其他 cache 只需 invalidate 或直接從 memory 讀；不用追蹤 dirty bits，snoop 邏輯最簡單。
Write-back + write-allocate 效能好但 dirty block 管理讓 coherence 複雜很多。

Exercise 5.18 — CMP Private vs Shared L2 Cache

L1 miss：每 32 instructions 一次（= 0.03125 misses/instr）
Private L2 hit = 5 cycles，Shared L2 hit = 20 cycles，Memory = 180 cycles

	Private MPI（misses/instr）	Shared MPI
Benchmark A	0.30% = 0.003	0.12% = 0.0012
Benchmark B	0.06% = 0.0006	0.03% = 0.0003

5.18.1

哪種 cache 設計對各 benchmark 更好？用數據支持你的結論。

看答案

CPI = 1 + (MPI × memory_cycles) + ((L1_miss_rate - MPI) × L2_hit_cycles)
L1 miss rate = 1/32 = 0.03125

Benchmark A：
Private: 1 + 0.003×180 + (0.03125-0.003)×5 = 1 + 0.54 + 0.141 = 1.681
Shared: 1 + 0.0012×180 + (0.03125-0.0012)×20 = 1 + 0.216 + 0.601 = 1.817
→ Private 較好

Benchmark B：
Private: 1 + 0.0006×180 + (0.03125-0.0006)×5 = 1 + 0.108 + 0.153 = 1.261
Shared: 1 + 0.0003×180 + (0.03125-0.0003)×20 = 1 + 0.054 + 0.619 = 1.673
→ Private 較好

5.18.2

① Shared cache latency 加倍（→40 cycles）時哪種更好？
② Off-chip memory latency 加倍（→360 cycles）時哪種更好？

看答案

① Shared latency 加倍 → Shared 的 L2 hit cost 更高，Private 優勢更大 → Private 更好
② Memory latency 加倍 → miss penalty 大增，Shared 的低 MPI 優勢更顯著（少一半的 memory access）→ Shared 可能更好

5.18.3

討論 single-threaded、multi-threaded、multiprogrammed workload 下 private vs shared L2 的優缺點。若加上 on-chip L3 cache 呢？

看答案

Private L2：優→低延遲；缺→跨 core 無法共享資料，重複資料浪費空間
Shared L2：優→多執行緒可共享資料減少 miss，容量利用率高；缺→延遲高，bandwidth 競爭

Single-threaded：Private 優（低延遲）；Multi-threaded：Shared 優（thread 間共享資料多）；Multiprogrammed：Private 優（各程式資料獨立）

加上 L3：主流設計變成 Private L2 + Shared L3，兩全其美——L2 快，L3 大且共享

5.18.4

Base CPI = 1（ideal L2），non-blocking cache 讓 concurrent L2 misses 從 1 提升到 2，
對 Shared L2 和 Private L2 各提升多少效能？

看答案

Concurrent misses 加倍 → effective miss penalty 減半 → memory stall 部分大約砍半

以 Benchmark A 為例：
Shared L2 原 CPI=1.817，stall=0.817 → 砍半 → stall≈0.41 → 新 CPI≈1.41（提升約 22%）
Private L2 原 CPI=1.681，stall=0.681 → 砍半 → stall≈0.34 → 新 CPI≈1.34（提升約 20%）

5.18.5

假設每 18 個月 core 數加倍，3 年後需要多少倍的 off-chip memory bandwidth 才能維持相同的 per-core 效能？

看答案

3 年 = 2 個 18 個月週期 → cores × 2² = 4×
維持相同 per-core bandwidth → 總 bandwidth 需要 4 倍

5.18.6

在整個 memory hierarchy 中，哪些優化可以增加 concurrent misses 的數量？

看答案

① Non-blocking (lockup-free) cache：允許 hit under miss / miss under miss
② Out-of-order execution：CPU 在 miss 期間繼續執行不相依指令
③ Hardware prefetching：預取資料，隱藏 miss latency
④ MSHR (Miss Status Holding Registers)：同時追蹤多個 outstanding misses
⑤ Memory-level parallelism (MLP)：多個 miss 同時在 memory 系統中進行

Processors	Time	Speedup	% of potential
1（baseline）	110 t_add	1×	—
10	10 + 100/10 = 20 t_add	110/20 = 5.5×	55%
100	10 + 100/100 = 11 t_add	110/11 = 10×	10%

Processors	Time	Speedup	% of potential
10	10 + 10000/10 = 1010 t_add	10010/1010 = 9.9×	99%
100	10 + 10000/100 = 110 t_add	10010/110 = 91×	91%

Large and Fast:Exploiting Memory Hierarchy

📋 章節目錄

§5.1 Locality 原則與記憶體階層

Principle of Locality（局部性原理）

⏱ Temporal Locality（時間局部性）

📍 Spatial Locality（空間局部性）

Memory Hierarchy（記憶體階層）

基本術語

§5.2 記憶體技術

各類記憶體比較

DRAM 技術細節

Flash Storage 重點

磁碟存取時間計算（重要！）

§5.3 Cache 基礎

Direct Mapped Cache

Address 分解（超重要！）

Valid Bit 與 Tag

Block Size 考量

Cache Miss 處理

Write 策略（很常考！）

✍️ Write-Through

🔄 Write-Back

Write Miss 時的 Write Allocation

實例：Intrinsity FastMATH

§5.4 Cache 效能量測與改善

Cache 效能公式（超重要！）

AMAT（Average Memory Access Time）

Associativity（關聯度）

Replacement Policy（替換政策）

Multilevel Cache（多層 Cache）

Software 優化：Cache Blocking（DGEMM）

§5.5 可靠記憶體階層（ECC）

可靠性指標

Hamming SEC Code（Single Error Correction）

SEC/DEC（加上 Double Error Detection）

§5.6 Virtual Machines

Virtual Machine 概念

Virtual Machine Monitor (VMM)

Timer Virtualization 範例

ISA 支援需求

§5.7 Virtual Memory & TLB

Virtual Memory 概念

Page Table

Page Fault 處理（OS 負責）

TLB（Translation Look-aside Buffer）

TLB Hit（最常見）

TLB Miss

Memory Protection

§5.8 記憶體階層統一框架 & 3C Misses

各層級通用的四個問題

3C Miss 分類（超重要！）

❄️ Compulsory Miss（Cold Start Miss）

📦 Capacity Miss

⚔️ Conflict Miss（Collision Miss）

Cache Design Trade-offs 表格

§5.9 用 FSM 控制 Cache

範例 Cache 特性

FSM 控制的概念

§5.10 Cache Coherence

Cache Coherence 問題

Coherence 的正式定義

Coherence Protocols

👁 Snooping Protocol

📋 Directory-based Protocol

Invalidating Snooping Protocol（重要！）

Memory Consistency

§5.13 ARM Cortex-A8 & Intel Core i7 實例

Multilevel On-Chip Caches 比較表（ARM Cortex-A8 vs Intel Nehalem/Core i7）

2-Level TLB 組織比較表

Supporting Multiple Issue（多發射支援）

§5.14 Going Faster: Cache Blocking & Matrix Multiply

進階 DGEMM 優化

§5.15 Fallacies and Pitfalls（常見錯誤與陷阱）

Pitfall 1：Byte vs. Word Addressing 混淆

Pitfall 2：忽略 Memory System 對程式碼的影響

Pitfall 3：多核心共享 L2/L3 的 Conflict Miss

Pitfall 4：用 AMAT 評估 Out-of-Order Processor

Pitfall 5：用 Segments 擴展位址範圍

Pitfall 6：在不支援虛擬化的 ISA 上實作 VMM

§5.16 Concluding Remarks（結語）

Large and Fast:
Exploiting Memory Hierarchy

Parallel Processors
§6.1 Introduction & §6.2 Parallel Programming