并行计算的二元性：强扩展与弱扩展

玻尔百科

关键要点

强扩展旨在通过增加更多处理器来更快地解决一个固定规模的问题，但最终会受到代码串行部分的限制，正如阿姆达尔定律所述。
弱扩展通过增加更多处理器来处理一个按比例增大的问题，从而能够应对更大的挑战，但可能会受到全局通信成本的阻碍。
并行性能受到通信成本（表面积-体积问题）和负载不均衡等实际开销的影响，这些开销实际上增加了串行部分的比例。
扩展性原理以及计算与通信之间的张力是普适的，适用于天体物理学、人工智能和经济学等不同领域。

引言

在探索解决世界上最复杂问题的过程中——从模拟宇宙到训练高级人工智能——我们已转向并行计算的巨大威力。然而，仅仅增加更多计算能力并不能保证获得更快或更好的结果。核心挑战在于如何有效组织这种能力，这一难题揭示了两种截然不同的理念：强扩展和弱扩展。本文将探讨这种核心的二元性。首先，在“原理与机制”部分，我们将为两种扩展模型奠定理论基础，探讨 Amdahl 定律和 Gustafson 定律以及支配它们的现实世界开销。接着，在“应用与跨学科联系”部分，我们将看到这些原理在从地球物理学到经济学等不同领域中的实际应用。让我们首先考察支配并行性能的核心机制。

原理与机制

想象一下，你接到一项艰巨的任务：烘焙一个巨大无比、如国家般大小的披萨。你一个人绝无可能完成。唯一的方法是雇佣一支厨师大军，让他们并行工作。你如何组织这支军队以及披萨本身，揭示了高性能计算核心处一种深刻而美妙的二元性。这种二元性由两个基本概念所捕捉：强扩展和弱扩展。理解它们不仅仅是为了让计算机变得更快，更是为了理解当我们试图分而治之地解决一个复杂问题时所出现的内在限制和惊人机遇。

通往并行计算能力的两条路径

有两种主要方式来利用你的厨师大军。

第一种策略是更快地制作那个巨大的披萨。你从一个固定大小、国家般大的披萨开始，然后分配越来越多的厨师去做。每个新来的厨师都负责整体中更小的一块。目标是减少总烘焙时间。这就是强扩展的精髓：总问题规模固定，我们增加更多处理器（ $P$ ）来更快地解决它。

第二种策略是制作更多的披萨。你不是要做一个巨型披萨，而是要喂饱越来越多的人群。每雇佣一个新厨师，你就给他们一个个人尺寸的披萨来烘焙。随着你增加厨师，你生产的披萨总数会增长，但每个厨师负责的工作量保持不变。这就是弱扩展：每个处理器的工作负载是固定的，随着我们增加更多处理器，总问题规模（ $N$ ）也成比例增长。

这两种方法看似简单，但它们会导致截然不同的结果，并受到不同定律的支配和不同瓶颈的制约。

流水线：强扩展与阿姆达尔极限

让我们回到那个巨大的披萨。你有固定的工作量要做。如果你有一个厨师，完成时间是 $T(1)$ 。如果你雇佣一百个厨师（ $P=100$ ），你可能希望他们用百分之一的时间完成。单个厨师用时与多个厨师用时之比， $S(P) = T(1)/T(P)$ ，被称为加速比。在理想情况下，加速比应等于厨师的数量， $S(P) = P$ 。

但现实很快就介入了。并非所有任务都能被完美划分。假设披萨制作过程的某个部分——比如由主厨进行的最终检查和批准——本质上是串行的。无论有多少厨师在处理面团和配料，这个部分都需要固定的时间。这个不可分割的部分就是串行部分，我们可以称之为 $f$ 。剩下的部分， $1-f$ ，是可并行的部分。

即使并行部分完美加速，总时间也会受到那个顽固的串行部分的限制。在 $P$ 个处理器上的总时间 $T(P)$ 将是串行时间与新的、更快的并行时间之和： $T(P) = f \cdot T(1) + \frac{(1-f) \cdot T(1)}{P}$ 。这个简单的观察导出了一个强有力的结论，即阿姆达尔定律。加速比受限于：

