x86 - AVX-512 和分支

Question

我对掩蔽在理论上可以做什么与分支相关的事情感到困惑。假设我有一个 Skylake-SP(哈，我希望......)，我们忽略了编译器功能，只是理论上可能的:

如果分支条件依赖于静态标志，并且所有分支都将数组设置为计算结果，假设编译器无论如何都没有将其优化为两个单独的循环，它可以矢量化吗？

do i = 1, nx
  if (my_flag .eq. 0) then
    a(i) = b(i) ** 2
  else
    a(i) = b(i) ** 3
  end if
end do

如果仅作为分支的子集设置有问题的值，它可以矢量化吗？

do i = 1, nx
  if (my_flag .eq. 0) then
    a(i) = b(i) ** 2
  end if
end do

如果分支条件本身依赖于向量数据，它可以向量化吗？

do i = 1, nx
  if (c(i) > 0) then
    a(i) = b(i) ** 2
  else
    a(i) = b(i) ** 3
  end if
end do

Answer 1

注意: 这个答案主要讨论了一个非常具体的内存访问问题，当涉及到向量化时，它主要适用于概念级别，将一系列对数组的标量访问转换为向量化访问，而无需假设底层数组的哪些部分被映射。在像 Fortran 这样的语言中，语言本身的语义可以保证数组是连续映射的，或者在进入循环之前的边界检查可能足以避免下面提到的问题。

这个答案一般不应被视为对矢量化的一种很好的处理，当然也不应该特别是在 Fortran 中。对矢量化问题的更全面处理出现在 another answer 中，该文件还专门针对 AVX-512。

向量化条件的一个经常被忽视的问题是，编译器可以通过混合或其他元素预测技术对您感兴趣的类型的条件循环进行向量化，前提是它们可以证明向量化访问的元素与在逐个元素的标量实现。如果指令集不提供按照此条件执行向量加载的逐元素方式，或者编译器无法使用它们，则这可以有效地阻止向量化。

换句话说，如果通过循环体的所有路径都访问相同的元素，编译器通常只能使用普通矢量加载完全矢量化。

根本原因是编译后的代码 不能访问原始代码语义未访问的 元素，即使它们后来被“混合”，因为这样做可能会导致错误!如果指令集不提供指令来有条件地访问内存中的元素并抑制来自未选择元素的错误，这将是优化的重大障碍。

在您给出的示例中，这意味着 (1) 和 (3) 可以“不提升条件”进行矢量化，而 (2) 则不能，因为 (2) 仅在 a[i] 主体中访问 b[i] 和 if，但如果 if 则不能没有被执行。当然，在 myflag == false 的情况下，真正的编译器只会将一个简单的标志检查提升到循环之外，而根本不执行循环，因此这不是一个很好的例子。

让我们看看包含所有示例的几个案例。首先，我们需要一个不能被提升的标志——让我们只使用一个 bool 值的数组。因此，一个带有输出数组 a 、两个输入数组 b 和 c 以及一个标志数组 f 的有趣的通用循环可能看起来像:

do i = 1, nx
  if (f(i) > 0) then
    a(i) = g(b(i), c(i));
  else
    a(i) = h(b(i), c(i));
  end if
end do

根据与每个元素对应的标志 f(i)，我们将函数 g 或 h 应用于输入元素 b(i) 和 c(i) 。根据我上面的条件，只有当 g 和 h 实际访问 b 和 c 的相同元素时，我们才能矢量化。

让我们继续上面的两个实际工作示例:

void example1(bool* f, int* __restrict__ a, int* __restrict__ b, int* __restrict__ c, size_t n) {
    for (size_t i = 0; i < n; i++) {
        if (f[i]) {
            a[i] = b[i];
        } else {
            a[i] = c[i];
        }
    }
}

void example2(bool* f, int* __restrict__ a, int* __restrict__ b, int* __restrict__ c, size_t n) {
    for (size_t i = 0; i < n; i++) {
        if (f[i]) {
            a[i] = b[i] + c[i] ;
        } else {
            a[i] = b[i] - c[i] * 2 + 1 ;
        }
    }
}

两者都有相同的基本形式，但哪个更难矢量化？第一个是根据标志简单直接分配 b[i] 或 c[i]。第二个是 b[i] 和 c[i] 的更复杂的函数，它们在两条路径上都显着不同。

那么第二个更容易矢量化，因为它无条件访问 b[i] 和 c[i]。事实上， gcc 由于某种原因没有设法矢量化任何一个。 clang 只矢量化第二个。有点令人惊讶的是 icc 设法对两者进行了矢量化 - 因为它足够聪明，可以使用 vpmaskmovd，这是一个屏蔽负载，可以抑制未加载元素的故障。

您可以检查 generated assembly on godbolt 。

我最初开始这个答案的想法是访问不同的数组元素目前是当前编译器无法克服的矢量化障碍，但那是因为我通常不检查 icc 。 icc 以这种方式使用蒙版移动对我来说实际上是新闻。所以障碍就在那里，但至少有些编译器可以解决它2。

作为开发人员，您通常知道这两个数组都是完全可访问的，因此可以安全地访问 b 和 c 范围内 [0, n) 的所有元素，并且最好将其传达给编译器。我已经尝试添加无条件的虚拟语句，如 b[i] = b[i]; c[i] = c[i]; 或 ... + c[i] * 0，它们应该编译为空，但至少允许编译器在语义上看到所有元素都被访问。确实“编译”但代码生成没有改进:不会发生额外的矢量化。可能在矢量化分析完成之前，它们在编译过程的早期就已经被消除了，因此矢量化器会丢失信息。

除了不免费且不完全通用的屏蔽移动指令之外，还有其他方法可以改善这种情况吗？那么编译器可以利用它对平台内存保护模型的了解。例如，一旦 x86 上的 4K 页中的任何字节被访问，就可以自由读取该页上的所有其他字节。可以想象一个复杂的实现，它以安全的标量代码开始，但是一旦“注意到”对两个数组的写入，就立即切换到页面其余部分的矢量化循环。

如果数组访问对齐，则可以使用类似的技巧:向量化循环可以检查标志数组是否一致为 0 或一致为 1，如果不是，则使用简单的无条件无掩码读取实现是安全的，否则会退回到 more认真执行。这种转换显然只有在掩码很少统一或几乎总是统一的情况下才会有利可图，因此在实践中可能不太可能实现。

2 至少在 AVX 可用的情况下:如果将第一个示例限制为 pre-AVX 指令， icc 仍将无法矢量化，因为那时引入了 vpmaskmovd/q 和 vmaskmovps/pd。

3 由于在这种情况下，如果您已经确定掩码是统一的，您可以无条件地执行该操作，只需根据它是统一的 if 或统一的 0 不进行任何屏蔽/混合即可执行 1 的选定一侧。因此，您最终会得到三个内部实现的循环:全零标志情况、全 1 标志情况和混合标志情况，当下一个标志向量与当前循环不同时，它们之间会跳转.