多核及GPU程序设计1简介（下）性能指标：加速比、效率；及预测和测量并行程序性能：阿姆达尔定律、古斯塔夫森定律

1.4 性能指标

推动多核硬件和软件开发的动机是提取更高的性能：更短的执行时间、更大的问题和数据集等。显然，需要一个或多个客观标准来评估这些努力的有效性或益处。
至少，并行程序应该能够在执行时间方面胜过其顺序程序（但这不是每次都能拿到银行的东西）。执行时间的提升通常以加速比 (speedup) 来表示，其正式定义为以下比率：

其中，t-seq 是顺序程序的执行时间，t-par 是并行程序的执行时间，用于解决同一问题实例。
tseq 和 tpar 均为实际时间，因此并非客观数据。它们可能受以下因素影响：

• 编写实现的程序员的技能 •
• 编译器的选择（例如，GNU C++ 与 Intel C++） •
• 编译器开关（例如，打开/关闭优化） •
• 操作系统
• 保存输入数据的文件系统类型（例如，EXT4、NTFS 等） •
• 时间（不同的工作负载、网络流量等）。

为了对报告的加速比数据有一定程度的信心，应遵循以下规则：

• 所有程序（顺序和并行）都应在相同的软件和硬件平台上，并在类似的条件下进行测试。
• 顺序程序应是已知问题中最快的解决方案。

第二个要求是两者中最不明显的，但却是一个至关重要的要求：并行算法与顺序算法完全不同。事实上，顺序算法可能没有并行派生算法。甚至并行派生算法根本不可能被创建。第二个要求背后的原因是一个根本性的原因：实现并行程序所需的大量工作（就开发成本而言，高昂的工作量）只有在能够带来切实的收益时才是合理的。

对于给定数量的处理器，并行算法提供的加速比仍然会根据输入数据而变化。因此，通常在对大量相同规模的输入测试两个程序后，报告其加速比的平均值，或者甚至报告观察到的平均值、最大值和最小值。

加速比仅能说明部分问题：它可以告诉我们加速问题的求解是否可行，例如，加速比是否大于 1。它无法告诉我们是否可以高效地完成求解，即是否可以使用少量资源。为此目的采用的第二个指标是效率。效率的正式定义为以下比率：

其中，N 是用于执行并行程序的 CPU/核心数量。效率可以理解为并行执行期间节点被利用时间的平均百分比。如果效率等于 100%，则意味着加速比为 N，工作负载在 N 个处理器之间平均分配，这些处理器的利用率为 100%（执行期间从不空闲）。当加速比 = N 时，相应的并行程序表现出所谓的线性加速。

遗憾的是，这只是理想情况。当多个处理器共同努力实现某个目标时，它们需要花时间相互协调，无论是图 1.1 (a) 加速比曲线，还是 (b) 效率曲线，它们都用于在多核 CPU 上通过可变数量的线程执行并行积分计算。每条曲线对应于 x 范围的不同划分数（如图例所示）。(a) 中的理想加速比线衡量了性能下降，这是协调成本增加的一个常见问题。通过交换消息或处理共享资源。与活动相关的协调会占用 CPU 时间，最终导致加速比低于 N。

下图展示了一个示例程序的加速比和效率曲线，该程序通过应用梯形规则算法计算函数的定积分。

计算负载由计算中使用的梯形数量控制。结果是在 i7 950 四核 CP 上获得的，并且是 10 次运行的平均值。对于谨慎的读者来说，这里有一个矛盾之处：如果我们只有四核 CPU，如何测试和报告八个线程的加速比？i7 950 四核 CPU 支持一种称为超线程的技术，6 该技术允许一个 CPU 内核通过复制CPU 硬件的各个部分。启用此功能的 CPU 看起来拥有实际两倍的物理核心数。遗憾的是，性能平均只提高了 30%，与建议的两倍提升相差甚远。因此，上图报告的结果存在偏差，因为在给定平台上，我们并没有 8 个不同的物理 CPU 来运行 8 个线程。

然而，随着线程数增加，效率下降并非偶然：这是并行应用程序的典型行为，尽管下降程度因应用程序而异。这一切都归结于我们通常所说的协调成本，而这只有在更多参与方/CPU 相互通信时才会增加。超线程是英特尔创造的一个营销术语，指的是所谓的硬件线程。

