AVX-512 和分支 [英] AVX-512 and Branching

问题描述

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

I'm confused as to what masking can do in theory in relation to branches. Let's say I have a Skylake-SP (ha, I wish..), and we're ignoring compiler capabilities, just what's possible in theory:

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

If a branch conditional is dependant on a static flag, and all branches set an array to a computational result, assuming the compiler does not optimize this to two separate loops anyways, can it vectorize?

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

如果仅作为分支的子集设置相关值，它可以向量化吗?

If only as subset of the branches are setting the value in question, can it vectorize?

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

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

If a branch conditional is in itself dependent on vector data, can it vectorize?

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

推荐答案

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

Note: This answer mostly discusses a very specific memory-access issue when it comes to vectorization and it applies mostly at a conceptual level to transforming a series of scalar accesses to arrays into vectorized accesses without assuming anything about what portions of the underlying arrays are mapped. In languages like Fortran, the semantics of the language itself may guarantee that arrays are contiguously mapped, or bounds-checks before entering the loop might be enough to avoid the problem mentioned below.

一般来说，这个答案不应该被视为对矢量化的良好处理，当然也不应该专门用于 Fortran.another answer 中对矢量化问题进行了更全面的处理，该答案也专门针对 AVX-512.

This answer shouldn't be seen as a good treatment of vectorization in general and certainly not in Fortran specifically. A more comprehensive treatment of vectorization issues appears in another answer, which also specifically addresses AVX-512.

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

One often overlooked issue with vectorizing conditions is that compilers can vectorize conditional loops of the type you are interested in, via blending or other element-wise predication techniques, only if they can prove that the vectorization accesses the same elements as are accessed as in the scalar element-by-element implementation. If the instruction set doesn't offer an element-wise way to do vector loads respecting this condition, or if the compiler is unable to use them, this can effectively block vectorization.

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

Said another way, compilers can generally only fully vectorize with plain vector loads if all paths through the loop body access the same elements.

根本原因是编译后的代码不得访问原始代码语义未访问的元素，即使它们后来被混合"，因为这样做可能会导致过错！如果指令集没有提供指令来有条件地访问内存中的元素并抑制未选择元素的故障，那么这就是优化的一个重要障碍.

The underlying reason is that the compiled code must not access elements that aren't accessed by the semantics of the original code, even if they are later "blended away" since doing so might cause a fault! If the instruction set doesn't provide instructions to conditionally access elements in memory and suppress faults from not-selected elements, this is a significant barrier to optimization.

在您给出的示例中，这意味着 (1) 和 (3) 可以在不提升条件"的情况下进行矢量化，而 (2) 则不能，因为 (2) 访问 a[i]和 b[i] 仅在 if 正文中，但如果 if 未执行则不会.当然，真正的编译器只会从循环中提升一个微不足道的标志检查，而在 myflag == false 的情况下根本不执行循环，所以这不是一个很好的例子.

In the examples you gave this means that (1) and (3) could be vectorized "without hoisting the condition" while (2) could not, since (2) accesses a[i] and b[i] only in the if body, but not if the if isn't executed. Of course, a real compiler would just hoist a trivial flag check out of the loop and just not execute the loop at all in the myflag == false case, so it's not really a good example.

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

Let's just look at a couple of cases that subsumes all your examples. First, we need a flag that cannot be hoisted - let's just use an array of bool values. So an interesting somewhat general loop with an output array a, two input arrays b and c and a flag array f might look something like:

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.

Depending on the flag f(i) corresponding to each element, we apply either the function g or h to the input elements b(i) and c(i). Per my condition above we can vectorize only if both g and h actually access the same elements of b and c.

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

Let's move on to two real work examples of the above:

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] 的简单直接分配，具体取决于标志.第二个是 both b[i] 和 c[i] 的更复杂的函数，它们在两条路径上都有很大的不同.

Both have the same basic form, but which is harder to vectorize? The first is a simple direct assignment of either b[i] or c[i] depending on the flag. The second is a more complex function of both b[i] and c[i] which are significantly different on both paths.

第二个更容易向量化，因为它无条件地访问 b[i] 和 c[i].事实上，出于某种原因，gcc 无法对其中任何一个进行矢量化.clang 只对第二个进行矢量化.有点令人惊讶的是，icc 设法矢量化 both - 因为它足够聪明，可以使用 vpmaskmovd，这是一种屏蔽加载，可以抑制未加载元素的错误.

Well the second is much easier to vectorize since it accesses b[i] and c[i] unconditionally. In fact, gcc doesn't manage to vectorize either one for some reason. clang only vectorizes the second. Somewhat surprisingly icc manages to vectorize both - since it is smart enough to use vpmaskmovd which is a masked load that suppresses faults for unloaded elements.

您可以检查 在 godbolt 上生成的程序集.

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

I had originally started this answer with the idea that accessing different array elements is currently an insurmountable barrier to vectorization for current compilers, but that's because I usually don't check icc. It's actually news to me that icc uses masked moves in this way. So the barrier is there, but at least some compilers can fault over it².

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

As the developer, you usually know that both arrays are fully accessible, such that it is safe to access all elements of b and c in the range [0, n) and it would be nice to communicate that to the compiler. I've tried adding unconditional dummy statements like b[i] = b[i]; c[i] = c[i]; or ... + c[i] * 0 which should compile to nothing but at least allow the compiler to see that semantically all elements are accessed. The do indeed "compile away" but the code-generation is not improved: additional vectorization doesn't occur. Probably they are already eliminated early in the compilation process before the vectorizaton analysis is done, so that information is lost to the vectorizer.

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

Other than the masked-move instructions, which aren't free and are not fully general, are there any other ways this situation could be improved? Well a compiler could take advantage of its knowledge of the platform memory protection model. For example, once any byte in a 4K page on x86 has been accessed, it is free to read all other bytes on that page. One could imagine a complicated implementation that started out in safe scalar code but as soon as a write to both arrays was "noticed" switched over to a vectorized loop for the remainder of the page.

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

Similar tricks could be played if the array accesses were aligned: the vectorized loop could check that if flag array was uniformly 0 or uniformly 1, if not it is safe to use the straightforward unconditional unmasked read implementation, otherwise it would fall back to the more careful implementation. Such a transformation would evidently only be profitable if the masks were rarely uniform, or almost always uniform³, and so are probably unlikely to be implemented in practice.

² 至少如果 AVX 可用:如果将第一个示例限制为前 AVX 指令，icc 仍然无法矢量化第一个示例，因为那是 vpmaskmovd/q 和 vmaskmovps/pd被介绍了.

² At least if AVX is available: icc will still fail to vectorize the first example if you restrict it to pre-AVX instructions, since that's when vpmaskmovd/q and vmaskmovps/pd were introduced.

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

³ Since in that case if you've already determined the mask is uniform, you can implement the operation unconditionally by just doing the selected side of the if without any masking/blending based on whether it was uniform-0 or uniform-1. So you end up with three loops that internally implement: the all-zeros flag case, the all-ones flag case, and the mixed flag case, with jumps between them when the next vector of flags isn't the same as the current loop.

这篇关于AVX-512 和分支的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！