位摆动到右包位

Question

我有以下代码，它每 4 位 64 位 int 正确打包一次。这是天真的方法，我正在使用查找表和循环。我想知道是否有一种更快的比特摆动、swar/simd、并行方法来更快地做到这一点？ (msb() 返回最高有效位)

def pack(X):
compact = [
0b0000,   # 0
0b0001,  #  1
0b0001,  # 10
0b0011,  # 11
0b0001,  #100
0b0011,  #101
0b0011,  #110
0b0111,  #111
0b0001, #1000
0b0011, #1001
0b0011, #1010
0b0111, #1011
0b0011, #1100
0b0111, #1101
0b0111, #1110
0b1111, #1111
]
K = 0
while X:
i = msb(X)
j = (i//4 )*4
a = (X & (0b1111 << j))>>j
K |= compact[a] << j
X = X & ~(0b1111 << j)
return K

Answer 1

大多数 SIMD ISA 都有一个字节随机，可用于实现具有 4 位索引的 16 个条目 LUT。 例如 x86 SSSE3pshufb或 ARM/AArch64vtbl/tbl。

显然，msb()只是跳过全零半字节的优化，而不是真正的数据依赖关系，这是跨半字节的纯垂直 SIMD。

因此，只需拆分为 4 位半字节并再次打包即可。 对于 x86，可能是一个奇数/偶数拆分，并且两次进行半字节 LUT 比将它们打包在一起更好(例如punpcklbw或movlhps)

; asm pseudocode; translate into intrinsics in a language of your choice
; constants:
XMM7 = _mm_set1_epi8(0x0f)
XMM6 = LUT
; input in XMM0, perhaps from  vmovq xmm0, rdi  or a load
vpsrld xmm1, xmm0, 4          ; v >> 4
vpand  xmm0, xmm0,  XMM7      ; v &= 0x0f
vpand  xmm1, xmm1,  XMM7
vpshufb xmm0, XMM6, xmm0      ; low nibbles
vpshufb xmm1, XMM6, xmm1      ; high nibbles
vpslld xmm1, xmm1, 4          ; high << 4   ; alternative: make a shifted copy of the LUT to avoid this
vpor   xmm0, xmm0, xmm1
; result in low qword of XMM0; in C you might want  _mm_cvtsi128_si64
;  vmovq  rax, xmm0     get it back into an integer registers if necessary

这实际上可以在 XMM0 的高半和低半并行执行两个 64 位整数，如果你在循环中执行此操作。

使用 AVX-512 VBMI 进行vpermb，您无需在 LUT 查找之前删除高位。 (vpshufb使用索引的高位有条件地将输出中的该元素归零，这意味着在大多数情况下将其用作LUT时，您需要将其为零。

只做一个vpshufb可能涉及vpunpcklbw复制每个字节，可能允许在vpackuswb之前与具有常量(如set1_epi16(0x1001))的vpmaddubsw重新组合以移动和添加字节对。 或者可能是广播负载来复制整个 64 位输入，然后 AVX2vpsrlvq仅右移高半部分。 然后 AND/vpshufb 各一次，而不是两次。 然后 vpunpckhqdq + vpslld + vpor 让高半部分回落并组合。 所以这些似乎都不是很好。

Answer 2

不需要任何特殊 SIMD 指令的替代方法是分别考虑 4 位中的每一个：

def pack(x):
r = x & 0x11111111
r |= r + ((x >> 1) & 0x11111111)
r |= r + ((x >> 2) & 0x11111111)
r |= r + ((x >> 3) & 0x11111111)
return r