上图有两个用途：(a) 它展示了典型的速度和效率曲线；(b) 它提高了人们对正确实验技术的认识。衡量性能应该涉及真实的硬件资源，而不是超线程提供的虚拟资源。

上图中的理想加速曲线衡量了并行程序的成功程度。正如我们提到的，这是性能的上限。但并非总是如此！在某些情况下，加速比 > N，效率 > 1，这被称为超线性加速场景。根据我们对效率的解释，这似乎是不可能的。然而，我们应该记住，顺序程序和并行程序以不同的方式处理其输入数据，遵循不同的执行路径。因此，如果程序的目标是在搜索空间中获取某个对象，那么并行程序可能只需遵循不同的路径即可比所用计算资源数量所暗示的更快地达到这一点。

加速比涵盖了并行解决方案的有效性：它是否有用？效率是衡量资源利用率的标准：我们投入的计算资源所能提供的潜力有多少被实际利用？效率低表明设计不佳，或者至少需要进一步改进。
最后，我们想知道并行算法在计算资源和/或问题规模增加时的表现如何：它是否具有可扩展性？
通常，可扩展性是指（软件或硬件）系统高效处理不断增长的工作量的能力。在并行算法和/或平台的背景下，可扩展性转化为能够 (a) 解决更大的问题和/或 (b) 整合更多的计算资源。
有两个指标用于量化可扩展性：强扩展效率（与 (b) 相关）和弱扩展效率（与 (a) 相关）。强扩展效率的定义与公式 (1.2) 中定义的通用效率相同：

它是用于解决与单个处理器相同问题的处理器数量 N 的函数。
弱扩展效率同样是用于解决处理器数量 N 的函数：

其中 t′par 是解决比单个机器解决时间 tseq 大 N 倍的问题所需的时间。

有许多当涉及 GPU 计算资源时，计算扩展效率时存在一些问题：应该使用多少 N 值？GPU 通常拥有数百或数千个核心，但将单个 GPU 核心上的执行时间报告为 tseq 会显得笨拙或不科学。如果我们选择将单个 CPU 核心的执行时间报告为 tseq，那么在计算效率时，我们是否应该将 GPU 核心总数作为 N？此外，GPU 是托管设备，即它需要一个 CPU 代表其执行 I/O。这个 CPU 算数吗？
显然，在这种情况下，效率可以通过多种不同的方式计算。为了避免争议，我们仅报告涉及异构平台的案例研究中的加速比数据。

参考资料

• 软件测试精品书籍文档下载持续更新 https://github.com/china-testing/python-testing-examples 请点赞，谢谢！
• 本文涉及的python测试开发库 谢谢点赞！ https://github.com/china-testing/python_cn_resouce
• python精品书籍下载 https://github.com/china-testing/python_cn_resouce/blob/main/python_good_books.md
• Linux精品书籍下载 https://www.cnblogs.com/testing-/p/17438558.html
• python八字排盘 https://github.com/china-testing/bazi
• 联系方式：钉ding或V信: pythontesting

1.5 预测和测量并行程序性能

构建并行应用程序比构建其对应的顺序应用程序更具挑战性。程序员必须解决协调问题，例如如何正确访问共享资源、负载平衡问题（即如何在可用计算资源之间分配工作负载以最小化执行时间）、终止问题（即以协调的方式暂停程序）等等。

只有当应用程序能够通过加速问题解决方案真正受益时，才应该尝试进行此类尝试。开发成本决定了我们不能仅仅实现多个备选设计并进行测试以选出最佳方案，或者更糟的是，评估项目的可行性。对于最简单的问题来说，这或许是可行的，但即使如此，如果我们能够先验地确定最佳的开发路线，那就更好了。

问题的并行解决方案的开发始于其串行变体的开发！这听起来似乎自相矛盾，但请尝试回答这些问题：如果我们没有串行解决方案可以比较，我们如何知道并行解决方案的速度有多快？我们需要一个基准，而这只能通过顺序解决方案获得。此外，我们如何检查并行程序生成的解决方案是否正确？顺序程序的输出并不能保证正确，但使其正确要容易得多。
顺序算法和相关程序的开发也可以为并行化设计提供重要的参考。

