跳轉到

1.1 Amdahl 定律與效能定量分析#

學習目標#

讀完本節後，你應當能夠：

  1. 推導並正確使用 Amdahl 定律 \(S=\frac{1}{(1-p)+p/n}\) ，說明其對平行化上限的含義。
  2. 說明 Gustafson 修正的動機、假設與適用情境，並能對照兩者的差異。
  3. 運用 Little's Law 分析流水線、多核心與儲存系統的吞吐量與延遲關係。
  4. 對實際工作負載執行定量效能分析，辨識「可加速比例」的量測陷阱。

1.1.1 為什麼需要定量分析#

計算機結構是一門「以定量原則驅動設計」的學科。Hennessy 與 Patterson 在《計算機結構：定量研究方法》中反覆強調三條定量原則：注意成本的佔比（make the common case fast）、Amdahl 定律、以及 ** locality 原則**。其中 Amdahl 定律之所以位居核心，是因為它是所有「區域最佳化」與「整體加速」之間的仲裁者：無論你把某個子系統最佳化得多麼漂亮，它對整體效能的貢獻都被「該子系統佔整體執行時間的比例」封頂。

研究生層級的效能分析必須回答三個問題：(a) 加速比的上限在哪裡？(b) 該上限由什麼參數決定？(c) 這些參數在真實系統中如何量測、又有哪些陷阱？本節依序處理這三個問題。

1.1.2 Amdahl 定律的推導與直覺#

設一個程式的總執行時間為 \(T\) ，其中比例 \(p\) 的部分可以被加速 \(n\) 倍（例如放到 \(n\) 個處理器上平行執行），其餘 \((1-p)\) 的部分完全無法加速（序列部分）。則加速後的執行時間為：

\[ T_{new} = (1-p)T + \frac{p}{n}T \]

因此整體加速比為：

\[ S(n) = \frac{T}{T_{new}} = \frac{1}{(1-p) + p/n} \]

這條公式有三個關鍵推論：

  1. 序列部分主導上限：當 \(n \to \infty\) ， \(S \to \frac{1}{1-p}\) 。若程式有 10% 的序列碼（ \(p=0.9\) ），無論用多少處理器，加速比都不會超過 10 倍。
  2. 邊際報酬遞減： \(S(n)\) 對 \(n\) 的增益隨 \(n\) 增大而快速衰減。當 \(p=0.95\) 、 \(n=16\) 時 \(S \approx 11.4\) ；把 \(n\) 提升到 1024 也只有 \(S \approx 19.1\) ——多花 64 倍硬體只換到不到 1.7 倍。
  3. 適用範圍遠大於平行化：Amdahl 定律本質上是「整體 = 各部分時間之和」的機率加權。它同樣適用於：把 5% 的時間用更好的記憶體加速 2 倍（整體只快 \(2.4\%\) ）、硬體頻率提升對非 CPU-bound 程式的影響等等。任何「只動一部分」的最佳化都受它約束。

實務計算例 1：該投資哪一個最佳化？#

某資料庫伺服器執行時間分布如下：CPU 計算 55%、磁碟 I/O 等待 30%、網路傳輸 15%。

  • 方案 A：換新 CPU，計算部分加速 1.4 倍， \(S_A = \frac{1}{0.45 + 0.55/1.4} \approx 1.25\) 。
  • 方案 B：換 SSD，I/O 部分加速 4 倍， \(S_B = \frac{1}{0.70 + 0.30/4} \approx 1.32\) 。
  • 方案 C：上 4 路平行查詢，假設 80% 的時間（計算 + I/O）可攤平， \(S_C = \frac{1}{0.20 + 0.80/4} = 2.5\) 。

雖然 CPU 加速比 SSD 加速的「硬體規格差距」看起來差不多，但 Amdahl 定律告訴我們要看佔比 × 加速倍數，而不是只看加速倍數。

實務計算例 2：反推需要的平行度#

目標是整體加速 20 倍，已知序列部分佔 10%。代入公式：

\[ 20 = \frac{1}{0.1 + 0.9/n} \implies 0.1 + \frac{0.9}{n} = 0.05 \]

