并行与分布式系统中的并行前缀和（扫描）算法：Sklansky并行前缀扫描算法
字数 6027 2025-12-20 02:09:33

并行与分布式系统中的并行前缀和（扫描）算法：Sklansky并行前缀扫描算法

题目描述

前缀和（Prefix Sum，也称为扫描 Scan）是并行计算中的一个基础且重要的问题。给定一个包含 n 个元素的输入数组 A[0...n-1] 和一个二元结合运算符 ⊕（例如加法、乘法、最大值、最小值等），我们需要计算输出数组 B[0...n-1]，使得对于每个位置 i（0 ≤ i < n），都有：
B[i] = A[0] ⊕ A[1] ⊕ ... ⊕ A[i]。

在串行计算中，这可以通过一次从左到右的遍历轻松完成，时间复杂度为 O(n)。然而，在并行计算中，我们希望利用多个处理器（例如 p 个）来加速这个计算过程。Sklansky算法是一种经典的并行前缀和算法，其目标是最小化计算的总时间（深度），即使得计算从输入到输出的最长路径（关键路径）最短。Sklansky算法能在 O(log n) 的时间（在 PRAM 并行计算模型中，假设有足够多的处理器）内完成计算，但其总的操作数（工作负载）并非最优，为 O(n log n)。

解题过程循序渐进讲解

我们将从最简单的问题入手，逐步构建出 Sklansky 算法的完整思路。请注意，我们假设处理器数量足够多（例如 p = n），并且处理器之间可以任意两两通信（这在 PRAM 的 CREW 或 CRCW 模型中是可以实现的）。我们的目标是理解算法的计算结构。

步骤 1：理解核心思想——倍增法（Recursive Doubling）

并行前缀和的一个直观想法是“倍增法”。让我们用一个长度为 8 的数组为例，运算符为加法。

初始数组 A: [a0, a1, a2, a3, a4, a5, a6, a7]

我们想要计算 B: [a0, a0+a1, a0+a1+a2, ..., a0+...+a7]

倍增法的基本思想是，在每一步，每个元素都试图“收集”距离它更远的元素的和。我们把计算过程看作一个有向无环图（DAG），节点代表中间结果，边代表一次 ⊕ 操作。

  1. 第1步：每个位置 i (i ≥ 1) 计算 A[i-1] ⊕ A[i]。这样，位置 i 现在拥有了从 i-1 到 i 的局部和。但我们需要的是从0开始的和。

    • 计算后（临时存储）: S1 = [a0, a0+a1, a1+a2, a2+a3, a3+a4, a4+a5, a5+a6, a6+a7]

  2. 第2步：现在，我们希望每个位置能“跳”得更远。规则是：对于位置 i (i ≥ 2)，它将当前自己保存的值与相距2个位置的那个位置在第1步计算前的值相加？不对。更高效的方法是：让位置 i 获取它前面距离为2的位置在第1步后计算出的和。

    • 具体操作：对于 i ≥ 2，计算 S1[i] ⊕ A[i-2]。但A[i-2]是原始值，我们想要的是累积和。更好的模式是：对于 i ≥ 2， New[i] = S1[i] ⊕ S1[i-2]。让我们验证：
      • i=2: New[2] = (a1+a2) ⊕ (a0+a1) = a0 + a1 + a2 （正确，是B[2]）
      • i=3: New[3] = (a2+a3) ⊕ (a1+a2) = a1 + a2 + a3 （但我们需要 a0+...+a3，这里缺了a0）
        我们发现简单的两两合并不能直接得到正确结果。我们需要一个更系统的方法。

步骤 2：引入“向前传播”的计算图（Sklansky结构）

Sklansky 算法提供了一个非常规则的计算结构。我们不再把数组看作是线性的，而是看作一棵“计算树”，不过这是一棵所有中间结果都会被保留的树。

我们定义状态：设 P(i, j) 表示从位置 i 到位置 j 的累积和（即 A[i] ⊕ A[i+1] ⊕ ... ⊕ A[j]）。我们的目标是为每个 k 求出 P(0, k)。

Sklansky 算法的计算可以按“轮次”（或“层级”）来组织，总轮数为 ⌈log₂ n⌉。在每一轮中，处理器会进行特定的配对和组合操作。