这是一个实际问题，因为我们需要回答以下与并行程序的可行性和成本效益相关的问题：

• 程序中最耗时的部分是什么？这些部分应该是并行执行的主要候选。
• 一旦确定了这些部分并假设它们可以并行化，可以预期获得多少性能提升？
  这里需要澄清的是：所需的顺序程序并非只是解决同一问题的任何顺序程序。它必须是被并行化的同一算法的顺序实现。例如，如果我们需要并行排序数据，那么适合并行实现的算法是桶排序。桶排序的顺序实现可以帮助预测并行性能，并找出算法中最耗时的部分。快速排序的顺序实现可以提供基准性能信息，但它无法解决上述两个问题。
  一旦实现了顺序版本，我们就可以使用性能分析器来回答这些问题。性能分析器是一种工具，可以收集有关程序各部分调用频率、调用持续时间以及内存使用量的信息。性能分析器使用多种不同的技术来执行其任务。最常用的技术是：
• 仪表化：修改被分析程序的代码，以便收集信息，例如，在执行任何指令之前增加一个特殊计数器。这会产生非常准确的信息，但同时也会大大增加执行时间。此技术需要重新编译目标程序。
• 采样：目标程序的执行会被定期中断，以便查询正在执行的函数。显然，这种方法的准确性不如仪表化。虽然需要进行插桩，但程序不需要重新编译，执行时间也仅会受到轻微影响

下图为kcachegrind 的示例屏幕截图，显示了顺序桶排序实现的分析结果，该实现在桶较小时会切换到快速排序。
valgrind 分析工具集合包含一个基于插桩的分析器。插桩在分析之前执行，这意味着无需用户干预。这是一个调用示例：

$ valgrind --tool=callgrind ./bucketsort 1000000

其中 ./bucketsort 1000000 是待分析的程序及其参数。分析结果文件名为“callgrind.out”，其中包含分析结果。分析结果可以通过 kcachegrind 等前端程序进行可视化。

经验和对问题领域的深入了解是宝贵的资源，它们可以帮助人们精准定位需要并行化的“热点”，而无需对顺序程序进行性能分析。

然而，性能分析器可以帮助我们回答上面提出的第二个问题，即我们可以从并行解决方案中获得多少潜在性能。传统上，这是通过近似数学模型来实现的，这些模型使我们能够捕捉待执行计算的本质。这些模型的参数可以通过对顺序应用程序进行性能分析来估算。在下一节中，我们将描述基于这种简单模型的阿姆达尔定律。

无论数学模型的性能预测如何，出于两个原因，必须对已实施的并行设计进行实际测试：正确性和性能。必须验证并行实现的正确性。并行程序的行为可能具有不确定性，因为以未指定的顺序发生的事件可能会影响计算结果。除非事先计划，否则不确定性是一种不良特性，如果存在，必须根除。此外，测试还可以揭示原始设计的缺陷或需要解决的性能问题。
以下列表包含执行正确实验程序的准则：

• 除非另有明确说明，否则应测量整个执行的持续时间。例如，如果仅要并行化程序的一部分，则只能针对执行时间线的特定部分计算速度和效率。然而，总体时间可以用来衡量并行解决方案的影响及其是否具有成本效益。例如，一个程序解决问题需要 100 秒，如果其中 10% 的部分以 100 倍的速度执行，仍然需要 90 多秒。
• 结果应以多次运行的平均值形式报告，可能包含标准差。运行次数因应用而异，例如，将一个持续 3 天的实验重复 100 次，并且对于许多不同的场景来说，这是完全不现实的。然而，为了解决这个问题，三次运行的平均值只能产生不可靠的统计数据。因此，必须谨慎权衡。
• 异常值（即过大或过小的结果）应从平均值计算中排除，因为它们通常表示异常情况（例如，主内存耗尽或机器工作负载发生变化）。然而，应给出理由，以免不利结果被一笔带过，而只加解释。
• 可扩展性至关重要，因此应报告各种输入规模（理想情况下涵盖实际数据的大小和/或质量）和各种并行平台规模的结果。
• 测试输入应从非常小到非常大不等，但如果可以识别，则应始终包含生产环境中典型的问题规模。
• 当使用多核机器时，如果要计算效率，线程和/或进程的数量不应超过可用的硬件核心数量。超线程是一种特殊情况，因为这项技术使CPU在操作系统看来拥有实际核心数量的两倍（或更多）。然而，这些逻辑核心与满负荷核心的能力并不匹配。因此，尽管操作系统可能报告例如八个核心的可用性，但相应的硬件资源并不存在，这实际上损害了任何可扩展性分析。理想情况下，为了衡量可扩展性，应该禁用超线程，或者将线程数限制为硬件核心数。

