記憶體階層練習題 (Practice - Memory Hierarchy)

Key Patterns (click to expand)

關鍵字	答案
SRAM vs DRAM	SRAM:6 電晶體雙穩態、不需 refresh、貴 1,000 倍、用於 cache;DRAM:1 電晶體+電容、需 refresh、用於 main memory
讀 supercell (i, j)	先 RAS = i(整列進 internal row buffer)再 CAS = j(取出 w bits)
磁碟存取時間	T_access = T_avg seek + T_avg rotation + T_avg transfer;由 seek + rotation 主宰,經驗法則 ≈ 2 × T_avg seek
SSD 隨機寫慢	erase 以整個 block 為單位且慢(約 1 ms);寫既有資料的 page 前須先搬走同 block 有用 pages
Temporal vs spatial locality	重複引用同一位置 → temporal;引用鄰近位址 → spatial;stride 越小 spatial 越好
快取容量	C = S × E × B(不含 tag bits 與 valid bit)
位址切割	低 b bits = block offset、中 s bits = set index、高 t bits = tag
命中條件	valid = 1 且 tag 相符,兩者缺一即 miss
Miss 三分類	cold(空 cache 必 miss)/ conflict(placement 限制互逐)/ capacity(working set > C)
Thrashing 解法	陣列尾端加 B bytes padding 錯開 set 映射
寫入策略配對	write-through + no-write-allocate;write-back + write-allocate(程式設計者假設後者)
stride-k miss 公式	每迭代平均 min(1, wordsize × k / B) 次 miss;stride-1 最佳
Memory mountain 兩軸	size → temporal locality(四條稜 = L1/L2/L3/Mem);stride → spatial locality(下坡)

Question 1 - SRAM vs DRAM [recall]

你的同事宣稱:「SRAM 與 DRAM 都是 volatile,所以兩者都需要週期性 refresh。」
請指出這句話對錯,並比較兩者的 cell 結構、相對速度、相對成本與典型用途。

查看答案

前半對、後半錯:兩者確實都是 volatile(斷電即失去資料),但只有 DRAM 需要 refresh。

SRAM:6 電晶體雙穩態 (bistable) 電路,供電期間值可無限期保持,不需 refresh、不怕干擾;速度約 1×、成本約 1,000×,用於 cache。
DRAM:1 電晶體 + 1 電容,漏電流使電荷在 10-100 ms 內流失,必須週期性讀出再寫回;速度約 10×、成本 1×,用於 main memory 與 frame buffer。

Question 2 - DRAM RAS/CAS 讀取 [recall]

Memory controller 要從一顆 conventional DRAM 讀出 supercell (2, 1)。
請依序說明兩步驟定址流程,並解釋 DRAM 為何採二維陣列組織、其代價為何。

查看答案

送 RAS (row access strobe) = 2:DRAM 把整個 row 2 複製到 internal row buffer。
送 CAS (column access strobe) = 1:從 row buffer 取出 supercell (2, 1) 的 w bits 送回 controller。

二維組織的目的:減少位址 pin 數(RAS/CAS 共用同一組 addr pins);代價是位址須分兩步傳送,增加存取時間。FPM DRAM 即利用 row buffer,讓同列連續存取只需補 CAS。

Question 3 - Nonvolatile Memory 分類 [recall]

PROM、EPROM、EEPROM 三種 ROM 的差異在於「可重寫次數」與「重寫機制」。
請分別說明,並解釋 firmware 一詞的意義與 flash memory 的定位。

查看答案

PROM:每 cell 有保險絲,高電流燒斷,只能燒錄 1 次。
EPROM:以紫外線透過石英窗清為全 0 再重寫,約 1,000 次。
EEPROM:電氣就地重寫、不需獨立裝置,約 10^5 次。

存於 ROM 裝置的程式稱 firmware(如 PC 的 BIOS)。Flash memory 是基於 EEPROM 的技術,為 SSD 的基礎。

Question 4 - 磁碟存取時間計算 [application]