让我们以 n=8 为例，详细展示这个过程。我们用下标 0~7。

  • 初始化：第0轮，每个位置 i 的当前值 C[i] 初始化为 A[i]。也就是说，C[i] 目前代表 P(i, i)。

  • 第1轮 (d=1): 步长 (stride) s = 2⁰ = 1。

    • 操作规则：对于所有满足 i mod 2^1 == 1 的位置 i（即 i 是奇数：1,3,5,7），它需要将当前位置的值与它前面距离为 s=1 的位置的值进行 ⊕ 操作。
    • 具体计算：
      • C[1] = C[0] ⊕ C[1] (现在 C[1] 代表 P(0,1))
      • C[3] = C[2] ⊕ C[3] (现在 C[3] 代表 P(2,3))
      • C[5] = C[4] ⊕ C[5] (现在 C[5] 代表 P(4,5))
      • C[7] = C[6] ⊕ C[7] (现在 C[7] 代表 P(6,7))
    • 此时状态:
      • C[0]=P(0,0), C[1]=P(0,1), C[2]=P(2,2), C[3]=P(2,3), C[4]=P(4,4), C[5]=P(4,5), C[6]=P(6,6), C[7]=P(6,7)
    • 注意到，所有下标为奇数（且非2的更高次幂的倍数）的位置，已经计算出了以某个偶数开头、长度为2的区间和。

  • 第2轮 (d=2): 步长 s = 2¹ = 2。

    • 操作规则：对于所有满足 i mod 2^2 == 3 的位置 i（即 i 对4取模余3：3,7）。注意，这里不是所有奇数，而是更特定的位置。它需要将当前位置的值与它前面距离为 s=2 的位置的值进行 ⊕ 操作。
    • 具体计算：
      • C[3] = C[1] ⊕ C[3] (C[1]是P(0,1), C[3]原是P(2,3)，结果 C[3] = P(0,1) ⊕ P(2,3) = P(0,3))
      • C[7] = C[5] ⊕ C[7] (C[5]是P(4,5), C[7]原是P(6,7)，结果 C[7] = P(4,5) ⊕ P(6,7) = P(4,7))
    • 此时状态:
      • C[0]=P(0,0), C[1]=P(0,1), C[2]=P(2,2), C[3]=P(0,3), C[4]=P(4,4), C[5]=P(4,5), C[6]=P(6,6), C[7]=P(4,7)
    • 现在，位置3和7已经拥有了长度为4的区间和。

  • 第3轮 (d=3): 步长 s = 2² = 4。

    • 操作规则：对于所有满足 i mod 2^3 == 7 的位置 i（即 i 对8取模余7：7）。它需要将当前位置的值与它前面距离为 s=4 的位置的值进行 ⊕ 操作。
    • 具体计算：
      • C[7] = C[3] ⊕ C[7] (C[3]是P(0,3), C[7]原是P(4,7)，结果 C[7] = P(0,3) ⊕ P(4,7) = P(0,7))
    • 此时状态:
      • C[0]=P(0,0), C[1]=P(0,1), C[2]=P(2,2), C[3]=P(0,3), C[4]=P(4,4), C[5]=P(4,5), C[6]=P(6,6), C[7]=P(0,7)
    • 位置7已经得到了最终的全前缀和 P(0,7)。

步骤 3：填补空缺——最终传播阶段

经过上面的“收集”阶段（也称为“向上传播”或“Reduce”阶段），我们得到了一些位置上的完整前缀和（如C[1], C[3], C[7]），但其他位置（如C[2], C[4], C[5], C[6]）的值还不是从0开始的前缀和。

我们需要一个“分发”或“向下传播”阶段，将这些完整的部分和传播到其他位置。Sklansky 算法的精妙之处在于，这个传播过程可以遵循一个对称的、反向的规则。

实际上，标准的 Sklansky 算法将“收集”和“分发”融合在一个对数步的过程中。让我们继续上面的例子，完成计算。我们需要让每个位置 i 的 C[i] 最终等于 P(0,i)。

观察当前状态，哪些位置已经是最终结果？

  • C[0] = P(0,0) -> 是最终结果 B[0]。
  • C[1] = P(0,1) -> 是最终结果 B[1]。
  • C[3] = P(0,3) -> 是最终结果 B[3]。
  • C[7] = P(0,7) -> 是最终结果 B[7]。