S(P) = \frac{T(1)}{T(P)} = \frac{1}{f + \frac{1-f}{P}}

当你雇佣无限多的厨师（ $P \to \infty$ ）时，分母中的第二项消失了，但第一项仍然存在。最大可能加速比的上限是 $1/f$ 。如果你的代码中仅有 5% 是串行的（ $f=0.05$ ），那么即使使用一百万个处理器，你也永远无法获得超过 20 倍的加速比！这是对强扩展的一个发人深省的基本限制。例如，在一个多物理场仿真中，一个串行的耦合步骤约占总工作的 4.8%（ $f=1/21$ ），即使使用 64 个处理器，加速比也只有 16，并且永远不会超过 21。

串行部分的来源无处不在。在科学计算中，它不仅仅是显式的串行代码。通信是一个主要元凶。当你为更多的厨师把披萨切成越来越小的块时，“饼边”（厨师必须与邻居交谈的边缘）与“馅料”（他们可以独立工作的部分）的比例会增加。这就是臭名昭著的表面积与体积比问题。对于一个分解到 $P$ 个处理器上的三维仿真区域，计算量与子区域的体积（如 $N/P$ ）成比例，但通信量与其表面积（如 $(N/P)^{2/3}$ ）成比例。因此，通信与计算的比率会像 $P^{1/3}$ 一样增长，最终会压倒增加更多处理器带来的任何收益。这种不断增加的开销实际上增加了串行部分的比例，从而扼杀了性能。

扩张的厨房：弱扩展与古斯塔夫森视界

现在让我们考虑另一条路径：弱扩展。在这里，我们不是想更快地制作一个披萨，而是想制作更多的披萨。每个厨师都有自己的披萨。每个厨师的问题规模， $n_0=N/P$ ，是恒定的。理想的目标是，随着我们扩大厨房规模，求解时间保持不变。

这一观点由 John Gustafson 倡导，他指出，对于许多科学问题，我们不是想更快地解决同一个小问题，而是想用更大的计算机来解决更大的问题（例如，以更高的分辨率）。在这种情况下，并行工作的总量随 $P$ 的增加而扩展。串行部分虽然仍然存在，但在扩展后的总工作量中占的比例越来越小。

让我们看看在 $P$ 个处理器上的运行时间 $T(P)$ 。它由一个串行部分 $T_s$ 和一个并行部分 $T_{par}(n_0)$ 组成，由于每个处理器的工作量是恒定的，所以并行部分也是恒定的。因此， $T(P) = T_s + T_{par}(n_0)$ 。一个处理器完成这个巨大工作所需的假设时间将是 $T(1)_{\text{scaled}} = T_s + P \cdot T_{par}(n_0)$ 。那么，根据古斯塔夫森定律，扩展加速比为：

S_g(P) = \frac{T(1)_{\text{scaled}}}{T(P)} = \frac{T_s + P \cdot T_{par}(n_0)}{T_s + T_{par}(n_0)}

如果串行时间 $T_s$ 与并行工作相比很小，那么这个加速比几乎随 $P$ 线性增长。这是一个更为乐观的观点，它表明通过随机器扩展问题规模，我们可以有效地使用数千个处理器。

然而，弱扩展有其自身的阿喀琉斯之踵：全局通信。虽然每个厨师的本地工作以及与近邻的通信可能保持不变，但某些操作需要整个厨房的协调。想象一下，主厨需要找出所有烤箱中的最热点来调整全局烘焙时间（这是模拟中一个常见的步骤，称为 CFL 条件）。这需要一次“全体大会”，或者在计算中称为全局归约。其所需时间不随本地数据规模扩展，而是随参与者总数扩展，通常以 $O(\log P)$ 的速度增长。这个缓慢增长的开销项意味着，即使在弱扩展中，运行时间最终也会开始攀升，效率将降至理想的 100% 以下。

当现实来袭：开销与不均衡

并行计算的真实世界比这两种理想模型所揭示的要更加混乱和迷人。其他几个效应会极大地改变性能。

