平行程式設計與計算思維 練習題 (Practice - Parallel Programming and Computational Thinking)

三大目標:① Less time——用更少時間解同一問題(序列需 200 小時,但決策要求 4 小時內完成);② Bigger problem——固定時間內解更大問題(擴大持股數量後序列版會超時);③ Better solution——固定時間內得到更好的解(改用更精確、更複雜的模型)。三者本質都是 increased speed(分別作用在「現有模型+現有規模」「現有模型+更大規模」「更複雜模型+現有規模」),且可組合。好的平行候選具備:大資料量、每次迭代計算量大、迭代次數多。

① Definiteness(明確):每一步都精確陳述,沒有模糊空間;② Effective computability(可計算):每一步都能由電腦實際執行;③ Finiteness(會終止):保證會結束、不無限執行。這三性質是「是不是合法演算法」的門檻,與平行/序列無關;選哪個演算法上平行硬體則是另一層(四面向)的問題。

四面向:algorithmic complexity / work、parallelism exposed、generality、accuracy / numerical stability;通常無單一演算法在四者全勝,須為目標硬體挑最佳折衷。三大經典權衡:① 複雜度 vs 平行度 → Kogge-Stone vs Brent-Kung(Ch.11 Scan);② 一般性 vs 效率 → radix sort vs merge sort(Ch.13 Sorting);③ 複雜度 vs 準確度 → DCS vs cutoff summation(Ch.18 電位圖)。高複雜度可用 hybrid 或 thread coarsening 緩解。

屬於 一般性 (generality) vs 效率 (efficiency) 的權衡。Radix sort 是 noncomparison sort,複雜度可低於 merge sort 且高度適合平行化,但只能用於特定型別的 key(一般性低)。Merge sort 是 comparison-based,任何有良好定義比較運算子的 key 都能用(一般性高),但效率/平行度較不及 radix。選哪個取決於 key 型別與資料特性。

Output-centric:每個 thread 處理一個 output 元素,gather/collect 多個 input 的貢獻,結果累積在 private register;單一寫者 → 免 atomics,且多 thread 可共享 input(用 constant/shared memory 省 bandwidth)。Input-centric:每個 thread 處理一個 input 元素,scatter/distribute 影響到多個 output;多 thread 可能同時寫同一 output → 必須用 atomic operations 防 race condition,而 atomics 遠慢於 register 存取。故 GPU 通常偏好 output-centric (gather)。兩種分解結果相同,但效能可能天差地別。

① Task-level parallelism:某些小活動不值得「細粒度大規模平行」,但資料夠大時可讓它們彼此並行——用 multicore host 同時跑多個小任務,或用 CUDA streams 同時啟動多個小 kernel(各對應一個 task)。② Hierarchical MPI-CUDA:用階層式 data parallelism,MPI 把空間網格大塊分送到叢集各節點(粗粒度),每個節點的 host CPU 算小模組(如 vibrational/rotational force)、CUDA device 高倍率算大模組(nonbonded force),節點間再交換邊界資料。MPI 與 CUDA 互補、階層式地共同達到更高速度。

三大基礎技能:① Computer architecture(memory organization、caching & locality、bandwidth、SIMT/SPMD/SIMD、floating-point precision vs accuracy);② Programming interfaces & compilers(parallel execution models、memory 種類、synchronization、data layout、thread granularity transformation);③ Domain knowledge(problem formulation、hard vs soft constraints、numerical methods、numerical stability)。
SIMT/SPMD/SIMD 差異:SIMD = 硬體層級,一條指令操作多筆資料(vector lane);SIMT = GPU 執行模型,warp 內 thread 各有自己 PC/狀態但鎖步執行(容許 control divergence);SPMD = 程式層級,所有 thread/process 跑同一份程式但處理不同資料(含 MPI ranks)。

Good——「accelerate」legacy code:最基本是 recompile 換平台,可再用 optimized libraries/directives(CuBLAS、CuFFT、Thrust、MATLAB、OpenACC);不需 algorithm selection/decomposition/tuning,適合 domain scientists,立即見效但無平行洞見。Better——用平行技巧 rewrite 或從頭寫新 code,做 decomposition+optimization,適合 nondomain computer scientists;但缺 domain 知識,無法做有效的 algorithm selection。Best——holistic:三步驟全做,並 rethink numerical methods & algorithms(如 cutoff binning),需 CS+domain 跨領域,報酬最大、可能帶來 fundamental new discoveries。目標是讓科學「better, not just faster」。

公式 $\text{speedup}={\displaystyle \frac{1}{(1-p)+p/s}}$,此處 $p=0.95$、$s=100$。

