第一章：为什么需要并行计算

1.1 为什么你应该学习并行计算？
- 1.1.1 并行计算有哪些潜在的好处呢？
- 1.1.2 并行计算注意事项
1.2 并行计算的基本定律
- 1.2.1 并行计算的极限：阿姆达尔定律
- 1.2.2 突破并行极限：古斯塔夫森-巴尔西斯定律
1.3 并行计算是如何工作的？
1.4 对并行方法进行分类
1.5 并行策略
1.6 并行加速与比较加速：两种不同的度量标准
1.7 在这本书中，您将学到什么？

本章内容包括：

并行计算是什么以及为什么它变得越来越重要
现代硬件中存在并行性的位置
应用程序并行性的重要性
利用并行性的软件方法

在今天的世界中，你会发现许多挑战需要广泛而高效地利用计算资源。大多数需要性能的应用程序传统上属于科学领域。但人工智能（AI）和机器学习应用预计将成为大规模计算的主要用户。其中一些应用示例包括：

模拟巨大火灾，以协助消防队和帮助公众
模拟海啸和飓风引起的风暴潮（有关简单海啸模型，请参见第13章）
计算机界面的语音识别
模拟病毒传播和疫苗开发
对数十年和世纪的气候条件进行建模
用于无人驾驶汽车技术的图像识别
为紧急救援队提供运行模拟，模拟诸如洪水等危险
减少移动设备的功耗

通过本书介绍的技术，您将能够处理更大的问题和数据集，同时运行模拟速度可提高十倍、一百倍，甚至一千倍。典型的应用程序往往未充分利用当今计算机的计算能力。并行计算是释放计算资源潜力的关键。那么什么是并行计算，以及如何利用它来增强您的应用程序呢？

并行计算是在同一时刻执行许多操作的过程。充分利用并行计算并非自动发生，而是需要程序员付出一些努力。首先，您必须确定并展示应用程序中的并行潜力。潜在的并行性，或并发性(concurrency)，意味着您确认以任意顺序执行操作是安全的，只要系统资源变得可用。而且，在并行计算中，还有一个额外的要求：这些操作必须同时发生。为了实现这一点，您还必须正确利用资源，以同时执行这些操作。

并行计算引入了在串行世界中不存在的新问题。我们需要改变我们的思考过程，以适应并行执行的额外复杂性，但通过实践，这将变得自然而然。本书将带您开始发现如何利用并行计算的威力。

生活中有许多并行处理的例子，这些例子通常成为计算策略的基础。图1.1显示了一个超市收银线，目标是让顾客快速付款购买所需物品。可以通过雇佣多个收银员逐个处理或结账顾客来实现这一目标。在这种情况下，熟练的收银员可以更快地执行结账流程，使顾客更快离开。另一种策略是雇佣许多自助结账站，允许顾客自己执行结账过程。这种策略需要超市的人力资源较少，并且可以开设更多的通道来处理顾客。顾客可能不能像训练有素的收银员那样高效地结账，但由于增加的并行性导致排队时间缩短，更多的顾客可能可以迅速结账。

图 1.1 超市结账队列中的日常并行处理。结账出纳员（戴着帽子）处理他们队列中的顾客（拿着篮子）。在左边，一个收银员同时处理四个自助结账通道。在右边，每个结账通道都需要一个出纳员。每个选项都会影响超市的成本和结账速度

我们通过开发算法来解决计算问题：一组步骤，以实现期望的结果。在超市的类比中，结账的过程就是算法。在这种情况下，它包括从篮子中卸下物品，扫描物品以获取价格，然后支付物品的过程。这个算法是顺序的（或串行的）；它必须按照这个顺序进行。如果有数百名顾客需要执行这个任务，检查许多顾客的算法包含可以利用的并行性。理论上，通过使用多个结账通道或自助结账站，超市暴露了并行性，从而提高了顾客购物和离开商店的速度。我们在如何实现这种并行性的选择中，每一种选择都会产生不同的成本和效益。

定义：并行计算是识别和暴露算法中的并行性，将其表达在我们的软件中，并理解所选实现的成本、效益和限制的实践。

最终，并行计算关乎性能。这不仅包括速度，还包括问题的规模和能源效率。我们在本书中的目标是让您了解当前并行计算领域的广度，并让您熟悉最常用的语言、技术和工具，以便您能够自信地处理并行计算项目。关于如何整合并行性的重要决策通常在项目开始时就会做出。合理的设计是成功的重要步骤。跳过设计步骤可能导致以后出现问题。同样重要的是保持对可用资源和项目性质的现实期望，并了解两者。

本章的另一个目标是介绍并行计算中使用的术语。一种方法是指向附录 C 中的词汇表，以便您在阅读本书时快速查阅术语。由于这个领域和技术是逐步发展的，因此并行社区中的许多术语的使用往往不够严谨和精确。随着硬件复杂性和应用程序内并行性的增加，我们从一开始就建立清晰、明确的术语使用变得至关重要。

欢迎来到并行计算的世界！随着深入研究，技术和方法会变得更加自然，您会发现其强大的魅力。您从未考虑过的问题变得司空见惯。

1.1 为什么你应该学习并行计算？

未来是并行的。随着处理器设计达到了微型化、时钟频率、功耗甚至热量的极限，串行性能的增长已经趋于平稳。图1.2显示了商用处理器的时钟频率（指令执行速率）、功耗、计算核心数量（简称核心）以及硬件性能随时间变化的趋势。

图1.2显示了从1970年到2018年的单线程性能、CPU时钟频率（MHz）、CPU功耗（瓦特）以及CPU核心数量。并行计算时代大约始于2005年，当时CPU芯片中的核心数量开始上升，而时钟频率和功耗趋于平稳，但性能持续增长（参考Horowitz等人和Rupp的https://github.com/karlrupp/microprocessor-trend-data）。

