玻尔百科解决日益庞大和复杂问题的雄心——从模拟气候到设计新药——推动了对巨大计算能力的需求。并行计算通过将任务划分给多个处理器，是我们实现这一目标的主要手段。然而，简单地增加处理器数量并不能保证速度成比例地提升。衡量成功的真正标准是并行可扩展性：即应用程序有效利用不断增加的处理器数量的能力。
不幸的是，性能常常受到意想不到的瓶颈的阻碍，其中通信开销和代码的串行部分使我们无法完全发挥硬件的潜力。本文旨在通过剖析支配并行性能的核心原则来弥补这一知识鸿沟。
首先，我们将探讨基础的原理与机制，从阿姆达尔定律描述的经典限制到古斯塔夫森定律更乐观的视角，并审视算法设计中决定可扩展性的关键权衡。随后，应用与跨学科联系部分将展示这些原理如何在不同科学领域中应用，揭示算法的选择如何成为从量子化学到广义相对论等领域释放高性能计算全部潜力的关键。
想象你有一项艰巨的任务要完成——比如，拼一个一百万片的拼图。如果你雇一个朋友帮忙，你会直觉地期望工作时间减半。如果你雇了九十九个朋友，你可能会梦想着在百分之一的时间内完成。这个简单而美好的想法就是并行计算的梦想。我们将加速比 定义为一个工人所需时间 与 个工人所需时间 的比值。我们的梦想是 。
但任何真正尝试过与一大群人一起拼图的人都知道，现实要复杂得多。不可避免地，会有人说：“等等，我们先找出所有的边块。” 这个单一的任务，需要所有人协调，变成了一个瓶颈。无论有多少人可以各自拼凑自己的部分，寻找边块的这个环节都使整个努力串行化了。这正是并行可扩展性面临的根本挑战。
在1960年代，计算机架构师 Gene Amdahl 将这一洞见形式化，成为了我们现在所称的阿姆达尔定律。他指出，任何任务都是两种工作的混合：一部分（比例为 ）是完全可并行的，另一部分（比例为 ）是固有串行的。想象一个厨师团队准备一场宴会。切菜可以并行完成——厨师越多，速度越快。但如果只有一个烤箱来烘焙最后的主菜，那么烤箱就成了一个串行瓶颈。
让我们来追溯其逻辑。如果一个厨师完成任务的总时间是 ，那么花在可并行部分的时间是 ，花在串行部分的时间是 。当我们引入 个厨师时，并行工作可以分配给他们，耗时为 。然而，串行工作仍然需要相同的时间，即 ，因为一次只能有一个厨师来做（或者烤箱一次只能放一道菜）。因此，使用 个厨师的总时间是：
加速比 则是：
请注意这个简单公式的后果。随着处理器数量 趋向于无穷大， 项趋于零，加速比会触及一个硬性上限：。如果你的程序哪怕只有 是串行的（），那么你所能实现的最大加速比永远是 ，无论你拥有一千个还是一百万个处理器！
这可能具有欺骗性。一个现代服务器应用程序可能表现出很高的并发性，有数千个线程准备运行。然而，如果它们都频繁地排队等待访问一个由锁（一种一次只能由一个线程持有的数字“令牌”）保护的单一共享资源，那么该临界区就是纯粹串行的。想象一个工作负载，其中一个任务耗时 毫秒： 毫秒是可并行的本地计算， 毫秒在串行临界区中。在这里，可并行的比例 仅为 。即使有大量的核心，加速比的上限也仅为 。阿姆达尔定律为我们提供了一个关于强可扩展性（即通过增加更多处理器来更快地解决一个固定大小问题）的重要而清醒的视角。
几十年来，阿姆达尔定律被解读为大规模并行计算的一个根本障碍。但在1980年代，John Gustafson 和他在桑迪亚国家实验室的同事们，在使用当时首批大规模并行计算机之一时，注意到他们实现的加速比远远超出了阿姆达尔定律似乎允许的范围。这是怎么回事？
他们意识到他们玩的是一场不同的游戏。他们不是用新的超级计算机来更快地解决同样的老问题，而是用它来解决更大的问题。这不像一个厨师团队更快地做同一份小餐，而是制作一场单个厨师根本不可能完成的盛宴。
这就是弱可扩展性的视角，被形式化为古斯塔夫森定律。我们不再固定总问题规模，而是固定每个处理器的负载，并让总问题规模随处理器数量的增加而增长。让我们从这个新视角重新审视我们的加速比公式。设在一台拥有 个处理器的并行机器上花费的时间归一化为 。这段时间由一个串行部分 和一个并行部分 组成，使得 。现在，同样规模的问题在单个处理器上需要多长时间？串行部分仍然需要时间 ，但原本分布在 个处理器上的并行部分，将需要 倍的时间，即 。因此，单处理器的总时间是 。
于是，可扩展的加速比为：
关键的洞见在于，如果我们保持每个处理器的负载固定，那么对于大型问题，总执行时间中的串行部分比例 通常会变得非常小。一个固定的启动成本（问题 中的 ）与随问题规模扩展的大规模并行计算相比，变得可以忽略不计。随着问题规模的增长，并行部分占主导地位， 趋近于零，加速比 趋近于 。这是一个更为乐观的前景，也是我们今天衡量从气候建模到天体物理学等最大规模科学模拟的标准。
这两条定律，阿姆达尔定律和古斯塔夫森定律，为我们设定了舞台，它们是这片土地的法则。但它们都隐含地假设了底层的计算方法，即配方本身，是固定的。实际上，并行应用程序的性能取决于硬件和算法之间深度的相互作用。这引导我们做出一个关键的区分：
算法可扩展性：你的算法的计算成本是否随着问题规模 高效地增长？例如，对于一个迭代求解器，我们会问：随着我们细化模拟网格（增加 ），求解所需的迭代次数是否保持不变？如果答案是肯定的，那么该算法就被认为是“最优的”或“算法上可扩展的”。
并行可扩展性：对于给定的算法，当改变处理器数量 时，实际运行时间（wall-clock time）如何变化？这就是我们在强可扩展性（固定 ，增加 ）和弱可扩展性（固定 ，同时增加两者）中测量的指标。
一个算法可能在算法上是最优的，但并行可扩展性很差，反之亦然。科学计算的“圣杯”是找到在两种意义上都可扩展的算法。唯一了解的方法是设计能够分离这些效应的实验，例如，首先固定机器规模（）来研究迭代次数与问题规模（）的关系，然后固定问题规模（）来研究运行时间与机器规模（）的关系。
设计可扩展的算法是一门管理权衡的艺术。在用于求解支配物理世界方程的庞大数值方法领域，这一点表现得尤为清晰。
许多经典的迭代算法，如高斯-赛德尔（Gauss-Seidel）方法，通过遍历问题中的未知数，并使用其邻居的最新计算值来更新每一个未知数。这就像一排人传递水桶：第二个人必须等收到第一个人的水桶后才能开始。这产生了一个串行的据依赖。乘性施瓦茨（Multiplicative Schwarz）方法是这一思想的更复杂版本，其中更新是按子域顺序依次应用的。这些方法通常很强大，因为它们能快速传播信息，所以在很少的迭代次数内就能收敛。但它们的串行性使其难以并行化。
另一种选择是做出妥协。在雅可比（Jacobi）方法中，每个未知数都仅使用前一次迭代的“旧”值来同时更新。这就像水桶传递队伍中的每个人同时向前迈出一步。加性施瓦茨（Additive Schwarz）方法是这一思想的块版本：所有子域的校正都基于相同的全局状态并行计算，然后相加。这些方法具有极好的并行性，但它们通常收敛得慢得多，因为它们使用的是过时的信息。
选择是严峻的：是用较少的并行性换取更快的收敛，还是用较慢的收敛换取更多的并行性。幸运的是，巧妙的设计有时能让我们两全其美。对于结构化网格上的问题，红黑着色（red-black ordering）排序可以打破高斯-赛德尔方法的串行依赖。通过像棋盘一样对网格点进行着色，我们注意到所有“红”点只依赖于“黑”点，反之亦然。这样我们就可以在一个并行扫描中更新所有红点，然后在另一个并行扫描中更新所有黑点。这个优雅的技巧在保留高斯-赛德尔方法优越收敛性的同时，恢复了高度的并行性——对于这类问题，高斯-赛德尔方法的收敛速度是雅可比方法的两倍。
并行可扩展性中最深刻的挑战，或许出现在那些本应是已知最强大的数值方法中：多重网格方法。多重网格背后的思想非常直观。为了解决细网格上的问题，我们认识到简单的迭代方法（如雅可比或高斯-赛德尔，被称为“平滑算子”）擅长消除高频、振荡的误差，但对于消除平滑的、长波长的误差则非常糟糕。
多重网格的魔力在于将平滑的误差投影到一个更粗的网格上，在那里它突然变得像振荡误差，从而可以被同样简单的平滑算子轻松消除。这个过程在一系列越来越粗的网格层次结构上递归应用，直到问题变得足够小，可以被轻易地直接求解。然后，校正量再逐层插值回传到上层。
该方法在算法上是最优的：解决一个规模为 的问题的总工作量与 成正比。那么，问题出在哪里呢？问题出在粗网格。在强可扩展性场景下，我们将巨大的细网格问题分布在，比如说，一百万个处理器上。但在V循环的底部，“最粗”的网格可能只有几百个未知数。让一百万个处理器协作解决一个微小的 问题，正是并行效率低下的定义。通信和同步的成本完全压倒了微不足道的计算量。这就是臭名昭著的粗网格瓶颈，它代表了强可扩展性的一堵坚固壁垒。
克服这个瓶颈需要一整套复杂的策略工具箱：
通往并行可扩展性的旅程将我们从简单的算术带到算法的深邃、复杂的结构。它揭示了实现加速不仅仅关乎原始计算能力，更关乎算法与架构的和谐协同设计，一场计算与通信之间的持续舞蹈，以及对优雅和效率的不懈追求。我们探讨的原则——阿姆达尔的限制，古斯塔夫森的希望，并行性与收敛性之间的张力，以及粗网格的深刻挑战——是指导我们寻求将百万台计算机的力量合而为一的根本真理。
当自然的法则被写成数学的语言，便可以通过计算来探索，这其中蕴含着一种深邃的美。但当我们的问题变得更加宏大——当我们试图模拟的不再是单个恒星，而是整个星系；不再是几个原子，而是一个有生命的蛋白质时——我们便会撞上一堵根本性的高墙。单台计算机，无论多快，都已不足够。唯一的出路是将任务分配给成千上万，乃至数百万个协同工作的处理器。这就是并行计算的领域，而其核心挑战便是可扩展性。
仅仅将更多工人投入一个问题是远远不够的。想象一下建造一座大金字塔。如果你有一万名工人却没有恰当的协调，他们会把更多的时间花在互相碰撞和等待指令上，而不是铺设石块。并行可扩展性的艺术与科学，就在于确保每一个新增的工人都能有效地为最终目标做出贡献。这是一场计算与通信之间，任务划分与结果整合之间的微妙舞蹈。当我们探索其应用时，我们会发现，可扩展性并非计算机科学中某个深奥的细节；它是我们用以理解世界的算法的一种深刻而富有启发性的属性，触及从救命药物的设计到宇宙奥秘的方方面面。
在我们欣赏一个良好扩展的并行应用程序所奏响的交响乐之前，我们必须首先理解两种最常见的不和谐之源。第一个是阿姆达尔定律，一个简单但强大的思想，它指出程序的加速比受限于必须串行完成的那部分工作。即使你的任务中只有1%无法并行化，你也永远无法获得超过100倍的加速比，即便使用一百万个处理器。
这种串行瓶颈并不总是显而易见的。考虑处理一幅巨大的、TB级别的卫星图像的任务。我们可以轻易地将图像切割成数百万块，并将每一块分配给不同的处理器进行滤波和分析。计算本身是极易并行的。但在开始时，整个TB级的数据必须从存储系统中读取，在结束时，处理后的图像必须写回。这些I/O操作常常通过一个具有有限全局带宽的共享并行文件系统进行。随着我们增加越来越多的处理器，计算时间急剧下降，但I/O时间却触及了一个由文件系统最大速度施加的硬性下限。在一个现实场景中，这个I/O瓶颈将最大可能加速比限制在区区11倍，无论使用多少千个处理器。系统变得“I/O受限”，庞大的计算军团只能闲置着等待数据到来。
第二个主要障碍是通信成本本身。当处理器需要协作时，它们必须相互交谈。每一次对话都有两种成本：一个是启动成本，即延迟，仅仅为了建立联系；另一个是传输成本，即带宽，取决于你需要说多少话。对于许多小而频繁的对话，延迟可能是致命的。
想象一个“分治”算法，这是一种经典的并行策略。我们可能将一个问题分解成 个小块，在本地分别求解，然后在一个层次树中合并结果。这个合并过程大约需要 个阶段。在每个阶段，处理器配对交换信息。即使信息量很小，每个阶段都会产生一次延迟成本。仅延迟所花费的总时间就随着处理器的增加而增长，其扩展方式类似于 。对于一个固定规模的问题（一种称为*强可扩展性*的场景），总会有一个临界点，此时仅仅用于启动对话的时间就超过了通过并行化工作所节省的时间。超过这个最佳处理器数量后，增加更多的工人实际上会减慢项目进度。这种“延迟的暴政”是在大规模超级计算机上实现可扩展性的最重大挑战之一。
串行瓶颈和通信的障碍并非不可逾越。通常，关键在于选择正确的算法——一种其结构本身就适合并行化的算法。在单个处理器上最快的方法，在一百万个处理器上往往不是最佳选择。这个主题在几乎所有计算科学领域都反复出现。
一个经典的例子来自模拟物理系统随时间的演变，无论是地球地幔中岩石的缓慢变形，还是桥梁的高频振动。我们可以选择一种显式方法，它仅根据当前状态计算未来状态。这种方法涉及大量微小的时间步长，每一步计算量小，且仅需邻近域之间的局部通信——这是一种可扩展性极佳的模式。然而，这些方法通常只是条件性稳定的，这意味着对于细粒度的模拟，时间步长必须非常之小，可能导致总步数达到天文数字。
或者，我们可以选择一种隐式方法。这些方法是无条件稳定的，允许使用大得多的时间步长。但天下没有免费的午餐。每一步都需要求解一个庞大的、耦合的线性方程组，它连接了域中的每一点。用于此任务的迭代求解器，如克雷洛夫（Krylov）方法，在每一次迭代中都需要执行全局归约（例如，从所有处理器求和一个数）。这些全局通信充当了同步点，是可扩展性的主要障碍。此外，要使这些求解器高效，需要复杂的预条件子，如代数多重网格（AMG），而这些预条件子自身也有可扩展性瓶颈，尤其是在将大问题压缩到少数处理器上的“粗网格”上。
这就带来了一个重大的权衡：我们是选择数万亿个廉价、可扩展的步骤（显式），还是几千个昂贵、可扩展性较差的步骤（隐式）？答案取决于问题的物理特性、算法的数学原理以及超级计算机的架构之间复杂的相互作用。
这个原则——即算法的通信模式决定其可扩展性——是普适的。物理学的伟大方程，从流体动力学中的纳维-斯托克斯方程到广义相对论中的爱因斯坦方程，通常都需要求解某种形式的泊松方程。人们可能倾向于使用快速傅里叶变换（FFT），一种看似神奇的、计算成本为 的算法。然而，并行FFT需要“全局转置”或“全对全”通信，即每个处理器都必须与所有其他处理器交换数据。这是一个可扩展性的噩梦。而一种更复杂的方法，如几何多重网格，它在一系列网格层次上求解问题，主要使用局部的、最近邻通信，在算法上是“最优的”，成本为 ，并且在并行机器上扩展性要好得多。数值相对论专家们也依赖同样的智慧，他们采用多重网格和基于物理的块预条件子来驯服控制黑洞碰撞的巨型方程，同时避开那些更简单但不可扩展的方法。教训是明确的：对于并行计算，算法的数据流与其操作计数同等重要。
掌握了这些原则，我们现在可以欣赏现代计算科学中展现的惊人创造力。
在化学和材料科学的量子世界里，计算成本是惊人的。一个分子的电子结构的“常规”计算需要存储的值数量与系统规模的四次方 成比例。仅这一内存需求就足以让一台超级计算机屈服。在这里，可扩展性在几个方面得到了提升。首先，通过算法创新：像*密度拟合*这样的方法用三指标量来近似四指标量，将内存占用从 大幅减少到 ，计算成本从 降低到 。这个巧妙的技巧还提供了一个额外的维度（辅助指标）来进行并行化，从而提升了效率。其次，通过算法设计：更新的方法，如N电子价态微扰理论（NEVPT2），其构建方式避免了耦合线性系统，允许能量计算的不同部分独立并行进行，这使其相比于CASPT2等旧方法具有决定性的可扩展性优势。
即使在计算要求较低的经典分子动力学世界里，这些选择也至关重要。模拟水中的蛋白质涉及数百万个原子。为了采用更大的时间步长，我们约束了最快的运动，比如化学键的振动。如何实施这些约束这个看似微小的细节，却对性能有巨大影响。一种解析的、非迭代的算法如SETTLE，可以在常数时间内处理刚性水分子中的三个约束；这项任务是易于并行的，因为数百万个水分子中的每一个都可以被独立处理。相比之下，像SHAKE这样的旧迭代方法在相连的约束之间产生了依赖关系，限制了并行性。而像LINCS这样的现代算法则使用了一种绝妙的数学近似——截断矩阵级数——来为蛋白质复杂的约束网络同时实现高精度和出色的并行性。最强大的模拟代码正是这些专门化、高度可扩展算法的集合体。一个完整的第一性原理分子动力学模拟，结合了量子和经典力学，是许多不同计算核心（FFT、正交化、对角化）的复杂配方，每个核心都有自己的扩展特性。整体性能是这些相互竞争的组件之间的微妙平衡。
还存在另一种完全不同风格的并行。有时，目标不是让一个单一、巨大的计算更快，而是同时执行成千上万个独立的计算。这就是系综计算的范式。想象我们有一个多物理场模型——比如流体流动与结构力学耦合——其中一个耦合参数是不确定的。我们不想要单一的答案；我们想了解系统在整个不确定性范围内的行为。
使用像随机配置这样的技术，我们可以为数百个不同的不确定参数值运行我们的模拟。这些运行中的每一个都完全独立于其他运行。这是一个“令人愉悦的并行”工作负载。我们可以将每个模拟分派到不同的处理器组。通信量极小，只在最后需要汇总结果时（例如，计算输出的均值和方差）才发生。这里的主要挑战不是管理复杂的数据依赖，而是有效地调度这批庞大的作业并避免开销。这种系综方法是支撑不确定性量化、高通量材料发现、药物筛选以及大量机器学习应用的引擎。
从星系的运动到蛋白质的折叠，通过计算追求科学知识的道路最终都会面临规模的挑战。我们所看到的是，并行可扩展性不是一个你可以在最后才添加的特性；它是一个必须被编织进我们算法结构本身的基本属性。
反复出现的主题陈述起来简单，但其含义却很深远。我们必须警惕串行瓶颈，无论是在我们的代码中还是硬件中。我们必须留意通信的成本，因为延迟和带宽是对并行化征收的无情税收。我们已经学会珍视具有局部通信模式的算法，并对那些需要全局同步的算法持怀疑态度。最重要的是，我们已经看到，最有效的前进道路往往在于根据并行机器的架构重新设计我们的数学方法。通过掌握这些原则，我们构建了驱动现代发现的计算引擎，使我们能够提出更大、更大胆的问题，并且，如果运气好，再加上大量的创造力，我们就能瞥见答案。