一顆磁碟轉速 7,200 RPM、T_avg seek = 9 ms、平均每 track 有 400 個 sector。
請計算讀取一個 sector 的平均存取時間 T_access,並指出哪些成分主宰整體時間。

查看答案

T_avg rotation = 1/2 × (60/7,200) × 1,000 ≈ 4 ms
T_avg transfer = (60/7,200) × (1/400) × 1,000 ≈ 0.02 ms
T_access = 9 + 4 + 0.02 ≈ 13.02 ms

存取時間由 seek time 與 rotational latency 主宰,transfer 幾乎可忽略——存取 sector 的第一個 byte 最貴,其餘 bytes 幾乎免費;快速估算可用 2 × T_avg seek。

Question 5 - SSD 讀寫特性 [recall]

SSD 以 page 與 block 組織 flash memory。
請說明讀寫與 erase 的單位分別是什麼,以及隨機寫入比讀取慢的兩個原因。

查看答案

資料以 page 為單位讀寫;erase 以整個 block 為單位,page 必須等所屬 block 被 erase 後才能寫入。隨機寫慢的原因:

erase block 很慢(約 1 ms),比 page 存取高一個數量級以上;
若要修改已含資料的 page,同 block 中所有含有用資料的 pages 必須先複製到新的(已 erase)block。

FTL 以 wear-leveling 與寫入攤銷減輕成本,但隨機寫仍追不上讀取。

Question 6 - 區域性辨識 [recall]

以下函式循序加總向量:
int sumvec(int v[N]) {
    int i, sum = 0;
    for (i = 0; i < N; i++)
        sum += v[i];
    return sum;
}
請分別分析 sum 與 v[i] 各具有哪種 locality,並判斷整體區域性好壞。

查看答案

sum(scalar):每次迭代都被引用 → temporal locality 好;純量無 spatial locality 可言。
v[i]:stride-1 循序讀取 → spatial locality 好;每元素只讀一次 → temporal locality 差。

迴圈本體中每個變數至少具備一種好的區域性 → sumvec 整體區域性良好。判斷函式區域性的方法就是逐一檢視每個變數的引用模式。

Question 7 - 迴圈重排求 stride-1 [application]

三維陣列走訪(改編自 Practice 6.7):
int productarray3d(int a[N][N][N]) {
    int i, j, k, product = 1;
    /* 迴圈順序待定 */
    product *= a[j][k][i];
    return product;
}
C 為 row-major。請給出使空間區域性最佳的三層迴圈排列,並說明判斷原則。

查看答案

排成 j 最外、k 中間、i 最內。

原則:row-major 下最右邊的陣列索引必須由最內層迴圈變動最快,才能得到 stride-1(sequential)參照模式;索引是 a[j][k][i],故最內層應變動 i,依次往外是 k、j。stride 越大 spatial locality 越差。

Question 8 - Miss 三分類 [recall]

請為以下三種情境各標上正確的 cache miss 類型並說明成因:
(a) 剛開機、cache 全空,第一次存取任何資料必 miss;
(b) cache 容量明明裝得下,但交替存取 block 0 與 block 8(皆映到同一位置)每次都 miss;
(c) 迴圈的 working set 大於 cache 總容量。

查看答案

(a) Cold miss(compulsory miss):cache 是空的(cold cache),屬暫態,warmed up 後消失,且無法靠加大容量避免。
(b) Conflict miss:限制性 placement policy 使多個 block 映射到同一 cache block,互相踢來踢去(thrashing)。
(c) Capacity miss:working set 超過 cache 容量,cache 就是太小。

Question 9 - 快取參數計算 [application]

一個快取:m = 32 位元位址、C = 32 KB、B = 64 bytes、E = 8(8-way set associative)。
請求出 S、b、s、t,並說明 C 的計算是否包含 tag bits 與 valid bit。

查看答案

S = C / (E × B) = 32,768 / (8 × 64) = 64 個 set
b = log2(64) = 6;s = log2(64) = 6;t = m − (s + b) = 32 − 12 = 20