• 無重疊:${\displaystyle \frac{1}{0.05+0.95/100}}={\displaystyle \frac{1}{0.05+0.0095}}={\displaystyle \frac{1}{0.0595}}\approx$ 17×。
• 有重疊(平行段完全隱藏):整體只剩序列段 → ${\displaystyle \frac{1}{0.05}}=$ 20×。
  啟示(Amdahl's Law):即使平行段加速高達 100× 並完全被隱藏,僅 5% 的序列段就把整體封在 20×。$s\to \mathrm{\infty }$ 時上限 $={\displaystyle \frac{1}{1-p}}=20\times$,由序列段決定天花板。Ch.17 的 CG 只佔 ~1% 卻成 speedup 限制,即同一現象。

atom-centric 的散佈 (scatter) 記憶體存取行為不利 GPU(多原子向外更新 grid),故改採 grid-centric (output-centric) 分解:每條 thread 算一個 grid point 的能量,用 gather 把鄰近原子貢獻累積到 register。① Bins:先把輸入原子依座標排序進固定容量的 bins(每個 bin 對應 grid 空間一個 box)。② Neighborhood:為每個 grid point 定義「所有可能對其能量有貢獻的原子所在的那些 bins」;執行時各 block 走訪自己的 neighborhood bins,block 內所有 thread 一起掃描原子但各自判斷是否落在 cutoff radius 內。③ Overflow list:bin 容量設得遠小於最大可能原子數,若某原子的 home bin 已滿就改放進 overflow list,kernel 結束後由 host 序列補算缺漏貢獻(解 load imbalance)。SmallBin-Overlap 把這段序列 overflow 處理與下一個 kernel 執行重疊,對 CPU-SSE 序列版達 17× 並維持大體積可擴充性。

SpMV/COO 採 input-centric 分解:每條 thread 對應輸入矩陣的一個 nonzero,並用 atomicAdd 更新 output vector 對應元素(scatter access)。雖然付出 atomics 代價,但相較 output-centric kernel 它能抽取更多平行度(nonzero 數通常遠多於 output 元素)且load balance 更好(每 thread 處理一個 nonzero,工作量均勻)。這說明「output-centric 永遠較好」是錯誤簡化:當平行度與負載均衡更關鍵時,input-centric 反而勝出。最佳分解最終取決於 input dataset;Hybrid ELL-COO 即是混合兩種分解的例子。

不一定。這正是 複雜度 (work) vs 平行度 (parallelism) 的經典權衡:

• Brent-Kung:複雜度低、做同一計算所需 operations 少(O(N),~2N−3)→ work-efficient;但兩階段(reduction tree + reverse distribution tree)使步數較多(~2 倍 log N)。
• Kogge-Stone:暴露更多平行度,能在更少 iteration(log₂N 步)完成;但 work 達 O(N log N),做了較多冗餘運算。
  誰勝出取決於目標硬體:執行單元充足(P 大、延遲主導)時 Kogge-Stone 步數少而較快;執行資源有限(P 小、總運算量主導)時 Brent-Kung work 少而較快。緩解高複雜度的手段:用 hybrid(結合兩個平行演算法)或把平行演算法與低複雜度的序列演算法經由 thread coarsening 結合——這也呼應「best」approach 在演算法層級重新設計的精神。

對 histogram,output-centric(讓每條 thread 負責一個 output bin、去搜尋哪些 input 屬於它)看似能用 gather 免除 atomics,但有三大致命缺點:① 平行度低——output bin 數通常遠小於 input 數,可用 thread 大減;② 不 work-efficient——thread 無法在不檢視所有 input 的情況下知道哪些 input 屬於自己的 bin,每個 bin thread 都得掃過全部 input,工作量 O(#bins × #inputs) 而非 O(#inputs);③ load imbalance——每個 bin 對應的 input 數量不同。三點皆不利,故改採 input-centric:每條 thread 對應一個 input 元素並 atomically 更新對應 bin,雖付出 scatter+atomics 代價,卻換到高平行度(≈#inputs)、work-efficient(每 input 處理一次)與良好負載均衡。此例說明 gather vs scatter 不是唯一考量,parallelism、mapping、load balance 同樣關鍵。

核心心法:平行程式設計 = 三步驟(algorithm selection → problem decomposition → optimization & tuning)。Amdahl's Law 提醒天花板由序列段決定;演算法選擇是在四面向間取最佳折衷;問題分解的 gather/scatter 只是考量之一,平行度與 load balance 常逆轉直覺;真正的突破來自 fresh computational thinking——以 domain 洞見重新設計演算法(如 cutoff binning),而非「just recompile」。