玻尔百科在高性能计算领域，一个根本性的悖论主宰着性能：我们执行计算的能力已远远超过我们供应所需数据的能力。这条日益扩大的鸿沟被称为“内存墙”，它意味着在内存和处理器之间移动数据所花费的时间，往往超过了计算本身所花费的时间。本文将深入探讨针对这一关键瓶颈的优雅解决方案：通信避免算法。我们将探索一种算法设计的范式转变，它优先考虑最小化数据移动，而不仅仅是最小化算术运算。 我们的旅程始于“原理与机制”一章，在那里我们将揭示数据局部性和计算强度的核心思想。我们将审视一些基础技术，如矩阵运算的分块、高瘦QR分解（TSQR）的巧妙层次化结构，以及s步迭代方法的延迟隐藏策略。随后，“应用与跨学科联系”一章将揭示这些算法的深远影响。我们将看到它们如何革新从数值线性代数、计算流体力学到数据分析的各个领域，证明了避免通信是在各种尺度上实现高效计算的普适原则。
想象一位能够以闪电般的速度切菜、混合和烹饪的大厨。这位大厨就是我们计算机的处理器。现在，想象这位大厨在一个狭小的工作空间（处理器的缓存）里工作，而他所有的食材都来自一个巨大但遥远的储藏室（主内存）。一个服务员（数据总线）负责取食材。即使这位大厨快如超人，他整体的烹饪速度也受限于服务员运送食材的速度。如果服务员一次只拿一根胡萝卜，然后一次只拿一个洋蔥，再然后一次只拿一瓣大蒜，每次都分開跑一趟，那么整个厨房的运作就会陷入停顿。这正是现代高性能计算面临的核心挑战，通常被称为内存墙：我们执行计算的速度与我们为其供应数据的速度之间日益扩大的差距。
移动数据所需的时间主要有两个组成部分。第一个是延迟，即任何请求的固定延迟，就像服务员往返储藏室的行程时间。第二个是带宽，即数据传输的速率，就像服务员一次能携带多少食材。几十年来，处理器速度飞速增长，但延迟的改善却步履蹒跚。结果是，移动数据的成本，特别是频繁、小量请求的延迟成本，常常远超实际计算的成本。通信避免算法正是一系列旨在克服数据移动这一“暴政”的优美思想的集合。
如果我们的大厨必须等待食材，解决方案是什么？最合乎逻辑的策略是让服务员一次性带来尽可能多的食材，并让大厨在请求更多食材之前，用手头的食材完成尽可能多的烹饪步骤。这个简单的想法正是高性能计算的黄金法则：数据局部性。我们希望最大化对已处于快速、本地内存中数据所做的工作量。
我们可以用计算强度这一概念来更精确地表述这个想法，它是算术运算（浮点运算次数）与从慢速内存移动到快速内存的数据量（字节）之比。具有高计算强度的算法就是我们那位高效的大厨，每获取一字节的数据就能执行许多次操作。而强度低的算法则是我们那位低效的大厨，总是在等待下一份食材。因此，寻求通信避免算法，本质上就是寻求重构计算以最大化其计算强度。
让我们看看这个原则在实践中的应用。大量的科学问题都依赖于线性代数。最基本的操作涉及向量（Level-1 BLAS）或矩阵与向量（Level-2 BLAS）。考虑一个矩阵-向量乘积，。如果矩阵太大而无法装入缓存，我们别无选择，只能从主内存中流式传输它。我们读取的每个元素，用它进行一次乘法和一次加法，然后就 фактически地丢弃它。工作量与数据移动量的比率非常糟糕。
真正的魔力始于我们将计算安排为处理两边都是矩阵的运算（Level-3 BLAS），例如矩阵-矩阵乘法，。我们不再逐个元素地处理矩阵，而是可以将它们分割成保证能装入快速缓存的小块，或称为瓦片（tiles）。为了计算结果矩阵的单个瓦片，我们可以加载和对应的瓦片，然后当这些数据可以快速访问时，执行所有必需的子乘法和子加法。我们加载的每个元素现在都被反复重用。这种简单而深刻的分块思想是现代高性能线性代数的基础。
这种重构不仅仅是一种巧妙的技巧；它使算法能够接近一个已证明的基本极限。对于一大类矩阵算法，理论告诉我们，要完成计算，必须移动的数据量有一个最小值。对于一台拥有大小为的快速内存的机器上，一个具有次浮点运算的操作，其通信下界为字。基于Level-2的朴素算法移动字的数据，远未达到此下界。而基于Level-3的分块算法实际上可以达到这个理论最优值。
分块对于矩阵乘法效果极佳，但对于更复杂、看似顺序的算法又该怎么办呢？以QR分解为例，它是求解方程组的主力。经典的Householder QR算法是逐列进行的。在每一步中，它计算一个特殊的正交变换（一个Householder反射），以将某一列中的元素置零，然后必须将这个变换应用于矩阵的所有剩余列。这个更新是一个矩阵-向量式的（Level-2）操作。对于一个大矩阵来说，这意味着我们必须为每一列对不断缩小的剩余矩阵进行一次完整的遍历。就通信而言，这是极其低效的，移动的数据量远远超过理论下界。
通信避免方法从根本上重新思考了这一过程。首先，我们不再逐一应用反射，而是可以一次性计算一整个面板（panel）的个反射，并将它们聚合成一个单一、紧凑的块变换，通常写作。应用这个单一的块变换现在是一个Level-3操作，使我们回到了高效的矩阵-矩阵更新世界，并将遍历内存的次数从次减少到次。这将消息数量减少了倍。
这就提出了一个新问题：我们如何计算面板变换本身而不陷入通信瓶颈？这引出了一个更优雅的想法：归约树。高瘦QR（TSQR）算法提供了一个完美的例证。想象一个非常高而瘦的矩阵，其行分布在许多处理器上。每个处理器首先对它本地的行集合进行一次小规模的QR分解，这个过程完全不需要通信，而不是由一个处理器费力地从上到下处理整个矩阵。这样，每个处理器都会得到一个小三角矩阵。现在，奇迹发生了：这些小矩阵成对组合，堆叠起来，然后再次进行分解。这个过程在一个二叉树上重复进行。这就像一场体育锦标赛：局部优胜者晋级下一轮比赛，直到唯一的全局冠军——最终的三角因子——诞生。这种层次化结构 brilliantly地将同步步骤（延迟成本）的数量从与列数成正比，即，减少到与处理器数量的对数成正比，即。
这种“锦标赛”思想是如此强大，以至于它也出现在其他地方。在标准的带部分主元选择的LU分解（GEPP）中，寻找每列中的最大元素需要在所有处理器间进行全局搜索——这在每一步都是一个通信瓶颈。通信避免LU（CALU）算法用锦标赛主元选择（tournament pivoting）取而代之。每个处理器找到其局部的最佳主元候选。然后，这些候选者进入一场锦标赛，在归约树的每一层被聚合和重新分解，直到为整个面板选出最终的全局主元。我们再次用一个高度结构化的层次化通信，取代了许多缓慢的顺序通信。
这些思想构成了完整的图景。像通信避免QR（CAQR）这样的算法使用TSQR来分解面板，然后用分块的Level-3操作更新矩阵的其余部分。类似地，CALU为其面板使用锦标赛主元选择。两者都旨在达到理论上的通信下界。同样的理念也延伸到特征值问题，其中一种两阶段方法，首先将矩阵约简为一个窄带（一个Level-3过程），然后沿着该带追逐“凸起”（一个内存局部过程），与经典的单阶段方法相比，极大地减少了通信。
将工作捆绑起来以减少通信延迟的原则，超越了这些“直接”方法，延伸到广阔的迭代求解器世界。这些算法，如共轭梯度法或GMRES方法，对于求解模拟物理现象时产生的巨大的稀疏方程组至关重要。典型的迭代涉及一次矩阵-向量乘积和一次或多次点积。每个点积分布在数千个处理器上，需要一次全局求和——这是一个使整个并行计算短暂停止的同步点。当一个算法需要数千次迭代时，这种延迟成本变得巨大。
通信避免的解决方案是将算法重构为s步方法（s-step method）。核心思想是一次性生成未来次迭代的基。我们不再逐个向量地计算Krylov基，而是致力于计算向量块。这可以组织成一个稀疏矩阵乘以一个向量块，它比一系列稀疏矩阵-向量乘积提供了更多的数据重用。在此之后，这个向量的正交化也可以作为单个块操作来执行。结果是全局同步点的数量减少了倍。我们用更少、粗粒度、受带宽限制的步骤，换掉了许多细粒度、受延迟限制的步骤。
对算法进行这种激进的重构并非没有代价。通常，通信避免算法执行的总算术运算量略高于其经典 counterparts。然而，在现代计算机上，等待数据是主要成本，这几乎总是一笔划算的交易。
一个更深层次的担忧是数值稳定性。经典算法的设计通常将稳定性作为首要任务。例如，LU分解中的部分主元选择是一种避免除以小数和控制舍入误差增长的策略。当我们放宽这些主元选择规则时，如在锦标赛主元选择中，我们可能为了节省通信而故意选择一个数值上较差的主元。对于某些“对抗性”矩阵，这可能导致比经典方法更大的误差。同样，在s步方法中，基向量随着的增加，往往会变得近似平行，这使得从它们创建正交基的过程成为一项微妙且数值上具有挑战性的任务。
因此，开发通信避免算法是一项有趣的协同设计实践，是纯粹数学、数值稳定性与计算机体系结构物理现实之间的一场精妙舞蹈。该领域的美妙之处在于发现这些新颖的表述方式，它们达成了一种新的、更有效的平衡，从而推动了我们能够模拟、预测和发现的疆界。
在迄今为止的旅程中，我们已经探讨了通信避免算法的内容和方式。我们已经深入其内部，看到了那些巧妙的机制——归约树、分块操作、融合通信——它们都是为一个单一而执着的目的而设计的：赢得与数据移动的战争。但一个工具的趣味性取决于它能建造出什么。现在，我们将注意力从工具的设计转向它帮助建立的宏伟结构。这些思想在何处安家？它们开启了哪些新的科学前沿？
你会发现答案很简单：无处不在。最小化通信的原则并非针对特定问题的 niche trick；它们代表了我们处理计算方式本身的一种根本性转变。从最抽象的数学领域到喷气发动机的有形模拟，这一个思想得以衍伸、重塑和赋能。
大量科学和工程问题的核心都潜伏着一个熟悉的野兽：线性代数。无论我们是在分析堆积如山的数据，求解微分方程组，还是寻找桥梁的振动模式，我们最终都会发现需要在一个系统中求解未知向量，或者需要理解矩阵的内在属性。几十年来，我们一直在磨练解决这些问题的算法。但是，大规模并行的出现迫使我们从头开始重新思考它们。
考虑QR分解任务，它是数值线性代数的“主力”，用途广泛，从解决统计学中的最小二乘问题到正交化向量集。像Householder QR这样的经典方法是逐列进行的，每一步都需要所有处理器进行一次全局“对话”。对于一个有很多列的矩阵来说，这就像一个委员会会议，对一个议题做出决定，通知所有人，然后会议才能进行到下一个议题——慢得令人痛苦。当我们处理一个“高瘦”矩阵，即有数百万行但只有几十列时，这个问题变得尤其严重，而这在现代数据分析中是一种常见情况。
通信避免方法，例如高瘦QR分解（TSQR），则以不同方式工作。它主张：让每个处理器在本地处理自己的矩阵块，计算一个初步的QR分解。然后，我们安排一场快速的、层次化的锦标赛，而不是一系列全局会议。来自成对处理器的结果被合并，然后这些对的结果再被合并，如此在一个二叉树上进行，直到我们得到最终答案。通信轮数从与列数成正比，骤降到与处理器数量的对数成正比。在一台拥有数千个处理器或高网络延迟的机器上，这种差异不仅仅是一种改进；它是一个计算能在几分钟内完成，还是可能永远也运行不完的区别。
这一理念延伸到其他基本任务。Gram-Schmidt过程是构建标准正交基的另一种方法，也可以用类似的方式重新构想。通过分块处理列，我们可以用少数几次大的、受带宽限制的数据传输，取代许多小的、受延迟限制的通信。这不仅加快了计算速度，而且当通过再正交化等技术精心设计时，还可以克服经典方法臭名昭著的数值不稳定性。即使是像为LU分解寻找稳定主元这样看似固有顺序的过程也可以并行化。一种“车行主元选择”（rook pivoting）策略可以在矩阵的面板内举行局部锦标赛，而不是全局搜索单一最佳主元，从而大大减少为确保稳定和精确解所需的全局同步。
那么对于那些真正巨大的问题，其中矩阵是如此巨大和稀疏（大部分为零），以至于我们甚至无法梦想直接分解它，该怎么办？在这里，我们转向迭代方法，它生成一系列希望能收敛到正确答案的近似解。著名的共轭梯度（CG）法是一个明星选手，但它也有一个致命弱点：在每一次迭代中，它都需要一次全局内积，即跨所有处理器的求和。这充当了一个全局同步屏障。通信避免的洞见是深刻的：为什么不一次性执行一个次迭代的块，並在数学上重构它们，使得整个块只需要一组通信？这个革命性的想法，体现在像CA-CG这样的算法中，将同步次数减少了倍。虽然这种重构可能会轻微影响收敛速度——我们可以用一个“有效条件数”来量化这个代价——但通信时间的大量节省往往带来惊人的整体加速。
这些思想的影响甚至更远，深入到矩阵理论的核心。特征值问题要求找到那些仅被矩阵拉伸（而非旋转）的特殊向量，它们对于量子力学（能级）、结构工程（振动频率）和网络分析至关重要。计算Schur分解是关键一步。在这里，两阶段的通信避免算法同样使我们能够在并行机上处理巨大的矩阵。它们还揭示了一个基本限制：“强扩展性上限”，即在某一点之后，增加更多处理器实际上会减慢计算速度，因为通信开销开始压倒计算收益。通信避免算法推高了这个上限，让我们能更有效地使用更大的机器。
更高级的概念，如在控制理论和电子结构计算中有应用的矩阵符号函数，也可以由这些技术驱动。一个优雅的牛顿迭代法来计算它可以被构造成一系列矩阵乘法和求逆。这些高层步骤中的每一步都可以由通信避免的模块构建——如CAQR和并行三角求解——这些模块需要最少数量的同步步骤,。
这些数学工具的美妙之处在于，它们不仅仅是抽象的奇珍。它们是我们用来创建物理世界计算模型的画笔和颜料。
让我们想象模拟空气流过飞机机翼。为此，计算流体力学（CFD）代码将机翼周围的空间划分为一个精细的单元网格。物理定律——在这种情况下是欧拉方程——然后被转化为一个庞大的、耦合的非线性方程组。通常为了稳定性而必需的隐式时间步进格式，需要在每一步求解一个巨大的线性系统。因为一个单元内的物理过程只直接影响其近邻，这个线性系统具有一个特殊的稀疏结构：它是块三对角的。
当我们在超级计算机上求解它时，我们使用区域分解：我们将网格的一个连续块分配给每个处理器。挑战在于这些块之间边界上的数据依赖。一个朴素的并行求解器对于每一个跨越边界的行操作都需要一个通信步骤。然而，一个通信避免的求解器在通信之前，会在其域内执行一整个“面板”的消元。同步轮数被大大减少。这种方法还使另一件事变得清晰：整个模拟的运行速度只能和最过载的处理器一样快。因此，通过尽可能均匀地平衡区域分解来最小化最大工作量，与最小化通信频率同样至关重要。
同样的理念也适用于许多其他物理现象。像间断Galerkin（DG）方法这样的高阶方法特别擅长模拟波的传播——无论是声波、地震波还是电磁波。在一个并行的DG代码中，处理器需要跨越其计算单元的“面”来交换信息，以计算数值通量。一个朴素的实现可能为每个面发送一条消息。这就像与你的邻居进行数百次独立的、简短的对话。通信避免的策略是“面融合”：如果你需要与邻居交谈，就把所有需要发送的信息收集起来，打包成一条更大的消息。这个听起来简单的技巧极大地减少了等待网络延迟所花费的总时间，因为它用一次消息启动取代了许多次小的消息启动([@problemid:3407860])。
到目前为止，我们关于通信的故事都集中在跨网络在不同计算机之间飞行的消息上。但完全相同的斗争正在每个处理器芯片内部以微缩的形式发生。现代计算机有一个内存层次结构：一组微小、闪电般快速的寄存器，一个稍大且稍慢的缓存（或多级缓存），然后是一个巨大但相对迟缓的主内存（DRAM）。
在这些层级之间移动数据也是一种“通信”，而且它通常是主要的瓶颈。同样的核心原则适用：一旦一块数据被移动到内存层次结构的快速层级，就对其执行尽可能多的计算。这就是经典的Roofline性能模型背后的思想。对于像矩阵乘法这样的操作，这意味着设计具有多级分块的算法，块的大小完美地调整到每个缓存级别的容量。为了最小化总时间（受层次结构中最紧的带宽瓶颈限制），必须选择能够在每个级别容纳的最大块大小。这最大化了数据重用，并最小化了到较慢内存层级的流量。
这揭示了我们主题的美妙、统一的真理。我们正在避免的“通信”并非仅指一件事。它是集群中处理器之间的数据移动，是处理器与主内存之间的数据移动，或是不同级别缓存之间的数据移动。像TSQR这样的算法的数学重构和面融合的实践工程，只是同一个基本思想的两种不同表现形式。对抗数据移动的战争正在所有战线上进行，从数据中心的规模一直到单个硅芯片的规模。
最后，通信避免算法不仅仅是一系列巧妙的优化。它们是对一个基本物理现实的回应：计算很便宜且越来越便宜，而移动数据很昂贵且其成本下降得远没有那么快。通过重新设计我们的算法以尊重这一现实，我们不仅使我们当前的代码更快；我们正在为新一代的科学模拟和数据分析工具铺平道路，使我们能够提出更大的问题，并模拟比以往任何时候都更复杂的系统。