容量 C = S × E × B 不含 tag bits 與 valid bit 等 overhead,只計 data blocks。此組態即 Core i7 的 L1 cache。

Question 10 - Direct-mapped 位址判讀 [application]

Direct-mapped cache:(S, E, B, m) = (4, 1, 2, 4),初始所有 valid bit = 0。
CPU 依序讀取位址 0、1、13、8、0。請切割位址欄位,逐步判斷各次存取是 hit 或 miss,並說明第 5 次存取的 miss 屬於哪一類。

查看答案

4-bit 位址切成:1 bit offset(低)、2 bits set index(中)、1 bit tag(高)。

讀 0 → miss(set 0 valid=0,載入 block 0);2. 讀 1 → hit(同 block);3. 讀 13 → miss(set 2 無效);4. 讀 8 → miss(set 0 valid=1 但 tag 不符,block 4 取代 block 0);5. 讀 0 → miss——block 0 剛被驅逐,屬 conflict miss。

命中必須 valid=1 且 tag 相符;E=1 時替換 trivial(直接覆蓋)。

Question 11 - 寫入策略 [recall]

快取寫入有兩個獨立決策點:write hit 時與 write miss 時。
請說明 write-through / write-back 與 write-allocate / no-write-allocate 的作法、典型配對,以及程式設計者應假設哪種模型、為什麼。

查看答案

Write hit:write-through 立即寫到下一層(簡單但每寫必產生 bus traffic);write-back 延遲到 block 被驅逐時才寫回(需 dirty bit,大幅減少流量)。
Write miss:write-allocate 先載入 block 再更新;no-write-allocate 繞過快取直接寫下層。
典型配對:write-through + no-write-allocate;write-back + write-allocate。

程式設計者應假設 write-back + write-allocate:符合現代趨勢、與讀取的處理對稱,只需專注寫出局部性好的程式。

Question 12 - Fully Associative 與 TLB [recall]

某快取的位址欄位只有 tag 與 block offset,完全沒有 set index。
這是哪種快取組織?為何它只適合小型快取?請舉一個實際應用。

查看答案

Fully associative cache(E = C/B,整個快取只有單一 set),set selection 為 trivial,故不需 set index 位元。

line matching 必須平行比對所有 line 的 tag,電路又大又貴、難以做快 → 只適合小型快取。實例:虛擬記憶體系統中快取 page table entries 的 TLB。

Question 13 - Thrashing 分析與修復 [analysis]

快取:direct-mapped、C = 32 bytes、B = 16 bytes(2 sets)。float x[8] 從位址 0 起、float y[8] 緊接於位址 32 起連續放置:
float dotprod(float x[8], float y[8]) {
    float sum = 0.0;
    for (int i = 0; i < 8; i++)
        sum += x[i] * y[i];
    return sum;
}
此程式空間區域性良好,實測卻每次引用都 miss。請解釋原因、指出 miss 類型,並提出不改變演算法的修復方法。

查看答案

x 與 y 大小為 2 的冪次且相距恰為 C 的倍數,使每個 x[i] 與 y[i] 映射到同一 set:讀 x[0] miss 載入 x[0..3],接著讀 y[0] miss 又把它覆蓋,如此往復——這是 conflict miss 造成的 thrashing(容量足夠卻互相驅逐,可拖慢 2-3 倍)。

修復:在陣列尾端加 B bytes 的 padding(float x[8] 改 float x[12]),使 x[i] 與 y[i] 落在不同 set。這也說明「空間區域性好 → 命中率高」有例外。

Question 14 - 矩陣乘法迴圈順序 [analysis]

n×n double 矩陣乘法 C = AB 的三重迴圈有 6 種排列,總浮點運算量相同。假設 B = 32 bytes(裝 4 個 double)、n 大到一列塞不進 L1、區域變數放暫存器。
已知三等價類每迭代的統計:class AB (ijk/jik) 2 loads、1.25 misses;class AC (jki/kji) 3 memory ops、2.00 misses;class BC (kij/ikj) 3 memory ops、0.50 misses。
請排序三類的效能、指出哪個指標更能預測效能,並解釋大 n 時 class BC 效能為何不隨 n 惡化。

