时间戳

首页 > 解决方案 > 如何自动矢量化一个循环，该循环 1）修改数组，2）指示数组最后是否更改？

c++ - 如何自动矢量化一个循环，该循环 1）修改数组，2）指示数组最后是否更改？

问题描述

我有这个 C++ 函数：

#include <stddef.h>

typedef unsigned long long Word;

bool fun(Word *lhs, const Word *rhs, size_t s)
{
    bool changed = false;
    #pragma omp simd
    for (size_t i = 0; i < s; ++i) {
        const Word old = lhs[i];
        lhs[i] |= rhs[i];
        changed = changed || old != lhs[i];
    }

    return changed;
}

lhs |= rhs本质上，它是位向量 ( )的按位或实现。我对编写具有 SIMD 意识的代码还很陌生，而且我不太清楚如何让编译器在不引入额外开销的情况下对其进行向量化（例如，创建changed一个数组然后循环它）。删除这changed = ...条线可以让一切都很好地矢量化。

我试过omp simd有无。我认为这无关紧要，但我想保留它，因为lhs永远rhs不会重叠，我想align最终添加该子句。

目前，我正在与 GCC 合作，但我希望最终能够与 GCC 和 Clang 一起工作。

标签： c++copenmpvectorizationsimd

解决方案

TL:DR: 使用Word unchanged = -1ULL;和更新它，unchanged &= (old == lhs[i]) ? -1ULL : 0;因此它自然地映射到 SIMD 比较相等和 SIMD AND。

或者更好的是，changed |= old ^ lhs[i];使用 GCC 和 clang 很好地矢量化，用于Word changed = 0;. 使用 clang，它提供了最佳的汇编。使用 GCC，第一种方法更好，因为 GCC 不希望changed |= (~old) & rhs[i]; // find RHS bits that weren't already set花费额外的 movdqa 寄存器副本，或者使用 AVX 删除将未对齐的负载折叠到内存源中的能力vpor（因为它需要两个操作数两次，一次用于此，一次用于主要|）。

在 AVX-512 之前，比较不相等不直接可用；这样做必须在组合成changed向量之前反转比较结果。

整个操作可以使用内部函数（或 asm）手动矢量化，几乎与编写的一样，无需任何重大转换，当然除了优化为按位|OR 而不是实际的短路评估。所以这基本上是一个错过的优化。 但是在这个自然的 asm 实现中，你的changed元素向量将与数据的宽度相同，而不仅仅是 4bool秒。 （对于 x86 来说，需要额外vmovmskpd提供一个标量or而不仅仅是一个 SIMD vpor，并且大多数 ISA 没有移动掩码操作，所以可能通用矢量化器甚至没有考虑使用它。有趣的事实：clang 自动矢量化你的原始代码真的很糟糕，bool每次迭代都做一个水平或下降到一个标量。）

使用Word changed = 0;可以使这个向量化得相当体面，有changed |= ...、有或没有 OpenMP 编译指示（不同的是，还没有确定哪个实际上对每个组合更好）。编译器是愚蠢的（复杂的机器部件，不是人类的理解）并且通常不会自己弄清楚这样的事情 - 自动矢量化已经足够困难，以至于他们有时需要一些手把手。

所以诀窍是使changed宽度与数组元素相同。

如果您使用 OpenMP，则需要告诉 OpenMP 矢量化器有关减少的信息，例如带有 的数组的总和+，或者在这种情况下为 OR。在这种情况下，#pragma omp simd reduction(|:changed)。changed |= stuff如果您希望将其矢量化为无分支 SIMD，则无论如何 您都应该使用而不是逻辑短路评估。reduction(|:changed)实际上似乎在某种程度上覆盖了您的实际代码，所以要小心它匹配。

#pragma omp simd 如果您只使用https://godbolt.org/z/bG98Kz，ICC 甚至会破坏您的代码（不会在 SIMD 部分更新更改）。（也许这给了它忽略串行依赖的许可，或者至少是减少，你没有告诉它？无论是那个还是 ICC 错误，我不太了解 OpenMP。）

使用原始bool changed而不是Word，GCC 根本不会自动矢量化，并且 clang 做了一件令人讨厌的工作（bool在内部循环中水平减少为标量！）

自动矢量化的两个版本：

在 Godbolt上-O3 -march=nehalem -mtune=skylake -fopenmp（所以使用 SSE4.1 / 4.2，但不使用 AVX 或 BMI1/BMI2）。我还没有详细研究哪个最终会得到不那么笨重的清理代码。

#include <stddef.h>
typedef unsigned long long Word;

