加速、平行程式設計挑戰與相關介面 (Speedup, Challenges & Interfaces)
重點總覽 (Overview)
| 主題 | 核心要點 | 量化結論 |
|---|---|---|
| Speedup 定義 | system A 對 system B 的加速 = Time_B / Time_A |
200s / 10s = 20× |
| Amdahl's Law | 整體加速被「可平行化比例 p」限制 | p=30% → 上限僅 1.43×;p=99% → 50× |
| Memory bandwidth 牆 | 直接平行化常飽和 DRAM bandwidth | 通常只有 ~10×,須用 on-chip memory 減少 DRAM 存取 |
| Peach 比喻 | pit = sequential (CPU 強)、flesh = parallel (GPU 強) | pit 佔大量程式碼但只佔少量執行時間 |
| 4 大挑戰 | work efficiency、memory- vs compute-bound、input 特性、synchronization | 見下方各節 |
| 相關介面 | OpenMP (shared mem)、MPI (cluster)、OpenCL (跨廠商) | 概念與 CUDA 高度相似,CUDA 為最佳學習載具 |
加速的定義與 Amdahl's Law (Speedup & Amdahl's Law)
Speedup = 在 system B 執行某應用的時間 ÷ 在 system A 執行「同一」應用的時間。
- 例:應用在 A 跑 10s、在 B 跑 200s → A 對 B 加速 = 200/10 = 20×。
Amdahl's Law
可達成的加速取決於可平行化的時間比例 p。設 parallel 部分自身加速為 s:
| 可平行比例 p | parallel 部分加速 s | 整體加速 | 縮短時間 |
|---|---|---|---|
| 30% | 100× | 1/(0.7+0.003) = 1.42× |
29.7% |
| 30% | ∞ | 1/0.7 = 1.43× (硬上限) |
30% |
| 99% | 100× | 1/(0.01+0.0099) = 50× |
98% |
| 99.9% | 充分調校 | >100× | — |
原始執行時間 (=1.0)
[ serial 0.7 ][ parallel 0.3 ]
│ parallel 部分加速 100×
▼
[ serial 0.7 ][p] ← serial 完全沒變 → 卡住整體加速
└────── 0.703 ──┘ 整體只有 1.42×
Important
重點:即使把 parallel 部分加速到「無限大」,serial 部分仍原封不動。所以要讓 massively parallel processor 真正發揮,應用程式絕大多數執行時間必須落在 parallel 部分(實務上 >99.9%)。
Warning
100× 的加速通常不是直接平行化就能拿到,而是在演算法改良 + 大量 optimization/tuning 之後,把 >99.9% 的工作搬進 parallel 部分才達成。
Memory Bandwidth 限制與 Peach 比喻 (Memory Bandwidth & the Peach Analogy)
除了 p 之外,資料讀寫 memory 的速度是另一個關鍵限制。
- 直接 (straightforward) 平行化往往飽和 DRAM bandwidth → 通常只剩 ~10× 加速。
- 解法:做各種 transformation,改用 GPU 的 on-chip memory(shared memory / cache)大幅減少對 DRAM 的存取次數。
- 但 on-chip memory 容量有限,需進一步優化才能繞過此限制(見 05-Memory-Architecture-And-Data-Locality/02-Tiling-and-Tiled-Matrix-Multiplication)。
Tip
加速比也反映「CPU 對該應用的適配度」。若 CPU 本身就跑得很好,GPU 反而難加速。應給 CPU 公平機會,讓 CPU/GPU 互補(heterogeneous computing),把 serial 部分留在 CPU。
Peach (桃子) 比喻 — Fig. 1.2
___________
/ peach 果肉 \ ← parallel 部分:易平行,GPU 強項
/ (flesh) \ CUDA 覆蓋大片;舊 GPGPU 只覆蓋一小塊
| ___________ |
| / pit /核 \ | ← serial 部分:極難平行,CPU 強項
| | sequential | | 佔「程式碼」很大,但只佔「執行時間」一小部分
| \___________/ |
\ /
\_______________/
| 部位 | 對應 | 平行化難度 | 適合處理器 |
|---|---|---|---|
| pit (核) | sequential 部分 | 極難(咬到核很痛) | CPU (low latency) |
| flesh (果肉) | data-parallel 部分 | 容易 | GPU (high throughput) |
- 舊 GPGPU 必須把運算偽裝成「畫 pixel」(OpenGL/Direct3D),只能覆蓋一小塊果肉。
- CUDA 提供 general-purpose 介面,覆蓋大片果肉。
平行程式設計的四大挑戰 (Challenges in Parallel Programming)
名言:「若不在乎效能,平行程式很簡單,一小時就能寫一個。但不在乎效能又何必寫平行程式?」
| # | 挑戰 | 問題描述 | 解法 / 章節 |
|---|---|---|---|
| 1 | Work efficiency | 部分平行演算法做的 work 比 sequential 多,大輸入時反而更慢 | prefix sum/scan 等 primitive;11-Prefix-Sum-Scan/01-Scan-Foundations-and-Kogge-Stone |
| 2 | Memory- vs compute-bound | 受 memory latency/throughput 限制 = memory-bound;受指令數/byte 限制 = compute-bound | memory optimization;Ch.5、Ch.6 |
| 3 | Input 資料特性 | 大小不規則、分布不均 → 各 thread 工作量不均 | regularize 分布、動態調整 thread 數 |
| 4 | Synchronization | embarrassingly parallel 之外需 thread 協作 → barrier/atomic 造成等待 overhead | 降低同步 overhead 的策略 (全書) |
1. Work efficiency
- 許多 parallel 演算法 work 與 sequential 相同;但有些做更多 work,大資料集時甚至更慢 —— 這特別致命,因為「快速處理大資料」正是平行化的主要動機。
- 數學 recurrence(遞迴關係) 的問題尤其棘手,平行化常需非直覺思考與冗餘計算 (redundant work)。
- 正式定義見 work efficiency,用 prefix sum 等 pattern 達到與 sequential 相同的 computational complexity。
2. Memory-bound vs Compute-bound
| 類型 | 受限於 | 衡量指標 |
|---|---|---|
| Memory-bound | memory access latency / throughput | bytes 搬移量 |
| Compute-bound | 每 byte 資料所做的指令數 | arithmetic intensity (OP/B) |
Warning
「memory-bound」不是指記憶體不夠大,而是頻寬/延遲成為瓶頸。提高 arithmetic intensity(每讀一個 byte 多做幾次運算)才是把 memory-bound 推向 compute-bound 的關鍵。
3. Input data characteristics
- 平行程式效能比 sequential 更敏感於輸入資料特性(資料大小不可預測、分布不均)。
- 不均的分布 → thread 工作量不均 (load imbalance) → 平行效率大降。
- 解法:regularize 資料分布、動態 refine thread 數量(見 sparse matrix / graph 章節)。
4. Synchronization
embarrassingly parallel: T0 T1 T2 T3 (各做各的,不需協作)
│ │ │ │
▼ ▼ ▼ ▼ 無 overhead
需協作: T0──┐ T1──┐ T2──┐ T3──┐
▼ ▼ ▼ ▼
┌──────── barrier ────────┐ ← thread 互等 = overhead
T0 T1 T2 T3
- Embarrassingly parallel:thread 幾乎不需協作。
- 需協作者:用 barrier 或 atomic operations 同步 → thread 互等而非做有用工作,造成 overhead。
- 詳見 09-Parallel-Histogram/01-Atomic-Operations-and-Basic-Histogram 與 04-Compute-Architecture-And-Scheduling/01-GPU-Architecture-and-Block-Scheduling。
相關平行程式設計介面 (Related Parallel Programming Interfaces)
| 介面 | 目標系統 | 機制 | 與 CUDA 關係 |
|---|---|---|---|
| OpenMP | shared-memory 多處理器 | compiler + runtime;directives(命令)與 pragmas(提示)標註 loop → 自動產生平行碼 |
抽象化高、performance portability;但仍需懂平行概念,CUDA 給予明確控制,適合學習 |
| MPI | 可擴展 cluster (>100,000 nodes) | nodes 不共享記憶體,一切靠 explicit message passing | 需 domain decomposition,porting 成本高;CUDA 在 node 內提供 shared memory → 常 MPI + CUDA 合用 |
| OpenCL | 跨廠商 (Apple/Intel/AMD/NVIDIA, 2009) | language extensions + runtime APIs(更依賴 API、較少語言擴充) | 概念與 CUDA 高度相似,CUDA programmer 幾乎無痛轉換 |
| CUDA | NVIDIA GPU (+ host CPU) | C/C++ 語言擴充 + runtime | 本書主軸,作為學習載具 |
重點細節
OpenMP
用 #pragma 標註 loop,compiler 自動平行化 → 跨廠商/跨世代的 performance portability。原為 CPU 設計,已擴充支援 GPU。但 compiler 仍在演進,許多情況仍需 CUDA-style 介面補足。
MPI
Cluster 節點間無共享記憶體,須手動 domain decomposition + MPI_Send/MPI_Recv。現代 HPC cluster 多為 heterogeneous CPU/GPU 節點 → 需 joint MPI/CUDA;多 GPU 可用 NCCL (NVIDIA Collective Communications Library)。見 20-Heterogeneous-Computing-Cluster/01-MPI-Cluster-Background-and-Basics。
OpenCL 的 portability
OpenCL 程式可不修改就正確執行於任何支援的處理器(functional portability),但要達高效能通常仍需針對新處理器修改程式(非 performance portability)。
考試/面試重點 (Exam / Test Patterns)
| 情境 / 關鍵字 | 答案 / 技巧 |
|---|---|
| 「Speedup 怎麼算」 | Time_old / Time_new;A 對 B = T_B / T_A |
| 「p=30%,parallel 加速無限大,整體加速?」 | 1/(1-0.3) = 1.43×(Amdahl 硬上限) |
| 「p=99%,parallel 加速 100×」 | 1/(0.01+0.0099) ≈ 50× |
| 「為何只拿到 ~10× 加速?」 | 飽和 DRAM memory bandwidth → 用 on-chip memory 減少 DRAM 存取 |
| 「Amdahl's Law 啟示」 | serial 部分不變 → 必須讓 >99.9% 執行時間落在 parallel 部分 |
| 「memory-bound vs compute-bound」 | memory-bound 受頻寬/延遲;compute-bound 受指令/byte (arithmetic intensity OP/B) |
| 「parallel 演算法可能更慢」 | work efficiency 問題:做了更多/冗餘 work,大輸入時更慢 |
| 「load imbalance 來源」 | input 資料大小不規則、分布不均 → 各 thread 工作量不均 |
| 「embarrassingly parallel」 | thread 幾乎不需協作,無 synchronization overhead |
| 「同步機制」 | barrier、atomic operations;代價是 thread 互等 |
| 「peach pit / flesh」 | pit=sequential(CPU)、flesh=parallel(GPU);舊 GPGPU 只覆蓋小塊果肉 |
| 「OpenMP vs CUDA」 | OpenMP 用 directive/pragma 自動化、portability 高;CUDA 明確控制、學習載具 |
| 「MPI 特性」 | 節點不共享記憶體、靠 message passing、需 domain decomposition |
| 「OpenCL 特性」 | 跨廠商標準、依賴 API、與 CUDA 高度相似、functional 但非 performance portable |
Related Notes
- 01-Introduction/01-Heterogeneous-Parallel-Computing-and-the-Demand-for-Speed
- 01-Introduction/03-Overarching-Goals-and-Book-Organization
- 19-Parallel-Programming-And-Computational-Thinking/01-Goals-of-Parallel-Computing-and-Amdahls-Law
- 11-Prefix-Sum-Scan/02-Work-Efficient-Scan-Brent-Kung-and-Coarsening
- 20-Heterogeneous-Computing-Cluster/01-MPI-Cluster-Background-and-Basics
- 06-Performance-Considerations/04-Optimization-Checklist-and-Bottlenecks