到了2005年，核心数量从单核心突然增加到多核心。与此同时，时钟频率和功耗趋于稳定。理论性能持续增加，因为性能与时钟频率和核心数量的乘积成正比。这种向增加核心数量而非时钟速度的转变表明，实现中央处理单元（CPU）最理想性能的途径只能通过并行计算。现代消费级计算硬件配备了多个中央处理单元（CPU）和/或图形处理单元（GPU），能够同时处理多个指令集。这些较小的系统往往可以媲美二十年前的超级计算机的计算能力。充分利用计算资源（在笔记本电脑、工作站、智能手机等设备上）需要您作为程序员具备编写并行应用程序的工具的实际知识。您还必须了解提升并行性的硬件特性。由于存在许多不同的并行硬件特性，这给程序员带来了新的复杂性。其中之一是由英特尔推出的超线程技术。通过使两个指令队列交替工作到硬件逻辑单元，使单个物理核心在操作系统（OS）中显示为两个核心。矢量处理器是另一种硬件特性，大约在2000年左右开始出现在商用处理器中。这些处理器可以同时执行多个指令。矢量处理器的位宽（也称为矢量单元）指定了同时执行的指令数量。因此，一个256位宽的矢量单元可以同时执行四个64位（双精度）或八个32位（单精度）的指令。

示例

我们来看一个带有超线程和256位宽矢量单元的16核CPU，这在家用台式机中很常见。一个使用单个核心且没有矢量化的串行程序仅使用这个处理器的理论处理能力的0.8%！计算方法是

16核 × 2超线程 × （256位宽矢量单元）/（64位双精度）= 128路并行

其中1个串行路径 / 128个并行路径 = 0.008或0.8%。下图显示了这只是总CPU处理能力的一小部分。

串行应用程序仅访问16核CPU处理能力的0.8%。

计算理论和实际串行与并行性能的期望，正如这个示例中所示，是一项重要的技能。我们将在第3章中更深入地讨论这个问题。

一些软件开发工具的改进帮助我们将并行性添加到我们的工具包中，目前，研究界也在做更多工作，但要解决性能差距仍然任重道远。这使得我们，软件开发人员，需要充分发挥新一代处理器的潜力。

不幸的是，软件开发人员在适应这一计算能力的根本性变化方面进展较慢。此外，由于新的编程语言和应用程序编程接口（API）的爆炸性增长，将当前应用程序转移到利用现代并行架构可能令人生畏。但对应用程序的良好工作知识，发现和暴露并行性的能力，以及对可用工具的充分了解，都可能带来可观的好处。应用程序可能会获得哪些好处？让我们仔细看一看。

1.1.1 并行计算有哪些潜在的好处呢？

并行计算可以缩短解决问题的时间，提高应用程序的能源效率，并使您能够在当前现有的硬件上处理更大的问题。如今，并行计算不再是最大计算系统的专属领域。这项技术现在存在于每个人的台式机或笔记本电脑上，甚至在手持设备上也有应用。这使得每个软件开发人员都有可能在本地系统上创建并行软件，从而极大地扩展了新应用的机会。

来自行业和学术界的前沿研究揭示了随着兴趣从科学计算拓展到机器学习、大数据、计算机图形学和消费者应用，新的并行计算领域。新技术的出现，如自动驾驶汽车、计算机视觉、语音识别和人工智能，要求在消费者设备内部以及开发领域具有强大的计算能力，需要处理和消耗大规模的训练数据集。在长期以来一直是并行计算专属领域的科学计算中，也出现了新的令人兴奋的可能性。远程传感器和手持设备的泛滥可以将数据输入到更大、更真实的计算中，以更好地支持围绕自然和人为灾害的决策，这带来了更广泛的数据。

必须记住，并行计算本身并不是目标。相反，目标是并行计算带来的结果：减少运行时间、执行更大的计算或减少能源消耗。

更多计算核心意味着更短的运行时间

减少应用程序的运行时间，或称为加速比，通常被认为是并行计算的主要目标。事实上，这通常是其最大的影响。无论您的应用程序需要花费几天甚至几周的时间来处理，还是需要实时结果，并行计算都可以加速密集的计算、多媒体处理和大数据操作。

在过去，程序员会更加努力地进行串行优化，以挤出一些百分点的改进。现在，有可能通过多种途径获得数量级的改进。这在探索可能的并行范式时产生了一个新问题——机会比编程人力还多。但是，对应用程序的深入了解和对并行性机会的认识可以让您更清晰地减少应用程序的运行时间。

更大的问题规模，使用更多的计算节点

通过在应用程序中暴露并行性，您可以将问题的规模扩展到串行应用程序无法达到的维度。这是因为计算资源的数量决定了可以做什么，而暴露并行性允许您在更大的资源上操作，提供了以前从未考虑过的机会。较大的规模是通过更多的主存储器、磁盘存储器、网络和磁盘带宽以及中央处理器实现的。类比之前提到的超市，暴露并行性相当于雇佣更多的收银员或开设更多的自助结账通道，以处理不断增长的顾客数量。

通过更少的资源实现更多，提高能源效率

并行计算的一个新影响领域是能源效率。随着手持设备中并行资源的出现，并行性可以加速应用程序。这使设备更快返回休眠模式，并允许使用速度较慢但更并行的处理器，从而消耗更少的电力。因此，将重量级的多媒体应用程序移至在GPU上运行可以在提高性能的同时对能源效率产生更显著的影响。应用并行性的净结果是降低功耗并延长电池寿命，这在这一市场领域具有强大的竞争优势。

能源效率至关重要的另一个领域是远程传感器、网络设备和操作场地部署的设备，例如远程气象站。通常，这些设备必须能够在资源有限的小型封装中运行，而无需大型电源。并行性扩展了这些设备上的操作范围，并在一个被称为边缘计算的不断增长的趋势中卸载了中央计算系统的工作。将计算移到网络的极端位置可以在数据源处进行处理，将其压缩成一个较小的结果集，更容易通过网络发送。

在没有直接测量能耗的情况下准确计算应用程序的能源成本是具有挑战性的。但是，您可以通过将制造商的热设计功率乘以应用程序的运行时间和使用的处理器数量来估算成本。热设计功率是在典型操作负载下能量消耗的速率。可以使用以下公式估算您的应用程序的能耗：

P=(N处理器)×(R瓦特/处理器)×(T小时)

其中P是能耗，N是处理器数量，R是热设计功率，T是应用程序运行时间。

示例

Intel的16核Xeon E5-4660处理器的热设计功率为120瓦特。假设您的应用程序使用20台这样的处理器运行24小时以完成。您的应用程序的估计能耗为

