Learning Objectives
- 說出記憶體階層各層（暫存器、快取、主記憶體、儲存裝置）在速度、容量與成本上的取捨
- 說明快取命中、未命中與命中率，並估算平均存取時間
- 比較直接對映、集合關聯與全關聯快取，判斷一串存取的命中與未命中
- 用時間區域性與空間區域性解釋為什麼快取有效，以及走訪陣列的順序為什麼會影響速度
這一課要回答的問題
CPU 每秒可以做數十億次運算，但它要的資料放在記憶體裡。如果每做一次加法都要等主記憶體送資料過來， CPU 大部分時間都在空等。
你可能也有這些經驗：
- 同一個程式，第二次打開比第一次快
- 同樣是處理一張大表格，換一種走訪順序，速度差好幾倍
- 規格表上寫著「L2 快取」「L3 快取」，卻不知道它們是做什麼的
這一課要回答：電腦怎麼讓「又快又大」的記憶體看起來存在？ 答案是記憶體階層（memory hierarchy）與快取（cache）。
記憶體階層：越快的越小、越貴
沒有一種記憶體同時又快、又大、又便宜，所以電腦把幾種記憶體疊成一層一層：
| 層級 | 在哪裡 | 用什麼做 | 容量（大約的數量級，示意） | 存取時間（大約的數量級，示意） |
|---|---|---|---|---|
| 暫存器（register） | CPU 裡面 | 正反器 | 幾十到幾百個，每個 64 位元 | 不到 1 奈秒 |
| L1、L2、L3 快取 | CPU 晶片上 | SRAM | 幾十 KB 到幾十 MB | 約 1 到數十奈秒 |
| 主記憶體 | 主機板上的記憶體模組 | DRAM | 數 GB 到數十 GB | 約數十到一百奈秒 |
| 固態硬碟（SSD） | 儲存裝置 | 快閃記憶體 | 數百 GB 到數 TB | 約數十到數百微秒 |
| 傳統硬碟（HDD） | 儲存裝置 | 磁性碟片 | 數 TB | 約數毫秒 |
1 毫秒＝1000 微秒＝1,000,000 奈秒。從快取到硬碟，速度差了大約一百萬倍。
往下走的規律：速度越慢、容量越大、每個位元組越便宜。 另外，暫存器、快取與主記憶體是揮發性（volatile）的，斷電資料就消失；SSD 與硬碟是非揮發性的，關機後資料還在。
比喻：你寫報告時，正在看的那一頁攤在桌上（暫存器），常用的幾本書放在手邊的書架（快取）， 整個房間的書櫃放得更多但要起身去拿（主記憶體），找不到的再去圖書館借（硬碟）。 大部分時候你只需要桌上和書架上的東西，所以感覺很快。
SRAM 與 DRAM：SRAM 每個位元用好幾個電晶體保存，速度快、不需要更新，但佔面積、成本高，所以只做成容量小的快取； DRAM 每個位元只用一個電晶體加一個電容，密度高、便宜，但電容會漏電，必須定期「更新」（refresh），速度也比較慢，適合做容量大的主記憶體。
想一想：記憶體階層
關於記憶體階層，下面哪一個敘述正確？
突然停電再開機，下面哪一層原本的資料還在？
快取：先找手邊的
快取（cache）是放在 CPU 與主記憶體之間、容量小但很快的記憶體，存放「最近用過」的資料副本。CPU 要讀一個位址時：
- 先查快取。找到了叫命中（hit），很快就拿到。
- 找不到叫未命中（miss），要到主記憶體去拿，比較慢；拿回來時順便放一份進快取，下次就可能命中。
- 快取滿了，就要選一個舊的資料取代（replace）掉。
衡量快取好不好，看命中率：
命中率 = 命中次數 ÷ 存取次數
平均存取時間 = 命中時間 + 未命中率 × 未命中懲罰
假設命中只要 1 個時間單位、未命中要多花 100 個時間單位（示意值）：命中率 90% 時平均是 1 + 0.1 × 100 = 11；命中率 99% 時平均是 1 + 0.01 × 100 = 2。 命中率看起來只差 9%，平均速度卻差了 5 倍以上，所以快取的設計很在意命中率。
快取怎麼知道某一格放的是哪個位址？每一格除了資料，還記著一個標籤（tag），用來比對「這格放的是不是我要的那個」。 下面的程式模擬最簡單的一種快取：4 格，每個位址只能放在固定的一格。
逐步執行：直接對映快取的命中與未命中
串列 cache 代表快取的 4 格，'空' 表示這格還沒放東西。每個位址只能放在「位址除以 4 的餘數」那一格。注意位址 0 和 4 的餘數都是 0：它們會搶同一格。
三種對映方式
「一個位址可以放在快取的哪幾格」，叫做對映方式（mapping）：
| 對映方式 | 規則 | 找資料時要比對幾格 | 缺點 |
|---|---|---|---|
| 直接對映（direct mapped） | 每個位址只能放在固定的一格（位址 ÷ 格數的餘數） | 1 格，最簡單、最快 | 兩個位址搶同一格時，會一直互相趕走 |
| 集合關聯（set associative） | 快取分成好幾組，每組有 2、4、8…格；位址決定放哪一組，組內任選一格 | 組內那幾格 | 介於兩者之間 |
| 全關聯（fully associative） | 任何位址可以放在任何一格 | 全部的格子 | 每次都要同時比對全部格子的標籤，硬體貴、耗電 |
格子都滿了要取代誰？常見的做法是 LRU（Least Recently Used）：取代最久沒用到的那一格，因為最近用過的很可能馬上又會用到。
真實的 CPU 快取多半是集合關聯（例如每組 8 格或 16 格）：比直接對映少很多衝突，又不像全關聯那麼耗費硬體。
算一算：命中幾次
直接對映、4 格的快取，一開始是空的，依序存取位址 2 6 2 6，一共命中幾次？
2 路集合關聯、共 4 格（2 組，每組 2 格），未命中時取代組內最久沒用到的（LRU）。一開始是空的，依序存取 1 3 1 3 5 1，一共命中幾次？
命中時間 1 個單位、未命中懲罰 100 個單位、命中率 90%，平均存取時間大約是幾個單位？
區域性：快取為什麼有效
快取只有主記憶體的一小部分，卻常常有很高的命中率，因為程式存取資料有規律，叫做區域性（locality）：
- 時間區域性（temporal locality）：剛用過的資料，很快會再用到。例如迴圈裡每一圈都會讀寫的累加變數、迴圈本身的指令。
- 空間區域性（spatial locality）：用到一個位址，附近的位址很快也會用到。例如依序讀陣列的元素、依序執行的指令。
為了利用空間區域性，快取每次從主記憶體搬的不是一個字組，而是一整個區塊（block，也叫快取線 cache line）， 包含相鄰的好幾個字組。讀第一個元素時未命中，但同一個區塊裡的下幾個元素就都命中了。
陣列的走訪順序會影響速度。 二維陣列在記憶體裡通常是逐列存放：先放 a[0][0] a[0][1] a[0][2] a[0][3]，再放 a[1][0]…。
# 逐列走訪：依序讀相鄰的位址，空間區域性好
for i in range(4):
for j in range(4):
total = total + a[i][j]
# 逐行走訪：每次跳一整列，快取小時，載入的區塊還沒用完就被趕走
for j in range(4):
for i in range(4):
total = total + a[i][j]
兩段程式算出的結果一樣，存取次數也一樣，但命中率可以差很多。下面的模擬器用一個 4 × 4 的陣列和只有 2 格的快取，讓你親眼看到差別。
想一想：區域性
二維陣列 a 在記憶體中逐列存放（a[0][0]、a[0][1]… 相鄰）。要把每個元素加總，哪一種迴圈通常比較快？
同一個程式第二次打開通常比第一次快，最主要是利用了什麼？
重點整理
- 記憶體階層：暫存器 → 快取（SRAM）→ 主記憶體（DRAM）→ SSD → 硬碟；越往下越慢、越大、每個位元組越便宜。前三層斷電就消失，儲存裝置不會。
- 快取存放最近用過的資料副本；找到叫命中，找不到叫未命中，要到下一層拿並放一份進快取。
- 平均存取時間＝命中時間＋未命中率 × 未命中懲罰；命中率差一點，平均速度就差很多。
- 對映方式：直接對映（每個位址固定一格，簡單但容易衝突）、集合關聯（組內任選）、全關聯（任一格，硬體最貴）；滿了常用 LRU 取代最久沒用的。
- 時間區域性（剛用過的很快再用）與空間區域性（附近的很快會用到）讓小小的快取也有高命中率；快取以區塊為單位搬資料，所以走訪陣列要順著存放的順序。
下一課：記憶體階層的最底層，儲存裝置。硬碟與 SSD 的運作原理為什麼讓它們速度差這麼多，CPU 又怎麼和這些輸入輸出裝置溝通。