2.2 并行算法设计与优化

2.2 并行算法设计与优化

本节摘要：有了编程模型，还得会把串行算法拆成可并行的形式。本节讲清并行算法设计的核心技巧：分治（把大问题递归切成独立子问题）、 reductions（把分散的中间结果归约成全局结果）、数据分布（块分布、循环分布、随机分布的取舍）、负载均衡（静态与动态分配）。重点讲通信开销的评估方法——通信时间由启动延迟加消息长度乘带宽决定，这是并行算法性能的核心制约。

核心问题

阅读完本节，你应当能够：

1. 用分治把一个问题拆成可并行的子问题
2. 设计 reductions 来归约分散结果
3. 选对数据分布策略并说明理由
4. 估算一个并行算法的通信开销
5. 区分稠密计算与稀疏计算的不同并行策略

一、问题与直觉

很多人以为"会写并行程序就会设计并行算法"，其实差得远。编程模型给你的是"怎么让多个单元协同"的接口，但"怎么把一个问题拆成能协同的形式"是另一门学问。同样是矩阵乘法，按输出元素切、按内积维度切、按子块切，性能能差好几个数量级——区别全在算法设计。

并行算法设计的核心挑战是：怎么切才能让每个单元都有活干（负载均衡）、单元间少搬数据（通信开销小）、数据就近访问（局部性好）。这三者往往冲突：切得太细通信爆炸，切得太粗负载不均；按输出切局部性差，按数据切又要同步。好的并行算法就是在这几者间找到平衡。

这门学问最实用的切入点，是理解几个核心技巧（分治、 reductions、数据分布）和一把衡量标尺（通信开销模型）。掌握了这些，面对一个新问题你就有章可循，而不是凭感觉切。

二、核心原理

2.1 分治：递归切分

分治是把大问题递归切成独立子问题、各子问题并行求解、再合并结果。它是最自然的并行思路——很多问题本身就递归定义（如归并排序、快速傅里叶变换、矩阵乘法的 Strassen 算法），分治能直接暴露其内在并行性。

分治的关键是子问题间要尽量独立——独立度越高，并行度越大。如果子问题间有强依赖（比如动态规划的填表顺序），并行度就受限，得用特殊技巧（如对角线扫描、分块）来挖掘有限的并行性。

分治在实际工程里还要面对一个矛盾：递归切分会产生"合并代价"。切得越细，并行度越高，但合并子结果的步骤越多，每一步合并都要做通信或同步。所以分治算法的并行不是"切到原子级最好"，而是有个最优切分粒度，在并行收益和合并代价之间取平衡。这个最优粒度通常和通信启动延迟、带宽、以及子问题的计算量相关，可以粗略估算：当子问题的计算时间小于一次通信的启动延迟时，再切就没意义了。这也是为什么实践中分治算法会设一个"基例大小"，小于这个大小就转成串行求解，不再继续切。

矩阵乘法的 Strassen 算法是分治的一个经典案例，它把两个 n×n 矩阵的乘法拆成七个子矩阵乘法（而不是朴素的八个），把复杂度从 O(n³) 降到约 O(n^2.81)。理论上这是渐近更优的，但实际工程里 Strassen 在中等规模下往往跑不赢朴素算法——因为它要做更多的数据搬运和加法，常数因子大。只有当矩阵足够大、乘法的渐近优势压过常数因子时，Strassen 才占优。这个例子说明一个普遍规律：并行算法的"理论最优"和"工程最优"经常不是同一个，选算法要看具体规模和硬件参数。

2.2 Reductions：归约分散结果

很多并行算法的子任务各自算出一个局部结果，最后要归约（reduction）成全局结果。比如并行求一千万个数的和，每个线程算一部分的和，最后把所有部分和加起来——这个"加起来"就是 reduction。

reduction 看似简单，却是并行性能的关键。朴素的串行归约（一个线程依次加完所有部分和）会把并行度打回原形。高效的并行归约用树形结构：第一轮两两相加，第二轮结果再两两相加，log N 轮完成，每轮的加法并行执行。

MPI 的 Allreduce、CUDA 的 warp shuffle 这些底层原语，本质上都是高效的归约实现。理解 reduction 的树形结构，能帮你读懂很多并行代码的性能特征。

2.3 数据分布：怎么切数据

分布式内存里，数据怎么分布到各节点，直接决定通信开销。几种常见策略：

块分布把连续的数据分给同一节点，局部性好（访问邻居不用通信），但如果数据计算量不均匀（有些块重有些轻），会负载不均。循环分布轮流分配，负载更均衡，但访问邻居常要跨节点通信。块循环是小块轮流，在两者间折中。选哪个取决于数据的计算分布特征——计算均匀用块分布，计算不均用循环或块循环。

数据分布还有一个更深的考量：通信模式要和分布匹配。一个网格模拟里，每个节点只和邻居交换边界，这种"规则邻居通信"最适合块分布，因为邻居大概率在同一节点或相邻节点。但如果是 N 体问题（每个粒子受所有其他粒子影响），任何分布都改变不了"全连接"的通信结构，这时数据分布的优化空间就小，得靠算法层面的近似（比如 Barnes-Hut 用树结构把远距离粒子聚成一团近似计算）来减少通信。换句话说，数据分布能解决"通信局部"的问题，但解决不了"通信拓扑本身密集"的问题。

