AVX中的水平异或

Question

有没有一种方法可以水平地异或一个AVX寄存器--具体来说，是用来对256位寄存器的四个64位组件进行异或？

目标是获得AVX寄存器的所有4位64位组件的异或值.本质上，它将执行与水平添加(_mm256_hadd_epi32())相同的操作，但我想要的是异或而不是添加。

标量码是：

inline uint64_t HorizontalXor(__m256i t) {
  return t.m256i_u64[0] ^ t.m256i_u64[1] ^ t.m256i_u64[2] ^ t.m256i_u64[3];
}

Answer 1

正如注释中所述，最快的代码很可能使用标量操作，在整数寄存器中执行所有操作。您所需要做的就是提取四个打包的64位整数，然后您有三个XOR指令，您就完成了。这可以非常有效地完成，并将结果保留在整数寄存器中，这就是示例代码所建议的。

MSVC已经为标量函数生成了相当好的代码，作为问题中的一个示例：

inline uint64_t HorizontalXor(__m256i t) {
  return t.m256i_u64[0] ^ t.m256i_u64[1] ^ t.m256i_u64[2] ^ t.m256i_u64[3];
}

假设t在ymm1中，则所产生的反汇编如下所示：

vextractf128 xmm0, ymm1, 1
vpextrq      rax,  xmm0, 1
vmovq        rcx,  xmm1
xor          rax,  rcx
vpextrq      rcx,  xmm1, 1
vextractf128 xmm0, ymm1, 1
xor          rax,  rcx
vmovq        rcx,  xmm0
xor          rax,  rcx

…结果留在RAX中。如果这准确地反映了您需要的内容(一个标量uint64_t结果)，那么这段代码就足够了。

您可以通过使用内在属性来稍微改进它：

inline uint64_t _mm256_hxor_epu64(__m256i x)
{
   const __m128i temp = _mm256_extracti128_si256(x, 1);
   return (uint64_t&)x
          ^ (uint64_t)(_mm_extract_epi64(_mm256_castsi256_si128(x), 1))
          ^ (uint64_t&)(temp)
          ^ (uint64_t)(_mm_extract_epi64(temp, 1));
}

然后您将得到以下反汇编(同样，假设x在ymm1中)：

vextracti128 xmm2, ymm1, 1
vpextrq      rcx,  xmm2, 1
vpextrq      rax,  xmm1, 1
xor          rax,  rcx
vmovq        rcx,  xmm1
xor          rax,  rcx
vmovq        rcx,  xmm2
xor          rax,  rcx

注意，我们能够删除一个提取指令，并且确保使用了VEXTRACTI128而不是VEXTRACTF128 (尽管，this choice probably does not matter)。

您将在其他编译器上看到类似的输出。例如，下面是GCC 7.1 (假定x在ymm0中)：

vextracti128 xmm2, ymm0, 0x1
vpextrq      rax,  xmm0, 1
vmovq        rdx,  xmm2
vpextrq      rcx,  xmm2, 1
xor          rax,  rdx
vmovq        rdx,  xmm0
xor          rax,  rdx
xor          rax,  rcx

同样的指令在那里，但它们被稍微地重新排序了。本质允许编译器的调度程序按其认为最佳的顺序排序。Clang 4.0对它们进行了不同的安排：

vmovq        rax,  xmm0
vpextrq      rcx,  xmm0, 1
xor          rcx,  rax
vextracti128 xmm0, ymm0, 1
vmovq        rdx,  xmm0
xor          rdx,  rcx
vpextrq      rax,  xmm0, 1
xor          rax,  rdx

当然，当代码内联时，这种排序总是会发生变化的。

另一方面，如果您希望结果在AVX寄存器中，那么您首先需要决定如何存储它。我想您应该将单个64位结果存储为一个标量，如下所示：

inline __m256i _mm256_hxor(__m256i x)
{
   const __m128i temp = _mm256_extracti128_si256(x, 1);
   return _mm256_set1_epi64x((uint64_t&)x
                             ^ (uint64_t)(_mm_extract_epi64(_mm256_castsi256_si128(x), 1))
                             ^ (uint64_t&)(temp)
                             ^ (uint64_t)(_mm_extract_epi64(temp, 1)));
}

