5,707 讀數

深入研究阿姆达尔定律和古斯塔夫森定律

经过 Durganshu Mishra14m2023/11/11

太長; 讀書

当算法可以动态调整计算量以匹配可用的并行化时，古斯塔夫森定律就适用。相比之下，当计算负载固定并且不能通过并行化显着改变时，阿姆达尔定律更合适。应根据问题的性质进行弱测试和扩展测试。

想象一下：您急于准备一顿美味的盛宴，但您受到厨房大小和甲板上人员数量的限制。在并行计算的世界中，阿姆达尔定律和古斯塔夫森定律是您优化烹饪杰作所需的可靠配方。它们就像数十年来提高计算机性能的秘密成分，使我们能够享受更快的处理速度。这两个原则可能是并行计算的阴阳，它们一直在指导精通技术的奇才们征服多核处理器和高性能计算领域。但是阿姆达尔定律和古斯塔夫森定律是什么？它们如何单独或协同发挥作用？意识到并行编程的重要性，今天我们将深入研究这些法则的复杂性，并发现如何将它们作为知识渊博的程序员手中的强大工具来运用。

阿姆达尔定律：背景

早在 67 年，在春季联合计算机大会上，吉恩·阿姆达尔 (Gene Amdahl) 博士在 IBM 进行了一些严肃的计算机魔法，并与其他三位精通技术的人聚在一起，其中包括天才丹尼尔·斯洛特尼克 (Daniel Slotnick)，他是 Illiac-IV 内部运作背后的天才。你问他们在做什么？嗯，他们正在讨论计算机架构的未来。在这次会议上，Gene Amdahl 博士阐述了他对“多处理器方法”在处理现实世界问题及其所有混乱怪癖时所面临的障碍的看法。你猜怎么着，他对解决此类性质问题的“单处理器方法”大加赞赏！

在 IBM 工作期间，阿姆达尔敏锐地注意到，计算工作的很大一部分都被他恰当地称为“数据管理内务”的工作占据了。他坚定地认为，这一特定部分在大约十年内一直保持着惊人的一致性，始终吞噬着生产运行中执行指令的 40%。

这项“家政”工作的范围包括哪些内容？它涵盖了广泛的计算任务，这些任务虽然很重要，但并不直接有助于核心计算任务。根据具体的算法和应用程序，这可能涉及数据 I/O、预处理、内存管理、文件处理等。这种一致性表明，对于许多应用程序来说，很大一部分处理时间都花在这些任务上。一定程度的数据管理工作几乎是不可避免的，并且很难大幅减少。 Amdahl 指出，这种开销似乎是连续的，这意味着它是逐步发生的，并且不适合并行处理技术。

“此时可以得出的一个相当明显的结论是，为实现高并行处理速率而付出的努力是浪费的，除非它伴随着几乎相同数量级的顺序处理速率的成就。” - 吉恩·阿姆达尔博士[1]

Amdahl 在他的原始论文[1] 中补充道，“内务管理”任务领域只是“多处理器”方法面临的挑战的冰山一角。阿姆达尔是一名训练有素的理论物理学家，拥有博士学位，背景令人印象深刻，他对计算机设计要解决的现实世界物理挑战有着深入的了解。他强调了许多复杂性，例如不规则边界、不均匀内部以及对可变状态的空间和时间依赖性，所有这些都为“多处理器”范式带来了巨大的障碍。

例如，考虑计算二维笛卡尔网格上的热量分布。在任何给定点，温度 (T) 取决于相邻点的温度。当采用并行计算模型时，必须将这些值与相邻点进行通信，这些值可以存储在单独的处理器上。这些问题在当代情景中仍然普遍存在。

值得庆幸的是，计算专家的集体智慧已经产生了许多专门用于应对这些复杂挑战的数值方法和编程技术。

阿姆达尔定律：最大加速比

在阿姆达尔的原创作品中，他的公式并没有深入研究数学方程；而是深入研究了数学方程。只有在随后的分析中才对最大加速进行了量化。

阿姆达尔定律基于以下假设：串行程序执行时间的一小部分f理想情况下可以并行化，而无需任何通信或同步开销。互补部分表示为s = 1 − f，是完全连续的。

