并行计算、可复现性与性能测量

先固定科学问题，再并行实现

并行化改变执行顺序、数据位置和归约树，却不应悄悄改变所求物理问题。开始优化前应冻结方程、离散网格、边界条件、收敛容差、随机估计量、输入单位和输出定义，并保留一个小规模串行基准。若并行版本使用更粗网格、不同停止准则或更少样本，它与串行时间之比不是同一问题的加速比。

性能至少有三层口径：内核时间只覆盖核心算子；求解时间含迭代、通信和同步；端到端时间还含读入、预处理、写出与启动。时间统一用 s，内存用 B，通信带宽用 $\mathrm{B\,s^{-1}}$，浮点吞吐用 $\mathrm{FLOP\,s^{-1}}$。报告必须说明层级，不能把最短内核时间宣传成完整实验用时。

科学正确性也分层：离散方程残差是否满足容差，守恒量和解析基准是否通过，统计误差是否在预算内，以及改变并行度后可观测量是否保持约定等价。性能提升不能替代这些检查。

任务图、工作量与关键路径

把程序写成有向无环依赖图：节点是任务，边表示数据必须先产生。总工作量 $W$ 是单处理单元执行全部任务的时间，关键路径长度 $S$ 是依赖链上不可并行的最短完成时间。理想的 $p$ 路执行时间满足

平均可用并行度上限为 $W/S$。增加线程超过该值不会继续线性加速。真实调度还要支付任务创建、队列、同步和数据移动成本；任务太细时，开销可大于计算本身。

任务分解适合彼此相对独立的物理阶段或样本，例如多个参数点、Monte Carlo 独立副本和不同频率响应。数据分解把同一算子作用域切开，例如网格区域、粒子集合或矩阵块。混合方案可在节点间分区域、节点内分线程，并把独立样本分配给不同组。设计时应让逻辑任务 ID 与物理对象稳定对应，而不是与临时线程号绑定。

负载均衡比较每个处理单元的有效工作。若最慢单元时间为 $t_{\max}$、平均为 $\bar t$，可用 $\bar t/t_{\max}$ 作为无量纲均衡效率。静态规则适合成本可预知的均匀网格；动态队列适合粒子聚团、接受率不同或自适应网格，但会增加调度和结果顺序的不确定性。

数据分解、邻域通信与内存边界

局域偏微分算子常按空间区域分解。每个子域保存内部单元和一层或多层 halo，步进前与相邻子域交换边界数据。三维立方子域边长为 $n$ 个单元时，内部工作量通常按 $n^3$ 增长，单层六面 halo 按 $6n^2$ 增长，所以通信相对计算约为 $6/n$。并行度增加使每个子域变小，表面—体积比上升，这是强扩展最终饱和的重要原因。

单条消息的简化时间模型为

其中启动延迟 $\alpha$ 用 s，消息大小 $m$ 用 B，有效带宽 $B$ 用 $\mathrm{B\,s^{-1}}$。合并小消息可减少多次 $\alpha$，却可能延迟可用数据；非阻塞通信只有在其与独立计算真正重叠时才隐藏成本。测得的 $B$ 还受拓扑、争用、内存拷贝和通信库影响，不应直接用硬件标称峰值。

例 1：三维区域分解的表面—体积比

全局网格为 $512^3$，用 $4^3=64$ 个相同子域时，每个内部区域为 $128^3$。一层六面 halo 的近似元素数与内部元素数之比为

$$r_{64}=\frac{6(128)^2}{128^3}=0.0469.$$

改用 $8^3=512$ 个子域，每边只剩 64 个内部单元：

$$r_{512}=\frac{6(64)^2}{64^3}=0.0938.$$

并行度增加八倍，近似通信数据相对工作量翻倍。角和棱可能被重复计数，实际字节数还要乘变量数、每元素字节和 halo 层数；该比值用于解释趋势，不替代实测通信时间。