P=(20处理器)×(120瓦特/处理器)×(24小时)=57.60千瓦时

通常，GPU的热设计功率高于现代CPU，但可以通过减少运行时间或仅使用少量GPU来获得相同的结果。与以前相同的公式仍然适用，其中N现在被视为GPU的数量。

示例

假设您已将应用程序移植到多GPU平台。现在，您可以在四个NVIDIA Tesla V100 GPU上运行您的应用程序，运行时间为24小时！ NVIDIA的Tesla V100 GPU的最大热设计功率为300瓦特。您的应用程序的估计能耗为

P=(4 GPU)×(300 瓦特/GPU)×(24 小时)=28.80 千瓦时

在这个例子中，GPU加速的应用程序的能耗仅为CPU版本的一半。请注意，在这种情况下，即使解决方案的时间保持不变，能源开销也减少了一半！

通过诸如GPU之类的加速器设备实现能源成本的降低需要应用程序具有足够的可暴露的并行性，以便有效地利用设备上的资源。

并行计算可降低成本

实际货币成本对于软件开发团队、软件用户和研究人员而言变得更加明显。随着应用程序和系统的规模不断增长，我们需要对可用资源进行成本效益分析。例如，对于下一代大型高性能计算（HPC）系统，电力成本预计将是硬件采购成本的三倍。

使用成本也推动了云计算作为一种替代方案的发展，这种方案在学术界、初创公司和各个行业中越来越受到采用。一般而言，云服务提供商按照使用的资源类型和数量以及使用这些资源的时间来计费。尽管GPU的每单位时间成本通常高于CPU，但一些应用程序可以利用GPU加速器，使其在相对于CPU开销而言减少的运行时间足够多，从而降低成本。

1.1.2 并行计算注意事项

并行计算并非是万能的。许多应用程序既不足够大，也不需要足够长的运行时间来需要并行计算。有些甚至可能没有足够的固有并行性可以利用。此外，将应用程序转移到利用多核和多核（GPU）硬件需要投入专门的精力，这可能会暂时转移关注点，远离直接的研究或产品目标。在将时间和精力投资之前，必须首先确定其是否值得。在使应用程序运行并生成所需结果之前，使其运行更快并扩展到更大的问题规模通常更为重要。

我们强烈建议您在启动并行计算项目时制定计划。了解加速应用程序的可用选项非常重要，然后选择最适合您项目的选项。之后，估计涉及的工作量和潜在回报（以美元成本、能源消耗、解决方案时间和其他可能重要的度量为准）至关重要。在本章中，我们开始为您提供有关如何在并行计算项目上做出决策的知识和技能。

1.2 并行计算的基本定律

在串行计算中，随着时钟频率的增加，所有操作都会加速。相比之下，对于并行计算，我们需要深思熟虑并修改我们的应用程序，以充分利用并行硬件。为什么并行性的数量很重要呢？为了理解这一点，让我们来看看并行计算的定律。

1.2.1 并行计算的极限：阿姆达尔定律

我们需要一种计算的潜在加速方式，该方式基于代码的并行部分。这可以使用由基因·阿姆达尔（Gene Amdahl）于1967年提出的阿姆达尔定律来完成。该定律描述了在处理器数量增加时，固定大小问题的加速度。以下方程显示了这一点，其中P是代码的并行部分，S是串行部分，即P + S = 1，而N是处理器的数量：

\[\text{SpeedUp}(N) = \frac{1}{S+\frac{P}{N}}\]

【译注：这个公式比较好理解，N个处理器可以让原来可并行部分话的时间从P变化成P/N，但是串行的部分还是要花S这么多时间。】

图1.3显示了根据阿姆达尔定律对于固定大小问题的加速比，作为处理器数量的函数。曲线展示了在算法的100%、90%、75%和50%并行化时的理想加速比。阿姆达尔定律规定了加速的限制，由仍然串行的代码部分决定。

定义强可扩展性(Strong scaling)表示对于固定总大小，问题的求解时间与处理器数量的关系。

1.2.2 突破并行极限：古斯塔夫森-巴尔西斯定律

1988年，古斯塔夫森和巴尔西斯指出，并行代码运行时应随着添加更多处理器而增加问题的大小。这可以为我们计算应用的潜在加速提供另一种方式。如果问题的大小与处理器数量成比例增长，那么加速现在被表示为

\[\text{SpeedUp}(N)=N−S \cdot (N−1)\]

其中N是处理器数量，S是之前的串行分数。结果是，通过使用更多的处理器，可以在相同时间内解决一个更大的问题。这提供了利用并行性的额外机会。事实上，随着处理器数量的增加，问题的规模也增长是有意义的，因为应用程序用户希望从额外处理器的能力中受益，并希望使用额外的内存。这种情况下的运行时扩展，如图1.4所示，被称为弱可扩展性。

【译注：可以这样理解上面的公式。假设一个处理器单位时间处理规模为1的问题，其中串行部分时间为S，并行部分时间为P，P+S=1。而同样在一个单位时间，我们可以用N个处理器来处理并行部分，所以在P的时间里可以处理NP个问题，在S的时间只能处理S个问题，因为这是串行的。因此在单位时间可以处理的问题为NP+S=N(1-S)+S=N-(N-1)S】

图1.4 根据古斯塔夫森-巴尔西定律，当问题的大小随着可用处理器数量的增加而增长时，加速度的变化以处理器数量为函数呈现。图中的线显示了算法100%、90%、75%和50%并行化时的理想加速度。

定义弱可扩展性表示对于每个处理器的固定大小问题，解的时间与处理器数量的关系。

图1.5 在可视化表示中展示了强可伸缩性和弱可伸缩性之间的差异。弱可伸缩性的论点是，每个处理器上的网格大小应保持恒定，这样就能更好地利用额外处理器的资源。强可伸缩性的观点主要关注计算的加速度。在实践中，强可伸缩性和弱可伸缩性都很重要，因为它们涉及不同的用户场景。术语”可伸缩性”通常用来指硬件或软件中是否可以添加更多并行性，以及是否存在整体改进的限制。虽然传统关注点是运行时的可伸缩性，但我们将论证内存可伸缩性通常更为重要。