其中最显著的一个是负载不均衡。我们的模型假设并行工作可以被完美划分。但如果披萨的某些部分比其他部分更难准备呢？也许有一个部分铺满了需要精细放置的奇特配料。在科学模拟中，这种情况经常发生，例如在天体物理学代码中，恒星和气体聚集在模拟盒子里的一个小区域内。

如果工作分布不均，一些处理器会提前完成并处于空闲状态，而一个过载的处理器则决定了整个并行步骤的墙上时钟时间。商队的行进速度取决于最慢的那只骆驼。这种不均衡是另一种形式的开销。我们甚至可以将其建模为串行部分的有效增加。如果大小为 $\delta$ 的部分负载不均衡导致最慢的处理器耗时更长，它实际上就在我们的串行部分 $f$ 上增加了 $\delta$ ，使得新的加速比上限变为 $1/(f+\delta)$ 。这优雅地展示了不同物理来源的低效率如何能在同一个数学框架下被统一起来。

但也并非全是坏消息。有时，并行化会带来一个意想不到的、近乎神奇的额外好处。在单个处理器上解决问题时，数据可能太大而无法装入其快速的本地内存（CPU 缓存）中。处理器必须不断地从缓慢的主内存中获取数据，就像一个厨师的食材放在房间的另一头。当我们把问题分给多个处理器时（强扩展），每个处理器需要处理的数据块就变得小得多。如果该数据块变得足够小，可以完全放入快速缓存中，处理器的效率就会飙升。这可能导致超线性加速，即使用 $P$ 个处理器会带来超过 $P$ 倍的加速比。这是一个绝佳的例子，展示了算法策略如何与计算机硬件的物理现实相互作用。

物理学家的工具箱：分解问题

最后，我们分割问题的方式——区域分解策略——会产生深远的影响。想象一下对我们的三维仿真区域进行切分。“板状”分解（仅沿一个维度切分）导致每个进程有两个邻居。“笔状”分解（沿两个维度切分）导致四个邻居。这看起来可能差别不大，但实际上可能很大。

通信总时间不仅取决于你发送的数据量（带宽），还取决于你发送的消息数量（延迟）。成本可以建模为 $T_{\text{comm}} = \alpha \cdot (\text{消息数量}) + \beta \cdot (\text{发送字节数})$ ，其中 $\alpha$ 是延迟， $\beta$ 是带宽的倒数。笔状分解可能会发送更小的消息，但发送给更多的邻居，从而增加了延迟成本。最佳选择取决于具体的硬件和问题规模。对于某些全局操作，如三维傅里叶变换，笔状分解将每个进程的通信伙伴数量限制在 $O(\sqrt{P})$ ，而板状分解则强制与 $O(P)$ 个伙伴进行全对全通信。由于压倒性的延迟成本，后者的扩展性要差得多。

这凸显了计算科学家的工作。性能不是一个单一的数字。它是一个谜题。我的代码慢是因为底层算法对于大问题效率低下（算法可扩展性）？还是因为通信和负载不均衡等并行开销（并行可扩展性）？一个熟练的实践者必须设计实验来厘清这些效应——不仅测量时间，还要测量迭代次数、通信模式和算子复杂度——才能真正理解和优化他们的并行世界。对扩展性的追求是一次探索算法、硬件和通信法则之间基本相互作用的发现之旅。

应用与跨学科联系

既然我们已经探究了并行性能的齿轮与杠杆——Amdahl的串行部分和Gustafson的扩展工作负载——现在让我们退后一步，审视我们试图构建的宏伟机器。我们将要看到一些奇妙的东西。事实证明，让众人协同工作的挑战并非某一科学或工程领域所独有。无论我们是在模拟星系的诞生、预测天气、训练人工智能，甚至是对整个经济进行建模，同样的成功与失败的基本蓝图都会反复出现。

这种统一性的核心是一种美妙而简单的张力，是两种对立力量之间反复的对决。一方面，是我们问题的“体积”——需要执行的纯粹计算量。另一方面，是“表面”——协调我们分布在众多处理器上的问题碎片所需的通信。并行扩展的故事就是这场表面与体积之间永恒战斗的故事。

