第二章 时间与空间 (Time and Space)
一、导读
1.1 本章学习目标
理解并发程序中时间和空间复杂度的特殊性，掌握并发算法的分析方法
掌握工作（Work）和深度（Depth/Span）的概念及其在并行算法分析中的作用
理解 Brent 定理及其对并行算法设计的指导意义
学会分析并发数据结构的空间开销和时间开销的权衡
掌握并行算法的加速比（Speedup）和效率（Efficiency）的定义与计算方法
理解 Amdahl 定律和 Gustafson 定律对并行计算的限制
了解并发程序中缓存一致性和内存层次结构对性能的影响
1.2 为什么本章如此重要
在并发编程中，时间和空间的含义比顺序编程更加复杂。一个并发算法的性能不仅取决于总的计算量，还取决于任务之间的依赖关系——即使有无限多的处理器，有依赖关系的任务也不能同时执行。因此，并发算法需要两个维度的度量：总工作量（Work）和关键路径长度（Depth/Span）。
Brent 定理是并行算法分析中的基石。它告诉我们：给定一个有 W 个工作单元和 D 深度的计算，在 P 个处理器上的执行时间上界为 W/P + D。这个简单的公式揭示了并行计算的基本限制：即使处理器数量趋于无穷，执行时间也不会低于 D（关键路径长度）。
Amdahl 定律从另一个角度揭示了并行计算的限制：如果程序中有一部分是不可并行化的（必须顺序执行），那么无论使用多少处理器，加速比都有一个上限。例如，如果 10% 的代码必须顺序执行，那么即使使用无限多的处理器，加速比也不会超过 10 倍。
理解这些基本的时空关系，对于设计高效的并发算法至关重要。它帮助程序员在算法设计阶段就预估性能上限，避免在不可行的方向上浪费时间。
1.3 核心问题引导
什么是并行算法的"工作"和"深度"？它们如何共同决定算法的性能？
Brent 定理如何指导并行算法的设计？它告诉我们什么基本限制？
Amdahl 定律和 Gustafson 定律有什么区别？它们各自适用于什么场景？
并发数据结构的空间开销与顺序数据结构有什么不同？
缓存一致性协议如何影响并发程序的性能？
如何衡量一个并行算法的"好"与"坏"？有哪些标准？
二、核心概念详解
2.1 工作与深度
在并行算法分析中，两个最基本的度量是工作（Work）和深度（Depth，也称为 Span）。
工作（W）是指算法执行的总操作数，即如果只有一个处理器，完成算法所需的时间。它等同于顺序算法的时间复杂度。例如，对 n 个元素求和，无论是否并行，总的工作量都是 n 次加法。
深度（D）是指算法的关键路径长度，即从开始到结束的最长依赖链。它代表了即使有无限多的处理器，算法也需要的最少时间。例如，对 n 个元素求和，如果使用二叉树归约（每层将相邻的两个元素相加），深度为 log n。
工作和深度的关系决定了一个算法的并行潜力。工作/深度（W/D）的比值反映了算法中可以并行执行的部分有多大。比值越大，说明算法的并行度越高，可以从更多的处理器中获益。
2.2 Brent 定理
Brent 定理是并行计算理论中的一个基本结果。它指出：对于一个有 W 个工作单元和 D 深度的计算，在 P 个处理器上的执行时间 T(P) 满足：
T(P) ≤ W/P + D
这个定理的含义深刻：执行时间由两部分组成——可并行部分（W/P，随处理器数增加而减少）和不可并行部分（D，与处理器数无关）。即使 P → ∞，执行时间也不会低于 D。
Brent 定理的直接推论是：设计并行算法时，应该同时最小化 W 和 D。一个工作量大但深度小的算法，在处理器少时表现好；一个工作量小但深度大的算法，在处理器多时表现好。最优的算法在两者之间取得平衡。
Brent 定理还提供了一个调度策略的理论基础：在每一步，如果有可用的处理器，就分配给就绪的任务。这种贪心调度在 Brent 定理的意义上是最优的。
2.3 Amdahl 定律与 Gustafson 定律
Amdahl 定律描述了并行计算的固有限制。假设程序中_fraction_ f 的代码必须顺序执行，(1-f) 可以并行化，则在 P 个处理器上的加速比为：
Speedup(P) = 1 / (f + (1-f)/P)
当 P → ∞ 时，加速比趋近于 1/f。这意味着即使有无限多的处理器，加速比也受限于顺序部分的比例。例如，如果 f = 0.01（1% 的代码必须顺序执行），最大加速比为 100 倍。
Gustafson 定律从不同的角度看待这个问题。它认为，当处理器数量增加时，问题规模也可以相应增大。如果顺序部分的工作量不随问题规模增长，而并行部分的工作量线性增长，则加速比可以接近线性。
这两个定律并不矛盾，而是适用于不同的场景。Amdahl 定律适用于固定问题规模的场景（如实时系统），Gustafson 定律适用于可扩展问题规模的场景（如科学计算）。
2.4 并发数据结构的空间分析
并发数据结构通常需要额外的空间来支持并发访问。这些额外空间用于存储同步信息（如锁、标记位）、版本信息（用于乐观并发控制）或冗余数据（用于减少竞争）。
例如，一个并发链表可能需要每个节点包含一个锁，额外空间为 O(n)。一个并发哈希表可能需要每个桶包含一个锁，额外空间为 O(桶数)。一个无锁数据结构可能需要使用 CAS（Compare-And-Swap）操作，在失败时需要重试，可能导致额外的内存分配。
空间分析还需要考虑缓存行的影响。现代处理器的缓存以缓存行（通常 64 字节）为单位进行传输。如果两个线程频繁读写同一缓存行中的不同变量（即使它们是不同的变量），也会导致缓存一致性的开销，这种现象称为"伪共享"（False Sharing）。避免伪共享通常需要在变量之间插入填充（Padding），增加了空间开销。
2.5 并行算法的加速比与效率
加速比（Speedup）是衡量并行算法性能的基本指标：S(P) = T(1) / T(P)，其中 T(1) 是单处理器上的执行时间，T(P) 是 P 个处理器上的执行时间。
理想情况下，S(P) = P（线性加速比），意味着使用 P 个处理器可以将时间缩短为 1/P。但在实际中，由于同步开销、通信开销和不可并行化的部分，S(P) < P。
效率（Efficiency）定义为 E(P) = S(P) / P，衡量处理器的利用程度。理想情况下 E(P) = 1。效率随处理器数增加而下降是常见的现象，因为同步和通信的开销随处理器数增加。
另一个重要的指标是可扩展性（Scalability）：随着处理器数和问题规模的同步增长，效率是否能保持恒定。弱可扩展性（Weak Scalability）指问题规模与处理器数成比例增长时效率恒定；强可扩展性（Strong Scalability）指固定问题规模时增加处理器数的表现。
三、深入分析与讨论
3.1 并行算法设计的核心权衡
并行算法设计的核心权衡是：减少深度（增加并行度）vs 减少工作（总计算量）。许多并行算法通过将工作量的增加来换取深度的减少。
例如，前缀和（Prefix Sum）问题：给定数组 a[0..n-1]，计算 s[i] = a[0] + a[1] + ... + a[i]。顺序算法的工作为 O(n)，深度为 O(n)。Blelloch 的并行前缀和算法的工作为 O(n log n)，深度为 O(log n)。工作量增加了 log n 倍，但深度从 O(n) 降到了 O(log n)。
在 P 个处理器上，顺序算法的时间为 O(n)，并行算法的时间为 O(n log n / P + log n)。当 P > log n 时，并行算法更快。这说明：增加的工作量是值得的，因为它换来了更小的深度，使得算法可以从更多的处理器中获益。
3.2 缓存一致性对性能的影响
在多处理器系统中，缓存一致性协议对并发程序的性能有重要影响。当多个处理器同时读写同一个缓存行时，缓存一致性协议需要在处理器之间传递消息来维护一致性。
在 MESI 协议中，一个缓存行可以处于四种状态：Modified（已修改，只有本处理器有最新值）、Exclusive（独占，只有本处理器有副本，且与内存一致）、Shared（共享，多个处理器有副本，且与内存一致）、Invalid（无效）。
当一个处理器要写入一个处于 Shared 状态的缓存行时，它必须先使其他处理器的副本无效化（Invalidation），这需要处理器间的通信。如果多个处理器频繁交替读写同一个缓存行（"缓存行弹跳"，Cache Line Bouncing），会导致大量的通信开销，严重降低性能。
3.3 工作窃取调度
工作窃取（Work-Stealing）是一种高效的并行调度策略。每个处理器维护一个本地任务队列。当一个处理器完成本地队列中的所有任务时，它会从其他处理器的队列中"窃取"任务。
工作窃取的优势在于：减少了任务分配的中心化瓶颈（每个处理器独立管理本地队列）；自动实现负载均衡（忙碌的处理器的任务被空闲的处理器窃取）；缓存友好（本地任务在本地执行，数据局部性好）。
工作窃取调度的分析表明：在 P 个处理器上，一个有 W 个工作和 D 深度的计算，执行时间的期望为 O(W/P + D + log W)。额外的 log W 项来自窃取的开销，通常很小。
四、实践案例
4.1 并行归约（Parallel Reduction）
并行归约是将 n 个元素通过二元运算合并为一个值的操作（如求和、求最大值）。顺序归约的工作为 O(n)，深度为 O(n)。
并行归约使用二叉树结构：第一层将相邻的元素两两合并（n/2 个并行操作），第二层将第一层的结果两两合并（n/4 个并行操作），以此类推。总工作仍为 O(n)，深度降为 O(log n)。
在实际实现中（如 CUDA 的归约核函数），还需要考虑共享内存的 bank 冲突、线程束的同步等问题。通过分块归约和 warp-level 的优化，可以进一步提升性能。
4.2 并行前缀和的实现
Blelloch 的前缀和算法分为两个阶段：上扫（Up-sweep/Reduce）阶段和下扫（Down-sweep）阶段。
上扫阶段：从叶子到根，构建二叉树的归约结构。对于偏移 d = 1, 2, 4, ..., n/2，并行执行：对所有 i，a[i2d + 2d - 1] += a[i2d + d - 1]。
下扫阶段：从根到叶子，传播前缀和。先将根节点设为 0，然后对于偏移 d = n/2, ..., 4, 2, 1，并行执行：对所有 i，tmp = a[i2d + d - 1]，a[i2d + d - 1] = a[i2d + 2d - 1]，a[i2d + 2d - 1] += tmp。
总工作为 O(n log n)，深度为 O(log n)。在 P 个处理器上的执行时间为 O(n log n / P + log n)。
五、常见误区与注意事项
5.1 忽视深度的影响
许多程序员只关注总工作量（Work），忽视了深度（Depth）的重要性。即使工作量很大，如果深度很小，算法仍然可以在大量处理器上高效执行。反之，如果深度很大，即使工作量不大，算法也无法从多处理器中获益。
5.2 伪共享问题
伪共享（False Sharing）是并发程序中常见的性能陷阱。当两个线程频繁读写位于同一缓存行的不同变量时，会导致缓存行在处理器之间反复传递，性能可能下降 10 倍以上。解决方法是在变量之间插入填充，使它们位于不同的缓存行。
5.3 过度并行化
不是所有问题都适合并行化。如果问题的深度很大（依赖链很长），或者问题规模很小，并行化的开销（线程创建、同步、通信）可能超过收益。在决定并行化之前，应该先估算加速比是否值得。
5.4 线性加速比的幻觉
许多并行算法在理想条件下（无同步开销、完美负载均衡）可以达到接近线性的加速比。但在实际中，同步开销、负载均衡问题、NUMA 效应等因素会使实际加速比远低于理论值。评估并行算法时，应该在实际硬件上测量，而不是仅依赖理论分析。
六、本章小结
本章介绍了并发算法的时间和空间分析框架。工作（Work）和深度（Depth）是并行算法的两个基本度量。Brent 定理给出了在 P 个处理器上的执行时间上界：W/P + D。Amdahl 定律揭示了顺序部分对加速比的限制，Gustafson 定律展示了问题规模可扩展时的乐观前景。并发数据结构的空间分析需要考虑同步信息和缓存行的影响。加速比和效率是衡量并行算法性能的基本指标。理解这些时空关系对于设计高效的并发算法至关重要。
七、思考题与练习
计算以下场景的并行算法深度：（a）n 个元素的并行归约；（b）n × n 矩阵乘法的并行算法；（c）n 个元素的并行排序（如并行归并排序）。
使用 Brent 定理，计算在 P = 100 个处理器上执行一个 W = 10⁸、D = 1000 的算法所需的时间。
如果一个程序 5% 的代码必须顺序执行，使用 Amdahl 定律计算在 16 个处理器上的加速比。
实现一个并行前缀和算法，分析其工作和深度。
解释伪共享现象，并设计一个实验来测量其对性能的影响。
比较并行归并排序和并行快速排序的工作和深度。哪个更适合在多核上运行？
设计一个并行算法来计算一个有 n 个顶点、m 条边的图的连通分量。分析其工作和深度。
讨论：在什么情况下，增加处理器数量反而会导致性能下降？