右邊已經小於序列項 0.1，方程無解。也就是說，在 10% 序列碼存在的前提下，20 倍加速在數學上不可能，任何工程投入都無法達成。這是 Amdahl 定律作為「可行性檢查」的典型用法：在專案啟動前先用它篩掉不可行的目標。

1.1.3 Little's Law：延遲、吞吐量與並行度#

另一條同等重要的定量工具是 Little's Law：

\[ L = \lambda \cdot W \]

其中 \(L\) 是系統中的平均並行數（concurrency，如流水線中的指令數、佇列中的請求數）， \(\lambda\) 是平均吞吐率， \(W\) 是平均停留在系統中的時間（延遲）。此定律在穩態下恆成立，與到達分布無關。

它把「吞吐量導向」與「延遲導向」兩種設計觀點連接起來：

  • 流水線：五級流水線若每級一拍（ \(W = 5\) cycles），穩態下同時在管中有 5 條指令（ \(L = 5\) ），因此每拍可完成 1 條（ \(\lambda = L/W = 1\) IPC 上限）。深度 \(d\) 的超純量流水線可容納更多並行指令，但不能超過 \(L = \lambda W\) 所允許的穩態值——若依賴鏈不夠長、ILP 不足以維持 \(L\) ，流水線就會「空轉」，實際 \(L\) 下降， \(\lambda\) 隨之下降。
  • 儲存系統：一個 NVMe SSD 平均延遲 100 μs、系統內允許 32 條併發 I/O（ \(L=32\) ），則吞吐上限 \(\lambda = 32 / 100\mu s = 320{,}000\) IOPS。想在同樣延遲下提高 IOPS，唯一辦法是提高併發度（佇列深度、多執行緒、NVMe 多佇列）。這解釋了為什麼高階 SSD 的測試總是用高 queue depth 才能跑出標稱效能。
  • 服務容量規劃：Web 服務平均延遲 50 ms、要撐 10,000 QPS，需要 \(L = 10{,}000 \times 0.05 = 500\) 條併發處理單元。若單機只能提供 100 條執行緒的穩定並行，則至少需要 5 台機器。

Little's Law 與 Amdahl 定律的關係是互補的：Amdahl 約束「單一程式的加速上限」，Little's Law 則告訴你「要達到某吞吐目標需要多少並行資源」。在多核心伺服器設計中，兩者共同決定了「每核心效能 vs. 核心數」的取捨。

1.1.4 Gustafson 修正：換一種量測方式#

Amdahl 定律在 1967 年提出後，長期被用來論證「平行機不值得做」。1988 年，Sandia 國家實驗室的 Gustafson 等人在有 1024 個處理器的 nCUBE 上觀察到遠超 Amdahl 預測的加速比。他們指出問題出在量測基準的選擇：

Amdahl 假設問題規模固定（fixed-size model）：序列部分 \(B\) 的絕對時間不變。但實務上，拿到更多處理器的人會擴大問題（scaled-size model）：跑更大的網格、更多迭代、更精細的模擬。Gustafson 模型下，設 \(P\) 個處理器上執行時間為 1，其中平行部分佔 \((1-B)\) 、序列部分佔 \(B\) 。若只有單處理器，平行部分要花 \(P(1-B)\) 的時間，故

\[ S_{scaled} = \frac{B + P(1-B)}{1} = P - B(P-1) = P - B \cdot (P-1) \]

當 \(B\) 固定， \(S_{scaled}\) 對 \(P\) 近似線性成長。若 \(B = 0.05\) 、 \(P = 1024\) ， \(S_{scaled} \approx 973.5\) ，而非 Amdahl 模型下的 \(\frac{1}{0.95} \approx 1.05\) ——差距是天壤之別。

兩者的差異不在數學，而在什麼被視為「成功」：

Amdahl 模型 Gustafson 模型
問題規模 固定（快一點點就好） 隨 \(P\) 擴大（求更精確/更大的解）
序列項 不變的絕對時間 \(1-p\) 不變的時間佔比 \(B\)
加速比上限 \(\frac{1}{1-p}\) （飽和） 線性成長 \(P - B(P-1)\)
典型場景 批次編譯、互動程式、即時系統 科學模擬、AI 訓練、巨量資料