图1.5 强可伸缩性保持问题的总体大小不变，并将其分割到额外的处理器上。在弱可伸缩性中，每个处理器上网格的大小保持不变，总体大小增加。

术语“可伸缩性”通常用来表示无论是在硬件还是软件中是否可以增加更多的并行性，以及是否存在总体限制可以发生多大改进。虽然传统关注点在于运行时的可伸缩性，但我们将提出一个观点，即内存可伸缩性通常更为重要。

图1.6展示了一个具有有限内存可伸缩性的应用程序。复制的数组（R）是一个在所有处理器上都复制的数据集。分布式数组（D）被划分并分布在处理器上。例如，在游戏模拟中，可以将100个角色分布在4个处理器上，每个处理器上有25个角色。但游戏棋盘的地图可能会复制到每个处理器上。在图1.6中，复制的数组在整个网格上被复制。由于这个图是为了弱可伸缩性，问题的大小随着处理器数量的增加而增长。对于4个处理器，数组在每个处理器上的大小是原始大小的4倍。随着处理器数量和问题的大小的增长，很快处理器上的内存就不够运行作业了。有限的运行时可伸缩性意味着作业运行缓慢；有限的内存可伸缩性意味着作业无法运行。同样，如果应用程序的内存可以分布，运行时间通常也会相应地增加。然而，反之未必成立。

图1.6中，分布式数组的大小与问题规模和处理器数量相同（弱可伸缩性）。但是，复制的（复制的）数组需要在每个处理器上都有所有数据，并且随着处理器数量的增加，内存迅速增长。即使运行时间弱可伸缩（保持不变），内存需求也限制了可伸缩性。

对于计算密集型作业的一种看法是，在处理的每个周期中，每个字节的内存都会被访问，而运行时间是内存大小的函数。减小内存大小必然会减少运行时间。因此，并行性的初始关注点应该是随着处理器数量的增加而减少内存大小。

1.3 并行计算是如何工作的？

并行计算需要结合对硬件、软件和并行性的理解来开发应用程序。它不仅仅是消息传递或线程处理。当前的硬件和软件提供了许多不同的选项，可以将并行化引入您的应用程序中。其中一些选项可以组合使用，以获得更高的效率和加速。

了解应用程序中的并行化以及不同硬件组件允许您暴露它的方式非常重要。此外，开发人员需要认识到，在您的源代码和硬件之间，您的应用程序必须经过额外的层，包括编译器和操作系统（见图1.7）。

图1.7 并行化表现为一个应用软件层，通过编译器和操作系统映射到计算机硬件上。

作为开发人员，您负责应用软件层，其中包括您的源代码。在源代码中，您会选择使用哪种编程语言和并行软件接口来利用底层硬件。此外，您还会决定如何将工作分解为并行单元。编译器的设计目的是将您的源代码转换为硬件可以执行的形式。有了这些指令，操作系统负责在计算机硬件上执行这些指令。

我们将通过一个示例向您展示如何通过原型应用程序引入并行化到算法中。这个过程发生在应用软件层，但需要对计算机硬件有一定的理解。目前，我们将避免讨论编译器和操作系统的选择。我们将逐步添加每个并行化层，以便您了解其工作原理。对于每种并行策略，我们将解释可用硬件如何影响所做的选择。这样做的目的是展示硬件特性如何影响并行策略。我们将开发者可以采取的并行方法分为以下几类：

基于进程的并行化
基于线程的并行化
向量化
流处理

在示例中，我们将介绍一个模型，帮助您思考现代硬件。这个模型将现代计算硬件分解为各个组件和各种计算设备。本章还包括对内存的简化视图。对内存层次结构的更详细的介绍将在第3和第4章中呈现。最后，我们将更详细地讨论应用程序和软件层。

正如前面提到的，我们将开发者可以采取的并行方法分为基于进程的并行化、基于线程的并行化、向量化和流处理。基于各个进程的并行化具有各自的内存空间，可以分布在计算机的不同节点上或者在节点内部。流处理通常与GPU相关联。现代硬件和应用软件的模型将帮助您更好地理解如何计划将您的应用程序移植到当前的并行硬件上。

1.3.1 示例应用程序概览

在这个并行化介绍中，我们将看一下数据并行化方法。这是最常见的并行计算应用策略之一。我们将在由规则的二维网格(grid)组成的空间网格(mesh)上执行计算，该网格由矩形元素或单元格组成。创建空间网格并为计算做准备的步骤（在此概述并稍后详细描述）包括：

将问题分解为较小的单元格或元素
定义在网格的每个元素上执行的计算核心（操作）
在CPU和GPU上添加以下并行化层以执行计算：
- 向量化——同时处理多个数据单元
- 线程——部署多个计算路径以利用更多处理核心
- 进程——将程序实例分开以将计算分散到不同的内存空间
- 将计算转移(offload)到GPU上——将数据发送到图形处理器进行计算

我们从一个二维空间区域的问题域开始。为了说明，我们将以克拉卡托(Krakatau)火山的二维图像（图1.8）作为示例。我们计算的目标可能是模拟火山羽流(volcanic plume)、产生的海啸(tsunami)，或者使用机器学习对火山喷发(eruption)进行早期检测。对于所有这些选项，如果我们希望获得实时结果以指导我们的决策，计算速度至关重要。

图1.8 一个数值模拟的二维空间域示例。数值模拟通常涉及模板(stencil)操作（见图1.11）或大型矩阵-向量系统。这些类型的操作通常用于流体建模，以预测海啸到达时间、天气预报、烟雾羽流扩散等，这些都是做出明智决策所必需的过程。

步骤1：将问题分解为较小的单元或元素

对于任何详细的计算，我们必须首先将问题的域分解为较小的部分（见图1.9），这个过程称为离散化(discretization)。在图像处理中，这通常只是位图图像中的像素。对于计算域，这些被称为单元或元素。单元或元素的集合形成了一个计算网格(mesh)，覆盖了模拟的空间区域。每个单元的数据值可能是整数、浮点数或双精度数。

图1.9 域被离散化为单元。对于计算域中的每个单元，根据物理定律解算波高(wave height)、流体速度(fluid velocity)或烟雾密度(smoke density)等属性。最终，一个模板操作或矩阵-向量系统代表了这个离散方案。