内存也可能先于算力成为限制。每个进程若复制全局系数表、网格元数据或输出缓冲，弱扩展内存不会保持常数。报告应给每处理单元峰值常驻内存和全局总内存，并区分用户数组、通信缓冲、运行时和文件缓存。

强扩展、弱扩展与两个加速定律

强扩展固定问题规模 $N$，定义

弱扩展保持每个处理单元工作量近似不变，让总规模随 $p$ 增长，常报告 $E_p^{\mathrm{weak}}=T_1(N_1)/T_p(pN_1)$。弱扩展问题并非同一 $N$，不能把它的时间比称为强加速。两种实验都应使用相同物理时间区间、收敛容差和输出频率，否则比较混入工作量变化。

Amdahl 模型设固定问题中可并行比例为 $f$：

它把通信和负载不均衡隐含进串行或额外开销，适合解释固定工作量上限。Gustafson 模型从固定并行运行时间出发，让并行工作随处理单元增加；若缩放运行中串行比例为 $s$，缩放加速为

两式回答不同问题，不能拿同一个“串行比例”无条件互换。

例 2：Amdahl 与 Gustafson 的不同结论

固定问题有 $f=0.97$ 可并行，在 $p=32$ 时

$$S_{32}=\frac1{0.03+0.97/32}=16.6, \qquad E_{32}=0.518.$$

即使无限增加处理单元，上限也只有 $33.3$。若另一个弱扩展实验在 32 路运行中测得串行时间占比 $s=0.03$，则 $S_{32}^{\mathrm{scaled}}=32-31(0.03)=31.1$。后者扩大了总工作量，并不推翻前者对固定问题的限制。

超线性加速也不一定造假：分片后工作集进入更快缓存，或串行基准发生换页，可能得到 $S_p>p$。这时应报告缓存、内存容量和基准实现，而不是直接宣称算法突破线性上限。

延迟、吞吐与流水线

延迟是一个请求、一步时间积分或一个样本从开始到完成的 s 数；吞吐是在稳态时间内完成的任务数，例如 $\mathrm{samples\,s^{-1}}$ 或 $\mathrm{cell\ updates\,s^{-1}}$。批处理和流水线可提高吞吐，却可能增加单个任务排队延迟。实时控制关注最坏或高分位延迟，离线参数扫描通常关注总吞吐和完成全部工作的 wall time。

对于 $R$ 个独立副本，若单副本用一张设备需 $t$ 秒，同时运行 $q$ 个且无争用，理想总时间约为 $\lceil R/q\rceil t$。但共享内存带宽、文件系统和启动开销会降低吞吐。报告平均值之外还应给中位数、最慢批次或分位数；只选最快一次会隐藏抖动和资源争用。

异步加速器调用尤其容易误测：主机提交内核后立即返回，不同步就只计了排队时间。端到端测量要在起点前完成必要预热，在终点显式等待设备完成，并说明数据传输是否计入。

计时、剖析与 roofline 上界

可靠计时使用单调时钟，固定输入和线程数，区分冷启动与稳态，运行足够长以超过时钟分辨率，并重复多次报告分布。首次运行可能含即时编译、页面分配和缓存填充；是否排除这些成本取决于真实使用场景。单次交互任务应保留冷启动，长期服务可另报预热后的稳态。

剖析先回答时间花在哪里，再优化。调用采样适合找热点，硬件计数器可估计指令、缓存未命中和内存流量，通信追踪可显示等待与拥塞。插桩本身有开销，采样频率和追踪缓冲也应记录。优化一个只占总时间 $5\%$ 的内核，即使无限快，端到端最多改善约 $5.3\%$。

roofline 模型以运算强度 $I=N_{\mathrm{FLOP}}/N_{\mathrm{byte}}$ 衡量每搬运一字节做多少浮点运算，估计性能上界

$I$ 用 $\mathrm{FLOP\,B^{-1}}$，内存带宽用 $\mathrm{B\,s^{-1}}$，乘积用 $\mathrm{FLOP\,s^{-1}}$。模型指出算力受限还是带宽受限，但要求明确哪些层级的字节流和哪类浮点指令；把缓存流量与主存带宽混配会得到错误屋顶。

