向量化

在现代处理器上，使用SIMD指令可以在常规未向量化（标量）代码上实现巨大的加速。在进行性能分析时，软件工程师的首要任务之一是确保代码的热点部分被向量化。本节将指导工程师发现向量化的机会。对于现代CPU的SIMD能力的回顾，读者可以查看[@sec:SIMD]。

通常，向量化会自动发生，无需用户干预，这称为自动向量化。在这种情况下，编译器会自动识别从源代码生成SIMD机器代码的机会。自动向量化可能是一个方便的解决方案，因为现代编译器为各种程序生成快速的向量化代码。

然而，在某些情况下，如果没有软件工程师的干预，自动向量化就不会成功，这可能是基于他们从编译器或分析数据中得到的反馈2。在这些情况下，程序员需要告诉编译器某个特定的代码区域是可向量化的，或者向量化是有利可图的。现代编译器有扩展功能，允许高级用户控制自动向量化过程，并确保代码的某些部分被有效地向量化。然而，这种控制是有限的。在后续章节中，我们将提供几个使用编译器提示的例子。

需要注意的是，有一系列问题在其中SIMD很重要，而自动向量化就是不起作用，而且在未来也不太可能起作用。可以在[@Mula_Lemire_2019]中找到一个例子。编译器目前不会尝试外循环向量化。它们不太可能向量化浮点代码，因为结果在数值上会有所不同。涉及跨向量通道的排列或洗牌的代码也不太可能自动向量化，这可能仍然是编译器的一个难题。

自动向量化还有一个微妙的问题。随着编译器的发展，它们所做的优化在变化。在前一个编译器版本中成功自动向量化的代码可能在下一个版本中停止工作，反之亦然。此外，在代码维护或重构期间，代码的结构可能会发生变化，以至于自动向量化突然开始失败。这可能发生在原始软件编写很久之后，因此在这一点上修复或重新实现将更加昂贵。

当绝对需要生成特定的汇编指令时，不应依赖编译器的自动向量化。在这些情况下，可以使用编译器内联函数编写代码，我们将在[@sec:secIntrinsics]中讨论。在大多数情况下，内联函数提供了与汇编指令的1对1映射。内联函数比内联汇编更容易使用，因为编译器负责寄存器分配，并且它们允许程序员在代码生成上保留相当大的控制权。然而，它们仍然通常是冗长且难以阅读的，并且可能受到各种编译器的行为差异甚至错误的影响。

在低成本但不可预测的自动向量化和冗长/不可读但可预测的内在函数之间，可以使用围绕内在函数的包装库。这些库往往更易读，可以将编译器修复集中在库中，而不是分散在用户代码中，并且仍然允许开发人员控制生成的代码。许多这样的库存在，它们支持最新或"奇特(exotic)"操作的范围以及它们支持的平台数量各不相同。据我们所知，Highway 是目前唯一完全支持可扩展向量（如 SVE 和 RISC-V V 指令集）的库。需要注意的是，本文作者之一是该库的技术负责人。它将在 [@sec:secIntrinsics] 中介绍。

请注意，使用内在函数或包装库时，仍然建议使用 C++ 编写初始实现。这样可以通过将原始代码的结果与新的向量化实现进行比较，从而快速原型化和验证正确性。

在本节的其余部分，我们将讨论几种方法，尤其是内循环向量化，因为它是自动向量化最常见的类型。其他两种类型，外循环向量化和 SLP (Superword-Level Parallelism) 向量化，将在附录 B 中提到。

编译器自动向量化

多重障碍可能会阻止自动向量化，其中一些障碍是编程语言语义固有的。例如，编译器必须假设无符号循环索引可能会溢出，这可能会阻止某些循环转换。另一个例子是C编程语言所做的假设：程序中的指针可能指向重叠的内存区域，这可能会使程序分析变得非常困难。另一个主要障碍是处理器本身的设计。在某些情况下，处理器没有针对某些操作的高效向量指令。例如，大多数处理器上没有可用的受控（位掩码控制）加载和存储操作。另一个例子是不同大小向量寄存器之间进行有符号整数到双精度浮点数的向量宽格式转换。尽管存在所有这些挑战，软件开发者仍然可以解决许多挑战并启用向量化。在后面的部分中，我们将提供如何与编译器合作的指导，确保热点代码被编译器向量化。