查看答案

效能:BC(0.50)> AB(1.25)> AC(2.00),最快比最慢快近 40 倍。

miss rate 比總記憶體存取次數更能預測效能:class BC 有 3 個 memory ops 仍大勝只有 2 loads 的 class AB。
class BC 內層迴圈中 B、C 都是 stride-1(各 0.25 miss),A[i][k] 放暫存器;class AC 中 A、C 都沿行 stride-n(各 1.0 miss)最糟。
大 n 時 BC 效能恆定:硬體 prefetching 認得 stride-1 循序模式且跟得上內層迴圈,即使工作集遠超所有 SRAM 快取。

Question 15 - Memory Mountain 結構 [recall]

Memory mountain 把 read throughput(n/s,MB/s)畫成 size 與 stride 的二維函數。
請說明兩個軸各對應哪種 locality、垂直 size 軸的四條稜線代表什麼,以及「時間區域性差時空間區域性仍能救援」的證據。

查看答案

size 軸 → temporal locality(工作集越小越好);stride 軸 → spatial locality(stride 越小越好)。
四條稜線 = 工作集恰好塞進 L1 / L2 / L3 / main memory 的區域;L1 峰頂 >14 GB/s 與 Mem 谷底 900 MB/s 相差超過一個數量級。
證據:即使工作集塞不進任何快取,Mem 稜線上最高點(stride-1)仍比最低點高 8 倍;每台機器的記憶體山獨一無二。

Pattern Summary (click to expand)

答題模式	要點
儲存技術比較題	抓「每 bit 電晶體數 / 是否 refresh / 速度 / 成本 / 用途」五欄對照;volatile ≠ 需 refresh
DRAM 定址題	一律先 RAS(整列進 row buffer)後 CAS;二維陣列 = 省 pin 換兩步定址
磁碟時間計算題	先算 T_avg rotation = 0.5 × 60/RPM,再加 seek 與 transfer;seek + rotation 主宰
SSD 特性題	讀寫單位 page、erase 單位 block;隨機寫慢 = erase 慢 + 搬移有用 pages
區域性判斷題	逐變數分析:scalar 看 temporal、陣列看 stride;最右索引放最內層迴圈
快取參數題	S = C/(E×B);位址由低到高切 b、s、t;C 不含 tag/valid overhead
Hit/miss 模擬題	命中 = valid=1 且 tag 符;valid=1 但 tag 不符仍是 miss 並觸發替換
Miss 分類題	空 cache → cold;裝得下卻互逐 → conflict;working set 太大 → capacity
Thrashing 題	2 的冪次陣列交替存取 → 同 set 互逐;解法加 B bytes padding
寫入策略題	記兩組配對;程式設計者假設 write-back + write-allocate
效能預測題	看 miss rate 而非 memory ops 總數;stride-1 + prefetch 硬體是勝負關鍵

Related Concepts

Question 1 - SRAM vs DRAM [recall]

Question 2 - DRAM RAS/CAS 讀取 [recall]

Question 3 - Nonvolatile Memory 分類 [recall]

Question 4 - 磁碟存取時間計算 [application]

Question 5 - SSD 讀寫特性 [recall]

Question 6 - 區域性辨識 [recall]

Question 7 - 迴圈重排求 stride-1 [application]

Question 8 - Miss 三分類 [recall]

Question 9 - 快取參數計算 [application]

Question 10 - Direct-mapped 位址判讀 [application]

Question 11 - 寫入策略 [recall]

Question 12 - Fully Associative 與 TLB [recall]

Question 13 - Thrashing 分析與修復 [analysis]

Question 14 - 矩陣乘法迴圈順序 [analysis]

Question 15 - Memory Mountain 結構 [recall]