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为什么这个方法成立
- 每个当前元素对应原数组某个不相交连续区间的和。
- 合并相邻两个元素得到其区间并集的和,奇数末尾直接保留,区间仍不重不漏。
- 最后唯一元素覆盖全部输入,因此是总和;空输入以加法单位元 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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
5 个元素每层长度是多少?
需要一点提示
每次取上取整的一半。
查看解析与答案
5→3→2→1,共 3 层。
归约最大值的空输入单位元如何选?
需要一点提示
需要不会改变任何合法值的初值。
查看解析与答案
可用负无穷;若类型不支持或空集合不应有最大值,也可明确报错。
为什么不能把连续减法改成树?
需要一点提示
比较 (8−3)−1 与 8−(3−1)。
查看解析与答案
分别为 4 与 6,减法不满足结合律,重组改变语义。