平行運算的目標與 Amdahl's Law
重點總覽 (Overview)
| 項目 | 內容 | 關鍵點 |
|---|---|---|
| 三大目標 | ① 用更少時間解同一問題 ② 在固定時間內解更大問題 ③ 在固定時間內得到更好的解 | 三者本質都源自 increased speed |
| 好的平行候選 | 大資料量、高複雜度、迭代多 | 工作量小的應用不值得平行化 |
| Amdahl's Law | application-level speedup 受 sequential portion 限制 | 即使平行段加速 100×,小的序列段仍會封頂 |
| 緩解手段 1 | Task-level parallelism(CUDA streams / multicore host) | 讓不值得細粒度平行的小任務彼此並行 |
| 緩解手段 2 | Hierarchical MPI-CUDA(階層式 data parallelism) | host 算小模組、device 算大模組,跨節點分配 |
| 教科書範例 | molecular dynamics:nonbonded force 佔 95% | 95% 部分加速 100×,整體只到 17×(無重疊)/20×(重疊) |
Important
本章的核心心法:平行化的「天花板」不是由你加速最猛的那段決定,而是由你**沒有平行化的那段(serial fraction)**決定。
平行運算的三大目標 (Three Goals of Parallel Computing)
以投資公司「投資組合風險分析」為例貫穿三個目標:
| 目標 | 情境 | 達成方式 |
|---|---|---|
| ① Less time(更快) | 序列電腦需 200 小時,但決策要求 4 小時內完成 | 對 現有模型 + 現有問題規模 提速 |
| ② Bigger problem(更大) | 增加持股數量,放大後序列分析會超出時間窗 | 對 現有模型 + 更大問題規模 提速 |
| ③ Better solution(更好) | 改用更精確的模型(考慮更多風險因子互動),序列版會超時 | 對 更複雜模型 + 現有問題規模 提速 |
Tip
三個目標可以組合:平行化也能同時對「更複雜模型 + 更大規模」提速。三者的共同本質都是 increased speed。
好的平行化候選應用特徵:大資料量、每次迭代計算量大、迭代次數多。反之,問題小或複雜度低的應用本來就跑得快,沒有提速動機。
多模組應用與 Amdahl's Law (Multi-Module Apps & Amdahl's Law)
真實應用通常由多個協同模組組成。以 molecular dynamics 為例,各模組工作量差異巨大:
┌─────────────────────────┐
│ Neighbor List │ (host)
└─────────────────────────┘
│
┌───────────────┴────────────────┐
▼ ▼
┌──────────────────────┐ ┌────────────────────────────┐
│ Vibrational & │ │ Nonbonded Force │
│ Rotational Forces │ │ (atom-atom 互動,計算量爆炸) │
│ 工作量小 → host │ │ 工作量大 → GPU device │
└──────────────────────┘ └────────────────────────────┘
│ │
└───────────────┬─────────────────┘
▼
┌──────────────────────────────────┐
│ Update atomic positions/velocities │ (host: 合併 host+device 力)
└──────────────────────────────────┘
│
▼ Next Time Step
程式設計者須逐一決定每個 pass 是否值得放上 GPU。範例中振動/旋轉力工作量不足以划算上 GPU,故留在 host;只有 nonbonded force 上 device。
量化:speedup 公式
平行化後的 application-level speedup:
= 可平行段佔原始序列執行時間的比例 = 該平行段獲得的加速倍數 - 當
時,上限 (完全由序列段封頂)
範例計算(nonbonded force 佔 95%、加速 100×)
| 情境 | 計算式 | 結果 |
|---|---|---|
| 無重疊(host 與 device 不重疊) | ≈ 17× | |
| 有重疊(平行段完全藏在 host 執行陰影下) | = 20× |
無重疊 timeline:
host(5%) ──► device(0.95%) ──► 總 = 5.95% → 17×
有重疊 timeline:
host(5%) ───────────────►
device ─► (0.95%, 藏在 host 內) 總 = 5.00% → 20×
Warning
Amdahl's Law 的核心啟示:即使序列段只有 5%,且平行段加速高達 100× 並完全被隱藏,整體仍只能到 20×。許多「不值得單獨平行化的小活動」累積起來會成為使用者實際看到的速度上限。
章 17 的 iterative MRI 也驗證此現象:CG 計算只佔原始執行時間約 1%,卻成為 speedup 的限制因素。
緩解序列段:Task-Level Parallelism
當某些小活動不值得細粒度大規模平行(fine-grained massive parallelism),但資料夠大時,仍可讓它們彼此並行:
| 手段 | 機制 | 章節 |
|---|---|---|
| Multicore host | 用主機多核同時跑多個小任務 | — |
| CUDA streams | 同時啟動多個小 kernel,各對應一個 task(task parallelism) | 20-Heterogeneous-Computing-Cluster/03-Overlapping-Computation-and-Communication |
Tip
Task-level parallelism 攻擊的是 Amdahl's Law 中那塊「序列尾巴」:把多個原本序列排隊的小模組改成彼此並行,等效降低
緩解序列段:階層式 MPI-CUDA (Hierarchical Parallelism)
另一條路是用階層式 data parallelism 把小模組也平行化。以 MPI 版 molecular dynamics 為例:
┌──────────── Networked Cluster ────────────┐
│ │
spatial grid │ Node 0 Node 1 Node N │
切成大塊分送 │ ┌───────┐ ┌───────┐ ┌───────┐ │
───────────► │ │ host │ vib/rot host │ ... │ host │ │ ← 多 CPU 平行算「小模組」
│ │ CPU │ │ CPU │ │ CPU │ │
│ ├───────┤ ├───────┤ ├───────┤ │
│ │ CUDA │ nonbonded │ ... │ CUDA │ │ ← 各 GPU 高倍率算「大模組」
│ │ device│ │ device│ │ device│ │
│ └───────┘ └───────┘ └───────┘ │
│ ↑ 跨節點交換邊界力 / 移動原子 ↑ │
└────────────────────────────────────────────┘
- 每個節點的 host CPU 負責自己那塊的 vibrational/rotational force → 利用多 CPU 為小模組取得 speedup。
- 每個節點的 CUDA device 以更高倍率算 nonbonded force。
- 節點間需交換資料:跨塊的力、移動越過邊界的原子。
Important
MPI 與 CUDA 是互補、階層式的:MPI 在節點間做粗粒度分配,CUDA 在節點內做細粒度平行,共同在大資料集上達到更高整體速度。詳見 20-Heterogeneous-Computing-Cluster/01-MPI-Cluster-Background-and-Basics。
平行程式設計的三步驟 (The Three Steps)
| 步驟 | 內容 | 對應章節 |
|---|---|---|
| 1. Algorithm selection | 在多個演算法間取捨(複雜度 / 平行度 / 通用性 / 精度) | 19-Parallel-Programming-And-Computational-Thinking/02-Algorithm-Selection-and-Tradeoffs |
| 2. Problem decomposition | 把問題拆成可安全並行的子問題(output- vs input-centric) | 19-Parallel-Programming-And-Computational-Thinking/03-Problem-Decomposition-Output-vs-Input-Centric |
| 3. Performance optimization & tuning | 前面各章的優化主軸(章 6 通論) | 06-Performance-Considerations/04-Optimization-Checklist-and-Bottlenecks |
本筆記屬於 step 0(動機與 Amdahl's Law);後兩步是接下來兩個 sibling notes 的主題。
考試/面試重點 (Exam / Test Patterns)
| 情境 / 關鍵字 | 答案 / 技巧 |
|---|---|
| 「為什麼要平行運算?」 | 三大目標:less time / bigger problem / better solution,本質都是 increased speed |
| 給 |
|
| speedup 理論上限 | |
| 「平行段加速 100×,為何整體只有 17×?」 | Amdahl's Law:序列 5% 部分無法平行化,封住上限 |
| 無重疊 vs 重疊的整體加速 | 無重疊 |
| 「小任務太多怎麼辦?」 | Task-level parallelism:CUDA streams 或 multicore host 讓小 kernel 並行 |
| 「大資料集 + 叢集」 | Hierarchical MPI-CUDA:MPI 分節點(粗)+ CUDA 節點內(細),host 算小模組 |
| 哪種應用值得平行化? | 大資料量、高計算複雜度、多迭代;小問題不值得 |
| 章 17 的 CG 例子 | CG 僅佔 ~1% 卻成 speedup 限制因素 → Amdahl's Law 實證 |
Related Notes
- 19-Parallel-Programming-And-Computational-Thinking/02-Algorithm-Selection-and-Tradeoffs
- 19-Parallel-Programming-And-Computational-Thinking/03-Problem-Decomposition-Output-vs-Input-Centric
- 19-Parallel-Programming-And-Computational-Thinking/04-Computational-Thinking-and-Parallelization-Approaches
- 01-Introduction/02-Speedup-Challenges-and-Related-Interfaces
- 20-Heterogeneous-Computing-Cluster/01-MPI-Cluster-Background-and-Basics
- 20-Heterogeneous-Computing-Cluster/03-Overlapping-Computation-and-Communication