4. 并行算法设计基础

设计一个并行算法，本质上是在回答三个相互纠缠的问题：把计算切成什么、切多细、切完之后如何让各处理器尽量同时收工。这三个问题分别对应分解策略、并行粒度和负载均衡，而它们最终都要受通信与同步开销的约束，并通过加速比与可扩展性定律来检验。本节围绕这条主线展开，并给出可操作的判断依据。

一、两种基本分解策略

数据分解（域分解）把待处理的数据集合划分到各处理器，每个处理器对本地数据执行相同或相近的计算。它适用于数据规模大、计算模式统一的问题，例如有限差分网格、矩阵分块乘法、粒子模拟的区域划分。以二维泊松方程在 1024×1024 网格上用 Jacobi 迭代为例，若用 16 个进程做块状划分，可切成 4×4 的子域，每个子域 256×256；每个进程每轮只需与上下左右邻居交换一圈边界（halo）数据，内部点完全本地计算。

任务分解（功能分解）把计算过程拆成不同的任务，每个任务完成不同的操作，再通过数据流连接。它适用于计算步骤异质、存在流水线或依赖关系的场景，例如“读入→变换→归约→输出”的处理链，或稀疏矩阵求解中“符号分解、数值分解、三角求解”三个阶段。任务分解的关键是识别任务间的依赖方向与数据传递量，避免把强耦合的操作硬拆到不同处理器上。

实际系统常采用混合分解：先按数据划分大块，再在块内按任务分工。选择依据可以概括为：若各数据元素的计算逻辑相同且规模占主导，优先数据分解；若计算阶段差异明显、存在天然流水线，优先任务分解。

二、并行粒度：切多细才合适

粒度指一个并行任务所包含的计算量，通常用“计算时间 / 通信时间”的比值来衡量。粒度太细，任务数多、每次计算量小，通信与同步开销占比上升，管理开销压过有效计算；粒度太粗，任务数少于处理器数，部分处理器空闲，并行度不足。

设单个任务的本地计算时间为 T_comp，一次通信（含启动延迟与传输）时间为 T_comm，则效率大致随 T_comp/(T_comp+T_comm) 变化。工程上的经验做法是：先按处理器数确定任务数下限（一般不少于处理器数，常取 2～10 倍以留出负载均衡余地），再通过增大每任务数据块来提高计算通信比。例如上例中若把子域从 64×64 增大到 256×256，边界交换量按周长增长而计算量按面积增长，计算通信比约提升 4 倍，这正是粗化粒度的收益来源。

三、负载均衡：让所有处理器同时收工

并行程序的完成时间由最慢的那个处理器决定。负载不均衡的常见来源包括：数据分布不均（如非结构网格单元数差异）、计算量随数据变化（如稀疏矩阵非零元分布不均）、以及动态演化导致的不平衡（如粒子迁移、自适应加密）。

静态均衡在运行前一次性划分，适合计算量可预估的场景，常用方法有块划分、循环划分和块循环划分。以 1000 个任务分给 8 个进程为例：块划分每进程约 125 个连续任务，循环划分按 i mod 8 分配，块循环划分以块大小 4 轮转。当各任务耗时相近时块划分局部性好；当任务耗时有规律波动时，块循环划分更能摊平差异。

动态均衡在运行中调整，适合计算量不可预估的场景，典型策略是任务池加工作窃取：主进程维护待处理任务队列，空闲进程主动领取；或采用主从模式由调度者按需派发。动态均衡的代价是调度通信与数据迁移，因此任务粒度不能太小，否则调度开销会抵消均衡收益。

四、通信与同步开销

并行开销主要来自三处：点对点或集合通信的数据传输、屏障与锁带来的同步等待、以及为保持一致性而产生的额外计算（如 halo 更新、归约树）。降低开销的常用手段包括：合并小消息为大消息、用非阻塞通信重叠计算与传输、减少全局屏障次数、用局部归约替代全局归约。需要强调的是，通信开销与网络拓扑、消息大小和并发度都相关，不能只用“消息条数”估算。

五、加速比与可扩展性定律

加速比定义为 S(p) = T(1)/T(p)，即单处理器时间与 p 个处理器时间之比。Amdahl 定律从固定问题规模出发，若串行部分占比为 f，则 S(p) ≤ 1/(f + (1−f)/p)，当 p 趋于无穷时上限为 1/f。例如 f = 0.05 时，无论用多少核，加速比不超过 20。这提醒我们：优化并行部分之前，先压缩串行瓶颈往往收益更大。

Gustafson 定律则从固定时间出发，认为问题规模可随处理器数增长，此时 S(p) = p − f(p−1)，可扩展性表现为“规模扩大后仍能保持效率”。两者并不矛盾，而是对应两种使用场景：强可扩展关注固定规模下增加核数的效率，弱可扩展关注规模与核数同步增长时的效率。

并行效率 E(p) = S(p)/p 是判断设计是否值得的直接指标。若某次 16 进程运行得到 S = 12.8，则 E = 0.8，说明有 20% 的算力被开销吃掉，应回头检查粒度是否过细、负载是否不均、同步是否过频。

六、一个可操作的检查清单

面对一个新问题，可按以下顺序推进：先判断计算模式是否统一，选定数据分解或任务分解；再按处理器数确定任务数下限，用计算通信比粗化粒度；然后评估数据与计算量分布，选择静态或动态均衡；接着列出通信点与同步点，尝试合并消息、重叠传输；最后用强/弱可扩展两组实验测加速比与效率，定位瓶颈属于串行部分、通信还是负载不均。下表给出常见现象与对应处置，可作为调优时的对照参考。

需要强调的是，上述参数与数值均为教学示例中的合理假设，用于说明判断逻辑；真实系统的最优粒度与均衡策略必须结合具体硬件、网络和问题特征实测确定。分解、粒度、均衡、开销与可扩展性这五个要素并非线性步骤，而是一个需要反复迭代的设计闭环：每一次加速比测量都在告诉你，上一轮的设计假设是否成立。