因此，如果T是顺序程序的执行时间，则p 个内核上的执行时间T(p)由下式给出：

Speedup是顺序执行时间与并行执行时间的比率，给出：

因此，加速比的上限可以定义为：

注意事项

尽管阿姆达尔定律很简单，但它也有其局限性。该模型忽略了关键的硬件瓶颈，例如内存带宽、延迟和 I/O 限制。它还没有考虑线程创建、同步、通信开销和其他现实因素的性能缺陷。遗憾的是，这些未考虑的因素通常会对实际绩效产生不利影响。

下图说明了由阿姆达尔定律确定的并行化对加速的影响。很明显，即使并行率高达 95%，并且有大量处理器，可实现的最大加速也只能达到 20 倍左右。将并行化百分比提高到 99% 并使用无限多个处理器可以产生更令人印象深刻的 100 倍加速，这是有希望的。

然而，重要的是要认识到拥有如此多的处理器是罕见的。我们通常使用的数量要少得多，例如 64 甚至更少。

当我们将阿姆达尔定律应用于使用 64 个处理器的程序时（f 为 95%），最大加速徘徊在 15.42 倍左右。诚然，这个数字并不乐观！

这种见解在某种程度上被这个表达式中使用的限制所掩盖：

这个限制往往掩盖了这样一个事实：当我们考虑实际的、真实的处理器数量时，加速数字明显较低。

尽管如此，阿姆达尔定律最显着的缺点在于它假设当使用更多内核来执行应用程序时问题大小保持不变。

本质上，它假设可并行部分保持不变，无论使用多少个核心。约翰·古斯塔夫森 (John L. Gustafson)彻底解决并扩展了这一局限性，他提出了一种改进的观点，现在称为古斯塔夫森定律。然而，尽管存在这些公认的问题和警告，但必须认识到阿姆达尔定律有其自身的优点，为并行化的复杂性提供了宝贵的见解。阿姆达尔定律以强缩放测试的形式得到应用，我们稍后将探讨这个主题。

古斯塔夫森定律：背景

在桑迪亚国家实验室研究大规模并行计算系统时， John L. Gustafson 博士和他的团队在 1024 个处理器的超立方体上针对三种不同的应用程序获得了令人印象深刻的加速系数。序列码的比例相当于 0.4-0.8%。

“......我们在 1024 个处理器的超立方体上实现了我们认为前所未有的加速因子：使用共轭梯度进行梁应力分析的加速因子为 1020，使用显式有限差分的挡板表面波模拟的加速因子为 1020，使用通量校正的不稳定流体流动的加速因子为 1016运输。” — 约翰·古斯塔夫森博士[2]

我们在上一节中清楚地看到，根据阿姆达尔定律，大量处理器可实现的最大加速比为 1/s。那么，如何才能实现 1021 倍的令人困惑的加速呢？

Gustafson [2]强调数学表达式有一个微妙的假设，这意味着变量f与p无关。然而，这种情况很少是我们遇到的现实。在现实场景中，我们通常不会采用固定大小的问题并在不同数量的处理器上运行它，除非在学术研究的受控环境中。相反，在实际应用中，问题的规模往往随着处理器的数量而增加。

当更强大的处理器可用时，用户会通过扩大问题的复杂性来适应，以充分利用增强的功能。他们可以微调网格分辨率、时间步数、差分运算符的复杂性以及其他参数等方面，以确保程序可以在所需的时间范围内执行。

根据古斯塔夫森的说法，在实践中，假设运行时间保持相对恒定而不是问题大小通常更现实。

古斯塔夫森注意到，程序的并行或向量部分与问题大小成比例增长。矢量启动、程序加载、串行瓶颈和 I/O 操作等元素共同构成了程序运行时的s组成部分，通常保持相对恒定，并且不会随着问题大小而显着增长。

古斯塔夫森进一步论证，强调在物理模拟中将自由度加倍的情况下，处理器数量相应加倍通常是必要的。初步估计，可以有效并行分配的工作量往往随着处理器数量的增加而线性增长。

在对提到的三个应用程序进行深入检查时，Gustafson 和他的同事发现并行组件显示的缩放因子大约为 1023.9969、1023.9965 和 1023.9965。

