识别并行应用程序中的可伸缩性问题
如何使用新的 Intel® VTune™ Amplifier 内存分析来提高 Intel® Xeon 和 Intel® Xeon Phi™ 处理器的可伸缩性
点击此处注册并下载免费的 Intel® Parallel Studio XE 30天试用版.
Vladimir Tsymbal，英特尔公司软件技术咨询工程师
随着现代系统计算核心数量的不断增加，我们期望并行良好的软件能够随着核心数量的增加而提高性能——最好是线性的。然而，在多核系统上，有一些因素限制了并行性和可伸缩性。本文不打算涵盖所有这些因素。但在大多数情况下，限制是由于并行实现的
- 负载不平衡，导致线程和 CPU 核心空闲。
- 过度同步，结果是 CPU 时间在自旋等待和其他非生产性工作中被浪费。
- 并行运行时库开销，这可能是由于误用了库 API。
当这些限制因素被消除时，并行效率会显著提高——所有 CPU 核心都忙于执行有用的工作。在 STREAM 或 LINPACK 等经过良好调优的基准测试中，可以看到接近线性的加速。然而，随着系统上核心数量的增加（或当您的代码在具有更多核心的新系统上运行时），您可能会注意到应用程序的性能并未线性增长——或者并行性开始趋于平稳（图 1）。
根据自顶向下性能分析方法¹，您应该首先检查是否有其他组件限制了性能。确保
- 您的系统没有不断忙于其他可能消耗资源的事情，例如消耗计算时间的其他应用程序或服务。
- 您的应用程序没有绑定到系统 I/O（例如，等待磁盘或其他文件系统或网络系统操作完成）。
- 您的系统拥有足够的物理内存，以避免频繁地交换到硬盘驱动器。
作为一项通用建议，您应该了解硬件是否配置正确，内存子系统是否提供了预期的性能特征。例如，您已将所有内存插槽都装满了与主板特性（例如，通道数、内存速度）相符的 DIMM。您可以使用已知的基准测试轻松检查硬件性能。进行此类检查很重要，因为修复硬件问题比优化软件更容易。
完成所有这些检查后，将内存延迟视为并行可伸缩性差的主要原因之一。在 x86 系统体系结构中，CPU 从其缓存子系统中检索数据。理想情况下，在指令需要数据（图 2）时，数据会驻留在离 CPU 最近的缓存（L1 数据缓存）中。请求的数据离 CPU 越远，传输到 CPU 核心执行单元所需的时间就越长。CPU 硬件预取器应有助于更快地将数据调入，但这并非总是可能的。数据经常被延迟，这会使 CPU 停滞。²
基本上，数据延迟有两个原因
- 当 CPU 的 EXE 单元中执行的指令请求数据时，数据位会从主内存或其他缓存长途跋涉到 CPU 的 L1D（即，预取器未能工作）。这会造成**内存延迟**问题。
- 提前请求数据（即，预取器已完成工作），但由于传输基础设施容量的限制，数据在传输到 CPU 的途中被卡住了。这会造成**内存带宽**问题。
当然，如果多个源发出多个请求，可能会出现这两种问题。为了避免这些问题，明智地使用数据很重要。要解决内存延迟问题，请确保按地址增量访问数据。顺序数据访问（甚至单位步幅，具有恒定的小距离）可以使预取器的工作更轻松，并加快数据访问速度。要解决内存带宽问题，请重用数据并尽可能将其保留在缓存中。任何一种解决方案都需要重新考虑数据访问模式，甚至整个算法的实现。
是什么限制了您应用程序的可伸缩性？
一旦我们确定代码在 CPU 上的执行效率低下，并且观察到大多数停顿都是由内存引起的，我们就需要定义具体的内存问题，因为解决方案取决于问题是由于内存延迟还是带宽引起的。我们将使用 Intel® VTune™ Amplifier 的嵌入式内存访问分析来详细调查内存问题。
让我们考虑改进简化矩阵乘法基准测试的几次迭代。尽管它很简单，但它有效地演示了根据算法实现方式可能发生的内存问题。对于测量，我们将使用 Intel® Xeon® 处理器 E5-2697 v4（代号 Broadwell，36 核）系统，其已知的理论参数为内存带宽 = 76.8 GB/s，双精度（DP）浮点运算每秒（FLOPS）= 662 GFLOPS/s。
矩阵乘法算法的朴素实现
朴素的矩阵乘法实现（multiply1，图 3）永远无法线性扩展到大量 CPU 核心。尽管如此，为了教育目的，它是一个说明如何识别效率低下性能原因的好例子。我们唯一会进行的改进是添加 –no-alias 编译器选项，以允许向量化。否则，标量实现将大约慢 10 倍。在矩阵大小为 9216 x 9216 的向量化基准测试 multiply1 上运行的结果可以在表 1 中找到。请注意，最佳性能远低于理论最大 FLOPS。
表 1. 朴素矩阵乘法的性能和扩展性（36 核，Intel® Xeon® 处理器 E5-2697 v4，双路 @ 2300 MHz）
| 线程数 | 耗时，秒 | DP FLOPS，GFLOPS/秒 |
| 4 | 208 | 7.7 |
| 8 | 102 | 15.1 |
| 16 | 59 | 26.8 |
| 36 | 42 | 37.8 |
| 72 HT | 24 | 66.1 |
如表 1 所示，并行基准测试随着线程数量的增加几乎呈线性扩展。当涉及超过 30 个核心时，扩展性开始趋于平稳。表 1 中的数据可能会导致对 multiply1 基准测试的性能和扩展性产生误导性的信心。理解基准测试在多大程度上使用了机器的计算能力非常重要。在我们的例子中，报告的 FLOPS（在基准测试中确定）远远低于早期计算出的机器的理论数字（大约小 10 倍）。并行扩展性没有受到限制，但串行性能受到了限制。请注意，Intel VTune Amplifier 指出循环内的代码执行效率低下（图 4）。较低的*Retiring*和较高的*CPI*率有助于估算我们离实际极限有多远。
接下来，我们将研究矩阵乘法算法的优化实现（图 3 中的 multiply2）。如果算法足够简单，并且您的编译器足够智能，它将识别低效的索引步长并自动生成一个具有交换循环的版本（或者您可以手动完成）。
void multiply2(int msize, int tidx, int numt, TYPE a[][NUM], TYPE b[][NUM], TYPE c[][NUM], TYPE t[][NUM])
{
int i,j,k;
// Loop interchange
for(i=tidx; i<msize; i=i+numt) {
for(k=0; k<msize; k++) {
#pragma ivdep
for(j=0; j<msize; j++) {
c[i][j] = c[i][j] + a[i][k] * b[k][j];
}}}}
| 线程数 | 耗时，秒 | DP FLOPS，GFLOPS/秒 |
| 4 | 208.8 | 7.8 |
| 8 | 103.3 | 15.1 |
| 16 | 58.8 | 26.4 |
| 36 | 38.4 | 40.5 |
| 72 HT | 24.7 | 63.0 |
表 2. 优化矩阵乘法的性能和扩展性（36 核，Intel® Xeon® 处理器 E5-2697 v4，双路 @ 2300 MHz）
您可能已经注意到，表 2 中的绝对数字略有改善，但仍然远非理想。
让我们试着理解什么限制了性能和可伸缩性。*General Exploration*分析结果（图 5）实现了另一种自顶向下分析方法，这次是针对 CPU 微体系结构³。我们可能会注意到一些有趣的事情。
首先，请注意，从 DRAM 到 CPU 的数据延迟已减小。这是预期的，因为我们在算法中实现了连续地址访问。但是内存带宽指标非常高。考虑到这一点，我们应该检查主要数据路径的带宽数字，以确保 DRAM 控制器和 Intel® QuickPath Interconnect (QPI) 不是瓶颈。其次，请注意 L3 延迟也很高，即使数据访问具有连续模式。这需要额外的考虑。高 L3 延迟意味着我们经常出现 L2 缓存未命中，这很奇怪，因为硬件 L2 预取器应该工作（并且确实有效，因为连续访问不会降低 DRAM 延迟）。第三，远程 DRAM 延迟很显著。这表明存在非均匀内存访问（NUMA）效应，并且部分数据是从每个节点的远程 DRAM 中获取的。因此，为了更清楚地了解数据传输的整体情况，我们需要测量 DRAM 内存控制器和套接字之间 QPI 总线上的数据流量。为此，我们使用 VTune 内存访问分析。
图 6 显示了 72 个线程示例的分析结果。只有一个 DRAM 控制器加载了数据（package_1），平均数据速率接近 50 GB/秒，约占最大带宽的三分之二。在 package_0 的内存控制器上，流量可以忽略不计。
在同一时间段内，我们观察到出站 QPI 通道中的一半数据流量形成 package_1。这解释了数据如何从 package_1 DRAM 到 package_0 CPU 核心（图 7）。这种跨 QPI 流量会增加从预取器获取的远程 DRAM 或 CPU 核心获取的 LLC 的远程数据的额外延迟。消除 NUMA 效应对于基准测试来说可能很容易，因为数据结构良好且在线程之间均匀分布。我们只需将线程亲和性设置为 CPU 核心，并让每个线程初始化 *a*、*b* 和 *c* 矩阵。但我们需要谨慎假设在每个线程内分配数据可以消除所有 NUMA 效应。
图 8 显示了一个未能根据先前假设改进性能的示例，以及使用 Intel VTune Amplifier 检测问题的途径。在基准测试源代码中，我们引入了一个函数来表示固定到枚举 CPU 的线程。图 8 显示了代码的一部分。
CreateThreadPool( … )
{
pthread_t ht[NTHREADS];
pthread_attr_t attr;
cpu_set_t cpus;
pthread_attr_init(&attr);
for (tidx=0; tidx<NTHREADS; tidx++) {
CPU_ZERO(&cpus);
CPU_SET(tidx, &cpus);
pthread_attr_setaffinity_np(&attr, sizeof(cpu_set_t), &cpus);
pthread_create( &ht[tidx], &attr, (void*)start_routine, (void*) &par[tidx]);
}
for (tidx=0; tidx<NTHREADS; tidx++)
pthread_join(ht[tidx], (void **)&status);
}
在数据初始化函数中，数组的分配方式应与乘法函数中数组的乘法方式相同。图 9 显示了用于简化 NUMA 感知的函数修改。在初始化函数中，数据数组按大小为 `msize`/`numt` 的块进行划分，这是矩阵大小除以线程数。乘法函数（图 10）也进行了相同的处理。令人惊讶的是，基准测试的运行时间与非 NUMA 感知版本相比并没有好多少，因此让我们使用 Intel VTune 内存访问分析进行分析（图 11）。
InitMatrixArrays (int msize, int tidx, int numt, … )
{
int i,j,k,ibeg,ibound,istep;
istep = msize / numt;
ibeg = tidx * istep;
ibound = ibeg + istep;
for(i=ibeg; i<ibound; i++) {
for (j=0; j<msize;j++) {
a[i][j] = 1.0*i+2.0*j+3.0;
b[i][j] = 2.0*i+1.0*j+3.0;
c[i][j] = 0.0;
}
}
}
multiply2(int msize, int tidx, int numt, … )
{
int i,j,k,ibeg,ibound,istep;
istep = msize / numt;
ibeg = tidx * istep;
ibound = ibeg + istep;
for(i=ibeg; i<ibound; i++) {
for(k=0; k<msize; k++) {
for(j=0; j<msize; j++) {
c[i][j] = c[i][j] + a[i][k] * b[k][j];
}}}}
./matrix.icc
Threads #: 72 Pthreads
Matrix size: 9216
Using multiply kernel: multiply2
Freq = 2.30100 GHz
Execution time = 20.162 seconds
MFLOPS: 72826.877 mflops
摘要页面通知我们，应用程序仍然受内存限制（由于来自内存的数据延迟和数据流量而停顿），但延迟主要是由 LLC 引起，DRAM 引起的较少。此外，本地访问和远程访问的比例非常高，这意味着 NUMA 感知方法不起作用。如果我们检查 DRAM 控制器和 QPI 上的流量时间线（图 12），我们会发现来自 DRAM 的数据流几乎没有达到峰值带宽的 30%，但 QPI 在每个方向上都达到了其容量的约 90%（对于此系统，QPI 的实际极限是 29.2 GB/s）。
远程访问（无论是 DRAM 还是 LLC）会增加读取内存块的延迟，并导致 CPU 停顿。这些延迟可以通过 Intel VTune Amplifier 的内存访问进行测量，它使我们能够识别哪些数据（矩阵）仍然以低效的远程方式被访问。如果我们检查内存分析摘要（图 13），我们可以观察到哪些内存对象造成了最大的延迟。
在前三个内存对象（由其分配函数表示）中，我们注意到其中一个明显代表了最大部分的延迟，并且负责大量的加载操作（图 14）。请注意，只有一个对象的平均延迟足够高，可以得出数据来自 LLC 的远程 DRAM 的结论。我们可以通过“远程 DRAM 访问”列中的数字来确认此结论。
很容易发现这三个对象是三个矩阵 *a*、*b* 和 *c*。具有高存储操作的对象是矩阵 *c*。要确定哪个矩阵数据造成了高延迟，您需要检查 Intel VTune Amplifier 堆栈窗格中内存对象的堆栈（图 15）。通过用户代码中的堆栈，我们可以钻取到 Intel VTune Amplifier 源视图（图 16）中显示的数据分配源行。在这种情况下，是矩阵 *b* 数据造成了延迟干扰和加载次数的增加。现在我们需要了解为什么会发生这种情况，尽管数据数组是在固定线程内分配和初始化的。
对转置矩阵的算法进行快速调查，揭示了数据访问模式的基本低效（图 17）。对于矩阵 *a* 的每一行，都需要从内存中完全读取整个矩阵 *b*。
矩阵包含约 9K 个列/行元素。因此，整个矩阵内存块的大小将超过任何 CPU 缓存容量，导致缓存数据不断被逐出并从 DRAM 重新加载。尽管矩阵 *c* 和 *a* 的分布式行由分配在这些核心上的 CPU 核心上的线程访问，但这并不完全适用于矩阵 *b*。在此算法实现中，矩阵 *b* 数据的一半将由远程套接字上的线程读取。更糟糕的是，为矩阵 *a* 的每一行读取整个矩阵 *b* 会导致冗余的数据加载操作（比需要的 N 倍）并产生过多的 QPI 流量以访问远程数据。
类似地，您可以定义哪些数据对象导致了 Intel Xeon Phi 处理器系统上 DRAM 或 MCDRAM 的流量增加。您只需要选择要分析的内存域流量。您可以获得对象的引用和分配堆栈信息（图 18），当按带宽域和带宽利用类型分组时，您可以看到对象并确定哪些对象对 L2 缓存未命中次数（图 19）的贡献最大。
数据分块
通过对乘法算法的又一次修改，我们可以减少数据延迟以消除 CPU 停顿。我们希望所有三个矩阵中的数据都能被在本地套接字上运行的线程访问。一种众所周知的、常用的修改是数据分块（图 20）。它允许处理来自每个矩阵的较小数组块，将它们保留在缓存中并被 CPU 重用（这反过来又为通过优化块以适应 CPU 缓存大小来进一步提高性能提供了机会）。此外，这使得在线程之间分配块更容易，并防止了大量的远程访问和重新加载。
如果我们查看缓存分块修改的结果（图 21），我们可以观察到，即使在未修复 NUMA 效应的情况下，内存延迟也大大减小，并且执行速度也大大加快。
./matrix.icc
Threads #: 72 Pthreads
Matrix size: 9216
Using multiply kernel: multiply3
Freq = 2.3 GHz
Execution time = 12.08 seconds
MFLOPS: 128710.367 mflops
根据*General Exploration*分析（图 22），Retiring 流水线槽增加了高达 20%，而其余的 CPU 停顿则在 Memory Bound 和 Core Bound 执行之间共享。
根据延迟直方图（图 23），大多数延迟集中在 L2 访问值附近，而其余的则在 50 到 100 个周期区域，这在 LLC 命中延迟数字的区域。带宽时间线图（图 24）显示，大部分数据来自本地 DRAM，QPI 上的流量略有增加。对于此大小的矩阵，这仍然比 Intel® Math Kernel Library (Intel® MKL) 实现的双精度矩阵乘法（dgemm）性能要差，但更接近它（图 25）。因此，我们可以进行的最终优化是修改算法以使其被分块并且完全 NUMA 感知。最终性能显示在表 3 和图 26 中。
$./matrix.mkl
Threads #: 72 requested OpenMP threads
Matrix size: 9216
Using multiply kernel: multiply5
Freq = 2.799980 GHz
Execution time = 2.897 seconds
MFLOPS: 540032.936 mflops
表 3. 最终 matrix3 优化的性能（36 核，Intel® Xeon® 处理器 E5-2697 v4，双路 @ 2300 MHz）
| 线程数 | 耗时，秒 | DP FLOPS，GFLOPS/s |
| 4 | 104.8 | 14 |
| 8 | 60.1 | 25 |
| 16 | 31.3 | 49 |
| 36 | 17.85 | 87 |
| 72 HT | 12.08 | 128 |
关于可伸缩性图的说明
- matrix3 线超出理想线是由于缓存分块效应，这使得单线程版本比朴素实现执行得更快。
- 在线程数等于物理核心数之前，matrix3 线更接近理想线，而添加超线程并不能提高可伸缩性。
结论
一些内存访问模式可能会因 CPU 微体系结构限制而在并行应用程序中显示出较差的可伸缩性。要避免这些限制，您需要准确识别哪些数据数组导致 CPU 在等待数据时停顿。使用 Intel VTune Amplifier 内存访问分析，您可以识别导致最大延迟的数据对象，以及以 CPU 时钟周期计量的延迟量、数据驻留的缓存子系统级别以及数据对象分配和延迟访问的源代码。这些信息应有助于您重新考虑算法，以提供更好的内存访问模式。
参考文献
- Charlie Hewett. 软件性能分析的自顶向下方法
- Intel® 64 和 IA-32 架构优化参考手册.
- Ahmad Yasin. "A Top-Down Method for Performance Analysis and Counters Architecture." IEEE Xplore: 2014 年 6 月 26 日。电子 ISBN：978-1-4799-3606-9。