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

用树形求和区分总工作量与依赖深度,理解结合律及浮点求和差异。

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

并行归约Parallel Reduction

用树状合并完成求和等操作,工作 O(n)、理想深度 O(log n);浮点加法顺序会影响舍入。

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

本课要建立的能力

用树形求和区分总工作量与依赖深度,理解结合律及浮点求和差异。

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

01先把问题说具体

八个数求和,顺序累加要等待前一个结果,怎样让互不依赖的加法同时进行?

02一步步得到方法

把长链改成树

先把相邻两个数分别相加,再对这些局部和两两相加,直到只剩一个。每一层的加法彼此独立,但下一层必须等待上一层完成。

对 n=8,顺序链的依赖深度为 7 次加法;平衡树只需 3 层。总加法次数仍是 7,所以并行缩短的是依赖链,没有凭空减少总工作。

工作量与跨度分开算

工作量 W 是全部操作数量,跨度 S 是无限处理器下最长依赖链。树形归约 W=O(n)、S=O(log n)。使用 P 个处理器时,运行时间至少受 W/P 和 S 两者限制,还要考虑调度、同步与内存访问。

若当前层为奇数个元素,最后一个直接进入下一层,不与不存在的元素相加。本课 CPU 代码按顺序模拟每层,显示算法结构,不能据此声称获得真实并行加速。

运算次序改变需要什么条件

数学整数加法具有结合律,所以任意分组结果相同;最大值、按位或等运算也可归约。减法和除法一般不满足结合律,不能随意重组。

浮点加法受舍入影响,并不严格结合。不同归约树可能产生微小甚至显著差异,需要根据目标选择更高精度、补偿求和或可复现归约方案。

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

输入 [1,2,3,4,5,6,7,8]。

步骤计算与状态为什么这样做
第 1 层[3,7,11,15]4 次独立加法
第 2 层[10,26]2 次独立加法
第 3 层[36]最后 1 次加法

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

总共 7 次加法、3 层依赖,和为 36。

04为什么这个方法成立

  1. 每个当前元素对应原数组某个不相交连续区间的和。
  2. 合并相邻两个元素得到其区间并集的和,奇数末尾直接保留,区间仍不重不漏。
  3. 最后唯一元素覆盖全部输入,因此是总和;空输入以加法单位元 0 处理。

05把推导翻译成代码

Python · 按轮模拟树形归约

def tree_sum(values):
    level = list(values)
    trace = [level.copy()]
    if not level:
        return 0,trace
    while len(level)>1:
        next_level = []
        for i in range(0,len(level),2):
            next_level.append(level[i]+level[i+1] if i+1<len(level) else level[i])
        level = next_level
        trace.append(level.copy())
    return level[0],trace

print(tree_sum(list(range(1,9))))

逐个理解关键决定

range(0,len(level),2)
每对输入只参与一个局部合并。
i+1<len(level)
处理非二次幂长度,末尾元素原样传递。
trace.append(level.copy())
记录各轮便于观察依赖树;它是 CPU 模拟,不包含线程。

06时间、空间与实现范围

工作 O(n),树高 O(log n);此串行模拟实际运行时间仍 O(n)。

各层长度形成几何级数,保存全部层仍为 O(n) 空间,不能把每层都误算成 n 个元素。

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

并行时间就是总工作量除线程数

还受依赖链、同步、带宽和线程利用率限制。

浮点结果必须逐位等于顺序求和

分组改变可导致不同舍入路径。

08从手算到独立迁移

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

练习 1 · 复现与理解

5 个元素每层长度是多少?

需要一点提示

每次取上取整的一半。

查看解析与答案

5→3→2→1,共 3 层。

练习 2 · 边界与辨析

归约最大值的空输入单位元如何选?

需要一点提示

需要不会改变任何合法值的初值。

查看解析与答案

可用负无穷;若类型不支持或空集合不应有最大值,也可明确报错。

练习 3 · 变式与迁移

为什么不能把连续减法改成树?

需要一点提示

比较 (8−3)−1 与 8−(3−1)。

查看解析与答案

分别为 4 与 6,减法不满足结合律,重组改变语义。

继续深入这个专题

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

NVIDIA · CUDA Best Practices Guide

理解之后,继续递进

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