步骤2：定义一个计算核心或操作，用于对网格中的每个元素进行处理

对这些离散化数据的计算通常是一种模板操作，因为它涉及到一个相邻单元的模式，用于计算每个单元的新值。这可以是一个平均值（模糊操作，可以使图像模糊或变得更模糊）、一个梯度（边缘检测，可以使图像边缘更加清晰），或者与解决由偏微分方程（PDEs）描述的物理系统相关的另一个更复杂的操作。图1.10展示了一个五点模板操作，通过使用模板值的加权平均值执行模糊操作。

图1.10 在计算网格上以十字形图案表示的五点模板算子。由模板标记的数据在操作中被读取并存储在中心单元中。这个模式对每个单元都重复。模糊操作是较简单的模板操作之一，是由大点标记的五个点的加权和，更新了模板中心点的值。这种类型的操作用于平滑操作或波传播数值模拟。

但是什么是这些偏微分方程呢？让我们回到我们的例子，并想象这次是由单独的红色、绿色和蓝色数组组成的彩色图像，以构建RGB色彩模型。这里的“偏”一词意味着存在多个变量，并且我们正在将红色随着空间和时间的变化与绿色和蓝色分开。然后，我们分别对每种颜色执行模糊操作。

还有一个要求：我们需要应用时间和空间上的变化率。换句话说，红色会以一定速率扩散，而绿色和蓝色会以其他速率扩散。这可以用于在图像上产生特殊效果，也可以描述在照片图像的开发过程中真实颜色如何渗透和融合。在科学世界中，我们可能不是红色、绿色和蓝色，而是质量、x 和 y 速度。再加上一些物理学，我们可能会得到波的运动或火山灰羽流的运动。

步骤3：向量化(vectorization)，同时处理多个数据单元

我们开始介绍并行化，首先看一下向量化。什么是向量化？一些处理器具有同时操作多个数据的能力；这种能力称为向量操作(vector operations)。图1.11中的阴影块说明了在具有向量单元的处理器中，多个数据值如何在一个时钟周期内同时进行操作，只需一条指令。

图1.11 对四个双精度数进行了特殊的向量操作。这个操作可以在一个时钟周期内执行，而且与串行操作相比，额外的能量成本很小。

步骤4：线程，部署多个计算路径以利用更多处理核心

因为大多数现代 CPU 至少有四个处理核心，我们使用线程来同时操作这些核心，每次跨越四行。图1.12展示了这个过程。

图1.12 向量单元四个线程同时处理四行向量单元。

步骤5：进程，将计算分散到不同的内存空间

我们可以进一步将工作分配给两台台式机上的处理器，通常称为并行处理中的节点。当工作在节点之间分配时，每个节点的内存空间是独立和分开的。这可以通过在图1.13中在行之间放置间隙来表示。

图1.13 这个算法可以进一步并行化，通过将4×4块分配给不同的进程。每个进程使用四个线程，每个线程在一个时钟周期内处理一个四节点宽的向量单元。图中的额外空白区域表示了进程边界。

即使对于这种相当简单的硬件场景，也有可能获得32倍的速度提升。这可以通过以下方式表示：

2 台台式机（节点） × 4 核心 ×（256 位宽向量单元）/（64 位双精度数） = 32 倍潜在加速

如果我们看一个高端集群，有16个节点，每个节点有36个核心，并且有一个512位的向量处理器，那么潜在的理论加速比是比串行处理快4,608倍：

16个节点 × 36个核心 ×（512位宽向量单元）/（64位双精度数）= 4,608倍潜在加速

步骤6：将计算转移到 GPU

GPU 是另一个可以加速并行化的硬件资源。通过 GPU，我们可以利用大量的流式多处理器来处理工作。例如，图1.14展示了如何将工作分开成8x8的瓦片。利用 NVIDIA Volta GPU 的硬件规格，这些瓦片可以由32个双精度核心在84个流式多处理器上操作，总共为我们提供了2,688个双精度核心同时工作的能力。如果在一个16节点集群中每个节点上都有一个 GPU，每个 GPU 都有一个2,688个双精度流式多处理器，那么这就是从16个GPU获得的43,008种并行化。

图1.14 在 GPU 上，向量长度比在 CPU 上要大得多。这里，8×8的瓦片分布在 GPU 的工作组中。

这些数字令人印象深刻，但在这一点上，我们必须通过承认实际加速远远落后于这个潜力的全部来控制期望。我们现在面临的挑战是组织如此极端和不同层次的并行化，以尽可能获得更多的加速。

对于这个高级应用程序演练，我们忽略了许多重要的细节，这些细节将在后面的章节中进行讨论。但即使是这种名义上的详细程度也突显了一些暴露算法并行化策略的方法。要能够为其他问题开发类似的策略，必须了解现代硬件和软件。我们现在将深入探讨当前的硬件和软件模型。这些概念模型是对多样化的现实世界硬件的简化表示，以避免复杂性并在快速发展的系统上保持一般性。

1.3.2 今天的异构(heterogeneous)并行系统的硬件模型

为了建立对并行计算工作原理的基本理解，我们将解释今天硬件中的组件。首先，动态随机存取存储器，简称 DRAM，用于存储信息或数据。计算核心，简称核心，执行算术操作（加、减、乘、除），评估逻辑语句，并从 DRAM 加载和存储数据。当对数据执行操作时，指令和数据从内存加载到核心，进行操作，然后存储回内存。现代 CPU，通常称为处理器，配备了许多能够并行执行这些操作的核心。越来越常见的是，系统配备了加速器硬件，如 GPU。GPU 配备了数千个核心和一个与 CPU DRAM 分开的内存空间。处理器（一个或两个）、DRAM 和加速器的组合形成了一个计算节点，可以在单个家庭台式机或超级计算机的“机架”环境中提到。计算节点可以通过一个或多个网络连接到彼此，有时称为互连。在概念上，一个节点运行一个操作系统的单个实例，管理和控制所有的硬件资源。随着硬件变得更加复杂和异构，我们将从系统组件的简化模型开始，使每个组件更加明显。

分布式内存架构：跨节点并行方法