现在计算其他位置：

  • 计算 C[2]: B[2] = P(0,2) = P(0,1) ⊕ A[2] = C[1] ⊕ A[2]。但A[2]当前保存在哪里？在初始值中，或者更优地，我们可以利用已知的中间结果。注意 P(0,2) = P(0,1) ⊕ P(2,2)。而 P(2,2) 是 C[2] 的当前值！所以 C[2]（新）= C[1] ⊕ C[2]（旧）。
  • 计算 C[4]: B[4] = P(0,4) = P(0,3) ⊕ A[4] = C[3] ⊕ C[4]（旧，即P(4,4)）。
  • 计算 C[5]: B[5] = P(0,5) = P(0,3) ⊕ P(4,5) = C[3] ⊕ C[5]（旧）。
  • 计算 C[6]: B[6] = P(0,6) = P(0,3) ⊕ P(4,5) ⊕ A[6]? 这样不高效。更好的方法是 B[6] = P(0,6) = P(0,5) ⊕ A[6]。但我们还没有B[5]。可以 B[6] = P(0,3) ⊕ P(4,6)。而P(4,6) = P(4,5) ⊕ P(6,6) = C[5]（旧） ⊕ C[6]（旧）。所以 C[6]（新）= C[3] ⊕ (C[5]（旧） ⊕ C[6]（旧）)。但注意，C[5]（旧）在后面计算B[5]时会被覆盖，所以需要临时变量或按顺序计算。

为了系统化，我们进行第二阶段的传播，其规则与第一阶段类似但方向是“利用已知的大区间和来推导小区间和”。

一种清晰的描述方式是：在完成第 logn 轮后，我们实际上构建了一个二叉树状的依赖关系。Sklansky 算法的计算图是一个有向无环图，其中每个节点 i 在第 d 轮的操作可以描述为：
if (i mod 2^d == 2^d - 1) then C[i] = C[i - 2^{d-1}] ⊕ C[i]

这个条件 i mod 2^d == 2^d - 1 就是找出那些二进制表示中，低 d 位全为 1 的索引。

对于 n=8:

  • d=1: 找低1位为1 -> 索引二进制最后一位是1: 1(001), 3(011), 5(101), 7(111)
  • d=2: 找低2位为11 -> 索引二进制最后两位是11: 3(011), 7(111)
  • d=3: 找低3位为111 -> 索引二进制最后三位是111: 7(111)

这个计算过程完成后，对于任意位置 i，其最终值 B[i] 可以通过以下方式得到：将 i 写成二进制，B[i] 等于所有那些二进制下标是 i 的“前缀”的节点值的和。更具体地，B[i] 是沿着从 i 节点向左、不断“翻转变低位的1为0”的路径上，所经过节点的初始 A 值之和。这个计算过程已经被上述的并行操作隐含完成了。

实际上，完整的 Sklansky 算法通常以如下伪代码描述（针对 PRAM CREW 模型，允许并发读）：

// 输入: A[0..n-1], n 是2的幂（简化，否则填充）
// 输出: B[0..n-1], B[i] = A[0] ⊕ A[1] ⊕ ... ⊕ A[i]
// 使用原位计算，即结果存在数组 A 中（或另一个数组 C）

for i from 0 to n-1 in parallel do
    C[i] := A[i]               // 初始化

// 前向传播（收集）阶段
for d from 1 to log2(n) do
    stride = 2^(d-1)
    for all i in [stride, n-1] in parallel do
        if (i mod 2^d) == (2^d - 1) then
            C[i] := C[i - stride] ⊕ C[i]
        end if
    end for
end for

// 此时，C 中某些位置已是最终前缀和
// 为了得到所有位置，需要一个反向传播或直接利用规则计算
// 一种常见的完整Sklansky变体是“递归倍增”，其循环体略有不同：

for d from 0 to log2(n)-1 do
    for all i in [2^d, n-1] in parallel do
        if (i+1) is divisible by 2^(d+1) then
            C[i] := C[i - 2^d] ⊕ C[i]
        end if
    end for
end for