研究生必須理解的是：Gustafson 並未推翻 Amdahl。如果你的工作負載真的不隨資源擴大（例如每天固定量的報表計算），Amdahl 的悲觀上限就是真的；反之，現代 AI 訓練正是 Gustafson 型的成功案例——模型與資料集規模隨 GPU 數量擴大，序列成分（通訊同步、資料載入）的佔比被控制在低水位。選擇哪個模型，取決於問題的可擴充性（scalability）本質，這也是效能規劃的第一個決策點。

1.1.5 「可加速比例」的量測陷阱#

公式中的 \(p\) 從哪裡來？實務上有幾個陷阱：

  1. ** \(p\) 隨 \(n\) 而變**：許多「序列部分」其實是通訊與同步開銷，處理器越多開銷越大（ \(p\) 隨 \(n\) 下降甚至變成負成長）。正確的模型應寫成 \(S(n) = \frac{1}{(1-p(n)) + p(n)/n}\) ，這也是近似的可擴充性分析（isoefficiency）的起點。
  2. 量測的自我實現：用 profiler 找 hotspot 時，profiler 的取樣開銷與編譯器最佳化互動可能改變 \(p\) 的估計。應採用統計取樣式（event-based sampling，如 Intel VTune、perf record）而非插樁式量測。
  3. 晶片上的 Amdahl：多核心晶片中，「序列部分」還包括共享資源（memory bandwidth、LLC、互連）上的排隊時間。20 核心 CPU 跑 20 個執行緒時，可能因記憶體頻寬飽和而每核心都變慢——這是 Amdahl 之外再加上的資源競爭效應，需結合下一節的 Roofline 模型分析。
  4. 加速比 vs. 效率： \(n=64\) 、 \(S=32\) 看起來漂亮，但平行效率 \(E = S/n = 0.5\) 意味著一半的硬體在閒置或互踩。報告結果時應同時給出 \(S\) 與 \(E\) 。

本章小結#

  • Amdahl 定律 \(S=\frac{1}{(1-p)+p/n}\) 以「佔比 × 加速倍數」的乘積視角，為任何區域最佳化設定整體上限： \(S_{max} = 1/(1-p)\) 。它是投資決策與可行性檢查的第一道關卡。
  • Little's Law \(L = \lambda W\) 連接延遲、吞吐與並行度，是流水線、儲存與服務容量規劃的普適工具。
  • Gustafson 修正把「問題規模固定」換成「時間預算固定、規模隨資源擴大」，得到線性加速模型；兩者是對不同工作負載本質的兩種正確描述，並不矛盾。
  • \(p\) 不是常數：同步開銷、資源競爭與量測方法都會使它隨系統規模變動，定量分析必須明確標示量測條件。

習題#

  1. （計算） 某程式 70% 的執行時間花在浮點運算。今以新浮點單元使其加速 3 倍，其餘部分不變。求整體加速比，以及理論上的最大可能加速比。
  2. （計算） 目標整體加速 5 倍。若序列部分佔 15%，需多少個處理器？若佔 25% 呢？並對第二種情況說明其工程含義。
  3. （計算，Little's Law） 某鍵值儲存單一連線平均延遲 800 μs（含網路 RTT）。系統允許最多 256 條併發連線，求理論最大吞吐。若實測僅 120,000 QPS，估計實際平均併發連線數。
  4. （計算，Gustafson） 在 \(P=512\) 個處理器上，序列部分佔執行時間的 \(B=0.04\) 。以 Gustafson 模型求加速比與平行效率 \(E\) ；再以 Amdahl 模型（假設相同的問題在單處理器上 \(p\) 亦為 0.96）求加速比，解釋兩者差距的來源。
  5. （分析） 你的同事宣稱「把 20% 的時間以 1000 倍 GPU 加速後，整體快了 5 倍」。請檢驗此宣稱在 Amdahl 模型下是否一致；若不一致，最可能的量測錯誤是什麼（提示：考慮 \(p\) 的估計與 GPU 啟動/資料搬移開銷）？