// 初始化
for all i in parallel do
    B[i] := A[i]
end for

// 主循环，log n轮
for k = 0 to (log2(n) - 1) do
    for all i where i >= 2^k in parallel do
        B[i] := B[i - 2^k] ⊕ B[i]
    end for
end for

并行与分布式系统中的并行前缀扫描：Sklansky并行前缀扫描算法 题目描述 前缀扫描（Prefix Scan），也称为前缀和（Prefix Sum），是并行计算中的一个基本且关键的算法。给定一个包含n个元素的数组A[ 0, n-1]和一个二元结合运算符⊕（通常为加法），前缀扫描计算出一个新的数组B，使得B[ i] = A[ 0] ⊕ A[ 1] ⊕ ... ⊕ A[ i ]。这个问题在许多领域都有广泛应用，如压缩、排序、图算法和线性递推。 Sklansky算法是一种经典的并行前缀扫描算法，以其规则的结构和对数级别的步数复杂度而闻名。我们的目标是详细讲解如何在共享内存的多处理器系统（如PRAM模型）上，实现Sklansky算法，并分析其性能。假设有p个处理器，n个输入元素，通常n远大于p，但为了简化分析，我们先从n=p的理想情况开始讨论。 解题过程 我们将循序渐进地讲解Sklansky算法，从基础概念到具体步骤，再到复杂度分析。 第一步：理解问题与基本概念 前缀扫描定义 ：给定数组A和结合运算符⊕，计算B[ i] = ⊕_ {j=0}^{i} A[ j]。例如，如果⊕是加法，A=[ 1,2,3,4]，则B=[ 1, 1+2=3, 1+2+3=6, 1+2+3+4=10 ]。 并行计算模型 ：假设我们在共享内存的并行随机存取机（PRAM）上工作，特别是CREW（并发读互斥写）模型。多个处理器可以同时读取同一个内存位置，但同一时间只能有一个处理器写入特定位置。我们有p个处理器，P0, P1, ..., P_ {p-1}。 目标 ：设计一个算法，使计算时间（步数）远小于串行的O(n)时间。Sklansky算法的目标是实现O(log n)的时间复杂度，但会使用O(n log n)的总操作数（在PRAM模型中，这被称为“工作”）。 第二步：Sklansky算法的直观思想 Sklansky算法的核心思想是通过一个类似于二叉树的结构，分阶段、分层级地组合部分和，最终为每个位置计算出正确的前缀和。它不是简单地构建一个全局的“和”，而是让每个处理器在每一轮中不仅计算自己负责的区间和，还为后续步骤积累“来自左侧的累积和”。 第三步：算法详细步骤（假设n=p，即每个处理器初始持有一个元素） 假设处理器Pi初始时存储A[ i]，最终需要计算并存储B[ i ]。算法将进行log₂ n轮（层），从k=0到(log₂ n)-1。在每一轮k，处理器将根据其索引i的二进制表示进行特定的通信和计算。 我们用图示和伪代码结合的方式讲解。设总处理器数n=8为例，索引i从0到7（二进制000到111）。算法进行log₂8=3轮。 初始化 ：每个处理器Pi设置一个局部变量 total 为A[ i]（自己持有的值），同时设置一个局部变量 prefix 为A[ i ]（初始前缀和就是自己）。 第0轮（k=0） ： 通信模式 ：每个处理器Pi（满足i mod 2^{k+1} = 2^{k+1}-1，即i的最低k+1位全为1时）从处理器P_ {i-2^k}（即i减去2^k）读取其 total 值。对于k=0，条件简化为i的最低1位是1（即i是奇数）。 操作 ： 对于奇数i的处理器 ：从处理器i-1读取其 total 值，记为 left_total 。然后更新自己的 prefix 值为： prefix = left_total ⊕ prefix 。这一步意味着奇数位置的处理器获取了其左侧紧邻元素的值，并将其合并到自己的前缀和中。 更新 total ：同时，所有奇数i的处理器更新自己的 total 值为： total = left_total ⊕ total 。这计算了从i-1到i这个区间的和，为下一轮更大范围的合并做准备。 示例（n=8） ： P1（i=1, 二进制001）从P0读取 total (A[ 0])，然后设置 prefix = A[0] ⊕ A[1] ， total = A[0] ⊕ A[1] 。 P3（i=3）从P2读取，设置 prefix = A[2] ⊕ A[3] , total = A[2] ⊕ A[3] 。 P5从P4读取，P7从P6读取，类似。 偶数处理器（P0, P2, P4, P6）本轮不执行读取操作，它们的 prefix 和 total 保持不变。 第1轮（k=1） ： 通信模式 ：k=1。处理器Pi在满足条件：i mod 4 = 3（即i的最低2位为二进制11）时，从处理器P_ {i-2}（即i-2）读取其 total 值。 操作 ： 对于满足条件的处理器 ：读取 left_total ，更新 prefix = left_total ⊕ prefix 。 更新 total ： total = left_total ⊕ total 。 示例 ： P3（i=3, 二进制011）从P1（i-2=1）读取 total （此时P1的 total 是A[ 0]⊕A[ 1 ]）。然后P3设置： prefix = (A[0]⊕A[1]) ⊕ (A[2]⊕A[3]) 。注意，P3上一轮结束后的 prefix 是A[ 2]⊕A[ 3]，现在更新后，P3的 prefix 变成了A[ 0]到A[ 3]的累积和， 这正是最终B[ 3]需要的值 。 total = (A[0]⊕A[1]) ⊕ (A[2]⊕A[3]) ，即A[ 0]到A[ 3 ]的和。 P7（i=7, 二进制111）从P5（i-2=5）读取 total （A[ 4]⊕A[ 5]），并类似地更新自己的 prefix 为A[ 4]到A[ 7]的累积和（但还不是最终B[ 7]，还缺左边A[ 0..3]的和）， total 更新为A[ 4]到A[ 7 ]的和。 不满足条件（i mod 4 != 3）的处理器（如P1, P5等）本轮不读取，但注意P1和P5的 total 在上轮已被更新，它们在本轮是数据的提供者。 第2轮（k=2） ： 通信模式 ：k=2。处理器Pi在满足条件：i mod 8 = 7（即i的最低3位为二进制111）时，从处理器P_ {i-4}（即i-4）读取其 total 值。在n=8时，只有i=7满足条件。 操作 ： P7从P3（i-4=3）读取 total （此时P3的 total 是A[ 0]到A[ 3 ]的和）。 P7更新： prefix = (A[0]⊕A[1]⊕A[2]⊕A[3]) ⊕ (A[4]⊕A[5]⊕A[6]⊕A[7]) 。这正是最终B[ 7 ]的值。 total 也被更新为整个数组的总和（此例中即B[ 7 ]）。 此时，处理器P7得到了最终的正确前缀和B[ 7]。但其他处理器呢？ 第四步：处理“缺失”的前缀和 你可能会注意到，上述过程只保证了某些特定位置（索引满足特定二进制模式的处理器）在每一轮结束后得到了截至该位置的正确前缀和。例如： 第0轮后，所有奇数索引处理器得到了自己及其左侧紧邻元素的和（B[ 1], B[ 3], B[ 5], B[ 7]的临时值，但B[ 7 ]还不是最终值）。 第1轮后，索引为3,7的处理器得到了更宽范围的前缀和（B[ 3]正确，B[ 7]是A[ 4..7 ]的和）。 第2轮后，只有索引7的处理器得到了最终的前缀和B[ 7 ]。 为了让 所有 处理器都得到正确的前缀和，Sklansky算法的经典描述通常采用一种“递归倍增”的模式，其中每个处理器Pi在每一轮k不仅从P_ {i-2^k}接收 total ，还用接收到的值去更新自己的 prefix 。关键在于， 更新 prefix 的条件与接收 total 的条件不同 。 更准确的标准Sklansky算法描述如下： 仍然进行log n轮，k从0到(log n)-1。 在每一轮k，对于每个处理器Pi（i ≥ 2^k）： 它从处理器P_ {i-2^k}读取其 total 值，记为 left_total 。 它将自己的 prefix 更新为： prefix = left_total ⊕ prefix 。 注意：这个更新是对所有i ≥ 2^k的处理器都执行的，而不仅仅是特定二进制模式的处理器。 它将自己的 total 更新为： total = left_total ⊕ total 。 注意：这个更新是对所有i ≥ 2^k的处理器都执行的。 让我们用n=8重新审视这个过程： 初始化 ： prefix[i] = A[i] , total[i] = A[i] 。 k=0 ： 所有i ≥ 1的处理器（P1到P7）从P_ {i-1}读取 total 。 更新： prefix[i] = total[i-1] ⊕ prefix[i] , total[i] = total[i-1] ⊕ total[i] 。 结果：P1的 prefix 变为A[ 0]+A[ 1] (B[ 1])；P2的 total 变为A[ 1]+A[ 2]，但 prefix 变为A[ 1]+A[ 2]（这是错的，B[ 2]应该是A0+A1+A2）。这就是问题所在。实际上，经典Sklansky算法通常不直接计算所有 prefix ，或者需要更精巧的初始化和数据传递。另一种常见的实现方式是使用一个二维数组 S ，其中 S[i][k] 表示从位置i开始向左延伸2^k个元素的区间和。然后前缀和可以通过组合这些区间和得到。 为了更清晰和避免混淆，我们给出Sklansky算法最常被引用的形式，它计算的是一个“进位”传播网络。其计算模式是：在每一层k，位置i（i >= 2^k）的值被更新为它自身与位置i-2^k的值的和。经过log n层后，每个位置都存储了从开头到该位置的前缀和。计算图示是一个有向无环图，其中每个节点i在层k有边来自节点i-2^k。 第五步：标准Sklansky算法的清晰描述与伪代码 我们假设输入数组 A 存储在共享内存，输出数组 B 也存储在共享内存。我们使用一个二维临时数组 S[0..n-1][0..log n] ，或者更节省空间地，只使用一维数组 X 来保存中间结果，通过多轮覆盖。 伪代码如下（简化版，n为2的幂） ： 注意 ：这个简洁的伪代码假设了在并行执行 for all 循环时，同一轮迭代中读取 B[i-2^k] 的值是读取本轮更新前的“旧”值。在PRAM CREW模型下，这是可行的，因为读是并发的，写是互斥的。但实际实现时，为了避免读写冲突，通常需要双缓冲或精心安排计算顺序，确保使用的是上一轮的值。 算法执行过程（n=8, ⊕=加法） ： 初始: B = [ A0, A1, A2, A3, A4, A5, A6, A7 ] k=0 (2^k=1): 更新所有i>=1 B[ 1] = B[ 0]+B[ 1 ] = A0+A1 B[ 2] = B[ 1]+B[ 2] = (A0+A1)+A2? 等等，这里有问题！因为B[ 1]刚被更新为新值，而B[ 2]读取B[ 1 ]时应该用旧值A1。所以这个简单伪代码在PRAM CREW下需要明确指定使用旧值。更严格的写法是使用临时数组或标明“使用本步开始前的值”。 假设我们使用旧值，记B_ old为步骤开始前的数组。 B[ 1] = B_ old[ 0] + B_ old[ 1 ] = A0 + A1 B[ 2] = B_ old[ 1] + B_ old[ 2 ] = A1 + A2 B[ 3 ] = A2 + A3 B[ 4 ] = A3 + A4 B[ 5 ] = A4 + A5 B[ 6 ] = A5 + A6 B[ 7 ] = A6 + A7 k=1 (2^k=2): 更新所有i>=2 B[ 2] = B_ old[ 0] + B_ old[ 2 ] = A0 + (A1+A2) = A0+A1+A2 B[ 3] = B_ old[ 1] + B_ old[ 3 ] = (A0+A1) + (A2+A3) = A0+A1+A2+A3 B[ 4] = B_ old[ 2] + B_ old[ 4 ] = (A1+A2) + (A3+A4) = A1+A2+A3+A4 B[ 5] = B_ old[ 3] + B_ old[ 5 ] = (A2+A3)+(A4+A5)= A2+A3+A4+A5 B[ 6] = B_ old[ 4] + B_ old[ 6 ] = (A3+A4)+(A5+A6)= A3+A4+A5+A6 B[ 7] = B_ old[ 5] + B_ old[ 7 ] = (A4+A5)+(A6+A7)= A4+A5+A6+A7 k=2 (2^k=4): 更新所有i>=4 B[ 4] = B_ old[ 0] + B_ old[ 4 ] = A0 + (A1+A2+A3+A4) = A0+A1+A2+A3+A4 B[ 5] = B_ old[ 1] + B_ old[ 5 ] = (A0+A1) + (A2+A3+A4+A5) = A0+A1+A2+A3+A4+A5 B[ 6] = B_ old[ 2] + B_ old[ 6 ] = (A0+A1+A2) + (A3+A4+A5+A6) = A0+...+A6 B[ 7] = B_ old[ 3] + B_ old[ 7 ] = (A0+A1+A2+A3) + (A4+A5+A6+A7) = A0+...+A7 最终B数组存储了正确的前缀和。算法结构规则，每轮每个活跃处理器（i >= 2^k）只进行一次加法和一次通信（读取远程数据）。 第六步：复杂度分析 时间 ：有log n轮。在PRAM CREW模型中，假设并发读是常数时间，每轮所有活跃处理器并行操作，每轮时间为O(1)。因此总时间为 O(log n) 。 工作 （总操作次数）：第k轮有n - 2^k个处理器活跃，总操作数约为 Σ_ {k=0}^{log n -1} (n - 2^k) ≈ n log n - n = O(n log n) 。这比最优工作O(n)要多，因此Sklansky算法是“工作非最优”但时间较快的算法。与之对应的是工作最优的Blelloch扫描算法（O(n)工作，O(log n)时间，但常数更大，结构稍复杂）。 空间 ：如果就地计算，只需要O(1)额外空间（如果不计输出数组）。但通常为了清晰避免读写冲突，会使用双缓冲，需要O(n)额外空间。 第七步：扩展到n>p的情况 当输入规模n大于处理器数p时，常见的策略是： 局部前缀和 ：每个处理器负责一个连续块，大小为n/p。每个处理器串行计算其本地块内的前缀和，得到本地前缀和数组 local_prefix ，并记住本块的总和 block_sum 。 全局前缀和 ：在p个处理器上，对 block_sum 数组应用Sklansky算法，计算这些块总和的前缀和，得到 global_block_prefix ，其中 global_block_prefix[i] 是前i个块（0到i-1）的总和。 组合 ：每个处理器Pi将其本地 local_prefix 数组中的每个元素都加上 global_block_prefix[i] ，得到最终的正确全局前缀和。 总结 Sklansky并行前缀扫描算法是一个结构规则、易于在规则互连网络（如超立方体）上映射的算法。它通过log n轮“递归倍增”式的通信和计算，高效地计算出所有位置的前缀和，虽然总操作数并非最优，但其简洁性和规则的通信模式使其在许多并行架构上具有实用价值。理解其二进制索引模式下的数据流动是掌握该算法的关键。