平行前綴和（parallel prefix sum）

假設你有一排數，想要每一個累計總和：第一個數、前兩個相加、前三個，依此類推直到總和。徒手做你會由左掃到右、帶著總和——每一步都需要前一步，看起來無望地序列。然而這「前綴和」（或稱掃描）是平行計算中最有用的基本運算之一，而令人意外的是它其實能在平行下快速完成，只需約 log n 輪、而非 n 步。

正式地說，陣列 a 的前綴和是陣列 p，其中 p_k = a_0 + a_1 + ... + a_k。天真方法依序做 n-1 次相依的加法。平行訣竅在資料的二元樹上分兩趟進行。在上掃中，相鄰元素兩兩相加，接著那些部分和兩兩相加，依此沿樹而上——每一層使數目減半，故總計在 log n 個平行輪次中抵達樹頂，沿途算出每棵子樹的和。接著一趟匹配的下掃把那些子樹和分配回下方，填出每一個前綴。整件事約做 2n 次加法（序列工作的兩倍），卻以 O(log n) 的平行深度、而非 O(n) 完成。這個模式——以一點額外總工作換取大幅縮短的關鍵路徑——正是把一個「看似序列」的遞迴轉成平行的精髓。

掃描之所以要緊，是因為它是一系列令人吃驚的平行演算法背後的隱藏引擎。它正是你如何在事先不知道每個倖存者該去哪的情況下壓縮陣列（只保留通過某測試的元素）：對一個 0/1 保留旗標陣列做前綴和，會平行地算出每個倖存者的目的索引。它驅動平行排序（計數排序、基數排序）、GPU 上的串流壓縮、多項式求值、以及稀疏矩陣核心內部的資源分配。平行歸約（把所有元素合併成一個值，如和或最大）是較簡單的表親——只要上掃、沒有下掃——是每個 MPI allreduce 與每個寫得好的平行求和背後的主力集體運算。認出一個看似序列的相依其實是一次掃描或一次歸約，是設計平行數值演算法的核心技能。