向量化器通常分为三个阶段：合法性检查、盈利性检查和转换本身：

  • 合法性检查(Legality-check)：在这个阶段，编译器检查是否可以合法地将循环（或其他类型的代码区域）转换为使用向量。循环向量化器检查循环的迭代是否连续，这意味着循环线性进展。向量化器还确保循环中的所有内存和算术操作可以扩展为连续操作。循环的控制流在所有通道中是统一的，内存访问模式也是统一的。编译器必须以某种方式检查或确保生成的代码不会触及它不应该触及的内存，并且操作的顺序将被保留。编译器需要分析指针的可能范围，如果有任何缺失信息，它必须假设转换是非法的。合法性阶段收集了一系列要求，这些要求需要发生以便向量化循环合法。

  • 盈利性检查(Profitability-check)：接下来，向量化器检查转换是否盈利。它比较不同的向量化因素，并找出哪个向量化因素执行最快。向量化器使用成本模型预测不同操作的成本，例如标量加法或向量加载。它需要考虑将数据洗牌到寄存器中添加的指令，预测寄存器压力，并估计确保允许向量化的前提条件得到满足的循环守卫的成本。检查盈利性的算法很简单：1) 将代码中所有操作的成本加起来，2) 比较每种代码版本的成本，3) 将成本除以预期的执行次数。例如，如果标量代码的成本为8个周期，向量化代码的成本为12个周期，但一次执行4次循环迭代，那么向量化版本的循环可能更快。

  • 转换(Transformation)：最后，在向量化器确定转换是合法和盈利之后，它转换代码。这个过程还包括插入使向量化成为可能的守卫。例如，大多数循环使用未知的迭代次数，所以编译器必须生成循环的标量版本，除了向量化版本的循环之外，以处理最后几次迭代。编译器还必须检查指针是否重叠等。所有这些转换都是在合法性检查阶段收集的信息的基础上完成的。

发现向量化机会

阿姆达尔定律6 告诉我们，我们应该只分析程序执行过程中使用最多的代码部分。因此，性能工程师应该专注于由分析工具突出显示的代码热点。如前所述，向量化最常应用于循环。

发现提高向量化的机会应该从分析程序中的热点循环开始，并检查编译器执行了哪些优化。查看编译器向量化备注（见[@sec:compilerOptReports]）是了解这一点的最简单方法。现代编译器可以报告某个循环是否被向量化，并提供额外的细节，例如向量化因子（VF）。在编译器无法向量化循环的情况下，它也能够说明失败的原因。

使用编译器优化报告的另一种方法是检查汇编输出。最好使用一个分析工具的输出，该工具显示给定循环的源代码与生成的汇编指令之间的对应关系。这样，你只关注重要的代码，即热点代码。然而，理解汇编语言比理解像C++这样的高级语言要困难得多。可能需要一些时间来弄清楚编译器生成的指令的语义。但这项技能非常有价值，通常能提供有价值的见解。有经验的开发者可以通过查看指令助记符和这些指令使用的寄存器名称，快速判断代码是否被向量化。例如，在x86 ISA中，向量指令操作打包数据（因此在它们的名称中有P），并使用XMM、YMM或ZMM寄存器，例如VMULPS XMM1, XMM2, XMM3将XMM2和XMM3中的四个单精度浮点数相乘，并将结果保存在XMM1中。但要小心，人们经常从看到使用XMM寄存器得出结论，认为这是向量代码——这不一定正确。例如，VMULSS指令只会乘以一个单精度浮点值，而不是四个。

开发者在尝试加速可向量化代码时经常遇到的一些常见情况如下。下面我们介绍四种典型场景，并给出每种情况下的一般指导。

向量化是非法的

在某些情况下，遍历数组元素的代码根本不可向量化。向量化备注非常有效地解释了出了什么问题以及为什么编译器无法向量化代码。@lst:VectDep 显示了一个循环内部的依赖关系，该依赖关系阻止了向量化31。

代码清单:向量化:读写后写依赖。 

void vectorDependence(int *A, int n) {
  for (int i = 1; i < n; i++)
    A[i] = A[i-1] * 2;
}

一些循环由于上述硬件限制无法向量化，但另一些循环在放松特定约束时可以向量化。有时，编译器无法向量化循环仅仅是因为它无法证明这样做是合法的。编译器通常非常保守，只会确信不会破坏代码时才进行转换。此类软限制可以通过向编译器提供额外的提示来放松。

例如，当转换执行浮点运算的代码时，向量化可能会改变程序的行为。浮点加法和乘法是交换的，这意味着您可以交换左手侧和右手侧而不改变结果：(a + b == b + a)。但是，这些操作不是关联的，因为舍入发生在不同的时间：((a + b) + c) != (a + (b + c))。@lst:VectIllegal 中的代码无法由编译器自动向量化。原因是向量化会将变量 sum 更改为向量累加器，这将改变运算顺序，并可能导致不同的舍入决策和不同的结果。