步骤 4：算法分析与特点

  • 时间复杂度：循环共有 log n 轮。在 PRAM CREW 模型中，每轮的所有并行操作可以在 O(1) 时间内完成（假设有 n 个处理器）。因此，总时间复杂度为 O(log n)。
  • 工作复杂度：每轮中，大约有 n/2, n/4, n/8, ... 个处理器是活跃的。总操作数（⊕ 运算次数）为 n/2 + n/4 + ... + 1 = n - 1。等等，这是最优的工作量 O(n)。抱歉，我前面的说法“工作负载非最优”是针对另一种结构（如 fan-in 二叉树归约）。标准的 Sklansky 前缀和算法的工作量实际上是 O(n log n)？让我们仔细计算上面伪代码中的操作数。
    • 在第 d 轮（从0开始），满足 (i+1) % 2^(d+1) == 0 的 i 的数量是 n / 2^(d+1)。所以总操作数 = Σ_{d=0}^{log n -1} n / 2^{d+1} = n/2 + n/4 + ... + 1 = n - 1。这是最优的 O(n) 工作量！ 我之前的记忆有误。Sklansky 算法在 O(log n) 时间和 O(n) 工作量下完成了前缀和，是工作最优的。它在 PRAM 模型上达到了最优的速度和线性工作量，这是一个非常优秀的性质。
  • 处理器需求：算法需要大约 n 个处理器来实现完全的并行性。在处理器数 p < n 时，可以将数据块分配给每个处理器，先在局部计算前缀和，然后对局部和进行全局的前缀和计算，最后将全局前缀和传播回每个块。这需要 O(n/p + log p) 时间。
  • 通信模式：算法中的通信模式非常规则，每个处理器在每一轮只与一个固定的、距离是2的幂的其他处理器通信。这种模式在超立方体、蝶形网络等互连拓扑上可以高效映射。
  • 与其它并行前缀和算法的对比：
    • Ladner-Fischer (Kogge-Stone)：另一种 O(log n) 时间、O(n log n) 工作量的算法，具有更规则的连接模式（每个节点在每一轮都与固定偏移的节点通信），常用于硬件电路设计。
    • Brent-Kung：一种 O(log n) 时间、但仅需 O(n) 工作量且处理器数只需 n/log n 的算法，它分两阶段进行，是工作最优且处理器数较少的方案。
    • Hillis-Steele：最简单的算法，O(log n) 时间，但工作量是 O(n log n)，不是工作最优的。

总结

Sklansky 并行前缀和算法是一种优雅且高效的工作最优并行算法。它通过 log n 轮计算，在每一轮中，让特定位置（其索引的二进制表示具有特定模式）的元素“吸收”其前方一段距离的和，从而逐步构建出完整的前缀和。其计算图形成了一个漂亮的递归结构，是并行算法设计中“分治”和“倍增”思想的经典体现。理解 Sklansky 算法不仅有助于解决前缀和问题，其设计思路也被广泛应用于其他并行扫描操作（如流压缩、分段扫描等）。

