x86 - 使用 AVX2 计算 8 个 long int 的最小值

Question

我试图使用 AVX2 找到 8 个 long ints 的最小值。我是 SIMD 编程的菜鸟，我不知道从哪里开始。我没有看到任何解释如何在 AVX2 中执行 min 和 max 的帖子/示例。我知道由于 256 位 限制，我不能超过 4 个 long ints，但我可以使用三个步骤解决我的问题。此外，我无法弄清楚如何将已经存在的普通 long int array 的数据加载到 vectors for avx2。

我知道这个过程背后的想法，这就是我想要实现的目标

long int nums = {1 , 2, 3 , 4 , 5 , 6 , 7, 8}
a = min(1,2) ; b = min(3,4) ; c = min(5,6) ; d = min(7,8)
x = min(a,b) ; y = min(c,d)
answer  = min(x,y)

有人可以帮我解决如何让它工作吗？最后一个 min 是一个单一的操作，在 CPU 上做它更好吗？我应该使用 AVX2 以外的其他东西吗？ (我在 x86 系统上)

Answer 1

对于 x86 优化等，请参阅 https://stackoverflow.com/tags/x86/info 上的链接.特别是Intel 的内在函数指南，以及 Agner Fog 的资料。

如果您总是恰好有 8 个元素(64 字节)，那么事情就会大大简化。向量化小东西时的主要挑战之一是不要添加太多启动/清理开销来处理未填充整个向量的剩余元素。

AVX2 没有用于打包 64 位整数的最小/最大指令。只有 8、16 和 32。这意味着您需要使用生成掩码的比较来模拟它(条件为假的元素为全 0，条件为真时为全 1，因此您可以与此掩码将元素清零在其他向量中。)为了节省实际执行 AND/ANDN 和 OR 操作以将事物与掩码结合起来，有混合指令。

AVX-512 将为这个操作带来很大的加速。 (支持进入(仅限至强)Skylake)。它有一个 _mm_min_epi64。此操作还有一个库函数:__int64 _mm512_reduce_min_epi64 (__m512i a)。我假设这个内在函数会发出一系列 vpminsq 指令。 Intel 将它列在他们的内部查找器中，但它只是一个 Intel 库函数，不是机器指令。

这是一个应该有效的 AVX2 实现。我还没有测试过它，但编译后的输出看起来像是正确的指令序列。我可能在某处得到了颠倒的比较，所以检查一下。

操作原理是:获取两个256b向量的elementwise min。将其拆分为两个 128b 向量并获取其元素最小值。然后将该两个 64b 值的向量返回到 GP 寄存器并执行最后的最小值。最大同时完成，与最小交错。

(哎呀，你在问题中提到了最小/最大值，但现在我看到你实际上只想要最小值。删除不需要的部分是微不足道的，你可以将其更改为返回值而不是通过指针存储结果/references。标量版本可能更快；在您的应用程序使用此操作的上下文中进行更好的测试(不是独立的微基准测试)。)

#include <stdint.h>
#include <immintrin.h>

int64_t input[8] = { 1, 2, 3, };

#define min(a,b) \
   ({ __typeof__ (a) _a = (a); __typeof__ (b) _b = (b); \
     _a < _b ? _a : _b; })

#define max(a,b) \
   ({ __typeof__ (a) _a = (a); \
       __typeof__ (b) _b = (b); \
     _a > _b ? _a : _b; })

// put this where it can get inlined.  You don't want to actually store the results to RAM
// or have the compiler-generated VZEROUPPER at the end for every use.
void minmax64(int64_t input[8], int64_t *minret, int64_t *maxret)
{
    __m256i *in_vec = (__m256i*)input;
    __m256i v0 = in_vec[0], v1=in_vec[1];  // _mm256_loadu_si256 is optional for AVX

    __m256i gt = _mm256_cmpgt_epi64(v0, v1); // 0xff.. for elements where v0 > v1.  0 elsewhere
    __m256i minv = _mm256_blendv_epi8(v0, v1, gt);  // take bytes from v1 where gt=0xff (i.e. where v0>v1)
    __m256i maxv = _mm256_blendv_epi8(v1, v0, gt);  // input order reversed

    /* for 8, 16, or 32b:  cmp/blend isn't needed
       minv = _mm256_min_epi32(v0,v1);
       maxv = _mm256_min_epi32(v0,v1);  // one insn shorter, but much faster (esp. latency)
       And at the stage of having a 128b vectors holding the min and max candidates,
       you'd shuffle and repeat to get the low 64, and optionally again for the low 32,
       before extracting to GP regs to finish the comparisons.
     */

    __m128i min0 = _mm256_castsi256_si128(minv); // stupid gcc 4.9.2 compiles this to a vmovdqa
    __m128i min1 = _mm256_extracti128_si256(minv, 1);  // extracti128(x, 0) should optimize away to nothing.

    __m128i max0 = _mm256_castsi256_si128(maxv);
    __m128i max1 = _mm256_extracti128_si256(maxv, 1);

    __m128i gtmin = _mm_cmpgt_epi64(min0, min1);
    __m128i gtmax = _mm_cmpgt_epi64(max0, max1);
    min0 = _mm_blendv_epi8(min0, min1, gtmin);
    max0 = _mm_blendv_epi8(max1, max0, gtmax);

    int64_t tmp0 = _mm_cvtsi128_si64(min0);    // tmp0 = max0.m128i_i64[0];  // MSVC only
    int64_t tmp1 = _mm_extract_epi64(min0, 1);
    *minret = min(tmp0, tmp1);  // compiles to a quick cmp / cmovg of 64bit GP registers

    tmp0 = _mm_cvtsi128_si64(max0);
    tmp1 = _mm_extract_epi64(max0, 1);
    *maxret = min(tmp0, tmp1);
}

这可能比在 GP 寄存器中完成所有事情更快，也可能不会更快，因为 64 位加载是一个 uop，cmp 是一个 uop，而 cmovcc 只是 2 uops(在英特尔上)。 Haswell 每个周期可以发出 4 微指令。在到达比较树的底部之前，还有很多独立的工作要做，即便如此，cmp 是 1 个周期延迟，而 cmov 是 2 个周期。如果您同时将工作交错进行最小值和最大值时间，有两个独立的依赖链(或在本例中为树)。

矢量版本的延迟比吞吐量高得多。如果您需要对多个独立的 8 个值集执行此操作，矢量版本可能会做得很好。否则，pcmpgt* 的 5 个周期延迟和 blendv 的 2 个周期延迟将会受到伤害。如果有其他可以并行进行的独立工作，那很好。

如果您有较小的整数，pmin*(有符号或无符号，8、16 或 32b)是 1 个周期延迟，每个周期 2 个吞吐量。仅对于 16b 无符号元素，甚至还有一个水平最小指令，它为您提供了一个向量中 8 个元素中的最小元素，正如 user-number-guy 评论的那样。这消除了在将最小候选者缩小到适合一个向量后所需的整个拆分/最小缩小过程。