餵飽處理器：快取與記憶體階層

處理器一直輸掉的那場賽跑

想像一位大廚能在一秒內完成切、煎、擺盤——但唯一的食材庫是一座要走十分鐘才到的倉庫。她的刀工再快也沒用，整個班次都耗在走路上。這正是現代 CPU 的處境。核心的運算單元每奈秒能完成好幾道指令，但跑一趟主記憶體取一個運算元卻要花 60 到 120 奈秒。在 DRAM 回答一次的時間裡，核心其實能執行上百道指令。這頭巨獸在等食物時，正餓著肚子。

這就是[[memory-wall|記憶體高牆]]，它源自一個簡單的分歧。數十年來處理器時脈陡升——部分要歸功於 Dennard 縮放，它讓每顆變小的電晶體能在相同功率密度下切換得更快。相對地，DRAM 是繞著一顆微小電容打造的，必須充電再感測，它的原始存取延遲在三十年間幾乎沒有進步。於是兩條曲線拉開了距離。CPU 快了約一千倍，DRAM 延遲卻大概只進步十倍。這道差距就是高牆。

階梯為何有效：局部性

如果記憶體存取真的是完全隨機——每一刻取到任何一個位元組的機率都相等——那任何花招都救不了你，你幾乎每次都得付 DRAM 的代價。救我們的，是關於真實程式的一條深刻經驗法則，叫做局部性，而它有兩種風味。

時間局部性——如果你現在碰了某個位址，很可能不久後又會碰它。迴圈計數器、堆疊頂端、一張熱門的查表：程式會一而再、再而三地回到同一小撮位置。
空間局部性——如果你碰了某個位址，很可能不久後會碰到它的鄰居。走訪一個陣列、依序執行指令、逐欄讀取一個結構：存取會聚集在相鄰的位址上。

局部性正是讓記憶體階層划得來的原因。我們蓋出一座儲存體的階梯，每一階都比上一階更大也更慢。最頂端的幾階小得可憐卻快得驚人；最底層則龐大而緩慢。我們把剛用過、以及即將要用的資料留在頂端附近。靠著時間局部性，剛用過的資料在我們再次需要時還待在上面；靠著空間局部性，我們以*區塊*為單位取資料（一次抓整條 64 位元組的快取列），所以便宜地抓一個位元組，就順手把它的鄰居都先載好了。

Level        Typical size     Latency (cycles)   Made from
-----        ------------     ----------------   ---------
Registers    ~ 1 KB total     0                  flip-flops in datapath
L1 cache     32-64 KB         ~4                 fast 6T SRAM, split I/D
L2 cache     256 KB-2 MB      ~12-15             SRAM, per-core
L3 cache     8-64 MB          ~40                SRAM, shared by all cores
Main memory  8-128 GB         ~200-400           DRAM (1T1C cells), off-chip
SSD / NVMe   0.5-8 TB         ~ 100,000+         flash, non-volatile

現代桌機／伺服器核心的代表性階層。往下每一階大約慢 3 到 10 倍、大約 10 倍。L1 用 [[ic-sram-bitcell|SRAM 位元單元]]；主記憶體用 [[ic-dram-cell|DRAM 單元]]。

實際算一遍：命中、未命中，與步幅的代價

讓數字具體一點。一條快取列是傳輸的單位——比方說 64 位元組，能裝下 16 個四位元組的整數。當核心要求某個位址時，快取會檢查包含該位址的那條列是否已經在裡頭。若在，就是命中（快）；若不在，就是未命中——快取會從下一階整條 64 位元組地取回，並付出代價。

// Sum a 1,000,000-element int array (4 bytes each, 64-byte lines)
// => 16 ints per line.
long sum = 0;
for (int i = 0; i < N; i++) sum += a[i];

Access pattern, sequential (stride 1):
  a[0]  MISS  -> fetch line, brings a[0..15]
  a[1]  hit   a[2]  hit   ...   a[15]  hit
  a[16] MISS  -> fetch next line, brings a[16..31]
  ...
  => 1 miss per 16 accesses  ->  miss rate = 1/16 = 6.25%

Effective access time (AMAT):
  AMAT = hit_time + miss_rate * miss_penalty
       = 4 cyc  + 0.0625 * 200 cyc
       = 4 + 12.5  =  16.5 cycles  (average per element)

依序存取把一次昂貴的未命中攤成 16 次便宜的命中——這就是空間局部性的實戰。平均記憶體存取時間（AMAT）公式，是你日後做每一個快取決策時都會用上的透鏡。

現在來破壞局部性。假設你走訪同一個陣列，但以步幅 16——碰 `a[0]、a[16]、a[32]…`——也許是因為你正在讀一個以列為主儲存的矩陣中的某一行。這下子*每一次*存取都落在一條全新的列上，於是每次都未命中：

Stride-16 access:
  a[0]  MISS   a[16] MISS   a[32] MISS  ...  every one a miss
  => miss rate ~ 100%
  AMAT = 4 + 1.00 * 200 = 204 cycles per element

  Slowdown vs. sequential:  204 / 16.5  ~=  12x  SLOWER

Same instructions. Same arithmetic. Same data.
Only the *order of access* changed.