例 3：带宽受限内核的性能上界

某内核运算强度 $I=0.25\,\mathrm{FLOP\,B^{-1}}$，实测可持续内存带宽 $B_{\mathrm{mem}}=200\,\mathrm{GB\,s^{-1}}$，设备峰值为 $2.0\,\mathrm{TFLOP\,s^{-1}}$。带宽屋顶为

$$B_{\mathrm{mem}}I=(200)(0.25)=50\,\mathrm{GFLOP\,s^{-1}},$$

远低于算力峰值。若实际达到 $35\,\mathrm{GFLOP\,s^{-1}}$，相对该问题屋顶为 $70\%$，而不是相对 $2.0\,\mathrm{TFLOP\,s^{-1}}$ 的 $1.75\%$ 就断言实现失败。

并行随机流不是“每个线程加一”

固定一个主种子只确定某个随机数生成器的起点。并行程序还必须规定生成器算法、版本、子流划分和逻辑任务到子流的映射。若简单令每个进程从相邻种子开始，不能自动保证子流独立；改变进程数还会改变哪些样本收到哪些随机数。

更稳健的办法是按不随并行布局变化的逻辑标识派生子流，例如由 masterSeed、副本 ID、时间块 ID 和变量 ID 组成键，使用有定义的跳跃或计数型生成器。这样副本 17 无论由哪个进程执行，都获得同一随机流。若目标是独立统计重复，则不同副本应使用不重叠子流，并报告副本间方差；若目标是逐位重放，则检查点必须保存计数器或完整生成器状态。

例 4：与进程数无关的随机子流

需要运行逻辑副本 $r=0,\ldots,7$。定义子流键 $K_r=H(20260714,r)$，其中 $H$ 是版本固定的确定性散列，再把 $K_r$ 交给支持独立键的计数型生成器。两进程时每个进程处理四个 $r$，四进程时各处理两个；输出最终按 $r$ 排序。

因为随机数由 $r$ 而非进程号决定，改变并行度不会改变每个副本的轨迹。若改用 seed = master + rank，四进程运行的 rank 2、3 在两进程运行中不存在，结果集合随布局改变，不能逐副本比较。

随机可复现不等于统计正确。仍需检查热化、自相关、有效样本量、分布覆盖和置信区间；同一错误算法在固定种子下也会稳定地产生同一错误答案。

浮点归约、非确定性与等价标准

浮点加法不满足结合律。并行求和的树形结构由任务完成顺序、线程数和通信库决定，所以相同输入可能只在末几位不同。考虑双精度数量级 $a=10^{16}$、$b=-10^{16}$、$c=1$：

因为 $b+c$ 在该量级舍入回 $-10^{16}$。大规模正负抵消、能量差或残差归约会放大这一效应。

可采用固定归约树、按指数分桶、成对求和、Kahan 补偿或更高精度累加改善稳定性；但编译器融合运算、不同数学库和设备指令仍可能改变位级结果。确定性归约通常牺牲调度自由和性能，应依据科学需求选择。

复现标准至少分四级：同环境位级一致；不同并行度在绝对或相对容差内数值一致；随机输出的均值、方差或分布在统计检验范围内一致；独立实现对同一物理可观测量一致。容差必须由离散、迭代、舍入和统计误差预算给出，不能看到差异后再临时放宽。

例 5：为守恒量定义可复算判据

某无量纲总质量初值 $M_0=1$，离散与迭代验证表明误差预算为 $3\times10^{-10}$，不同归约树的舍入差上界估为 $2\times10^{-12}$。可预先规定

$$|M(t)-M_0|\le3.1\times10^{-10}$$

作为物理数值验收，同时另记输出哈希是否逐位相同。若两个并行度分别给 $1.8\times10^{-10}$ 与 $1.9\times10^{-10}$，它们虽非位级相同，仍通过数值标准；若漂移为 $10^{-6}$，不能归咎于“浮点随机性”。

