並行思維（二）：可伸縮性、Amdahl 定律與 Gustafson 定律深度解析

可伸縮性與加速比

加速比 = 串行執行時間 / 並行執行時間。2x 加速 = 並行耗時為串行一半。理想：雙核 2x、四核 4x。現實：多數應用進入多核時代**效能不升反降**。

Amdahl 定律：悲觀的上限

Gene Amdahl 發現：**優化部分對整體提升有上限**。

數學模型

程序可分為：可並行部分 P、串行部分 S = 1-P。N 處理器下加速比：

Speedup(N) = 1 / (S + P/N)

圖解演示

核心洞見

• **串行部分形成硬天花板**：加速比極限 = 1/S。上例 S=0.6 → 極限 1.67x
• **邊際效應遞減**：增加核心帶來的增益急劇下降
• 指導意義：**盡量縮小串行部分**，否則堆疊硬體無意義

Gustafson 定律：樂觀的擴展視角

John Gustafson (Sandia 國家實驗室) 指出：**問題規模會隨資源增長而增長**。

Amdahl 的三個不切實際假設

1. **最優串行算法受限於 CPU** — 忽略多核獨享 Cache 降低延遲的紅利
2. **串行算法是最優解** — 部分問題本質並行，並行實現步驟更少
3. **問題規模固定** — 現實中資源增 → 問題規模增 (更大數據集、更精細模擬、更高解析度)

圖解：問題規模隨並行度伸縮

核心洞見

• **串行部分佔比隨問題增大而稀釋**
• **可伸縮性 = 並行工作增長速度 > 串行開銷增長速度**
• 超算領域驗證：Gustafson 更貼近現實；但 Amdahl 時刻警惕「固定負載下的並行化極限」

串行演算法 vs 並行演算法

**最佳串行演算法 ≠ 最佳並行演算法**，反之亦然。

• 單核優化技巧 (分支預測、Cache 友好、指令級並行) 可能阻礙並行化
• 並行演算法常需犧牲單核效率換取擴展性 (如冗餘計算避免同步)
• **目標決定選擇**：固定負載求快 → Amdahl 視角；擴大問題規模 → Gustafson 視角

應對多核時代的唯一出路

放棄串行思維，開始並行思考。從需求分析、架構設計、演算法選型、資料結構、同步策略、測試驗證——**全鏈路並行化**。