一模一樣的迴圈，只因為存取模式打敗了空間局部性，就慢了約 12 倍。這正是為什麼資料佈局（列主序對行主序、結構陣列對陣列結構）能主宰真實效能。

快取如何決定東西放哪：關聯度

快取遠比記憶體小，所以許多記憶體位址必須爭奪同一批儲存格。一個位址*如何*對應到一個格子，就是關聯度的問題，這是一個經典的「速度對彈性」取捨。可以把它想成衣帽間的寄物。

直接對映——每件外套都有一個依編號指定的唯一掛鉤。查找快得不得了（只看一個地方），但兩件被分到同一個掛鉤的熱門外套，即使其他衣架都空著，也會不斷把對方擠走。這就是*衝突未命中*。
全關聯——任何外套都能掛在任何掛鉤上。零衝突未命中、完美彈性——但要找一件外套，你得平行檢查*每一個*掛鉤，功耗與面積成本高昂。只有極小的結構（如 TLB）才負擔得起。
組關聯——甜蜜點。衣架分成許多小組（比方每組 8 個掛鉤）；外套的編號決定它的組，然後它可以用該組裡的*任何一個*掛鉤。一個「8 路組關聯」快取每次查找檢查 8 個候選。真實的 L1／L2／L3 快取就活在這裡，通常是 4 路、8 路或 16 路。

當一組滿了、又來一條新列時，快取必須趕走某人——這就是替換策略。直覺的選擇是 LRU（最近最少使用）：踢掉最久沒被碰過的那條，賭的是時間局部性。真正的 LRU 在高關聯度下追蹤成本很高，所以真實設計用便宜的近似（偽 LRU 樹、再參照預測）。但原則不變：趕走最不可能很快再被需要的那條列。

Address breakdown for a 32 KB, 8-way, 64-byte-line L1 (32-bit addr):

  line size  = 64 B            -> offset = log2(64)  = 6 bits
  num lines  = 32768 / 64 = 512
  num sets   = 512 / 8 (ways) = 64
                               -> index  = log2(64)  = 6 bits
  tag        = 32 - 6 - 6                = 20 bits

  +---------------------+--------+--------+
  |        TAG (20)      | INDEX  | OFFSET |
  |                     |  (6)   |  (6)   |
  +---------------------+--------+--------+

  Lookup: INDEX picks 1 of 64 sets; compare TAG against all
  8 ways in parallel; OFFSET picks the byte within the line.

一個位址如何被切開以找到一條列。索引選出一組；該組所有路的標籤同時比對；偏移選出列中的位元組。這種「平行比對」正是為什麼更高的關聯度要付出更多功耗與面積。

不只是延遲，還有頻寬——以及 HBM

快取對付的是延遲：它把等待任一單一數值的漫長時間藏了起來。但還有第二道牆：頻寬——你每秒實際能灌進多少位元組。當一個工作負載的工作集大到根本塞不進快取（想想擁有數十億權重的神經網路，或一張溢出 DRAM 的圖），快取就幫不上忙，機器只能不停地串流資料。這時的瓶頸不再是「一趟要多久」，而是「公路有多寬」。

對付頻寬的經典招數是又寬又快的介面——但電路板上一顆普通的 DRAM 晶片接腳數量有限，而且讓訊號橫越數公分的板子既耗電又限速。現代的解答是 [[high-bandwidth-memory|高頻寬記憶體（HBM）]]：把好幾片 DRAM 晶粒垂直堆疊，用數千條垂直導線（矽穿孔，TSV）連接，再把整疊放在矽中介層上、離處理器僅*數毫米*之遙。你得到的不是 64 位元寬的匯流排，而是每疊 1024 位元寬的介面，時脈不高卻能每秒搬運數 TB。

這就是貫穿本軌其餘篇章的關鍵句。一旦運算變得便宜又充裕——一片晶粒上有數千個乘法單元——稀缺的資源就變成了*把資料搬到它們面前*。正是這個體悟，解釋了為什麼脈動陣列要設計成讓每一個載入的數值在多次運算中被重複使用、為什麼AI 加速器的評等看記憶體頻寬不亞於看 FLOPS，以及為什麼架構師如今以*每搬一位元組耗多少能量*來衡量設計，而不只是每秒幾次運算。記憶體階層不是處理器的註腳——它正越來越成為處理器設計的*本體*。

把它兜起來：管線遇上階層

回想上一階的指令管線：一道穩定的指令流經過擷取、解碼、執行、記憶體、寫回。一旦某次載入未命中、管線得停頓 200 個週期等 DRAM，那「每週期一道指令」的吞吐幻覺就瞬間崩潰。快取與記憶體階層之所以存在，就是要讓這種停頓變得罕見——把管線餵得夠快，好讓執行單元保持忙碌。

現代核心更進一步對抗高牆：預取器觀察你的存取模式，在你開口前就先把下一條列取來；亂序執行讓核心在一次載入卡住等待時，先去跑後面互不相依的指令；多筆未決未命中讓好幾趟 DRAM 行程重疊，使它們的延遲彼此遮掩。每一招其實都在說同一件事：絕不讓巨獸閒坐著等記憶體。