并行前缀扫描

形式陈述 ​

接口与代数前提 ​

给定幺半群公理库幺半群Monoid具有双侧单位元的半群。 $(M,\otimes ,e)$ 与序列 $a_0,\dots ,a_{n-1}$。Exclusive scan 输出

$$y_i=a_0\otimes \cdots \otimes a_{i-1},y_0=e;$$

inclusive scan 输出 $z_i=y_i\otimes a_i$。本文后续算法先求 exclusive 版本，避免空前缀和公理库前缀和Prefix sum · Cumulative sum预先累计序列前缀，使静态区间和查询可由两个前缀值相减得到。单位元在边界处另设特判。

只要求结合律，不要求交换律或逆元。若 $\otimes$ 不交换，左右子树的组合顺序必须始终是“左摘要 $\otimes$ 右摘要”；任意交换会计算另一种前缀。

Upsweep：建立归约树 ​

先把长度补到二次幂，填充值为 $e$。叶子按原顺序存输入；每个内部节点保存左右孩子摘要的有序组合。第 0 层并行计算相邻二元组，第 1 层并行合并长度 2 的块，直到根保存全序列摘要。

Upsweep 不变量是：高度 $h$ 的已完成节点恰保存其连续叶区间、长度 $2^h$ 的聚合。归纳步由结合律成立；不需要把区间内部重新排序。

设补齐后长度 $N=2^{\lceil {\log }_{2}n\rceil }<2n$。在Work–Depth 模型公理库Work–Depth 模型work-depth model · work-span model · computation DAG model把并行计算表示为依赖 DAG，以总工作 W 和关键路径深度 D 分离工作量与并行性。中，整棵二叉树有 $N-1$ 个内部节点，每个只做一次 $\otimes$，所以 work 为 $N-1=\mathrm{\Theta }(n)$，span 为 $\lceil {\log }_{2}n\rceil$。

Downsweep：传播左侧上下文 ​

把根的外部前缀设为 $e$。若某内部节点收到进入其区间前的前缀 $p$，左孩子收到 $p$，右孩子收到

$$p\otimes L,$$

其中 $L$ 是 upsweep 保存的左子树摘要。两个孩子随后并行继续。到叶 $i$ 时，收到的正是 $a_0\otimes \cdots \otimes a_{i-1}$。

Downsweep 不变量只承担一个重心：节点携带的是“严格位于本节点区间左侧”的聚合。右孩子加上左摘要，左孩子不加本区间任何元素，因此叶端点自然得到 exclusive 语义。

Downsweep 同样访问 $O(n)$ 个节点、深度 $O(\log n)$。上下两遍合计

$$W=\mathrm{\Theta }(n),D=\mathrm{\Theta }(\log n).$$

由Brent 调度定理公理库Brent 调度定理Brent scheduling theorem · Brent's theorem · work-depth scheduling principle把 work 为 W、depth 为 D 的单位任务 DAG 贪心映射到 P 个处理器，得到 W/P+D 级时间上界。，$P$ 处理器时间为 $O(n/P+\log n)$。

直觉

Upsweep 先为每个连续区间建立聚合摘要，downsweep 再把“严格位于当前区间左边”的上下文从根传播到叶。每个叶最终收到自己的 exclusive 前缀；树上两个方向各只做线性工作，却把依赖链压到对数深度。

例子与边界

字符串拼接的状态轨迹 ​

取非交换运算字符串拼接，输入 a,b,c,d，单位元为空串。Upsweep 得到第一层 ab,cd，根为 abcd。Downsweep 从根前缀 "" 开始：左半收到 ""，右半收到 ab；左半两叶得到 "" 与 a，右半两叶得到 ab 与 abc。

最终 exclusive 输出为 "",a,ab,abc，inclusive 输出再分别拼当前字符，得到 a,ab,abc,abcd。若在右孩子更新时写成 $L\otimes p$，加法例子看不出错误，字符串例子会立即暴露次序颠倒。

推论与应用

Stream compaction ​

对每个输入并行计算保留标志 $b_i\in \{0,1\}$，对标志做 exclusive sum scan 得到位置 $p_i$。若 $b_i=1$，就把元素写到输出 $out[p_i]$；最后元素总数是根总和。

因为不同保留元素的前缀计数不同，scatter 下标互异，无需并发写同一槽。Scan 在这里不仅求和，还把全局稳定压缩转换成局部位置计算；输入相对次序被保留。

内存冲突与实现 ​

概念树可单独存 $2n$ 个节点，容易满足 EREW；in-place Blelloch 布局把内部摘要写回数组指定位置，需按层核对每个槽只有一个写者。Upsweep 与 downsweep 之间必须有依赖同步，不能让后者读到未完成摘要。

在 GPU 上，warp、shared-memory bank conflict 与跨 block scan 还需分层处理。块内 scan、块总和 scan、再把块前缀加回的三阶段仍保持同一不变量，但 barrier 和全局内存流量不在抽象 work/span 中。

数值与接口边界 ​

浮点加法不满足精确结合律，树形 scan 与串行左折叠可能有不同舍入结果；这不是 data race，却会破坏 bitwise reproducibility。需要确定复现时应固定树形、使用更高精度或补偿方案。

没有单位元时仍可定义非空 inclusive scan，但标准 downsweep 的根前缀无法设值；需改算法或显式提供 identity。Segmented scan 还要在摘要中携带段首标记，不能仅在普通结果上事后清零。

参考资料

• Guy Blelloch, Prefix Sums and Their Applications, CMU Technical Report, 1990.
• W. Daniel Hillis, Guy Steele, Data Parallel Algorithms, Communications of the ACM, 1986.
• Mark Harris, Shubhabrata Sengupta, John Owens, Parallel Prefix Sum (Scan) with CUDA, GPU Gems 3, 2007.