異質平行運算與對運算速度的需求 練習題 (Practice - Heterogeneous Parallel Computing and the Demand for Speed)

CPU 是 latency-oriented:用大 last-level cache、複雜 branch prediction / execution control、少而大的低延遲 ALU,來降低單一 thread 的延遲。GPU 是 throughput-oriented:用大量小 ALU + 大量 memory channel + 小 cache,靠大量 threads 隱藏長 latency,最大化整體吞吐。差距來自這兩種根本不同的設計取捨 (Fig. 1.1)。

Multicore trajectory:維持序列程式的執行速度,用少而強的 out-of-order、multiple-issue、hyperthreading 核心(例:Intel 24-core server、ARM Ampere 128-core)。Many-thread trajectory:最大化平行應用的吞吐量,用大量簡單的 in-order pipeline(例:NVIDIA A100,數萬個 threads)。自 2003 年起 many-thread GPU 在 FP 效能上持續領先。

NVIDIA 於 2007 年推出 CUDA。GPGPU 時代運算必須透過 graphics API (OpenGL / Direct3D) 偽裝成「畫 pixel」的函式,應用種類受限、未普及。CUDA 不只是軟體改變 — NVIDIA 投入晶片面積 (silicon) 提供通用平行程式介面,程式不再經過 graphics interface,可直接用 C/C++ 並支援 CPU-GPU 聯合執行。

(1) Work efficiency — 有些平行演算法比 sequential 做更多 work,大輸入時反而更慢(recurrence 問題常需冗餘計算);(2) Memory-bound vs compute-bound — 執行受 memory 頻寬/延遲或受每 byte 指令數限制;(3) Input 資料特性 — 大小不規則、分布不均造成各 thread 工作量不均 (load imbalance);(4) Synchronization — barrier / atomic operations 造成 thread 互等的 overhead。

OpenMP:shared-memory 多處理器;用 directives(命令)與 pragmas(提示)標註 loop,compiler + runtime 自動產生平行碼(強調 performance portability)。MPI:不共享記憶體的 cluster(可達 >100,000 nodes);一切靠 explicit message passing,需手動 domain decomposition + MPI_Send/MPI_Recv。OpenCL:2009 年跨廠商標準,更依賴 API、較少語言擴充,概念與 CUDA 高度相似。

① High performance(教你寫高效能平行程式,需直覺式硬體理解才能推理效能);② Correctness & reliability(用簡單的 barrier synchronization、memory consistency、atomicity,使程式可除錯、可維護);③ Future scalability(讓更平行的未來硬體自動跑更快)。Future scalability 的關鍵是 regularize 與 localize 記憶體存取,降低 critical resource 消耗與更新資料結構的衝突 — 與高效能技術其實是同一套。

Amdahl 上限 = 1/(1-p) = 1/(1-0.30) = 1/0.70 ≈ 1.43×,最多只能縮短 30% 的執行時間。即使 parallel 部分加速 100×,整體也只有 1/(0.7 + 0.30/100) = 1/0.703 ≈ 1.42×。原因:serial 的 70% 完全沒變,卡死整體加速。

Speedup = T_B / T_A = 200 / 10 = 20×。當 p=99%、s=100:1/((1-0.99) + 0.99/100) = 1/(0.01 + 0.0099) ≈ 50×。對比 Q7 的 p=30%,凸顯 Amdahl 的啟示:必須讓絕大多數(實務上 >99.9%)執行時間落在 parallel 部分,massively parallel processor 才能真正發揮。

吞吐加倍:把 ALU 數量加倍 → 約 2× 面積、2× 功耗(線性)。延遲減半:需把電流加倍 → >2× 面積、4× 功耗(超線性,昂貴得多)。因為降低延遲遠比提高吞吐昂貴,GPU 選擇為大量 threads 的吞吐量做優化、容忍長 latency,把省下的面積與功耗用來放更多小 ALU 與 memory channel;CPU 則反向地花資源在低延遲。這正是兩種設計哲學分歧的量化根源。

直接平行化常飽和 DRAM memory bandwidth,使應用成為 memory-bound → 通常只剩 ~10×。突破方法:做資料搬移的 transformation,改用 GPU 的 on-chip memory(shared memory / cache)大幅減少對 DRAM 的存取次數,但 on-chip 容量有限需進一步優化(如 tiling)。Memory-bound 受 memory 頻寬/延遲限制(瓶頸是搬多少 bytes);compute-bound 受每 byte 資料所做的指令數限制(arithmetic intensity, OP/B)。提高 arithmetic intensity 是把 memory-bound 推向 compute-bound 的關鍵。