并行计算的第一个且最具可扩展性的方法之一是分布式内存集群（图1.15）。每个 CPU 都有自己的本地内存，由 DRAM 组成，并通过通信网络连接到其他 CPU。分布式内存集群的良好可扩展性来自于它看似无限的增加节点的能力。

图1.15 分布式内存架构连接由单独内存空间组成的节点。这些节点可以是工作站或机架。

这种架构还通过将总可寻址内存分割成每个节点的较小子空间来提供一些内存局部性，这使得在节点内部和外部访问内存有着明显的不同。这迫使程序员显式访问不同的内存区域。这种方式的缺点在于程序员必须在应用程序开始时管理内存空间的分区。

共享内存架构：一种节点内并行方法

另一种方法是将两个 CPU 直接连接到同一共享内存（图1.16）。这种方法的优势在于处理器共享相同的地址空间，简化了编程。但这会引入潜在的内存冲突，导致正确性和性能问题。在多核 CPU 上同步内存访问和值，或者在多核 CPU 上的处理核心之间同步内存访问和值是复杂且昂贵的。

图1.16 共享内存架构在节点内提供并行化。

增加更多的 CPU 和处理核心并不会增加应用程序可用的内存量。这种情况以及同步成本限制了共享内存架构的可扩展性。

矢量单元：一条指令执行多个操作

为什么不像过去那样增加处理器的时钟频率以获得更高的吞吐量呢？增加 CPU 时钟频率的最大限制是它需要更多的电力并产生更多的热量。无论是 HPC 超级计算中心限制安装电源线还是你的手机具有有限的电池容量，现在的设备都有电力限制。这个问题被称为功率墙(the power wall)。

与其增加时钟频率，为什么不每个周期执行多个操作呢？这是许多处理器重新引入矢量化的想法。与单个操作（更正式地称为标量(scalar)操作）相比，在矢量单元中执行多个操作只需要稍微多一点能量。通过矢量化，我们可以在单个时钟周期内处理更多的数据，而不是进行串行处理。对于多个操作（而不只是一个）的功率需求几乎没有变化，执行时间的减少可以导致应用程序的能量消耗减少。就像一条四车道高速公路允许四辆车同时移动，而不是一条单车道，矢量操作提供了更大的处理吞吐量。事实上，图1.17中以不同阴影显示的矢量单元的四个通道通常称为矢量操作的通道。

图1.17 一个矢量处理示例，同时处理四个数组元素。

大多数 CPU 和 GPU 都具有某种矢量化或等效操作的能力。在一个时钟周期内处理的数据量，即矢量长度，取决于处理器上矢量单元的大小。目前最常见的矢量长度是256位。如果离散化的数据是64位的双精度数，则我们可以同时执行四个浮点操作作为矢量操作。正如图1.17所示，矢量硬件单元一次加载一块数据，同时对数据进行单个操作，然后存储结果。

加速设备：专用附加处理器

加速设备是一种专为以快速速度执行特定任务而设计的离散硬件。最常见的加速器设备是 GPU。当用于计算时，该设备有时被称为通用图形处理单元（GPGPU）。GPU 包含许多小型处理核心，称为流处理器（SMs）。虽然比 CPU 核心简单，但 SMs 提供了大量的处理能力。通常，你会在 CPU 上找到一个小型集成 GPU。

大多数现代计算机还配备有通过 Peripheral Component Interface（PCI）总线连接到 CPU 的独立 GPU（图1.18）。这个总线引入了数据和指令的通信成本，但独立卡通常比集成单元更强大。在高端系统中，例如，NVIDIA 使用 NVLink，AMD Radeon 使用他们的 Infinity Fabric 来减少数据通信成本，但这个成本仍然是相当大的。我们将在第 9-12 章讨论更多关于 GPU 架构的有趣内容。

图1.18 GPU有两种类型：集成和独立。独立或专用的GPU通常具有大量的流处理器和自己的DRAM。访问独立GPU上的数据需要通过PCI总线进行通信。

通用异构并行架构模型

现在让我们将所有这些不同的硬件架构结合成一个模型（图1.19）。两个节点，每个节点有两个CPU，共享同一片DRAM内存。每个CPU都是一个双核处理器，带有集成GPU。PCI总线上的独立GPU也连接到其中一个CPU。尽管CPU共享主内存，但它们通常位于不同的非均匀存储访问（NUMA）区域。这意味着访问第二个CPU的内存比访问自己的内存更昂贵。

图1.19 一个通用的异构并行架构模型，由两个节点通过网络连接而成。每个节点都有一个多核CPU，配有集成GPU和独立GPU，以及一些内存（DRAM）。现代计算硬件通常都有这些组件的一些配置。

在这次硬件讨论中，我们展示了一个简化的内存层次结构模型，只显示了DRAM或主内存。我们在综合模型中展示了一个高速缓存（图1.19），但没有详细说明其构成或工作原理。我们将在第3章讨论内存管理的复杂性，包括多级高速缓存。在本节中，我们只是简单地提供了一个针对现代硬件的模型，以帮助您识别可用的组件，以便您选择最适合您的应用程序和硬件选择的并行策略。

1.3.3 应用/软件模型适用于今天的异构并行系统

并行计算的软件模型必然受到底层硬件的影响，但仍然与硬件有所区别。操作系统提供了两者之间的接口。并行操作不会自行产生；相反，源代码必须指示如何通过生成进程或线程来并行化工作；将数据、工作和指令卸载到计算设备；或一次操作数据块。程序员必须首先暴露并行化，确定最佳的并行操作技术，然后明确地以安全、正确和高效的方式指导其操作。以下方法是最常见的并行化技术，然后我们将逐个详细介绍这些技术：

基于进程的并行化——消息传递
基于线程的并行化——通过内存共享数据
向量化——一条指令实现多个操作
流处理——通过专用处理器

基于进程的并行化：消息传递

消息传递方法是为分布式存储架构开发的，它使用显式消息在进程之间传递数据。在这种模型中，您的应用程序生成独立的进程，称为消息传递中的rank(进程编号)，每个进程都有自己的内存空间和指令流水线（图1.20）。图中还显示了进程被传递给操作系统以便在处理器上进行放置。应用程序位于标记为用户空间的图表部分，用户有权限操作。下面的部分是内核空间，受到用户危险操作的保护。