在某些情况下，线程数多于核心数是有利的：如果某些线程因某种原因阻塞，其余线程仍然可以利用 CPU。但是，在计算效率时，N 应该是核心数，而不是线程/进程数。为了在不经历昂贵的并行程序实现和测试步骤的情况下预测并行性能，提出了以下章节中描述的两条定律。尤其是阿姆达尔定律，尽管已被证明存在缺陷，但仍然具有影响力。

1.5.1 阿姆达尔定律

1967 年，吉恩·阿姆达尔 (Gene Amdahl) 设计了一个简单的思想实验，用于推导并行程序可以预期的性能优势。阿姆达尔假设：

• 顺序应用程序，在单个 CPU 上执行需要 T 时间。
• 该应用程序由 0 ≤ α ≤ 1 个可并行的部分组成。剩余的 1 − α 必须顺序执行。
• 并行执行不会产生通信开销，并且可并行化的部分可以在任意数量的 CPU 之间平均分配。此假设尤其适用于多核架构，因为这些架构中的内核可以访问相同的共享内存。
  基于上述假设，N 个节点获得的加速比应该有上限：

因为我们忽略了任何分区/通信/协调成本。如果我们获得 N → ∞ 的极限，则等式 (1.5) 也可以给出最大可能的加速比：

上面以简单易记的形式解决了一个难题：并行程序能将问题解决得快多少？而且，它以一种完全抽象的方式进行计算，没有考虑计算平台的特性。它仅依赖于问题的特性，即 α。显而易见的是，预测的加速比受到严重限制。即使对于较小的 α 值，最大加速比也很低。例如，如果 α = 0.9，则无论使用多少处理器来解决问题，加速比都小于 10。

阿姆达尔定律有一个有趣的推论，这或许就是它被提出的动机。阿姆达尔定律是在小型计算机问世的时代制定的。小型计算机比当时占主导地位的大型机便宜得多，但性能也较弱。图 1.1 不同 α 值下的加速曲线，即应用程序中可以并行化的部分，正如阿姆达尔定律所预测的那样。

1.5.2 Gustafson–Barsis 的反驳

阿姆达尔定律存在根本性缺陷，因为它已被反复证明无法解释经验数据：并行程序通常会超出预测的加速极限。
最终，在阿姆达尔定律发表二十年后，Gustafson 和 Barsis 终于从正确的角度审视了这个问题。
并行平台的作用不仅仅是加快顺序程序的执行速度。它可以容纳更大的问题实例。因此，与其考察并行程序相对于顺序程序的性能，不如考察如果顺序机器需要解决并行程序能够解决的相同问题，其性能会如何。
假设：

• 我们有一个并行应用程序，在 N 个 CPU 上执行需要 T 时间。
• 该应用程序在所有机器上运行的总时间中，0 ≤ α ≤ 1。剩余的 1 − α 必须顺序执行。

在顺序机器上解决同一问题需要的总时间为：
Tseq = (1 − α)T + N · α · T

那么加速比为：

相应的效率为：

当 N 趋于无穷大时，效率的下限为 α。
上图所示的加速曲线完全忽略了通信成本，结果显然过于理想化，但潜力确实存在。
下图的效率曲线仍然乐观。即使 α = 50%，在最多 16 个 CPU 的情况下，效率也不会低于 50%。这简直好得令人难以置信。即使对于所谓的高度并行问题，随着 N 的增加，通信开销也会成为一个决定性因素，导致加速增益降低，效率骤降。一般来说，在实践中获得 90% 以上的效率，我认为是一项值得称道的成就。