原型：网格上的宇宙

也许整个计算科学中最常见的任务就是在网格上模拟事物的变化。想象一块巨大的金属板，某些地方被加热，另一些地方被冷却。为了预测其温度将如何演变，我们可以将这块板切成一个由许多小方块组成的网格。下一刻每个方块的温度只取决于它自身的温度以及其紧邻方块的温度——这是一个优美的局部规则。

当我们将其并行化时，我们给每个计算机处理器分配一小块网格来管理。在一个时间步长内，处理器要完成其工作，只需要知道其邻居网格片最边缘方块的温度。这点信息，通常被称为“晕圈”或“幽灵区”，就是它需要请求的全部信息。剩下的工作它可以在辉煌的隔离中完成。

在这里，我们看到了最纯粹形式的表面积与体积比。计算量与网格片的面积（其二维“体积”）成正比，而通信量与其周长（其“表面”）成正比。当我们使用强扩展——保持总板面尺寸固定并增加更多处理器时——每个网格片会变小。周长收缩得比面积慢，因此通信与计算的比率变得更糟。最终，我们的处理器会花更多时间在边界上“喋喋不休”，而不是做有用的工作。

但在弱扩展中，我们保持网格片大小固定，并增加更多处理器来模拟一个越来越大的板面。在这里，每个网格片的周长与面积之比保持不变！理想情况下，执行一步所需的时间保持恒定。这就是弱扩展的力量：它使我们能够处理越来越大的问题，无论我们是在模拟热流，还是在地球力学模拟中模拟地壳内部的应力，这一原理都适用。

这个简单的想法具有深远的工程意义。邻居之间不断的“闲聊”提出了一个实际问题：对于我们的互连设备，是拥有一个超快的数据高速公路（高带宽， $\mathcal{B}$ ）更好，还是拥有一个极低的“上匝道”时间（低延迟， $\alpha$ ）更好？当强扩展使我们的网格片缩小时，消息就成了微小的耳语。时间主要由发送消息的启动成本所主导。但在弱扩展中，由于网格片很大，我们发送的是长长的数据队列，此时高速公路的容量才是关键。这也正是开发像 NVLink 这样的专用互连技术的原因——为了大幅降低延迟，并为其连接的强大 GPU 扩展强扩展的有效范围。

更深层次的结构与全局对话

当然，并非所有算法都是如此简单的局部事务。考虑一下多重网格方法，这是一种用于求解方程组的极其巧妙的方法。我们不只在细网格上工作，而是创建一系列越来越粗的网格。在粗网格上，信息只需几步就能传遍整个区域，从而快速解决大尺度误差。然后我们用这个粗网格解来修正细网格解。

这为我们的扩展故事增添了新的复杂性。大部分工作仍然是每个网格层级上的局部晕圈交换。但是，下探到最粗的单一网格再返回的过程可能成为一个瓶颈，一个所有并行工作都必须被汇集和重新分配的点。

这就给我们带来了一种新的通信方式，它远比晕圈交换的局部闲聊要求更高：全局对话。想象一下，你不是只和你的近邻交谈，而是需要计算整块板的平均温度。每个处理器都必须报告其局部平均值，然后一个处理器（或一系列处理器）必须将它们全部相加并做除法。这就是“全局归约”，其成本通常不随数据大小扩展，而是随参与者数量 $P$ 扩展，通常为 $\log P$ 。

这种全局对话是许多强大算法的阿喀琉斯之踵。著名的预条件共轭梯度（PCG）法是有限元分析的主力，它在每一次迭代中都需要进行数次这样的全局点积计算。在强扩展场景下，随着我们增加更多处理器，并行工作上花费的时间急剧下降，但用于这些全局归约的时间可能几乎不变甚至增加。这种开销，加上像在单个处理器上执行的粗网格求解这样的串行瓶颈，正是强扩展效率不可避免地下降的原因。我们甚至可以为湍流的直接数值模拟开发复杂的性能模型，来预测一个确切的处理器数量 $P^{\star}$ ，在该数量下，全局通信（对于基于 FFT 的方法）不断增加的成本会超过进一步并行化带来的好处。