并行与分布式系统中的并行前缀和（扫描）算法：Sklansky并行前缀扫描算法 题目描述 前缀和（Prefix Sum，也称为扫描 Scan）是并行计算中的一个基础且重要的问题。给定一个包含 n 个元素的输入数组 A[0...n-1] 和一个二元结合运算符 ⊕（例如加法、乘法、最大值、最小值等），我们需要计算输出数组 B[0...n-1] ，使得对于每个位置 i（0 ≤ i < n），都有： B[i] = A[0] ⊕ A[1] ⊕ ... ⊕ A[i] 。 在串行计算中，这可以通过一次从左到右的遍历轻松完成，时间复杂度为 O(n)。然而，在并行计算中，我们希望利用多个处理器（例如 p 个）来加速这个计算过程。Sklansky算法是一种经典的并行前缀和算法，其目标是 最小化计算的总时间（深度） ，即使得计算从输入到输出的最长路径（关键路径）最短。Sklansky算法能在 O(log n) 的时间（在 PRAM 并行计算模型中，假设有足够多的处理器）内完成计算，但其总的操作数（工作负载）并非最优，为 O(n log n)。 解题过程循序渐进讲解 我们将从最简单的问题入手，逐步构建出 Sklansky 算法的完整思路。请注意，我们假设处理器数量足够多（例如 p = n），并且处理器之间可以任意两两通信（这在 PRAM 的 CREW 或 CRCW 模型中是可以实现的）。我们的目标是理解算法的 计算结构 。 步骤 1：理解核心思想——倍增法（Recursive Doubling） 并行前缀和的一个直观想法是“倍增法”。让我们用一个长度为 8 的数组为例，运算符为加法。 初始数组 A: [ a0, a1, a2, a3, a4, a5, a6, a7 ] 我们想要计算 B: [ a0, a0+a1, a0+a1+a2, ..., a0+...+a7 ] 倍增法的基本思想是，在每一步，每个元素都试图“收集”距离它更远的元素的和。我们把计算过程看作一个有向无环图（DAG），节点代表中间结果，边代表一次 ⊕ 操作。 第1步 ：每个位置 i (i ≥ 1) 计算 A[ i-1] ⊕ A[ i ]。这样，位置 i 现在拥有了从 i-1 到 i 的局部和。但我们需要的是从0开始的和。 计算后（临时存储）: S1 = [ a0, a0+a1, a1+a2, a2+a3, a3+a4, a4+a5, a5+a6, a6+a7 ] 第2步 ：现在，我们希望每个位置能“跳”得更远。规则是：对于位置 i (i ≥ 2)，它将当前自己保存的值与 相距2个位置 的那个位置在第1步计算前的值相加？不对。更高效的方法是：让位置 i 获取它前面距离为2的位置在第1步后计算出的和。 具体操作：对于 i ≥ 2，计算 S1[i] ⊕ A[i-2] 。但A[ i-2]是原始值，我们想要的是累积和。更好的模式是：对于 i ≥ 2， New[i] = S1[i] ⊕ S1[i-2] 。让我们验证： i=2: New[ 2] = (a1+a2) ⊕ (a0+a1) = a0 + a1 + a2 （正确，是B[ 2 ]） i=3: New[ 3 ] = (a2+a3) ⊕ (a1+a2) = a1 + a2 + a3 （但我们需要 a0+...+a3，这里缺了a0） 我们发现简单的两两合并不能直接得到正确结果。我们需要一个更系统的方法。 步骤 2：引入“向前传播”的计算图（Sklansky结构） Sklansky 算法提供了一个非常规则的计算结构。我们不再把数组看作是线性的，而是看作一棵“计算树”，不过这是一棵所有中间结果都会被保留的树。 我们定义状态：设 P(i, j) 表示从位置 i 到位置 j 的累积和（即 A[ i] ⊕ A[ i+1] ⊕ ... ⊕ A[ j]）。我们的目标是为每个 k 求出 P(0, k) 。 Sklansky 算法的计算可以按“轮次”（或“层级”）来组织，总轮数为 ⌈log₂ n⌉。在每一轮中，处理器会进行特定的配对和组合操作。 让我们以 n=8 为例，详细展示这个过程。我们用下标 0~7。 初始化 ：第0轮，每个位置 i 的当前值 C[i] 初始化为 A[ i]。也就是说， C[i] 目前代表 P(i, i) 。 第1轮 (d=1): 步长 (stride) s = 2⁰ = 1。 操作规则 ：对于所有满足 i mod 2^1 == 1 的位置 i（即 i 是奇数：1,3,5,7），它需要将当前位置的值与它前面距离为 s=1 的位置的值进行 ⊕ 操作。 具体计算 ： C[ 1] = C[ 0] ⊕ C[ 1] (现在 C[ 1 ] 代表 P(0,1)) C[ 3] = C[ 2] ⊕ C[ 3] (现在 C[ 3 ] 代表 P(2,3)) C[ 5] = C[ 4] ⊕ C[ 5] (现在 C[ 5 ] 代表 P(4,5)) C[ 7] = C[ 6] ⊕ C[ 7] (现在 C[ 7 ] 代表 P(6,7)) 此时状态 : C[ 0]=P(0,0), C[ 1]=P(0,1), C[ 2]=P(2,2), C[ 3]=P(2,3), C[ 4]=P(4,4), C[ 5]=P(4,5), C[ 6]=P(6,6), C[ 7 ]=P(6,7) 注意到，所有下标为奇数（且非2的更高次幂的倍数）的位置，已经计算出了以某个偶数开头、长度为2的区间和。 第2轮 (d=2): 步长 s = 2¹ = 2。 操作规则 ：对于所有满足 i mod 2^2 == 3 的位置 i（即 i 对4取模余3：3,7）。注意，这里不是所有奇数，而是更特定的位置。它需要将当前位置的值与它前面距离为 s=2 的位置的值进行 ⊕ 操作。 具体计算 ： C[ 3] = C[ 1] ⊕ C[ 3] (C[ 1]是P(0,1), C[ 3]原是P(2,3)，结果 C[ 3 ] = P(0,1) ⊕ P(2,3) = P(0,3)) C[ 7] = C[ 5] ⊕ C[ 7] (C[ 5]是P(4,5), C[ 7]原是P(6,7)，结果 C[ 7 ] = P(4,5) ⊕ P(6,7) = P(4,7)) 此时状态 : C[ 0]=P(0,0), C[ 1]=P(0,1), C[ 2]=P(2,2), C[ 3]=P(0,3), C[ 4]=P(4,4), C[ 5]=P(4,5), C[ 6]=P(6,6), C[ 7 ]=P(4,7) 现在，位置3和7已经拥有了长度为4的区间和。 第3轮 (d=3): 步长 s = 2² = 4。 操作规则 ：对于所有满足 i mod 2^3 == 7 的位置 i（即 i 对8取模余7：7）。它需要将当前位置的值与它前面距离为 s=4 的位置的值进行 ⊕ 操作。 具体计算 ： C[ 7] = C[ 3] ⊕ C[ 7] (C[ 3]是P(0,3), C[ 7]原是P(4,7)，结果 C[ 7 ] = P(0,3) ⊕ P(4,7) = P(0,7)) 此时状态 : C[ 0]=P(0,0), C[ 1]=P(0,1), C[ 2]=P(2,2), C[ 3]=P(0,3), C[ 4]=P(4,4), C[ 5]=P(4,5), C[ 6]=P(6,6), C[ 7 ]=P(0,7) 位置7已经得到了最终的全前缀和 P(0,7)。 步骤 3：填补空缺——最终传播阶段 经过上面的“收集”阶段（也称为“向上传播”或“Reduce”阶段），我们得到了一些位置上的完整前缀和（如C[ 1], C[ 3], C[ 7]），但其他位置（如C[ 2], C[ 4], C[ 5], C[ 6 ]）的值还不是从0开始的前缀和。 我们需要一个“分发”或“向下传播”阶段，将这些完整的部分和传播到其他位置。Sklansky 算法的精妙之处在于，这个传播过程可以遵循一个对称的、反向的规则。 实际上，标准的 Sklansky 算法将“收集”和“分发”融合在一个对数步的过程中。让我们继续上面的例子，完成计算。我们需要让每个位置 i 的 C[ i ] 最终等于 P(0,i)。 观察当前状态，哪些位置已经是最终结果？ C[ 0] = P(0,0) -> 是最终结果 B[ 0 ]。 C[ 1] = P(0,1) -> 是最终结果 B[ 1 ]。 C[ 3] = P(0,3) -> 是最终结果 B[ 3 ]。 C[ 7] = P(0,7) -> 是最终结果 B[ 7 ]。 现在计算其他位置： 计算 C[ 2] : B[ 2] = P(0,2) = P(0,1) ⊕ A[ 2] = C[ 1] ⊕ A[ 2]。但A[ 2]当前保存在哪里？在初始值中，或者更优地，我们可以利用已知的中间结果。注意 P(0,2) = P(0,1) ⊕ P(2,2)。而 P(2,2) 是 C[ 2] 的当前值！所以 C[ 2]（新）= C[ 1] ⊕ C[ 2 ]（旧）。 计算 C[ 4] : B[ 4] = P(0,4) = P(0,3) ⊕ A[ 4] = C[ 3] ⊕ C[ 4 ]（旧，即P(4,4)）。 计算 C[ 5] : B[ 5] = P(0,5) = P(0,3) ⊕ P(4,5) = C[ 3] ⊕ C[ 5 ]（旧）。 计算 C[ 6] : B[ 6] = P(0,6) = P(0,3) ⊕ P(4,5) ⊕ A[ 6]? 这样不高效。更好的方法是 B[ 6] = P(0,6) = P(0,5) ⊕ A[ 6]。但我们还没有B[ 5]。可以 B[ 6] = P(0,3) ⊕ P(4,6)。而P(4,6) = P(4,5) ⊕ P(6,6) = C[ 5]（旧） ⊕ C[ 6]（旧）。所以 C[ 6]（新）= C[ 3] ⊕ (C[ 5]（旧） ⊕ C[ 6]（旧）)。但注意，C[ 5]（旧）在后面计算B[ 5 ]时会被覆盖，所以需要临时变量或按顺序计算。 为了系统化，我们进行 第二阶段的传播 ，其规则与第一阶段类似但方向是“利用已知的大区间和来推导小区间和”。 一种清晰的描述方式是：在完成第 logn 轮后，我们实际上构建了一个二叉树状的依赖关系。Sklansky 算法的计算图是一个有向无环图，其中每个节点 i 在第 d 轮的操作可以描述为： if (i mod 2^d == 2^d - 1) then C[i] = C[i - 2^{d-1}] ⊕ C[i] 这个条件 i mod 2^d == 2^d - 1 就是找出那些二进制表示中，低 d 位全为 1 的索引。 对于 n=8: d=1: 找低1位为1 -> 索引二进制最后一位是1: 1(001), 3(011), 5(101), 7(111) d=2: 找低2位为11 -> 索引二进制最后两位是11: 3(011), 7(111) d=3: 找低3位为111 -> 索引二进制最后三位是111: 7(111) 这个计算过程完成后，对于任意位置 i，其最终值 B[ i] 可以通过以下方式得到：将 i 写成二进制，B[ i] 等于所有那些二进制下标是 i 的“前缀”的节点值的和。更具体地，B[ i ] 是沿着从 i 节点向左、不断“翻转变低位的1为0”的路径上，所经过节点的初始 A 值之和。这个计算过程已经被上述的并行操作隐含完成了。 实际上，完整的 Sklansky 算法通常以如下伪代码描述（针对 PRAM CREW 模型，允许并发读）： 步骤 4：算法分析与特点 时间复杂度 ：循环共有 log n 轮。在 PRAM CREW 模型中，每轮的所有并行操作可以在 O(1) 时间内完成（假设有 n 个处理器）。因此，总时间复杂度为 O(log n) 。 工作复杂度 ：每轮中，大约有 n/2, n/4, n/8, ... 个处理器是活跃的。总操作数（⊕ 运算次数）为 n/2 + n/4 + ... + 1 = n - 1。等等，这是最优的工作量 O(n)。抱歉，我前面的说法“工作负载非最优”是针对另一种结构（如 fan-in 二叉树归约）。标准的 Sklansky 前缀和算法的工作量实际上是 O(n log n) ？让我们仔细计算上面伪代码中的操作数。 在第 d 轮（从0开始），满足 (i+1) % 2^(d+1) == 0 的 i 的数量是 n / 2^(d+1)。所以总操作数 = Σ_ {d=0}^{log n -1} n / 2^{d+1} = n/2 + n/4 + ... + 1 = n - 1。 这是最优的 O(n) 工作量！ 我之前的记忆有误。Sklansky 算法在 O(log n) 时间和 O(n) 工作量下完成了前缀和，是工作最优的。它在 PRAM 模型上达到了最优的速度和线性工作量，这是一个非常优秀的性质。 处理器需求 ：算法需要大约 n 个处理器来实现完全的并行性。在处理器数 p < n 时，可以将数据块分配给每个处理器，先在局部计算前缀和，然后对局部和进行全局的前缀和计算，最后将全局前缀和传播回每个块。这需要 O(n/p + log p) 时间。 通信模式 ：算法中的通信模式非常规则，每个处理器在每一轮只与一个固定的、距离是2的幂的其他处理器通信。这种模式在超立方体、蝶形网络等互连拓扑上可以高效映射。 与其它并行前缀和算法的对比 ： Ladner-Fischer (Kogge-Stone) ：另一种 O(log n) 时间、O(n log n) 工作量的算法，具有更规则的连接模式（每个节点在每一轮都与固定偏移的节点通信），常用于硬件电路设计。 Brent-Kung ：一种 O(log n) 时间、但仅需 O(n) 工作量且处理器数只需 n/log n 的算法，它分两阶段进行，是工作最优且处理器数较少的方案。 Hillis-Steele ：最简单的算法，O(log n) 时间，但工作量是 O(n log n)，不是工作最优的。 总结 Sklansky 并行前缀和算法是一种优雅且高效的工作最优并行算法。它通过 log n 轮计算，在每一轮中，让特定位置（其索引的二进制表示具有特定模式）的元素“吸收”其前方一段距离的和，从而逐步构建出完整的前缀和。其计算图形成了一个漂亮的递归结构，是并行算法设计中“分治”和“倍增”思想的经典体现。理解 Sklansky 算法不仅有助于解决前缀和问题，其设计思路也被广泛应用于其他并行扫描操作（如流压缩、分段扫描等）。