最小复现实验包与故障恢复

可复算记录至少包括：原始输入及其哈希、单位与预处理；代码提交标识和未提交差异；依赖、编译器、优化与数学模式；操作系统、处理器或加速器型号、内存、驱动和通信库；进程线程布局与环境变量；随机生成器、主种子和子流规则；运行命令、开始时间、wall time、退出状态；输出 schema、日志、校验和及分析脚本版本。容器可封装用户空间，却不能消除内核、驱动、硬件和并行调度差异。

检查点应原子写入或先写临时文件再提交，并保存物理状态、步数、时间、求解器历史和随机流状态。恢复后先核对版本、输入和检查点哈希；只恢复粒子位置而重置随机生成器，会得到一条新的随机轨迹。对于允许统计等价而非逐轨迹复现的任务，也应明确这是新副本还是原副本续跑。

性能记录和科学结果必须绑定同一运行身份。否则最快时间可能来自一个参数文件，最终图却来自另一个环境。最小报告同时给正确性门禁、性能分解、扩展曲线原始数据和复现标准，并保留失败运行的错误上下文，避免只发布“最好的一次”。

练习

练习 1：关键路径上限标记完成

所属知识

任务图

难度

3/5

给定 $W=120\,\mathrm s$、$S=15\,\mathrm s$，求最大理想加速。

查看提示

使用 $T_p\ge \max(W/p,S)$。

查看解答

$W=120\,\mathrm{s}$、$S=15\,\mathrm{s}$ 时并行度上限 $W/S=8$；即使 $p\to \infty$，$T_p$ 不小于 15 s，加速不超过 8。

练习 2：消息合并标记完成

所属知识

通信

难度

3/5

说明为何合并小消息可能降低通信时间，也可能增加等待。

查看提示

分别计算多次 $\alpha+m/B$ 与一次 $\alpha+$总字节/B。

查看解答

在总字节不变且无重叠时，合并减少启动延迟次数；是否更快还取决于数据就绪时间、缓存和并发。

练习 3：强弱扩展标记完成

所属知识

扩展性

难度

3/5

区分两种扩展实验并写出效率定义。

查看提示

先判断总问题规模是否固定。

查看解答

固定 N 比较 $T_p$ 是强扩展；每处理单元固定工作量、总 $N\propto p$ 是弱扩展。二者的效率分母和科学问题不同。

练习 4：吞吐与延迟标记完成

所属知识

性能口径

难度

2/5

解释批处理为何可提高吞吐但恶化延迟。

查看提示

一个看单任务时间，一个看单位时间完成数。

查看解答

批量增大可能提高设备利用率和 samples/s，却增加排队及单样本完成时间；两项应分别报告。

练习 5：并行随机流标记完成

所属知识

复现性

难度

4/5

设计不随进程数改变的随机副本映射。

查看提示

不要让随机流只依赖 rank。

查看解答

用稳定逻辑任务 ID 派生独立子流，记录生成器、主种子和派生规则；改变进程数后任务仍取得同一子流。

练习 6：归约差异标记完成

所属知识

浮点

难度

4/5

为并行求和制定可复算验收标准。

查看提示

区分位级、数值和统计一致。

查看解答

先由误差预算规定绝对/相对或统计容差，再用固定归约树等方法控制差异；末位不同不自动失败，超预算也不能只归因于舍入。

关系与资源

• 离散化、误差预算与模型验证
• 浮点数表示、舍入与误差传播
• 统计估计、区间与检验
• 计算物理综合项目与复习

课程 · 2015

Numerical Fluid Mechanics

Pierre Lermusiaux

用于核对 P11 的离散化误差、场方程网格算法、时间步稳定性、边界条件和数值验证流程。

打开官方来源

MIT OpenCourseWare 2.29 用于核对离散求解器、时间推进、稳定性和网格计算中的性能边界。本文的加速结论仅对固定的问题定义、测量层级和硬件环境成立。