bool fun_v1(Word *lhs, const Word *rhs, size_t s)
{
    Word changed = 0;
    #pragma omp simd reduction(|:changed)  // optional, some asm differences with/without
    for (size_t i = 0; i < s; ++i) {
        const Word old = lhs[i];
        changed |= (~old) & rhs[i];   // find RHS bits that weren't already set. pure bitwise, no 64-bit-element SIMD == needed.  Do this before storing so compiler doesn't have to worry about lhs/rhs overlap.
        lhs[i] |= rhs[i];
        //changed |= (old != lhs[i]) ? -1ULL : 0;    // requires inverting the cmpeq result, but can fold a memory operand with AVX unlike the bitwise version

        //changed = changed || (old != lhs[i]);    // short circuit eval is weird for SIMD, compiles inefficiently.
    }

    return changed;
}

（更新：在不等于上获得非零值changed |= old ^ lhs[i];似乎更好。它仅使用交换操作，不需要==/ pcmpeqq。@chtz 在评论中建议了这一点，我没有重写其余的答案减少对更糟糕的 optoins 的讨论。clang 将使用它进行自动矢量化，并且使用 AVX 允许 rhs 的内存源操作数，因为它只需要一次。https : //godbolt.org/z/ex5519 。所以这似乎是最好的两个世界。）

changed |= (old != lhs[i]) ? -1ULL : 0;changed |= (~old) & rhs[i];对于没有 AVX 的 GCC 10.2，内部循环中也仍然只有 10 条指令（9 微指令） 。但是对于 clang，这会破坏自动矢量化！Clang 将处理changed |= (old != lhs[i]); （或使用显式? 1 : 0）所以这很奇怪。 -1ULL避免需要set1_epi64x(1)向量常数，所以我使用了它。

使用==或!=将需要 SSE4.1pcmpeqq的版本进行 64 位比较的矢量化==： 编译器可能不够聪明，无法意识到任何整数元素大小都适合整体情况。并且模拟一个更窄的比较可能看起来不会有利可图。

该~old & rhs[i]方式仅适用于 SSE2。用 SSE4.1 而不是 shuffle 和 POR 和 MOVQ 结束循环ptest会更有效，但是编译器对这样的东西非常愚蠢。（并且一般处理循环的末端。只是天真的减少，以及奇数元素的标量清理，而不是在数组末端结束的可能重叠的最终向量。 |=是幂等的，所以在最坏的情况下它会导致存储转发停止如果你没有很好地安排你的负载.这是你可以通过手动矢量化做得更好的另一件事,但是使用内在函数会强制一个 SIMD 向量宽度,而 auto-vec 让编译器在你为 AVX2 CPU 编译时使用更宽的向量-march=haswell或-march=znver2.)

在 AVX-512 之前，只有比较 for==可用（或>），而不是!=直接比较。为了以我们想要的方式减少这种情况，我们需要unchanged &= (old == updated);. 这让 GCC 可以在循环中保存 1 条指令，将其减少到 9 条指令，8 uop。它可能每 2 个周期运行 1 次迭代。

但是由于某种原因，clang 根本不会自动矢量化它。显然，clang 不喜欢? -1 : 0这里或其他版本中的三元，也许没有意识到 SIMD 比较产生的就是这个。

bool fun_v2(Word *lhs, const Word *rhs, size_t s)
{
    Word unchanged = -1ULL;
// clang fails to vectorize?!?  GCC works as expected with/without pragma
    #pragma omp simd reduction(&:unchanged)
    for (size_t i = 0; i < s; ++i) {
        const Word old = lhs[i];
        lhs[i] |= rhs[i];
        unchanged &= (old == lhs[i]) ? -1ULL : 0;
    }
    return !unchanged;
}

有了可用的 AVX，vpor如果编译器不使用愚蠢的索引寻址模式，那么内存源操作数将是有效的，这会迫使它在 Intel Sandybridge 系列（但不是 AMD）上取消分层。

请注意，如果您正在考虑将Word其用作宽类型以在其他类型的任意数据上使用它，请注意严格别名规则和未定义行为。手动矢量化可能是一个不错的选择，因为_mm_loadu_si128((const __m128*)int_ptr);它是完全严格别名安全的：矢量指针（和加载/存储内在函数）就像char*它们可以别名任何东西一样。对于可移植版本，请使用 memcpy 或 GNU C typedef unsigned long unaligned_aliasing_chunk __attribute__((may_alias,aligned(1)))。对于不同的 ISA，“Word”在 asm 中具有不同的含义，例如 x86 中的 16 位，因此对于您想要宽泛的类型来说，它不是最好的名称，因为机器可以有效地使用它。 unsigned long通常是这样，但在某些 64 位机器上是 32 位的。 unsigned long long可能没问题。

推荐阅读