并行与分布式系统中的并行前缀扫描：Blelloch并行扫描算法
我们先明确问题：给定一个数组A[0..n-1]（假设n是2的幂以简化描述，实际算法可处理任意长度）和一个二元结合运算符⊕（例如加法、乘法、求最大值等），我们需要计算前缀扫描（prefix scan），也称为前缀和（如果⊕是加法）。前缀扫描包含两种形式：
- 包含性前缀扫描（inclusive scan）：输出数组B，其中B[i] = A[0] ⊕ A[1] ⊕ ... ⊕ A[i]。
- 排他性前缀扫描（exclusive scan）：输出数组B，其中B[0]是单位元（例如加法时是0），B[i] = A[0] ⊕ A[1] ⊕ ... ⊕ A[i-1] (对于i>0)。
目标：设计一个高效的并行算法来计算前缀扫描，使其在并行计算机模型（如PRAM）上具有良好的工作量和时间复杂度。
算法简介
Blelloch扫描算法是一个经典的工作最优（work-efficient）并行算法。它采用分治策略，分为两个阶段：上行阶段（up-sweep，或reduce阶段）和下行阶段（down-sweep）。这个算法可以在O(log n)时间（使用O(n)个处理器）内完成，总工作量是O(n)，与串行算法相同，因此是工作最优的。
我们以排他性前缀扫描为例，使用加法作为⊕运算进行讲解。假设输入数组A长度为n=8，初始值为[A0, A1, ..., A7]。
第一阶段：上行阶段（Reduce / Up-Sweep）
这个阶段自底向上计算一个“部分和”树，但计算过程中会覆盖原数组的部分值。我们可以想象构建一棵完全二叉树，叶子节点是输入元素。
-
初始化：将输入数组A视为二叉树的叶子节点。设d从1开始，步长s=1，直到s=n/2。
-
并行加和：对于每个下标i，满足 i 是 s2 的倍数减1，即 i = 2s - 1, 4*s - 1, ..., n-1。但更直观的方法是层级操作：
- 从最底层开始，将每对相邻元素相加，结果存到右孩子的位置。
- 更形式化地，对于层级k（k从0到log₂n -1），步长 stride = 2^(k+1)。对于所有 i = stride - 1, 2stride -1, 3stride -1, ... < n，执行：
A[i] = A[i] + A[i - stride/2]
例子（n=8）：
- 层级0 (stride=2): 操作下标 i=1,3,5,7。
A[1] = A[1] + A[0]
A[3] = A[3] + A[2]
A[5] = A[5] + A[4]
A[7] = A[7] + A[6]
此时，A[1], A[3], A[5], A[7]分别存储了A0+A1, A2+A3, A4+A5, A6+A7。 - 层级1 (stride=4): 操作下标 i=3,7。
A[3] = A[3] + A[1] (即(A2+A3) + (A0+A1) = A0+A1+A2+A3)
A[7] = A[7] + A[5] (即(A6+A7) + (A4+A5) = A4+A5+A6+A7) - 层级2 (stride=8): 操作下标 i=7。
A[7] = A[7] + A[3] (即(A4+A5+A6+A7) + (A0+A1+A2+A3) = A0到A7的总和)
-
第一阶段结束：此时，数组A的某些位置存储了不同范围的累加和。在我们的例子中，A[7]存储了所有元素的总和。这个阶段类似于并行归约（reduce）操作，构建了一棵隐式的求和树。
第二阶段：下行阶段（Down-Sweep）
这个阶段是算法的核心。它从上到下遍历这棵隐式树，将“左子树的累计和”传递给右子树，并最终计算出每个位置的排他性前缀和。
-
初始化：将最后一个元素（总和）清零，作为排他性前缀和的起点。即，设置 A[n-1] = 0。
-
逆序层级遍历：按照与上行阶段相反的层级顺序（从树根到叶子），对于每个层级k（从log₂n -1 递减到0），步长 stride = 2^(k+1)，对于所有 i = stride - 1, 2stride -1, 3stride -1, ... < n，执行以下两个操作：
a. 保存左子值：temp = A[i - stride/2]
b. 左子更新：A[i - stride/2] = A[i]（将父节点的当前值传给左孩子）
c. 右子更新：A[i] = A[i] + temp（将父节点的当前值加上左孩子的旧值，传给右孩子）这个过程的直观解释是：每个父节点持有“其左子树所有元素累加和”的值。在下行过程中，父节点将这个值传递给它的左孩子（作为左孩子子树的排他性前缀和），同时将这个值加上自己左孩子的值（即左子树的累加和）后传递给右孩子（作为右孩子子树的排他性前缀和）。
例子接续（n=8，当前A[7]在阶段1后存储总和，阶段2开始设A[7]=0）：
- 层级2 (stride=8, 操作i=7):
temp = A[3] (A[3]存储了A0..A3的和)
A[3] = A[7] (A[3]变为0)
A[7] = A[7] + temp = 0 + (A0..A3的和) = A0..A3的和
现在，A[3]是A[4]的排他性前缀和（A0..A3），A[7]是A[8]（不存在）的排他性前缀和，也是总和。 - 层级1 (stride=4, 操作i=3, 7):
对于i=3:
temp = A[1] (A[1]存储了A0+A1)
A[1] = A[3] (变为0)
A[3] = A[3] + temp = 0 + (A0+A1) = A0+A1
对于i=7:
temp = A[5] (A[5]存储了A4+A5)
A[5] = A[7] (变为A0..A3的和)
A[7] = A[7] + temp = (A0..A3的和) + (A4+A5) = A0..A5的和 - 层级0 (stride=2, 操作i=1,3,5,7):
对于i=1:
temp = A[0]
A[0] = A[1] (变为0)
A[1] = A[1] + temp = 0 + A0 = A0
对于i=3:
temp = A[2]
A[2] = A[3] (变为A0+A1)
A[3] = A[3] + temp = (A0+A1) + A2 = A0+A1+A2
对于i=5:
temp = A[4]
A[4] = A[5] (变为A0..A3的和)
A[5] = A[5] + temp = (A0..A3的和) + A4 = A0..A4的和
对于i=7:
temp = A[6]
A[6] = A[7] (变为A0..A5的和)
A[7] = A[7] + temp = (A0..A5的和) + A6 = A0..A6的和
- 层级2 (stride=8, 操作i=7):
-
第二阶段结束：此时，数组A存储的就是排他性前缀和结果。对照检查：
A[0] = 0
A[1] = A0
A[2] = A0+A1
A[3] = A0+A1+A2
A[4] = A0+A1+A2+A3
A[5] = A0..A4
A[6] = A0..A5
A[7] = A0..A6
完全正确。最后一个元素A[7]是前n-1个元素的和，而总和（A0..A7）在过程中被丢弃了（在开始下行阶段时被清零）。
算法总结与要点
- 工作最优：上行和下行阶段各自有log n步，每步有约n/2, n/4, ... 次独立并行操作。总操作数约为2n，是O(n)的，与串行算法相同。
- 并行模型：在PRAM（CRCW或CREW）模型上，该算法需要O(log n)时间和O(n)的处理器，达到最优。
- 包含性前缀扫描：如果要得到包含性前缀扫描，只需在排他性结果的基础上，将每个元素与对应的原始输入元素相加（一个简单的并行步即可）。
- 任意结合运算符：该算法适用于任意满足结合律的二元运算符⊕（加法、乘法、最大值、最小值、逻辑与/或等）。
- 任意长度数组：对于非2的幂的长度，可以通过填充一个不影响运算的单位元（如加法的0）来扩展到2的幂，或者修改下标计算来直接处理。
这个算法的优美之处在于它将看似顺序依赖的前缀计算，通过巧妙的树形结构和两阶段遍历，转化为高度并行的操作，是并行计算中的一个基础且重要的范式。