图1.20 消息传递库生成进程。操作系统将这些进程放置在两个节点的核心上。问号表示操作系统控制进程的放置，并可以在运行时根据虚线箭头所示移动这些进程。操作系统还为每个进程从节点的主存储器中分配内存。

请注意，处理器（CPU）拥有多个处理核心，这些核心与进程并不等同。进程是一个操作系统（OS）概念，而处理器是一个硬件组件。无论应用程序生成多少个进程，这些进程都由操作系统调度到处理核心上。实际上，在您的四核笔记本电脑上可以运行八个进程，这些进程只是在处理核心之间交换。因此，已经开发了机制来告诉操作系统如何放置进程以及是否将进程“绑定”到处理核心。有关控制绑定的详细信息，请参阅第14章。

要在进程之间传输数据，您需要将显式消息编程到应用程序中。这些消息可以通过网络或共享内存发送。许多消息传递库在1992年合并为消息传递接口（MPI）标准。自那时以来，MPI已经主导了这个领域，并几乎存在于所有超过单个节点的并行应用程序中。是的，您还会发现许多不同的MPI库实现。

分布式计算与并行计算

一些并行应用程序使用更低级别的并行化方法，称为分布式计算。我们将分布式计算定义为一组通过OS级别调用相互合作的松散耦合的进程。虽然分布式计算是并行计算的一个子集，但这个区别非常重要。分布式计算的示例包括点对点网络、万维网和互联网邮件。寻找外星智能（SETI@home）只是众多科学分布式计算应用程序的一个示例。

每个进程通常位于一个单独的节点上，并通过操作系统使用类似远程过程调用（RPC）或网络协议来创建。然后，进程通过进程间通信（IPC）传递消息来交换信息，这里有几种不同的方法。简单的并行应用程序通常使用分布式计算方法，但通常通过高级语言（如Python）和专门的并行模块或库来实现。

基于线程的并行化：通过内存共享数据

基于线程的并行化方法在同一进程中生成独立的指令指针（图1.21）。因此，您可以轻松地在线程之间共享进程内存的部分。但这也伴随着正确性和性能方面的问题。程序员需要确定指令集和数据的哪些部分是独立的并且可以支持线程。这些考虑在第7章中更详细地讨论，我们将会看到OpenMP，这是领先的线程系统之一。OpenMP提供了生成线程并将工作分配给这些线程的能力。

图1.21 线程并行化方法中的应用程序进程生成线程。这些线程受限于节点的领域。问号表示操作系统决定将线程放置在何处。一些内存在线程之间共享。

线程方法有许多不同的类型，从重型到轻型，由用户空间或操作系统管理。虽然线程系统在单个节点内扩展受限，但对于适度的加速来说，这是一个吸引人的选择。然而，单个节点的内存限制对应用程序有更大的影响。

向量化：一个指令处理多个数据

对于高性能计算中心，向量化应用程序可能比扩展计算资源更加成本有效，而且在便携设备如手机上可能是绝对必要的。在进行向量化时，工作是以2-16个数据项为一组进行的。这种操作分类的更正式术语是单指令多数据（SIMD）。在谈论向量化时，经常会使用SIMD这个术语。SIMD只是并行架构中的一个类别，在第1.4节将进一步讨论。从用户应用程序中调用向量化通常通过源代码的pragma或通过编译器分析完成。Pragma和指令是给编译器的提示，指导如何并行化或向量化代码的部分。Pragma和编译器分析高度依赖于编译器的功能（图1.22）。在这里，我们依赖于编译器，而前面的并行机制依赖于操作系统。此外，在没有显式编译器标志的情况下，生成的代码适用于最低性能的处理器和向量长度，极大降低了向量化的效果。有一些机制可以绕过编译器，但这些需要更多的编程工作，并且不具备可移植性。

图1.22 源代码中使用向量指令，不同编译器生成的代码性能也有所不同。

通过专用设备的流处理

流处理是一种数据流概念，其中数据流通过一个简化的专用处理器进行处理。这种技术长期以来一直用于嵌入式计算，在计算机显示器上渲染大量几何对象时，这种技术被适应到了一种专用处理器中，即GPU。这些GPU包含了广泛的算术运算和多个SM以并行处理几何数据。科学程序员很快发现了将流处理技术应用于大量模拟数据（如细胞）的方法，从而将GPU的角色扩展为通用图形处理器（GPGPU）。

在图1.23中，显示了通过PCI总线将数据和内核卸载到GPU进行计算的过程。与CPU相比，GPU的功能仍然有限，但在能够使用专门功能的情况下，GPU提供了极具计算能力的计算，而功耗较低。其他专用处理器也属于这一类别，不过我们的讨论重点在GPU上。

图1.23 在流处理方法中，数据和计算内核被转移到GPU及其流多处理器上。处理后的数据或输出传输回CPU进行文件IO或其他工作。

1.4 对并行方法进行分类

如果你阅读更多关于并行计算的内容，你会遇到诸如SIMD（单指令，多数据）和MIMD（多指令，多数据）之类的缩写。这些术语指的是由迈克尔·弗林在1966年提出的计算机架构类别，在所谓的弗林分类法中。这些类别有助于以不同的方式查看架构中的潜在并行化。分类是基于将指令和数据分解为串行或多个操作（图1.24）。请注意，尽管这个分类法很有用，但有些架构和算法并不完全符合某个类别。它的用处在于认识到SIMD等类别中存在潜在的条件困难。这是因为每个数据项可能希望处于不同的代码块中，但线程必须执行相同的指令。

图1.24 弗林分类法将不同的并行架构进行了分类。串行架构是单数据，单指令（SISD）。两个类别只有部分并行化，其中要么是指令并行，要么是数据并行，但另一个是串行。

在有多个指令序列的情况下，这个类别被称为多指令，单数据（MISD）。这不是常见的架构；最好的例子是对相同数据的冗余计算。这种方法常用于高度容错的应用，比如航天器控制器。由于航天器处于高辐射环境中，它们通常会运行两个副本的每个计算，并比较这两个副本的输出。