数据分布还要考虑稀疏性。稀疏矩阵的非零元分布不均，按行均匀切可能让某些节点拿到全是非零元的"重行"、另一些拿到全是零的"轻行"。这时常用的技巧是先按非零元数量重排矩阵（让每行非零元数大致均衡），再做块分布——这就是图划分在数据分布里的典型应用。

2.4 通信开销模型

通信开销是并行算法性能的核心制约。一个点对点消息的传输时间，可以用一个简单模型估算：通信时间等于启动延迟加上消息长度除以带宽。

这个模型揭示两个优化方向：减少消息数量（每条消息有固定启动延迟，消息越多开销越大），和增大每条消息的数据量（让带宽利用率上去）。所以并行算法常把多个小消息合并成一个大消息（消息聚合），用通信次数换通信量。

第三个技巧——重叠通信和计算——也很重要。如果一个节点在发数据时，接收方还能继续算别的，通信延迟就被"藏"起来了。MPI 的非阻塞通信、CUDA 的流异步，都是为此设计的。

把这个模型用具体数字感受一下。假设一次通信的启动延迟是 5 微秒，带宽是 10 GB 每秒。发一个 1 KB 的小消息，传输时间约 0.1 微秒，加上 5 微秒启动延迟，总共 5.1 微秒——绝大多数时间花在启动上，带宽根本没用上。发一个 1 MB 的大消息，传输时间约 100 微秒，启动延迟还是 5 微秒，总共 105 微秒——这时带宽才是主导。这解释了为什么"消息聚合"如此关键：把 1000 个 1 KB 小消息合成一个 1 MB 大消息，时间从 5100 微秒降到 105 微秒，快了快五十倍。

但消息也不是越大越好。单条消息过大会占满缓冲区、增加故障重传的代价，还可能触发流控让网络拥塞。实际工程里有个经验阈值（通常在几 MB 到几十 MB），超过它继续增大消息，带宽利用率不再明显提升，反而增加管理开销。找到这个甜点要靠测量，不是拍脑袋。

计算通信重叠的实现也有讲究。它要求程序里有"可以独立于通信进行的计算"。如果一个 kernel 发完数据就空等结果，重叠就没意义。好的实现是显式地把计算分成"依赖远端数据的"和"不依赖的"两部分，先发起非阻塞通信请求远端数据，同时推进本地不依赖那部分数据的计算，等本地算完再去等远端数据到达。这要求算法设计阶段就考虑数据依赖的解耦，而不是写完代码再硬塞重叠。

三、工程实践要点

3.1 稠密与稀疏的不同策略

稠密计算（如矩阵乘法、FFT）和稀疏计算（如稀疏矩阵向量乘、图算法）的并行策略差别很大。稠密计算的计算量随数据量多项式增长，计算强度高，通信开销相对小，容易高效并行。稀疏计算的计算量随非零元素线性增长，计算强度低，通信开销占比大，并行效率难做高。

稀疏和图算法的并行是 HPC 的难题，因为数据分布不均、访问模式不规则、通信频繁。这类问题常需要特殊的图划分、随机化、近似算法等手段。

3.2 负载均衡

💡 关键直觉：并行系统的整体速度被最慢的单元卡死——这就是"木桶效应"。一个单元比其他慢一倍，整个并行就慢一半，因为其他单元得等它。负载均衡的目标就是让所有单元的工作量尽量相等。

负载均衡分静态和动态。静态均衡在编译时或启动时分配好，适合计算量可预测的任务（如稠密矩阵）。动态均衡在运行时根据实际进度调整，用工作窃取（work stealing）等机制让闲的单元从忙的单元那偷任务，适合计算量不可预测的任务（如自适应网格细化、图遍历）。动态均衡更灵活但有调度开销，静态均衡开销小但不够灵活。

3.3 别过早优化

⚠️ 常见坑：一上来就追求极致的并行效率，把算法改得面目全非。正确的做法是先写一个正确的并行版本（哪怕效率不高），用性能分析工具测出瓶颈在哪（是通信、是负载、还是局部性），再针对性优化。盲目优化常导致代码复杂度爆炸而收益有限——并行优化的投入产出不是线性的，少数几个瓶颈往往贡献了大部分开销，集中火力打它们才划算。

本章回顾

• 分治把大问题递归切成独立子问题，是最自然的并行思路，子问题独立度决定并行度。
• reductions 用树形结构归约分散结果，log N 步完成，是很多并行原语的底层。
• 数据分布有块、循环、块循环三种，按计算均匀度选，影响局部性和负载。
• 通信时间等于启动延迟加长度除带宽，优化方向是减少消息数、增大数据量、重叠通信计算。
• 负载均衡防木桶效应：静态适合可预测任务，动态（工作窃取）适合不可预测任务，别过早优化。

下一章讲怎么调优这些并行程序，以及管理运行它们的集群和软件栈。