sse - 实用的 BigNum AVX/SSE 可能吗？

Question

SSE/AVX 寄存器可以被视为整数或浮点 BigNum。也就是说，人们可能会忽略车道的存在。是否存在一种简单的方法来利用这个观点并将这些寄存器单独或组合用作 BigNum？我问这个问题是因为从我对 BigNum 库的了解来看，它们几乎普遍在数组上存储和执行算术运算，而不是在 SSE/AVX 寄存器上。可移植性？

示例:

假设您将 SSE 寄存器的内容作为键存储在 std::set 中，您可以将这些内容作为 BigNum 进行比较。

Answer 1

我认为可以用 SIMD 有效地实现 BigNum，但不是按照您建议的方式。

您应该一次处理多个 BigNum，而不是使用 SIMD 寄存器(或 SIMD 寄存器数组)实现单个 BigNum。

让我们考虑 128 位加法。让 128 位整数由一对高位和低位 64 位值定义，并假设我们要添加一个 128 位整数 (y_low, y_high)转换为 128 位整数 (x_low, x_high) 。对于标量 64 位寄存器，这只需要两条指令

add rax, rdi // x_low  += y_low;
adc rdx, rsi // x_high += y_high + (x_low < y_low);

正如其他人所解释的那样，SSE/AVX 的问题是没有 SIMD 进位标志。必须计算进位标志，然后将其相加。这需要 64 位无符号比较。对于 SSE，唯一现实的选择是来自 AMD XOP 指令 vpcomgtuq

vpaddq      xmm2, xmm0, xmm2 // x_low  += y_low;
vpcomgtuq   xmm0, xmm0, xmm2 // x_low  <  y_low
vpaddq      xmm1, xmm1, xmm3 // x_high += y_high
vpsubq      xmm0, xmm1, xmm0 // x_high += xmm0

这使用四个指令来添加两对 128 位数字。对于标量 64 位寄存器，这也需要四个指令(两个 add 和两个 adc )。

使用 AVX2，我们可以一次添加四对 128 位数字。但是XOP中没有256位宽的64位无符号指令。相反，我们可以对 a<b 执行以下操作:

__m256i sign64 = _mm256_set1_epi64x(0x8000000000000000L);
__m256i aflip = _mm256_xor_si256(a, sign64);
__m256i bflip = _mm256_xor_si256(b, sign64);
__m256i cmp = _mm256_cmpgt_epi64(aflip,bflip);

sign64寄存器可以预先计算，因此实际上只需要三个指令。因此，用 AVX2 将四对 128 位数字相加只需 6 条指令即可完成

vpaddq
vpaddq
vpxor
vpxor
vpcmpgtq 
vpsubq

而标量寄存器需要八条指令。

AVX512 有一条指令用于进行 64 位无符号比较 vpcmpuq 。因此，仅使用 4 条指令就可以将 8 对 128 位数字相加

vpaddq
vpaddq
vpcmpuq
vpsubq

使用标量寄存器需要 16 条指令才能将 8 对 128 位数字相加。

下表总结了添加多个 128 位数字对(称为 npairs)所需的 SIMD 指令(称为 nSIMD)数量和标量指令(称为 nscalar)数量

              nSIMD      nscalar     npairs
SSE2 + XOP        4           4           2
AVX2              6           8           4
AVX2 + XOP2       4           8           4
AVX-512           4          16           8

请注意，XOP2 尚不存在，我只是推测它可能在某个时候存在。

另请注意，为了有效地执行此操作，BigNum 数组需要以数组结构数组 (AoSoA) 形式存储。例如使用 l表示较低的 64 位和 h表示 128 位整数数组的高 64 位存储为这样的结构数组

lhlhlhlhlhlhlhlh

应该使用像这样的 AoSoA 来存储

SSE2:   llhhllhhllhhllhh
AVX2:   llllhhhhllllhhhh
AVX512: llllllllhhhhhhhh