古斯塔夫森定律：按比例加速

Gustafson 的假设在于考虑p 个核心上的归一化运行时间，其总和为(1 − f) + f ，从而得出总值为 1。按照此逻辑，如果(1 − f) + f表示p 个核心上的运行时间，那么单核上的运行时间可以表示为(1 − f) + p*f 。因此，古斯塔夫森称之为“缩放加速比”的加速比可以计算如下：

当我们将古斯塔夫森定律应用于使用 64 个处理器的程序时（f 为 95%），预计加速率为 60.85 倍（与阿姆达尔定律的 15.42 倍相比）。现在我们正在说话😉

下图突出显示了这两个法律之间的差异。

注意事项

Amdahl 和 Gustafson 的观点对并行化提出了不同的观点，每个观点都有自己的假设。

阿姆达尔定律假设可以并行化的工作量是恒定的并且与处理器的数量无关，因此非常悲观。 Gustafson 的观点假设可以并行的工作量随着核心数量线性增长，这对于许多场景来说无疑是实用的。然而，有时可能过于乐观。

现实世界的应用程序经常遇到可能限制这种线性可扩展性的约束。例如，随着核心数量的增加，由于并行处理、数据依赖性和通信开销的复杂性，可能会出现回报递减。此外，硬件限制实际上限制了可以有效集成到单个芯片中的内核数量。古斯塔夫森定律可能并不总能解释这些复杂的现实世界挑战，因此有必要考虑影响其适用性的警告。

古斯塔夫森定律的有效性还取决于应用本身的性质。虽然一些应用程序随着核心数量的增加自然而然地适合线性可扩展性，但其他应用程序可能由于固有的限制或问题的性质而更快地达到稳定水平。在考虑实际应用中线性可扩展性的可行性时，必须考虑编程复杂性和收益递减的可能性。

本质上，在提供对并行化更加乐观的展望的同时，古斯塔夫森定律的应用需要对应用程序、硬件限制和并行编程的复杂性有深入的了解，以适应现代计算的现实世界的复杂性。

强缩放与弱缩放

从本质上讲，可扩展性是指系统或应用程序随着其规模的扩大而有效管理增加的工作负载的能力。

在计算中，无论是硬件还是软件，可扩展性都表示通过增加可用资源来增强计算能力的能力。

在高性能计算（HPC）集群的背景下，实现可扩展性至关重要；它意味着能够通过集成额外的硬件组件来无缝扩展系统的整体容量。对于软件而言，可扩展性通常与并行化效率同义，表示使用特定数量的处理器时实现的实际加速与可实现的理想加速之间的比率。该指标提供了有关软件如何有效地利用并行处理来提高性能的见解。

扩展测试

在大型应用程序的典型开发过程中，从一开始就以完整的问题大小和最大处理器数量开始测试通常是不切实际的。这种方法需要延长等待时间并过度利用资源。因此，更务实的策略包括首先缩小这些因素，从而加速测试阶段，并允许更精确地估计最终全面运行所需的资源，从而有助于资源规划。

可扩展性测试是评估应用程序适应不同问题规模和不同处理器数量的能力的方法，以确保最佳性能。

需要注意的是，可扩展性测试不会仔细检查应用程序的整体功能或正确性；而是会检查应用程序的整体功能或正确性。它的主要重点是计算资源调整时的性能和效率。

并行计算中广泛采用两种标准扩展测试：强扩展测试和弱扩展测试。

强大的扩展性

强扩展涉及增加处理器数量，同时保持问题大小不变。这种方法减少了每个处理器的工作负载，这对于长时间运行的 CPU 密集型应用程序尤其有价值。强大扩展的主要目标是确定一种配置，该配置可以提供合理的执行时间，同时将资源成本保持在可管理的范围内。

强缩放以阿姆达尔定律为基础，问题大小保持固定，同时处理元素的数量增加。对于具有大量 CPU 限制工作负载的程序，这种方法通常是合理的。

强扩展的最终目标是找到最佳的“最佳点”，使计算能够在合理的时间范围内完成，同时最大限度地减少并行开销造成的处理周期的浪费。