但是现在您正在做大量的数据洗牌，否定了代码矢量化可能带来的任何性能提升。

说到这点，我不太清楚你是如何让自己陷入这样一个局面的:首先你需要做这样的横向操作。SIMD操作的设计是垂直的，而不是水平的。如果您仍处于实现阶段，则重新考虑设计可能是合适的。特别是，您应该在4个不同的AVX寄存器中生成4个整数值，而不是将它们打包到一个寄存器中。

如果您实际上希望将结果的4个副本打包到一个AVX寄存器中，那么您可以这样做：

inline __m256i _mm256_hxor(__m256i x)
{
   const __m256i temp = _mm256_xor_si256(x,
                                         _mm256_permute2f128_si256(x, x, 1));    
   return _mm256_xor_si256(temp,
                           _mm256_shuffle_epi32(temp, _MM_SHUFFLE(1, 0, 3, 2)));
}

这仍然利用了一些并行性，同时执行两个XOR，这意味着总共只需要两个XOR操作，而不是三个。

如果它有助于可视化，这基本上是这样的：

   A         B         C         D           ⟵ input
  XOR       XOR       XOR       XOR
   C         D         A         B           ⟵ permuted input
=====================================
  A^C       B^D       A^C        B^D         ⟵ intermediate result
  XOR       XOR       XOR        XOR
  B^D       A^C       B^D        A^C         ⟵ shuffled intermediate result
======================================
A^C^B^D   A^C^B^D   A^C^B^D    A^C^B^D      ⟵ final result

实际上，在所有编译器上，这些内部代码将生成以下汇编代码：

vperm2f128  ymm0, ymm1, ymm1, 1    ; input is in YMM1
vpxor       ymm2, ymm0, ymm1
vpshufd     ymm1, ymm2, 78
vpxor       ymm0, ymm1, ymm2

(我在第一次发布这个答案后，在上床的路上想到了这个，并计划回来更新答案，但我发现wim在发布它时比我快。哦，这仍然是一个比我第一次有更好的方法，所以它仍然值得包括在这里。)

当然，如果你想把它放在整数寄存器中，你只需要一个简单的VMOVQ。

vperm2f128  ymm0, ymm1, ymm1, 1    ; input is in YMM1
vpxor       ymm2, ymm0, ymm1
vpshufd     ymm1, ymm2, 78
vpxor       ymm0, ymm1, ymm2
vmovq       rax,  xmm0

问题是，这比上面的标量代码更快吗？答案是肯定的很可能。尽管您使用的是AVX执行单元来执行XOR，而不是完全独立的整数执行单元，但是需要执行的AVX洗牌/置换/摘录更少，这意味着开销更少。因此，我也可能不得不接受标量代码是最快实现的话。但这确实取决于您在做什么，以及如何调度/交织指令。

Answer 2

如果水平xor-function的输入已经在AVX寄存器中，即t是某些SIMD计算的结果，则矢量化可能是有用的。否则，标量代码可能会更快，正如@Cody Gray已经提到的那样。通常，您可以在关于log_2(SIMD_width)的“步骤”中执行水平SIMD操作。在这种情况下，一个步骤是‘洗牌/置换’和'xor‘。这比@Cody的_mm256_hxor函数效率略高：

__m256i _mm256_hxor_v2(__m256i x)
{
    __m256i x0 = _mm256_permute2x128_si256(x,x,1);       // swap the 128 bit high and low lane 
    __m256i x1 = _mm256_xor_si256(x,x0);
    __m256i x2 = _mm256_shuffle_epi32(x1,0b01001110);    // swap 64 bit lanes                         
    __m256i x3 = _mm256_xor_si256(x1,x2);
    return x3;
}

该文件汇编为：

