第八章 并行算法 (Parallel Algorithms)

一、导读

1.1 本章学习目标

掌握并行算法设计的基本策略和模式

深入理解并行排序、并行搜索、并行图算法等经典并行算法

学会分析并行算法的工作（Work）、深度（Depth）和可伸缩性

理解分治策略在并行算法设计中的核心作用

掌握工作窃取（Work-Stealing）和 fork-join 并行框架的使用方法

了解并行算法在实际应用中的优化技术（如数据分片、缓存优化）

学会根据硬件特性和问题规模选择合适的并行算法

1.2 为什么本章如此重要

并行算法是利用多处理器性能的关键。随着多核处理器的普及，编写能够高效利用多核的程序变得越来越重要。并行算法的设计不仅需要正确的逻辑，还需要考虑任务分解、负载均衡、通信开销、缓存效应等多方面因素。

并行算法的设计与顺序算法有本质的不同。在顺序算法中，我们关注的是时间复杂度和空间复杂度；在并行算法中，还需要关注工作（总计算量）、深度（关键路径长度）和可伸缩性（随处理器数增加的性能表现）。一个"好"的并行算法不仅要在理论上高效，还要在实际硬件上能够充分利用资源。

分治策略是并行算法设计中最常用的方法。将问题分解为独立的子问题，递归地并行求解，然后合并结果。并行归并排序、并行快速排序、并行前缀和等都是基于分治策略。分治策略的优势在于子问题之间通常没有依赖关系，可以自然地并行执行。

fork-join 并行框架（如 Java 的 ForkJoinPool）提供了一种高层的并行编程抽象：程序员只需要将任务分解为子任务（fork），然后等待子任务完成并合并结果（join）。框架负责线程管理、任务调度和负载均衡。这种抽象大大简化了并行编程的复杂性。

1.3 核心问题引导

并行算法设计的基本策略有哪些？分治策略为什么如此重要？

如何设计一个高效的并行排序算法？并行归并排序和并行快速排序各有什么特点？

并行搜索（如并行二分搜索、并行图搜索）的设计挑战是什么？

工作窃取调度如何工作？它为什么能实现良好的负载均衡？

如何分析并行算法的可伸缩性？Amdahl 定律如何限制并行算法的性能？

在实际硬件上，哪些因素会影响并行算法的性能？如何优化？

二、核心概念详解

2.1 分治与并行算法

分治（Divide and Conquer）是并行算法设计中最自然的策略。其基本步骤是：将问题分解为若干个独立的子问题（Divide），递归地并行求解子问题（Conquer），合并子问题的解得到原问题的解（Combine）。

分治策略适用于并行算法的关键在于：子问题之间通常是独立的，可以并行执行。如果子问题的大小大致相等，则可以实现良好的负载均衡。合并步骤的复杂度决定了算法的深度。

并行归并排序是分治策略的经典应用：将数组分成两半，递归地并行排序每一半，然后合并两个有序数组。工作为 O(n log n)，深度为 O(n)（合并步骤的瓶颈）。使用并行合并算法可以将深度降到 O(log² n)。

并行快速排序：选择一个主元，将数组分为两部分，递归地并行排序。工作为 O(n log n)（平均），深度为 O(n)（最坏情况，当主元选择不当时）。通过随机选择主元或三数取中，可以使深度在期望意义下为 O(log² n)。

2.2 Fork-Join 并行框架

Fork-Join 框架是一种高层的并行编程抽象，它将并行计算建模为任务的递归分解。

Fork：创建一个新任务并异步执行。在实现中，fork 通常将任务放入工作线程的本地队列中。

Join：等待一个任务完成并获取其结果。如果任务尚未完成，当前线程可能帮助执行其他待处理的任务（工作窃取）。

Java 的 ForkJoinPool 是 Fork-Join 框架的标准实现。它维护一个工作线程池，每个线程有一个本地双端队列（deque）。新 fork 的任务放入当前线程的 deque 顶部（LIFO 顺序，有利于缓存局部性）。当线程的 deque 为空时，从其他线程的 deque 底部窃取任务（FIFO 顺序，减少冲突）。

使用 Fork-Join 框架的并行归并排序：

