并行前缀扫描

形式陈述 ​

接口与代数前提 ​

给定幺半群理路幺半群Monoid具有双侧单位元的半群。 $(M,\otimes ,e)$ 与长度 $n\ge 1$ 的序列 $a_0,\dots ,a_{n-1}$。目标是并行计算它的全部前缀聚合理路前缀和Prefix sum · Cumulative sum预先累计序列前缀，使静态区间和查询可由两个前缀值相减得到。。空序列直接返回空输出。Exclusive scan 输出

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

以下 work/span 按每次摘要组合、复制和节点访问的单位成本计；要得到同阶真实时间，摘要须占常数机器字，运算也须为常数时间。代数上只要求结合律，不要求交换律或逆元。若 $\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 分离工作量与并行性。中，整棵二叉树理路二叉树Binary tree由空树或根节点及左右两个子树槽位递归组成的有限结构；单孩子所在的左右位置也属于树形。有 $N-1$ 个内部节点，每个只做一次 $\otimes$，所以组合次数为 $N-1$，组合依赖的 span 为 $\lceil {\log }_{2}n\rceil$；$n=1$ 时两者均为零，仍须处理那个输出位置。

Downsweep：传播左侧上下文 ​

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

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

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

Downsweep 同样访问 $O(n)$ 个节点、深度 $O(\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+1))$。