演算法選擇與權衡 (Algorithm Selection and Tradeoffs)

重點總覽 (Overview)

平行程式設計三步驟的第一步是 algorithm selection。同一個問題通常有多個演算法可解，而它們在四個面向上各有優劣，沒有任何一個演算法在所有面向都最好，程式設計者必須為「目標硬體」挑出最佳折衷。

演算法的三大基本性質 (Essential Properties of an Algorithm)

演算法 = 一步步精確描述、且電腦能執行的程序。必須同時具備三性質:

平行演算法的四個比較面向 (Four Axes of Algorithm Tradeoffs)

給定問題,通常能想出多個演算法,它們在以下面向各異:

三大經典權衡 (Three Classic Tradeoffs)

本書多章已實際比較過演算法,可歸納為三個反覆出現的經典權衡:

複雜度 vs 平行度 (Complexity vs Parallelism)

• Brent-Kung:演算法複雜度低,做同一計算所需 operations 較少 → work efficient。
• Kogge-Stone:暴露更多平行度,能在更少的 iteration 完成。
• 量級對照(N 個元素的 scan):

一般性 vs 效率 (Generality vs Efficiency)

• Radix sort:noncomparison sort,複雜度可低於 merge sort,且高度適合平行化;但只能用於特定型別的 key(不夠一般)。
• Merge sort:comparison-based,任何有良好定義比較運算子的 key 都能用 → 一般性高。

複雜度 vs 準確度 (Complexity vs Accuracy)

• DCS 與 cutoff summation 平行度相同、一般性相同,差別純粹在「複雜度 vs 準確度」。
• DCS 的致命傷:完全準確的方法,計算量隨體積的平方成長 (O(V²));大體積時即使是大規模平行硬體也會被淹沒。
• Cutoff 的物理洞見:許多 grid 計算基於物理定律,遠處粒子的貢獻極小,可用隱式方法以低很多的複雜度集體處理 → 用很小的準確度損失換大幅效率提升。

Cutoff Binning 演算法 (Cutoff Binning Algorithm)

把 cutoff 概念真正搬上 GPU,展示「準確度換複雜度」在平行化時的額外挑戰。

序列 vs 平行的分解差異

序列版很直觀:對每個原子,走訪落在其半徑內的 grid point(grid 是可索引的陣列)。但 atom-centric 的 scatter 存取行為讓它難以平行,故 GPU 上改用 grid-centric 分解。

核心構想:分箱 (binning)

1. 先把輸入原子依座標排序進 bins;每個 bin 對應 grid 空間中的一個 box,裝下座標落在該 box 的所有原子。
2. 為每個 grid point 定義一個 neighborhood:包含「所有可能對該 grid point 能量有貢獻的原子」的那些 bins。
3. 執行時:所有 block 各自走訪自己的 neighborhood bins;block 內所有 thread 一起掃描這些 bin 中的原子,但各自判斷該原子是否落在自己的 cutoff radius 內。

// 概念性 pseudocode:grid-centric cutoff binning kernel
__global__ void cutoffBinningKernel(/* bins, neighborhood lists, grid */) {
    int gridPoint = blockIdx.x * blockDim.x + threadIdx.x; // 每 thread 一個 grid point
    float energy = 0.0f;                                   // 結果累積在 register (gather)
    for (bin in neighborhoodBinsOf(blockIdx)) {            // block 走訪自己的 neighborhood
        loadBinAtomsIntoSharedMemory(bin);                 // 協同載入到 shared memory
        __syncthreads();
        for (atom in sharedBinAtoms) {
            if (distance(atom, gridPoint) < cutoff)        // 各 thread 個別判斷半徑
                energy += contribution(atom, gridPoint);
        }
        __syncthreads();
    }
    grid[gridPoint] = energy;
}

ASCII:bins、neighborhood 與 overflow list

Grid 空間切成 bins (每個 bin 容量固定 = capacity)
┌────┬────┬────┬────┐
│ b00│ b01│ b02│ b03│      ● = grid point (一條 thread)
├────┼────┼────┼────┤      neighborhood(●) = ● 半徑內可能有貢獻的所有 bin
│ b10│ b11│●b12│ b13│           = { b01,b02,b03, b11,b12,b13, b21,b22,b23 }
├────┼────┼────┼────┤
│ b20│ b21│ b22│ b23│
└────┴────┴────┴────┘

分箱:每個 atom 依座標放進 home bin
  bin 容量足夠 → 放入 bin
  bin 已滿     → 改放 OVERFLOW LIST ┐
                                     ▼
   [ overflow list ]  → kernel 結束後由 host 序列補算缺漏的貢獻

分箱的隱患:負載不均 (load imbalance)

• 問題:bins 內原子數不一——有的很多、有的甚至是空的。
• 解法:把 bin 容量設在合理水準(遠小於單一 bin 可能的最多原子數),並維護一個 overflow list:分箱時若原子的 home bin 已滿,就改放進 overflow list。
• kernel 跑完後,overflow list 中的原子需另外處理以補上缺漏的貢獻。

擴充性與效能比較 (Scalability & Performance, Fig. 19.2)

以「跑多大體積仍划算」對比各實作 (CPU-SSE3 為序列 cutoff 基準):

三種 binning 實作:

考試/面試重點 (Exam / Test Patterns)

Related Notes

• 19-Parallel-Programming-And-Computational-Thinking/01-Goals-of-Parallel-Computing-and-Amdahls-Law
• 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
• 11-Prefix-Sum-Scan/02-Work-Efficient-Scan-Brent-Kung-and-Coarsening
• 13-Sorting/03-Parallel-Merge-Sort-and-Other-Methods
• 18-Electrostatic-Potential-Map/03-Cutoff-Binning-for-Scalability