vperm2i128  $1, %ymm0, %ymm0, %ymm1
vpxor   %ymm1, %ymm0, %ymm0
vpshufd $78, %ymm0, %ymm1
vpxor   %ymm1, %ymm0, %ymm0

如果您希望标量寄存器中的结果：

uint64_t _mm256_hxor_v2_uint64(__m256i x)
{
    __m256i x0 = _mm256_permute2x128_si256(x,x,1);
    __m256i x1 = _mm256_xor_si256(x,x0);
    __m256i x2 = _mm256_shuffle_epi32(x1,0b01001110);
    __m256i x3 = _mm256_xor_si256(x1,x2);
    return _mm_cvtsi128_si64x(_mm256_castsi256_si128(x3)) ;
}

该文件汇编为：

vperm2i128  $1, %ymm0, %ymm0, %ymm1
vpxor   %ymm1, %ymm0, %ymm0
vpshufd $78, %ymm0, %ymm1
vpxor   %ymm1, %ymm0, %ymm0
vmovq   %xmm0, %rax

完整测试代码：

#include <stdio.h>
#include <x86intrin.h>
#include <stdint.h>
/*  gcc -O3 -Wall -m64 -march=broadwell hor_xor.c   */
int print_vec_uint64(__m256i v);

__m256i _mm256_hxor_v2(__m256i x)
{
    __m256i x0 = _mm256_permute2x128_si256(x,x,1);
    __m256i x1 = _mm256_xor_si256(x,x0);
    __m256i x2 = _mm256_shuffle_epi32(x1,0b01001110);
    __m256i x3 = _mm256_xor_si256(x1,x2);
/* Uncomment the next few lines to print the values of the intermediate variables */ 
/*
    printf("3...0        =          3          2          1          0\n");
    printf("x            = ");print_vec_uint64(x        );
    printf("x0           = ");print_vec_uint64(x0        );
    printf("x1           = ");print_vec_uint64(x1        );
    printf("x2           = ");print_vec_uint64(x2        );
    printf("x3           = ");print_vec_uint64(x3        );
*/
    return x3;
}

uint64_t _mm256_hxor_v2_uint64(__m256i x)
{
    __m256i x0 = _mm256_permute2x128_si256(x,x,1);
    __m256i x1 = _mm256_xor_si256(x,x0);
    __m256i x2 = _mm256_shuffle_epi32(x1,0b01001110);
    __m256i x3 = _mm256_xor_si256(x1,x2);
    return _mm_cvtsi128_si64x(_mm256_castsi256_si128(x3)) ;
}


int main() {
    __m256i x = _mm256_set_epi64x(0x7, 0x5, 0x2, 0xB);
//    __m256i x = _mm256_set_epi64x(4235566778345231, 1123312566778345423, 72345566778345673, 967856775433457);

    printf("x            = ");print_vec_uint64(x);

    __m256i y = _mm256_hxor_v2(x);

    printf("y            = ");print_vec_uint64(y);

    uint64_t z = _mm256_hxor_v2_uint64(x);

    printf("z =  %10lX  \n",z);

    return 0;
}


int print_vec_uint64(__m256i v){
    uint64_t t[4];
    _mm256_storeu_si256((__m256i *)t,v);
    printf("%10lX %10lX %10lX %10lX \n",t[3],t[2],t[1],t[0]);
    return 0;
}

Answer 3

用于异或的_mm256_hadd_epi32()的直接模拟实现如下所示：

#include <immintrin.h>

template<int imm> inline __m256i _mm256_shuffle_epi32(__m256i a, __m256i b)
{
    return _mm256_castps_si256(_mm256_shuffle_ps(_mm256_castsi256_ps(a), _mm256_castsi256_ps(b), imm));
}

inline __m256i _mm256_hxor_epi32(__m256i a, __m256i b)
{
    return _mm256_xor_si256(_mm256_shuffle_epi32<0x88>(a, b), _mm256_shuffle_epi32<0xDD>(a, b));
}

int main()
{
    __m256i a = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
    __m256i b = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 7, 8);
    __m256i c = _mm256_hxor_epi32(a, b);
    return 0;
}