超越网格：粒子、射线与算法选择

世界并不总是一个整齐有序的网格。如果我们正在模拟十亿颗恒星形成星系时的旋转之舞呢？在平滑粒子流体动力学（SPH）模拟中，基本对象是粒子，而不是网格点。然而，同样的扩展原则依然适用。工作内容包括计算来自附近粒子的力。当我们在处理器之间分配这些粒子时，我们再次面临一个通信问题：如何有效地找到并交换那些空间上彼此靠近但位于不同处理器上的粒子的数据。当我们分析这类模拟的结果时，我们使用完全相同的强、弱扩展效率指标来判断我们的并行代码性能如何。

或许，我们这次巡览中最深刻的教训来自于比较解决同一问题的不同方法。考虑一下在宇宙学中模拟辐射转移的挑战——即来自第一批恒星和星系的光是如何在宇宙中传播的。

一种直观的方法是长特征线法：从光源开始追踪每一束光线穿越宇宙。这对扩展性来说是灾难性的。一条光线是一个非局部对象；它可能穿越数百个处理器区域，需要一个复杂而缓慢的通信网络。
一种完全不同的方法是 M1 矩方法。我们不是追踪单个光线，而是在网格上对辐射场的平均量（其能量和通量）进行演化。这些方程更加抽象，但它们具有优美的局部性。一个网格单元的更新只依赖于它的邻居。突然之间，这个问题看起来就像我们简单的热方程一样，并且它的扩展性非常好。
这个比较教给我们一个至关重要的教训：有时，并行化的关键不在于巧妙的编码，而在于对问题本身的数学表述进行根本性的重新思考。算法的选择可能比任何硬件或软件优化都更重要。

新前沿：人工智能与经济学

你可能会认为这一切都只关乎物理学和工程学，这情有可原。但这些扩展定律的美妙之处在于它们的普适性。让我们前往两个完全不同的知识领域。

首先是人工智能。当我们训练一个像驱动现代人工智能那样的巨型神经网络时，任务通常非常庞大，必须分布在数百个 GPU 上。在一种称为数据并行的通用策略中，每个 GPU 处理一批不同的数据（图像、文本等）——这是一个完全并行的任务。但在每一步结束时，它们都必须就如何更新网络参数达成一致。它们必须对各自计算出的梯度求平均值。这是一个全局 all-reduce 操作，一次“全局对话”，其精神实质与 PCG 中的点积或 FFT 求解器中的全对全交换完全相同。并且它受完全相同的扩展定律支配。计算（前向/后向传播）与通信（梯度同步）之间的斗争定义了一个性能阈值，超过该阈值后，增加更多 GPU 会带来递减的回报。

其次是计算经济学。现代宏观经济模型，如异质性代理人新凯恩斯（HANK）模型，异常复杂。它们模拟数百万个别家庭和公司的决策，以理解整个经济。我们如何将其并行化？我们给每个处理器分配一个家庭子集进行模拟——这又是一个完全并行的任务。但在每个周期结束时，我们必须汇总它们的行为来确定利率和通货膨胀等整个经济范围的变量，这些变量随后又会反馈到下一周期的决策中。这种聚合，又一次，是一个归约操作。使用这些模型的经济学家面临着我们一直以来看到的同样选择：我们是使用强扩展来更快地求解一个固定规模的经济体，还是使用弱扩展在相同时间内求解一个更大、更详细的经济体？

一场普适的对话

从恒星的核心到人工智能的逻辑，再到市场的动态，并行扩展的原理提供了一种通用的语言。工作体积与通信表面之间的张力，局部闲聊与全局广播的不同特性——这些主题在各个学科中回响。理解它们并不仅仅是计算机科学家的技术练习。它是现代科学事业的一个基本组成部分。它使我们能够协同利用计算的力量，建立保真度越来越高的模型，并对我们周围的世界提出更大、更深、更大胆的问题。