class MergeSortTask extends RecursiveTask<int[]> {
  protected int[] compute() {
    if (array.length < THRESHOLD) {
      return sequentialSort(array);
    }
    int mid = array.length / 2;
    MergeSortTask left = new MergeSortTask(leftHalf);
    MergeSortTask right = new MergeSortTask(rightHalf);
    left.fork();  // 异步执行左半部分
    int[] rightResult = right.compute();  // 当前线程执行右半部分
    int[] leftResult = left.join();  // 等待左半部分完成
    return merge(leftResult, rightResult);
  }
}

2.3 并行图算法

图算法的并行化面临独特的挑战：图的遍历通常有复杂的依赖关系，难以简单地分解为独立的子问题。

并行广度优先搜索（BFS）：每一层的节点可以并行处理。使用两个队列（当前层和下一层），并行处理当前层的所有节点，将新发现的节点放入下一层队列。挑战在于负载均衡——不同层的节点数可能差异很大。

并行最短路径（Bellman-Ford）：每轮迭代中，所有边可以并行处理（并行松弛操作）。工作为 O(V × E)，深度为 O(V × log V)（使用并行松弛）。

并行最小生成树（Borůvka 算法）：每轮中，每个连通分量并行找到其最小出边，然后合并连通分量。深度为 O(log V)，因为每轮至少将连通分量数减半。

并行图算法的主要挑战是数据局部性：图的邻接表表示可能导致大量的随机内存访问，缓存不友好。图分区（Graph Partitioning）技术将图分成多个子图，每个子图分配给一个处理器，减少跨处理器的通信。

2.4 并行数值算法

数值计算是并行算法最成功的应用领域之一。许多数值算法天然具有并行性。

并行矩阵乘法：最朴素的并行化是将结果矩阵的每个元素分配给一个线程计算。工作为 O(n³)，深度为 O(n)。使用 Strassen 算法可以将工作降到 O(n²·⁸¹)。使用分块技术可以优化缓存利用率。

并行线性方程组求解：高斯消元的并行化需要仔细处理依赖关系。LU 分解可以并行化每一列的消元操作。迭代法（如 Jacobi、Gauss-Seidel）的并行化更自然——每次迭代中所有变量的更新可以并行执行。

并行快速傅里叶变换（FFT）：Cooley-Tukey FFT 算法天然适合并行化。每一级的蝶形运算可以并行执行。工作为 O(n log n)，深度为 O(log² n)。

2.5 并行算法的优化技术

在实际硬件上运行并行算法时，需要考虑多种优化技术。

数据分片（Data Partitioning）：将数据分成多个块，每个块分配给一个处理器。分片策略影响负载均衡和通信开销。均匀分片适合均匀数据，非均匀分片（如基于范围的分区）适合倾斜数据。

缓存优化：通过数据布局优化（如矩阵的分块存储）和访问模式优化（如按行遍历）来提高缓存命中率。避免伪共享——确保不同线程访问的数据不在同一缓存行。

向量化（Vectorization / SIMD）：利用 SIMD 指令（如 SSE、AVX）同时处理多个数据元素。许多数值算法（如向量加法、矩阵乘法）可以自然地利用 SIMD。

通信优化：在分布式环境中，减少处理器之间的通信量是关键的优化目标。使用局部性原则（尽量在本地处理数据）和通信聚合（将多个小消息合并为一个大消息）来减少通信开销。

三、深入分析与讨论

3.1 负载均衡的挑战

负载均衡是并行算法设计中最具挑战性的问题之一。如果任务分配不均匀，某些处理器空闲而其他处理器忙碌，整体性能会大打折扣。

静态负载均衡：在运行前将任务均匀分配给处理器。适用于任务工作量可预测且均匀的场景。优势是零运行时开销，劣势是无法处理动态变化。

动态负载均衡：在运行时根据处理器的负载动态分配任务。工作窃取是一种动态负载均衡策略。优势是能处理不均匀的任务，劣势是有运行时开销。

自适应负载均衡：结合静态和动态策略。先静态分配，然后监控负载情况，必要时进行任务迁移。适用于任务工作量不确定但变化不大的场景。

3.2 并行算法的下界

许多并行算法问题存在理论下界，限制了可能的最优性能。

