使用 AVX2 计算 8 个 long int 的最小值
Calculating min of 8 long ints using AVX2
我试图使用 AVX2 找到 8 long ints 的最小值。我是 SIMD 编程的菜鸟，我不知道从哪里开始。我没有看到任何 post/example 解释如何在 AVX2 中执行 min 和 max。我知道由于 256 bit 的限制，我不能超过 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 系统上）
对于 x86 优化等，请参阅 https://whosebug.com/tags/x86/info 上的链接。特别是Intel 的内在函数指南和 Agner Fog 的资料。
如果你总是恰好有 8 个元素（64 字节），那会大大简化事情。向量化小东西时的主要挑战之一是不要添加太多 startup/cleanup 处理未填充整个向量的剩余元素的开销。
AVX2 没有 min/max 用于压缩 64 位整数的指令。只有 8、16 和 32。这意味着您需要使用生成掩码的比较来模拟它（条件为假的元素为全 0，条件为真时为全 1，因此您可以使用 AND 这个掩码将元素归零在其他向量中。）为了节省实际执行 AND/ANDN 和 OR 操作以将事物与掩码组合起来，有混合指令。
AVX-512 将 为这个操作带来很大的加速。 （支持进入（仅限至强）Skylake）。它有一个 _mm_min_epi64。此操作还有一个库函数：__int64 _mm512_reduce_min_epi64 (__m512i a)。我假设这个内在函数会发出一系列 vpminsq 指令。英特尔将其列在他们的内部查找器中，但它只是一个英特尔库函数，不是机器指令。
这是一个应该有效的 AVX2 实现。我还没有测试过它，但编译后的输出看起来像是正确的指令序列。我可能在某处得到了相反的比较，所以检查一下。
操作原理是：获取两个256b向量的elementwise min。将其拆分为两个 128b 向量并获取其元素最小值。然后将该两个 64b 值的向量返回到 GP 寄存器并执行最后的最小值。 max同时做，与min交错
(糟糕，你在问题中提到了 min/max，但现在我看到你实际上只想要最小值。删除不需要的部分很简单，你可以将其更改为 return 值而不是通过 pointers/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 uop（在 Intel 上). Haswell 每个周期可以发出 4 微指令。在到达比较树的底部之前，还有很多独立的工作要做，即便如此，cmp 是 1 个周期延迟，而 cmov 是 2 个周期。如果您同时将工作交错进行最小值和最大值时间，有两个独立的依赖链（在这种情况下或树）。
矢量版本的延迟比吞吐量高得多。如果您需要对多个独立的 8 个值集执行此操作，矢量版本可能会做得很好。否则，pcmpgt* 的 5 个周期延迟和 blendv 的 2 个周期延迟将会受到伤害。如果有其他独立的工作可以并行进行，那很好。
如果您有较小的整数，pmin*（有符号或无符号，8、16 或 32b）是 1 个周期延迟，每个周期 2 个吞吐量。仅对于 16b 无符号元素，甚至还有一个水平最小指令，它为您提供了一个向量中 8 个元素中的最小元素，正如 user-number-guy 评论的那样。这消除了将最小候选者缩小到适合一个向量后所需的整个拆分/最小缩小过程。
我试图使用 AVX2 找到 8 long ints 的最小值。我是 SIMD 编程的菜鸟，我不知道从哪里开始。我没有看到任何 post/example 解释如何在 AVX2 中执行 min 和 max。我知道由于 256 bit 的限制，我不能超过 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 系统上）
对于 x86 优化等，请参阅 https://whosebug.com/tags/x86/info 上的链接。特别是Intel 的内在函数指南和 Agner Fog 的资料。
如果你总是恰好有 8 个元素（64 字节），那会大大简化事情。向量化小东西时的主要挑战之一是不要添加太多 startup/cleanup 处理未填充整个向量的剩余元素的开销。
AVX2 没有 min/max 用于压缩 64 位整数的指令。只有 8、16 和 32。这意味着您需要使用生成掩码的比较来模拟它（条件为假的元素为全 0，条件为真时为全 1，因此您可以使用 AND 这个掩码将元素归零在其他向量中。）为了节省实际执行 AND/ANDN 和 OR 操作以将事物与掩码组合起来，有混合指令。
AVX-512 将 为这个操作带来很大的加速。 （支持进入（仅限至强）Skylake）。它有一个 _mm_min_epi64。此操作还有一个库函数：__int64 _mm512_reduce_min_epi64 (__m512i a)。我假设这个内在函数会发出一系列 vpminsq 指令。英特尔将其列在他们的内部查找器中，但它只是一个英特尔库函数，不是机器指令。
这是一个应该有效的 AVX2 实现。我还没有测试过它，但编译后的输出看起来像是正确的指令序列。我可能在某处得到了相反的比较，所以检查一下。
操作原理是：获取两个256b向量的elementwise min。将其拆分为两个 128b 向量并获取其元素最小值。然后将该两个 64b 值的向量返回到 GP 寄存器并执行最后的最小值。 max同时做，与min交错
(糟糕，你在问题中提到了 min/max，但现在我看到你实际上只想要最小值。删除不需要的部分很简单，你可以将其更改为 return 值而不是通过 pointers/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 uop（在 Intel 上). Haswell 每个周期可以发出 4 微指令。在到达比较树的底部之前，还有很多独立的工作要做，即便如此，cmp 是 1 个周期延迟，而 cmov 是 2 个周期。如果您同时将工作交错进行最小值和最大值时间，有两个独立的依赖链（在这种情况下或树）。
矢量版本的延迟比吞吐量高得多。如果您需要对多个独立的 8 个值集执行此操作，矢量版本可能会做得很好。否则，pcmpgt* 的 5 个周期延迟和 blendv 的 2 个周期延迟将会受到伤害。如果有其他独立的工作可以并行进行，那很好。
如果您有较小的整数，pmin*（有符号或无符号，8、16 或 32b）是 1 个周期延迟，每个周期 2 个吞吐量。仅对于 16b 无符号元素，甚至还有一个水平最小指令，它为您提供了一个向量中 8 个元素中的最小元素，正如 user-number-guy 评论的那样。这消除了将最小候选者缩小到适合一个向量后所需的整个拆分/最小缩小过程。