代码清单:向量化:浮点运算。 {#lst:VectIllegal .cpp .numberLines}

// a.cpp
float calcSum(float* a, unsigned N) {
  float sum = 0.0f;
  for (unsigned i = 0; i < N; i++) {
    sum += a[i];
  }
  return sum;
}

然而，如果程序可以容忍最终结果有一点小的不准确（通常情况下是这样），我们可以将此信息传达给编译器以启用向量化。Clang 和 GCC 编译器都有一个标志 -ffast-math29，它允许这种转换：

$ clang++ -c a.cpp -O3 -march=core-avx2 -Rpass-analysis=.*
...
a.cpp:5:9: remark: loop not vectorized: cannot prove it is safe to reorder floating-point operations; allow reordering by specifying '#pragma clang loop vectorize(enable)' before the loop or by providing the compiler option '-ffast-math'. [-Rpass-analysis=loop-vectorize]
...
$ clang++ -c a.cpp -O3 -ffast-math -Rpass=.*
...
a.cpp:4:3: remark: vectorized loop (vectorization width: 4, interleaved count: 2) [-Rpass=loop-vectorize]
...

不幸的是，此标志涉及微妙且潜在危险的行为变化，包括非数字 (NaN)、带符号零、无穷大和次正规数。由于第三方代码可能还没有准备好应对这些影响，因此不应在不仔细验证结果（包括边缘情况）的情况下在大段代码中启用此标志。

让我们看另一个典型情况，编译器可能需要开发人员的支持才能执行向量化。当编译器无法证明循环操作的是具有非重叠内存区域的数组时，它们通常会选择更安全的选项。让我们重新审视 [@sec:compilerOptReports] 中 @lst:optReport 提供的示例。当编译器尝试向量化 @lst:OverlappingMemRefions 中呈现的代码时，它通常无法做到这一点，因为数组 a、b 和 c 的内存区域可能重叠。

代码清单: a.c {#lst:OverlappingMemRefions .cpp .numberLines}

void foo(float* a, float* b, float* c, unsigned N) {
  for (unsigned i = 1; i < N; i++) {
    c[i] = b[i];
    a[i] = c[i-1];
  }
}

这是由 GCC 10.2 提供的优化报告（使用 -fopt-info 启用）：

$ gcc -O3 -march=core-avx2 -fopt-info
a.cpp:2:26: optimized: loop vectorized using 32 byte vectors
a.cpp:2:26: optimized: loop versioned for vectorization because of possible aliasing

GCC 识别到数组 a、b 和 c 的内存区域可能存在重叠，并创建了相同循环的多个版本。编译器插入了运行时检查36 来检测内存区域是否重叠。基于这些检查，它会在向量化和标量35 版本之间进行调度。在这种情况下，向量化会带来插入可能代价高昂的运行时检查的成本。

如果开发人员知道数组 a、b 和 c 的内存区域不会重叠，可以在循环前面插入 #pragma GCC ivdep37 或使用 __restrict__ 关键字，如 @lst:optReport2 所示。此类编译器提示将消除 GCC 编译器插入上述运行时检查的需要。

编译器本质上是静态工具：它们只根据所使用的代码进行推理。例如，一些动态工具（例如 Intel Advisor）可以检测跨迭代依赖或访问具有重叠内存区域的数组等问题是否确实出现在给定的循环中。但要记住，这类工具只提供建议。不加思索地插入编译器提示可能会导致实际问题。

向量化无益

在某些情况下，编译器可以向量化循环，但认为这样做没有好处。在 @lst:VectNotProfit 中呈现的代码中，编译器可以向量化对数组 A 的内存访问，但需要将对数组 B 的访问拆分为多个标量加载。这种分散/收集模式相对昂贵，并且能够模拟操作成本的编译器经常会决定避免向量化具有这种模式的代码。

代码清单:向量化:没有好处。 {#lst:VectNotProfit .cpp .numberLines}

// a.cpp
void stridedLoads(int *A, int *B, int n) {
  for (int i = 0; i < n; i++)
    A[i] += B[i * 3];
}

下面是@lst:VectNotProfit中的代码的编译器优化报告:

$ clang -c -O3 -march=core-avx2 a.cpp -Rpass-missed=loop-vectorize
a.cpp:3:3: remark: the cost-model indicates that vectorization is not beneficial [-Rpass-missed=loop-vectorize]
  for (int i = 0; i < n; i++)
  ^

用户可以使用 #pragma 提示强制 Clang 编译器向量化循环，如 @lst:VectNotProfitOverriden 所示。但是，请记住，向量化是否真正有利很大程度上取决于运行时数据，例如循环的迭代次数。编译器无法获得这些信息，1 因此它们往往保守行事。开发人员可以在寻找性能提升空间时使用此类提示。

代码清单:向量化:没有好处。 {#lst:VectNotProfitOverriden .cpp .numberLines}

// a.cpp
void stridedLoads(int *A, int *B, int n) {
#pragma clang loop vectorize(enable)
  for (int i = 0; i < n; i++)
    A[i] += B[i * 3];
}

开发人员应注意使用向量化代码的隐藏成本。使用 AVX 和特别是 AVX-512 向量指令可能会导致频率降频或启动开销，在某些 CPU 上还会影响后续代码数微秒。向量化部分的代码应该足够热门，以证明使用 AVX-512 的合理性。38 例如，排序 80 KiB 的数据被发现足以摊销这种开销，使向量化变得有价值。39

循环已向量化，但使用标量版本

在某些情况下，编译器可以成功地向量化代码，但向量化代码不会显示在性能分析器中。检查循环的对应汇编时，通常很容易找到循环体的向量化版本，因为它使用了向量寄存器（程序其他部分不常用），并且代码是展开的，并填充了检查和多个版本以启用不同的边缘情况。

如果生成的代码没有执行，一个可能的原因是编译器生成的代码假设循环执行次数高于程序使用的次数。例如，要在现代 CPU 上高效地进行向量化，程序员需要向量化并利用 AVX2，并且还要将循环展开 4-5 次，为管道化的 FMA 单元生成足够的工作。这意味着每次循环迭代都需要处理大约 40 个元素。许多循环可能运行的循环执行次数低于这个值，并可能退回到使用标量剩余循环。很容易检测这些情况，因为标量剩余循环会在性能分析器中亮起，而向量化代码将保持冷状态。

解决这个问题的方法是强制向量器使用较低的向量化因子或展开计数，以减少循环处理的元素数量，并使更多具有较低执行次数的循环访问快速向量化的循环体。开发人员可以使用 #pragma 提示来实现这一点。对于 Clang 编译器，可以使用 #pragma clang loop vectorize_width(N)，如 easyperf 博客上的文章 30 所示。

循环以次优方式向量化

当您看到一个循环被向量化并在运行时执行时，该部分程序可能已经运行良好。但是，也有一些例外情况。有时，人类专家可以编写出性能优于编译器生成的代码。

由于以下几个因素，最佳向量化因子可能并不直观。首先，人类很难在脑海中模拟 CPU 的操作，除了尝试多种配置之外别无其他方法。涉及多个向量通道的向量洗牌可能比预期的更昂贵或更便宜，这取决于许多因素。其次，在运行时，程序可能会表现出不可预测的行为，这取决于端口压力和许多其他因素。这里的建议是尝试强制向量器选择一个特定的向量化因子和展开因子，并测量结果。向量化编译器指令可以帮助用户枚举不同的向量化因子并找出性能最佳的因子。每个循环可能的配置相对较少，并且在典型输入上运行循环是人类可以做到的，而编译器却做不到。

最后，有时循环的标量非向量化版本比向量化版本性能更好。这可能是因为使用了昂贵的向量操作，例如“gather/scatter”加载、掩码、洗牌等，编译器必须使用这些操作才能进行向量化。性能工程师也可以尝试通过不同的方式禁用向量化。对于 Clang 编译器，可以通过编译器选项 -fno-vectorize 和 -fno-slp-vectorize 或针对特定循环的提示（例如，#pragma clang loop vectorize(enable)）来实现。

使用显式向量化的语言

向量化还可以通过用专用于并行计算的编程语言重写程序的部分来实现。这些语言使用特殊的结构和对程序数据的了解，将代码高效地编译成并行程序。最初，这些语言主要用于将工作卸载到特定处理单元，例如图形处理单元 (GPU)、数字信号处理器 (DSP) 或现场可编程门阵列 (FPGA)。然而，其中一些编程模型也能够针对您的 CPU（例如 OpenCL 和 OpenMP）。

其中一种这样的并行语言是 Intel® Implicit SPMD 程序编译器 (ISPC)(https://ispc.github.io/)33，我们将在本节稍作介绍。ISPC 语言基于 C 编程语言，并使用 LLVM 编译器基础架构为许多不同的架构生成优化代码。ISPC 的关键特性是“接近金属”的编程模型和跨 SIMD 架构的性能可移植性。它要求从编写程序的传统思维方式转变，但为程序员提供了更多控制 CPU 资源利用率的手段。

ISPC 的另一个优点是其互操作性和易用性。ISPC 编译器生成标准对象文件，可以与传统 C/C++ 编译器生成的代码链接。ISPC 代码可以很容易地插入任何原生项目，因为用 ISPC 编写的函数可以像 C 代码一样调用。

@lst:ISPC_code 显示了我们之前在 @lst:VectIllegal 中介绍的一个简单函数，用 ISPC 重写。ISPC 考虑程序将在并行实例中运行，基于目标指令集。例如，当使用 SSE 与 float 一起使用时，它可以并行计算 4 个操作。每个程序实例将在 i 的向量值上操作，分别是 (0,1,2,3)、然后是 (4,5,6,7)，以此类推，一次有效地计算 4 个和。正如您所看到的，使用了一些非典型 C 和 C++ 的关键字：

  • export 关键字意味着该函数可以从 C 兼容的语言调用。

  • uniform 关键字意味着变量在程序实例之间共享。

  • varying 关键字意味着每个程序实例都有自己的局部变量副本。

  • foreach 与经典的 for 循环相同，除了它会将工作分配到不同的程序实例。

代码清单:ISPC版本的数组元素求和。 

export uniform float calcSum(const uniform float array[], 
                             uniform ptrdiff_t count)
{
    varying float sum = 0;
    foreach (i = 0 ... count)
        sum += array[i];
    return reduce_add(sum);
}

由于函数 calcSum 必须返回单个值（一个 uniform 变量），而我们的 sum 变量是一个 varying，因此我们需要使用 reduce_add 函数来 收集 每个程序实例的值。ISPC 还负责生成剥离和剩余循环，以考虑未正确对齐或不是向量宽度倍数的数据。

“接近硬件”编程模型：传统 C 和 C++ 语言的一个问题是编译器并不总是向量化代码的关键部分。通常情况下，程序员会使用编译器内部函数（参见 [@sec:secIntrinsics]），这绕过了编译器自动向量化，但通常很困难，并且需要在出现新指令集时进行更新。ISPC 通过默认假设每个操作都是 SIMD 来帮助解决这个问题。例如，ISPC 语句 sum += array[i] 被隐含地认为是一个 SIMD 操作，可以并行进行多次加法运算。ISPC 不是一个自动向量化编译器，它不会自动发现向量化机会。由于 ISPC 语言与 C 非常相似，它比使用内部函数好得多，因为它可以让您专注于算法而不是低级指令。此外，据报道，它在性能方面与手写的内部函数代码相匹配或优于手写的内部函数代码34。

性能可移植性：ISPC 可以自动检测您 CPU 的特性，以充分利用所有可用资源。程序员可以编写一次 ISPC 代码，并编译到许多向量指令集，例如 SSE4、AVX 和 AVX2。ISPC 还可以为不同的架构（如 x86 CPU、ARM NEON）生成代码，并具有实验性的 GPU 卸载支持。

1. 除了配置文件引导优化（参见 [@sec:secPGO]）。 ↩
2. 例如，编译器优化报告，参见 [@sec:compilerOptReports]。 ↩
6. 阿姆达尔定律 - https://en.wikipedia.org/wiki/Amdahl's_law。 ↩
29. 编译器标志 -Ofast 启用 -ffast-math 以及 -O3 编译模式。 ↩
30. 使用 Clang 的优化编译器指令 - https://easyperf.net/blog/2017/11/09/Multiversioning_by_trip_counts ↩
31. 一旦展开几个循环迭代，很容易发现读后写依赖关系。请参见 [@sec:compilerOptReports] 中的示例。 ↩
33. ISPC 编译器: https://ispc.github.io/. ↩
34. 使用 SIMD 内部函数的虚幻引擎的一些部分使用 ISPC 重写，从而获得了速度提升: https://software.intel.com/content/www/us/en/develop/articles/unreal-engines-new-chaos-physics-system-screams-with-in-depth-intel-cpu-optimizations.html. ↩
35. 但循环的标量版本仍然可以展开。 ↩
36. 请参阅 easyperf 博客上的示例: https://easyperf.net/blog/2017/11/03/Multiversioning_by_DD. ↩
37. 它是 GCC 特定的编译器指令。对于其他编译器，请查阅相应的手册。 ↩
38. 有关更多细节，请阅读这篇博客文章: https://travisdowns.github.io/blog/2020/01/17/avxfreq1.html. ↩
39. AVX-512 降频研究: 在 VQSort readme: https://github.com/google/highway/blob/master/hwy/contrib/sort/README.md#study-of-avx-512-downclocking 中 ↩

results matching ""

    No results matching ""