使用 x64 SIMD 进行半字节改组

And*_*ács 3 sse x86-64 simd

我知道字节混洗指令,但我想对半字节(4 位值)做同样的事情,具体来说,我想在 64 位字中混洗 16 个半字节。我的洗牌索引也存储为 16 个半字节。最有效的实施是什么?

Pet*_*des 6

带有必须以这种方式存储的控制向量的任意洗牌?唉,很难共事。我想您必须将两者解压才能提供 SSSE3 pshufb,然后重新打包该结果。

可能只是punpcklbw针对右移副本,然后进行 AND 掩码以仅保留每个字节中的低 4 位。然后pshufb

有时,奇数/偶数分割比加宽每个元素更容易(因此位仅保留在其原始字节或字内)。在这种情况下,如果我们可以更改您的半字节索引编号,punpcklqdq可以将奇数或偶数半字节放在高半部分,准备将它们带回下方并进行“或”操作。

但如果不这样做,重新包装就是一个单独的问题。我猜想将相邻的字节对组合成低字节中的一个字,pmaddubsw如果吞吐量比延迟更重要的话,也许会这样。然后你可以packuswd(针对零或它本身)或pshufb(使用恒定的控制向量)。

如果您要进行多次此类洗牌,则可以将两个向量压缩为一个,以使用movhps/存储movq。使用 AVX2,可以让所有其他指令在两个 128 位通道中的两个独立的洗牌上工作。

// UNTESTED, requires only SSSE3
#include <stdint.h>
#include <immintrin.h>

uint64_t shuffle_nibbles(uint64_t data, uint64_t control)
{
  __m128i vd = _mm_cvtsi64_si128(data);    // movq
  __m128i vd_hi = _mm_srli_epi32(vd, 4);   // x86 doesn't have a SIMD byte shift
  vd = _mm_unpacklo_epi8(vd, vd_hi);       // every nibble at the bottom of a byte, with high garbage
  vd = _mm_and_si128(vd, _mm_set1_epi8(0x0f));  // clear high garbage for later merging

  __m128i vc = _mm_cvtsi64_si128(control);
  __m128i vc_hi = _mm_srli_epi32(vc, 4);
  vc = _mm_unpacklo_epi8(vc, vc_hi);

  vc = _mm_and_si128(vc, _mm_set1_epi8(0x0f));  // make sure high bit is clear, else pshufb zeros that element.
       //  AVX-512VBMI  vpermb doesn't have that problem, if you have it available
  vd = _mm_shuffle_epi8(vd, vc);

       // left-hand input is the unsigned one, right hand is treated as signed bytes.
  vd = _mm_maddubs_epi16(vd, _mm_set1_epi16(0x1001));  // hi nibbles << 4 (*= 0x10), lo nibbles *= 1.

  // vd has nibbles merged into bytes, but interleaved with zero bytes
  vd = _mm_packus_epi16(vd, vd);  // duplicate vd into low & high halves.
  //  Pack against _mm_setzero_si128() if you're not just going to movq into memory or a GPR and you want the high half of the vector to be zero.
  return _mm_cvtsi128_si64(vd);
}
Run Code Online (Sandbox Code Playgroud)

0x0f在混洗之前(而不是之后)屏蔽数据可以在具有两个混洗单元的 CPU 上实现更多 ILP。至少如果它们在向量寄存器中已经有 uint64_t 值,或者如果数据和控制值来自内存,那么两者都可以在同一周期中加载。如果来自 GPR,则 1/时钟吞吐量vmovq xmm, reg意味着 dep 链之间存在资源冲突,因此它们不能在同一周期启动。但由于数据可能在控制之前就准备好了,因此提前屏蔽可以使其远离控制->输出延迟的关键路径。

如果延迟而不是通常的吞吐量是瓶颈,请考虑pmaddubsw用右移 4、por和 AND/pack 替换。或者pshufb打包,同时忽略奇数字节中的垃圾。既然你无论如何都需要另一个常量,不妨将其设为pshufb常量而不是and

如果您有 AVX-512,则移位和位混合vpternlogd可以避免在洗牌之前需要屏蔽数据,并且vpermb可以避免vpshufb需要屏蔽控件,因此您可以set1_epi8(0x0f)完全避免使用常量。

clang 的 shuffle 优化器没有发现任何东西,只是像 GCC 那样编译它(https://godbolt.org/z/xz7TTbM1d),即使使用-march=sapphirerapids. 没有发现它可以使用/vpermb代替。vpandvpshufb

shuffle_nibbles(unsigned long, unsigned long):
        vmovq   xmm0, rdi
        vpsrld  xmm1, xmm0, 4
        vpunpcklbw      xmm0, xmm0, xmm1        # xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1],xmm0[2],xmm1[2],xmm0[3],xmm1[3],xmm0[4],xmm1[4],xmm0[5],xmm1[5],xmm0[6],xmm1[6],xmm0[7],xmm1[7]
        vmovq   xmm1, rsi
        vpsrld  xmm2, xmm1, 4
        vpunpcklbw      xmm1, xmm1, xmm2        # xmm1 = xmm1[0],xmm2[0],xmm1[1],xmm2[1],xmm1[2],xmm2[2],xmm1[3],xmm2[3],xmm1[4],xmm2[4],xmm1[5],xmm2[5],xmm1[6],xmm2[6],xmm1[7],xmm2[7]
        vmovdqa xmm2, xmmword ptr [rip + .LCPI0_0] # xmm2 = [15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15]
        vpand   xmm0, xmm0, xmm2
        vpand   xmm1, xmm1, xmm2
        vpshufb xmm0, xmm0, xmm1
        vpmaddubsw      xmm0, xmm0, xmmword ptr [rip + .LCPI0_1]
        vpackuswb       xmm0, xmm0, xmm0
        vmovq   rax, xmm0
        ret
Run Code Online (Sandbox Code Playgroud)

(如果没有 AVX,则需要 2 个额外的movdqa寄存器复制指令。)

  • 我已经包含了一个[测试](https://github.com/brettyhale/so-snippets/blob/main/so.71936833.c),其中包含您的代码序言/尾声到随机播放。一些测试向量包括:[https://godbolt.org/z/qMca4sPbh](https://godbolt.org/z/qMca4sPbh) (2认同)