c - AVX512 - 如何将所有设置位向右移动？

Question

如何将掩码寄存器的所有设置位向右移动？ (到底部，最不重要的位置)。

例如:

__mmask16 mask = _mm512_cmpeq_epi32_mask(vload, vlimit); // mask = 1101110111011101

如果我们将所有设置位向右移动，我们将得到:1101110111011101 -> 0000111111111111

我怎样才能有效地实现这一点？

下面您可以看到我是如何尝试获得相同结果的，但效率很低:

__mmask16 mask = 56797;
// mask: 1101110111011101
__m512i vbrdcast = _mm512_maskz_broadcastd_epi32(mask, _mm_set1_epi32(~0));
// vbrdcast: -1 0 -1 -1 -1 0 -1 -1 -1 0 -1 -1 -1 0 -1 -1
__m512i vcompress = _mm512_maskz_compress_epi32(mask, vbrdcast);
// vcompress:-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 
__mmask16 right_packed_mask =   _mm512_movepi32_mask(vcompress);   
// right_packed_mask: 0000111111111111                         

执行此操作的最佳方法是什么？

Answer 1

BMI2 pext是 v[p]compressd/q/ps/pd 的按位等效标量.
在掩码值上使用它，将它们左打包到值的底部。

  mask = _pext_u32(-1U, mask);    // or _pext_u64(-1ULL, mask64)  for __mmask64
// costs 3 asm instructions (kmov + pext + kmov) if you need to use the result as a mask
// not including putting -1 in a register.

__mmask16(在 GCC 中也称为 uint16_t)和 uint32_t 之间的隐式转换有效。
使用 _cvtu32_mask16和 _cvtu32_mask16如果您愿意，可以使 KMOVW 显式化。

参见 How to unset N right-most set bits有关以这种方式使用 pext/pdep 的更多信息。

目前所有带有 AVX-512 的 CPU 也有快速的 BMI2 pext (包括 Xeon Phi)，性能与 popcnt 相同。 AMD 很慢 pext直到 Zen 3，但如果/当 AMD 推出 AVX-512 CPU 时，它应该具有快速 pext/pdep .

对于没有 AVX512 的早期 AMD，您可能需要 (1ULL << __builtin_popcount(mask)) - 1 ，但如果所有位都已设置，请注意溢出。 1ULL << 64是未定义的行为，可能会产生 1不是0为 x86-64 编译时。

---

如果您打算使用 vpcompressd ，注意源 vector 可以简单地是全一 _mm512_set1_epi32(-1) ; compress 不关心掩码为零的元素，它们不需要已经为零。

(哪个您打包的 -1 并不重要；一旦您使用 bool 值，来自原始位掩码的 true 与常量 true 就在那里，你生成的成本更低，不依赖于你的输入掩码。同样的推理适用于 pext ，为什么你可以使用 -1U 作为源数据而不是 pdep 。即-1 或设置位没有身份；它与任何其他 -1 或设置位相同。

所以让我们尝试两种方法，看看 asm 的好坏。

inline
__mmask16 leftpack_k(__mmask16 mask){
    return _pdep_u32(-1U, mask);
}

inline
__mmask16 leftpack_comp(__mmask16 mask) {
    __m512i v = _mm512_maskz_compress_epi32(mask, _mm512_set1_epi32(-1));
    return _mm512_movepi32_mask(v);
}

查看这些的独立版本没有用，因为 __mmask16是 unsigned short 的类型定义，因此在整数寄存器中传递/返回，而不是 k寄存器。这使得 pext当然，版本看起来非常好，但我们想看看它如何内联到我们生成和使用带有 AVX-512 内在函数的掩码的情况。

// not a useful function, just something that compiles to asm in an obvious way
void use_leftpack_compress(void *dst, __m512i v){
    __mmask16 m = _mm512_test_epi32_mask(v,v);
    m = leftpack_comp(m);
    _mm512_mask_storeu_epi32(dst, m, v);
}

注释掉 m = pack(m) ，这只是生成并使用掩码的简单 2 条指令。

use_mask_nocompress(void*, long long __vector(8)):
        vptestmd        k1, zmm0, zmm0
        vmovdqu32       ZMMWORD PTR [rdi]{k1}, zmm0
        ret

因此，任何额外的指令都将归因于左包装(压缩)掩码。 GCC 和 clang 彼此制作相同的 asm，不同之处仅在于 clang 避免 kmovw永远支持kmovd . Godbolt

# GCC10.3 -O3 -march=skylake-avx512
use_leftpack_k(void*, long long __vector(8)):
        vptestmd        k0, zmm0, zmm0
        mov     eax, -1                        # could be hoisted out of a loop
        kmovd   edx, k0
        pdep    eax, eax, edx
        kmovw   k1, eax
        vmovdqu32       ZMMWORD PTR [rdi]{k1}, zmm0
        ret

use_leftpack_compress(void*, long long __vector(8)):
        vptestmd        k1, zmm0, zmm0
        vpternlogd      zmm2, zmm2, zmm2, 0xFF   # set1(-1)  could be hoisted out of a loop
        vpcompressd     zmm1{k1}{z}, zmm2
        vpmovd2m        k1, zmm1
        vmovdqu32       ZMMWORD PTR [rdi]{k1}, zmm0
        ret

所以不可提升的部分是

• kmov r,k (端口 0)/pext (端口 1)/kmov k,r (端口 5) = 3 微指令，每个执行端口一个。 (包括端口 1，它的 vector ALU 在 512 位 uops 运行时关闭)。 kmov/kmov 往返有 4 cycle latency on SKX , 和 pext是 3 个周期的延迟，总共有 7 个周期的延迟。

• vpcompressd zmm{k}{z}, z (2 p5)/vpmovd2m (端口 0)= 3 微指令，两个用于端口 5。vpmovd2m有3 cycle latency on SKX/ICL，和vpcompressd -zeroing-into-zmm 从 k 输入到 zmm 输出(SKX 和 ICL)有 6 个周期。因此，总共有 9 个周期的延迟，而且 uops 的端口分布更差。

此外，可提升部分通常更差( vpternlogd 比 mov r32, imm32 更长并且竞争更少的端口)，除非您的函数已经需要一个全一 vector 而不是全一寄存器。

结论:BMI2 pext方法在任何方面都不会更糟，而且在几个方面更好。 (除非周围代码严重在端口 1 微指令上出现瓶颈，如果使用 512 位 vector ，这种情况不太可能发生，因为在那种情况下它只能运行标量整数微指令，如 3 周期 LEA、IMUL、LZCNT，当然还有简单的 1 周期整数，比如加/减/和/或)。