0

我有以下代码，它正确打包 64 位 int 的每 4 位。这是一种天真的方法，我使用的是查找表和循环。我想知道是否有更快的旋转、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
4

1 回答 1

4

大多数 SIMD ISA 具有字节混洗，可用于实现具有 4 位索引的 16 条目 LUT。例如 x86 SSSE3pshufb或 ARM/AArch64 vtbl/ 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 for vpermb，您无需在查找 LUT 之前移除高位。（vpshufb使用索引的高位有条件地将输出中的该元素归零，这意味着在将其用作 LUT 的大多数情况下，您需要将其设为零。）

只做一个可能vpshufb涉及vpunpcklbw复制每个字节，可能允许在. 或者也许是一个广播负载来复制整个 64 位输入，然后 AVX2只右移高半部分。然后 AND/vpshufb 一次而不是两次。然后 vpunpckhqdq + vpslld + vpor 让高半部分回落并结合。所以这些看起来都不是很好。vpmaddubswset1_epi16(0x1001)vpackuswbvpsrlvq

于 2022-02-20T07:22:41.380 回答