专题进阶 · 并行算法推荐总顺序 · 第 108 / 148 课

从排他前缀和出发,手算 Blelloch 的上扫与下扫,理解工作高效的并行前缀计算。

先学会这些,再进入本课 前缀和 并行归约
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 并行算法

并行前缀和Parallel Scan

先归约再分发部分和,工作有效算法可在 O(n) 工作量下取得 O(log n) 深度。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

从排他前缀和出发,手算 Blelloch 的上扫与下扫,理解工作高效的并行前缀计算。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

每个位置都要知道自己之前元素的总和,怎样避免逐个等待前一项,也避免重复做大量加法?

02一步步得到方法

先区分包含当前元素与排除当前元素

输入 [3,1,7,0] 的排他扫描为 [0,3,4,11],第 i 项等于下标小于 i 的所有元素之和。包含当前元素的扫描则是 [3,4,11,11],可以在排他结果上逐项加原输入。

一种直接倍增方法每轮读更远的左邻居,虽然只有 O(log n) 轮,却做 O(n log n) 总工作。Blelloch 扫描使用树形上扫和下扫,把总工作降为 O(n)。

上扫先构造区间和

长度补成二次幂,空位填加法单位元 0。上扫先求长度 2 区间的和,再求长度 4、8 等区间,结果存放在各区间最右端。根节点最终保存整个数组总和。

扫描需要的是每个区间之前的总和,所以把根改成 0 开始下扫。对每个父区间,左孩子继承父前缀,右孩子得到父前缀加左子区间总和。

下扫传递前缀而非重复求和

原地布局中要先暂存左孩子的旧区间和,再用父前缀覆盖左孩子,最后把暂存值加到右孩子。顺序写反会丢失必要信息。

同一树层的区间互不重叠,可同时处理。以下代码串行模拟这些层,展示正确的数据依赖;真实实现还需要线程与层间同步。

03把一个小例子完全算清楚

输入 [3,1,7,0]。

步骤计算与状态为什么这样做
上扫[3,4,7,11]长度 2 局部和为 4、7,根为 11
根置零、第一轮下扫[3,0,7,4]左半前缀 0,右半前缀 4
第二轮下扫[0,3,4,11]每个叶子得到它之前的总和

窄屏可左右滑动表格,阅读完整计算与理由。

排他扫描结果为 [0,3,4,11],总和 11 可以单独保存。

04为什么这个方法成立

  1. 上扫不变量:每个已完成节点存储其区间的元素和。
  2. 下扫不变量:进入某节点时,已有该区间之前的总和;左孩子继承,右孩子再加左区间和。
  3. 叶子区间只含一个元素,因此叶子收到的值正是排他前缀;补零不改变真实元素的前缀。

05把推导翻译成代码

Python · Blelloch 扫描的串行层级模拟

def exclusive_scan(values):
    n = len(values)
    size = 1
    while size<n:
        size *= 2
    data = list(values)+[0]*(size-n)
    width = 2
    while width<=size:
        for end in range(width-1,size,width):
            data[end] += data[end-width//2]
        width *= 2
    data[-1] = 0
    width = size
    while width>=2:
        for end in range(width-1,size,width):
            left = end-width//2
            old_left = data[left]
            data[left] = data[end]
            data[end] += old_left
        width //= 2
    return data[:n]

print(exclusive_scan([3,1,7,0]))

逐个理解关键决定

data[-1] = 0
根从整段总和改成整段之前的空前缀。
old_left = data[left]
覆盖左节点前保存其区间和,否则右前缀无法计算。
data[:n]
移除二次幂补齐部分,只返回原输入对应的结果。

06时间、空间与实现范围

补齐长度小于 2n(n>0),上扫、下扫工作均为 O(n),跨度 O(log n)。

串行模拟耗时 O(n),使用 O(n) 空间;在真实并行机器上,层间同步与内存访问也有成本。

07改变条件,检查哪里会出错

根置零之前忘记保存总和

如果还需要总和,应先保存;扫描输出的最后一项不包含最后元素。

把原地改写次序颠倒

会把左子树总和覆盖掉,右前缀随之错误。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

[2,5,1] 的排他扫描是什么?

需要一点提示

第 0 项是空前缀。

查看解析与答案

[0,2,7]。

练习 2 · 边界与辨析

如何从排他结果得到包含当前项的前缀和?

需要一点提示

逐项加原数组。

查看解析与答案

inclusive[i]=exclusive[i]+values[i]。

练习 3 · 变式与迁移

扫描可如何分配并行输出的位置?

需要一点提示

把每个任务的输出个数作扫描。

查看解析与答案

排他扫描给出各任务不重叠输出区间的起始偏移,用于压缩、过滤等操作。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

NVIDIA · CUDA Best Practices Guide

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。