在强扩展中，如果加速（以每单位时间完成的工作单元表示）与所使用的处理元素的数量 (N) 一致，则认为程序是线性扩展的。同样，加速可以是次线性的，甚至是超线性的，具体取决于它如何随处理器数量扩展。

最后，我尝试对我的代码之一执行强大的扩展测试。 Fluidchen-EM是一款计算流体动力学求解器，能够解决许多流体动力学问题。以下结果对应于盖驱动腔的模拟。最终时间戳（收敛后）的速度被可视化，并计算执行运行时间。 Fluidchen-EM 使用 MPI 将计算域分配到iproc*jproc处理器中。

注意：结果是在我的个人计算机上运行的，所有内核仅对应于一个处理器。如果模拟在更大更好的机器上运行，结果可能会有所不同！

计算域共划分为imax*jmax个网格点。
iproc： x 方向的处理器数量
jproc： y方向的处理器数量

如图所示，随着处理器数量从 1 个增加到 2 个，执行时间急剧减少。但是，下一次处理器数量从 2 个增加到 4 个时，加速效果并不那么显着，甚至在进一步增加时开始饱和。在处理器的数量上。然而，结果是在具有八核的处理器上编译的，因此如果在更大、更强大的机器上执行，这些结果可能会改变。

弱扩展

在弱扩展中，处理器数量和问题规模都会增加，从而保持每个处理器的恒定工作负载。弱缩放符合古斯塔夫森定律，其中缩放加速是根据缩放问题大小的工作负载计算的，而不是阿姆达尔定律，后者侧重于固定问题大小。

分配给每个处理元素的问题大小保持不变，允许额外的元素共同解决更大的整体问题，这可能超出单个节点的内存容量。

弱扩展证明具有大量内存或资源需求（内存限制型）的应用程序是合理的，这些应用程序需要比单个节点可以提供的内存更多的内存。此类应用程序通常会表现出高效的扩展性，因为它们的内存访问策略优先考虑附近的节点，使它们非常适合更高的核心数量。

在弱扩展的情况下，当工作负载与处理器数量成正比增加时，运行时间保持恒定，即可实现线性可扩展性。

大多数采用这种模式的程序都表现出对更高核心数量的有利扩展，特别是那些采用最近邻居通信模式的程序，因为无论使用多少进程，它们的通信开销都保持相对一致。这一趋势的例外包括严重依赖全球通信模式的算法。

最后，我使用Fluidchen-EM执行了弱缩放测试。以下结果对应于瑞利-贝纳德对流的模拟。同样，最终时间戳（收敛后）的速度被可视化，并计算执行运行时间。 Fluidchen-EM 使用 MPI 将计算域分配到iproc*jproc处理器中。

注：结果是在我的个人电脑上运行的，所有核心仅对应一个处理器。如果模拟在更大更好的机器上运行，结果可能会有所不同！

计算域共划分为imax*jmax个网格点。
iproc： x 方向的处理器数量
jproc： y方向的处理器数量
imax：沿通道长度的网格点数
jmax：沿通道高度的网格点数
xlength：通道长度
ylength：通道的高度

如上图所示，执行时间随着问题规模和处理器数量的增长而增加。这种行为可以归因于几个因素。由于所有内核都驻留在单个处理器上，随着问题规模的扩大和更多处理器的参与，部分处理时间会消耗在建立 MPI（消息传递接口）通信上。此外，较大的问题规模需要增加内核之间的数据交换，从而由于通信网络的有限带宽而放大了通信延迟。

因此，这些测试结果为问题的并行化提供了重要的见解。

结论

算法并行化中Gustafson定律和Amdahl定律的选择取决于计算工作量的适应性。当算法可以动态调整计算量以匹配可用的并行化时，古斯塔夫森定律就适用。相比之下，当计算负载固定并且不能通过并行化显着改变时，阿姆达尔定律更合适。在现实场景中，采用并行化算法通常涉及一定程度的计算修改，这两个定律都可以作为有价值的基准，提供预测加速的上限和下限。它们之间的选择取决于并行化过程中引入的计算变化的程度，从而能够全面评估潜在的加速增益。