13

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

例子：

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

4

3 回答 3

12

我认为可以有效地使用 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 条指令来添加八对 128 位数字。

这是一个表格，其中汇总了 SIMD 指令（称为 nSIMD）的数量和添加 128 位数字对（称为 npairs）所需的标量指令数量（称为 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表示高 64 位的 128 位整数数组存储为这样的结构数组

lhlhlhlhlhlhlhlh

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

SSE2:   llhhllhhllhhllhh
AVX2:   llllhhhhllllhhhh
AVX512: llllllllhhhhhhhh
于 2015-01-16T05:52:39.213 回答
5

从上面的评论移动

可以这样做，但没有这样做，因为在向量寄存器中实现 bignums 不是特别方便。

对于简单的加法任务，使用 x86 EFLAGS/RFLAGS 寄存器的进位标志从最低的“肢体”向上传播加法的进位（使用GMP术语）并遍历任意数量的肢体是微不足道的在一个数组中。

相反，SSE/AVX 寄存器的通道没有进位标志，这意味着必须以不同的方式检测溢出，包括比较以检测回绕，这在计算上更加密集。此外，如果在一个肢体中检测到溢出，则必须通过丑陋的 shuffle “向上”传播，然后添加，这种添加可能会导致另一个溢出和结转，最多N-1为N-limb bignum 次。然后，一旦总和使 bignum 超过 128 位/256 位（或超过 128 位 x 寄存器数），无论如何您都必须将其移动到数组中。

因此，将需要很多特殊情况的代码，而且它不会更快（实际上，慢得多），只是为了添加。想象一下乘法需要什么？还是喘气，分裂？

于 2015-01-13T13:53:11.440 回答
3

这是可能的，但不实用。

正如我在另一个答案中所说，AVX/SSE 中没有进位标志，因此不可能有效地进行加法和减法。并且要进行乘法运算，您需要大量改组才能将扩大的乘法结果放在所需的位置。

如果您被允许使用较新的 Haswell/Broadwell 微架构，解决方案将是 BMI2 中的MULX和ADOX 中的 ADCX，ADX中的 ADCX 。您可以在此处阅读有关它们的信息。

于 2015-01-13T15:55:31.560 回答