向量化是SIMD的一个典型例子，在这种情况下，相同的指令被应用于多个数据上。SIMD的一个变体是单指令，多线程（SIMT），通常用于描述GPU的工作组。

最后一个类别同时在指令和数据上进行并行化，被称为MIMD。这个类别描述了多核并行架构，它构成了大多数大型并行系统。

1.5 并行策略

在我们在第1.3.1节中的初始示例中，我们探讨了网格或像素的数据并行化。但是，数据并行化也可以用于粒子和其他数据对象。数据并行化是最常见的方法，通常也是最简单的方法。基本上，每个进程执行相同的程序，但在独特的数据子集上进行操作，如图1.25右上方所示。数据并行方法的优势在于，随着问题规模和处理器数量的增长，它能够很好地扩展。

图1.25 展示了不同的任务和数据并行策略，包括主-工作器、流水线或桶队列以及数据并行化。

另一种方法是任务并行。这包括具有工作线程、流水线或桶队列策略的主控制器，也显示在图1.25中。流水线方法在超标量处理器中使用，其中地址和整数计算由单独的逻辑单元完成，而不是由浮点处理器完成，这样可以使这些计算并行进行。桶队列利用每个处理器对数据进行一系列操作和转换。在主-工作器方法中，一个处理器负责调度和分配所有工作，每个工作器在返回前一个完成的任务时检查下一个工作项。也可以结合不同的并行策略来暴露更大程度的并行性。

1.6 并行加速与比较加速：两种不同的度量标准

在本书中，我们将介绍大量的比较性能数据和加速比。通常，速度提升这个术语被用来比较两个不同运行时间，但很少有解释或背景来完全理解它的含义。速度提升是一个通用术语，在许多情况下都会用到，比如量化优化效果等。为了澄清两种主要的并行性能数字之间的区别，我们将定义两个不同的术语。

并行加速：我们应该真正称之为串行到并行的加速。这种加速相对于在标准平台上进行的串行运行，通常是单个 CPU，来衡量。并行加速可能是由于在 GPU 上运行，或者使用 OpenMP 或 MPI 在计算机系统的所有核心上运行。

比较加速：我们应该真正称之为架构之间的比较加速。这通常是两个并行实现之间的性能比较，或者是在合理约束的硬件集之间的其他比较。例如，它可以是在计算机节点的所有核心上运行的并行 MPI 实现与 GPU(s) 之间的性能比较。

这两种性能比较的类别代表了两种不同的目标。第一个目标是了解通过添加特定类型的并行性能可以获得多少加速。然而，这不是一个公平的架构比较。这是关于并行加速的。例如，将 GPU 运行时间与串行 CPU 运行时间进行比较，这并不是一个公平的多核 CPU 和 GPU 之间的比较。而当尝试比较多核 CPU 与一个或多个 GPU 在一个节点上的性能时，架构之间的比较加速更为合适。

近年来，一些人对这两种架构进行了规范化，使得相对性能比较是基于相似的功耗或能量需求，而不是一个任意的节点。然而，由于有许多不同的架构和可能的组合，任何用来证明结论的性能数字都是可以获取的。你可以选择一个快速的 GPU 和一个慢速的 CPU，或者一个四核 CPU 与一个 16 核处理器进行比较。因此，我们建议您在性能比较中添加以下术语以提供更多的背景：

对每个术语添加 (Best 2016)。例如，并行加速 (Best 2016) 和比较加速 (Best 2016) 表示该比较是在特定年份发布的最佳硬件之间进行的（在这个示例中为 2016 年），您可能会比较高端 GPU 与高端 CPU。
如果这两种架构是在 2016 年发布的，但不是最高端的硬件，则添加 (Common 2016) 或 (2016)。这可能与顶级系统中找到的部件不同，这可能与更多主流部件相关。
如果 GPU 和 CPU 是在 2016 年的 Mac 笔记本或台式机上发布的，则添加 (Mac 2016)，或者其他品牌的固定组件类似的内容（在这个示例中为 2016 年）。这种类型的性能比较对于使用普遍可用系统的用户来说是有价值的。
添加 (GPU 2016:CPU 2013) 以显示进行比较的组件的发布年份可能不匹配（在这个示例中为 2016 年与 2013 年），这是一个可能的不匹配。

比较数字中不添加任何限定词。谁知道这些数字意味着什么？

由于 CPU 和 GPU 型号的爆炸性增长，性能数字将更多地是苹果和橙子之间的比较，而不是一个明确定义的指标。但是在更正式的环境中，我们至少应该指出比较的性质，以便他人更好地了解数字的含义，并对硬件供应商更公平。

1.7 在这本书中，您将学到什么？

本书是针对应用程序开发人员编写的，不假设您具有并行计算的先前知识。您只需要有提高应用程序性能和可扩展性的愿望。应用领域包括科学计算、机器学习以及在从桌面电脑到最大超级计算机的系统上分析大数据。

要充分从本书中受益，读者应该是熟练的程序员，最好是具有编译的高性能计算语言，如 C、C++ 或 Fortran 的经验。我们还假设读者具有对硬件架构的基本了解。此外，读者应该对计算机技术术语如位、字节、操作、缓存、RAM 等感到熟悉。

具有对操作系统的基本理解以及它如何管理和与硬件组件进行交互的基本知识也是有帮助的。阅读本书后，您将获得以下一些技能：

确定何时使用消息传递（MPI）比使用线程（OpenMP）更合适，反之亦然
估计矢量化可以带来多少速度提升
分辨出应用程序中哪些部分具有最大的速度提升潜力
决定何时利用 GPU 来加速您的应用程序可能会更有利
确定您的应用程序的最大潜在性能是多少
估计您的应用程序的能源消耗

即使在这第一章之后，您也应该对并行编程的不同方法感到自如。我们建议您在每章中完成练习，以帮助您整合我们提出的许多概念。如果您开始感到对当前并行架构的复杂性感到有些不知所措，那么您并不孤单。理解所有可能性是具有挑战性的。我们将在接下来的章节中逐步分解，以使其对您更容易理解。

Additional reading

可以在劳伦斯利弗莫尔国家实验室网站上找到关于并行计算的良好基础介绍：Blaise Barney，《并行计算简介》。https://computing.llnl.gov/tutorials/parallel_comp/.