并行排序的下界：基于比较的排序，在 P 个处理器上的深度下界为 Ω(log n)（因为需要 Ω(n log n) 次比较，每次最多并行 P 次）。实际最优算法的深度为 O(log² n)（如并行归并排序的并行合并版本）。

并行前缀和的下界：深度下界为 Ω(log n)，因为每个输出可能依赖于所有输入。Blelloch 算法达到了这个下界。

图问题的下界：许多图问题（如连通分量、最小生成树）的并行深度下界为 Ω(log n)，因为可能需要 Ω(log n) 轮通信才能传播信息。

3.3 并行编程模型的选择

选择并行编程模型需要考虑问题的特性、硬件平台和性能目标。

共享内存模型：适用于多核服务器。使用线程和同步原语，或 Fork-Join 框架。优势是编程模型简单，劣势是可伸缩性受限于单机。

消息传递模型（MPI）：适用于分布式集群。使用显式的消息发送和接收。优势是可伸缩性好，劣势是编程复杂。

GPU 计算模型（CUDA/OpenCL）：适用于大规模数据并行。数千个线程执行相同的程序，处理不同的数据。优势是吞吐量极高，劣势是只适合规则的数据并行。

混合模型：结合多种模型。如在节点内使用共享内存（OpenMP），节点间使用消息传递（MPI）。

四、实践案例

4.1 并行归并排序的实现

使用 Fork-Join 框架实现并行归并排序。关键优化：当子数组大小低于阈值时切换到顺序排序（减少任务分解的开销）；使用临时数组避免合并时的额外分配。

性能分析：在 8 核处理器上，对 1000 万整数排序，并行版本比顺序版本快约 5-6 倍（不是 8 倍，因为合并步骤的开销和任务分解的开销）。

4.2 并行矩阵乘法

使用分块（Blocking）技术实现并行矩阵乘法。将矩阵分成 B × B 的块，每个块适合 L1 缓存。使用 OpenMP 或 Fork-Join 并行化外层循环。

性能分析：在 8 核处理器上，对 2000 × 2000 矩阵乘法，分块 + 并行版本比朴素顺序版本快约 20 倍（8 倍来自并行，约 2.5 倍来自缓存优化）。

五、常见误区与注意事项

5.1 过度分解任务

将任务分解得太细会导致大量的任务管理开销（创建、调度、同步），可能超过并行化带来的收益。应该设置合理的阈值，当任务足够小时切换到顺序执行。

5.2 忽视合并步骤的开销

分治策略中，合并步骤的复杂度往往被忽视。如果合并步骤的复杂度过高，它可能成为并行算法的瓶颈。应该尽量设计合并简单的算法。

5.3 假设线性加速比

由于同步开销、负载均衡问题和不可并行化的部分，实际加速比通常低于理论值。应该在实际硬件上测量性能，而不是仅依赖理论分析。

5.4 忽视数据局部性

并行算法的性能不仅取决于计算量，还受到内存访问模式的影响。糟糕的数据局部性（如随机访问、伪共享）可能导致性能远低于预期。

六、本章小结

本章介绍了并行算法的设计策略和优化技术。分治是并行算法最自然的策略，Fork-Join 框架提供了高层的并行编程抽象。并行排序、图算法和数值算法各有不同的设计挑战。负载均衡是影响并行性能的关键因素。并行算法存在理论下界，限制了可能的最优性能。在实际硬件上，缓存优化、向量化和通信优化是提升并行性能的重要技术。

七、思考题与练习

实现并行归并排序，使用 Fork-Join 框架。分析不同阈值对性能的影响。

设计一个并行快速排序算法，分析其在不同数据分布下的性能。

实现并行 BFS，比较不同并行策略（按层并行 vs 按节点并行）的性能。

实现并行矩阵乘法，比较朴素并行、分块并行和 SIMD 优化的性能差异。

设计一个并行算法来计算大规模数组的中位数。分析其工作和深度。

实现工作窃取调度器，测量其在不同任务粒度下的负载均衡效果。

设计一个并行算法来求解稀疏线性方程组（Ax = b）。分析其并行度。

讨论：GPU 计算模型适用于哪些并行算法？不适用于哪些？给出你的分析。