实用的大数AVX/SSE可能吗？

Question

实用的大数AVX/SSE可能吗？

17

SSE/AVX寄存器可视为整数或浮点BigNum。也就是说，可以忽略存在通道的事实。是否存在一种简单的方法来利用这种观点，并将这些寄存器作为单个或组合的BigNum使用？我之所以问，是因为我很少看到BigNum库，它们几乎普遍存储和对数组进行算术运算，而不是在SSE/AVX寄存器上。可移植性呢？

例如：

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

- user1095108

5

当然可以，但极其麻烦、低效且缓慢。如果你要对「_limbs_」（32/64位字）的数组进行加法操作，使用x86进位标志来传递进位比较容易。而SSE寄存器的通道没有进位标志，这意味着必须以一种不同的方式检测溢出（计算强度更大），即使检测到了溢出，也需要使用复杂的SSE / AVX洗牌方式将进位上移，并且必须为n个字的bignums执行「N-1」次此操作。那么，如果你需要将bignum扩展到超过128位/256位呢？ - Iwillnotexist Idonotexist

使用gcc/clang/icc的向量扩展，您可以将2个或多个寄存器连接在一起。您可以写一个答案，说明为什么您认为这样做是不实际的。事实上，我认为gcc将数组映射到SIMD寄存器时效果不佳，但它很容易且没有任何问题地将SIMD寄存器映射回来。 - user1095108

2

https://dev59.com/O2ct5IYBdhLWcg3wSbnY - phuclv

我已经确定，在当前的英特尔硬件上，没有一种有效的方法可以使用SIMD进行大数乘法。 - Z boson

@Zboson: 长整型例程能从SSE中受益吗？ - 如果重新设计存储格式，留出一些空余位以便延迟规范化/进位传递的话，是可以的。 - Peter Cordes

显示剩余2条评论

3个回答

6

从上面的评论中移动

这是可能的，但并不常见，因为在向量寄存器中实现大数并不特别方便。

对于简单的加法任务，可以轻松使用x86 EFLAGS / RFLAGS寄存器的进位标志来传播从最低“肢”（使用GMP术语）开始的加法进位，并循环遍历放置在数组中的任意数量的肢。

相反，SSE / AVX寄存器的通道没有进位标志，这意味着必须以涉及比较以检测环绕方式检测溢出，这更具计算强度。此外，如果在一个肢体中检测到溢出，则必须通过丑陋的洗牌“向上”传播，然后进行添加，而此添加可能会导致另一个溢出和进位，直到对于N-肢体的N-limb bignum，重复N-1次。然后，一旦总和将bignum带到128位/ 256位以上（或超过128位×＃寄存器），您仍需要将其移动到数组中。

因此，需要大量特殊情况代码，并且它不会更快（实际上要慢得多），仅用于加法。想象一下进行乘法需要多少工作？或者分割？

- Iwillnotexist Idonotexist

你可以并行地进行单词的初始添加，同时计算进位（比较），并并行地将它们相加。听起来还不错，是吧？ - user1095108

3

这是可能的，但不切实际。

正如我在另一个答案中所说，AVX/SSE中没有进位标志，因此无法高效地进行加减运算。而要进行乘法运算，则需要大量重排以将扩展乘积结果放置在所需位置。

如果您被允许使用更新的Haswell/Broadwell微架构，则解决方案是在BMI2中使用MULX和在ADX中使用ADOX, ADCX。您可以在此处了解更多信息。

- phuclv

请问您能否回答一下我在这个问题（http://stackoverflow.com/questions/27929402/can-someone-explain-this-sse-bignum-comparison）中提出的与您的回答相关的另一个问题吗？ - user1095108

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Z boson · Accepted Answer

我认为可以高效地使用SIMD实现大整数运算，但不是按你的方式。你应该一次处理多个大整数，而不是使用一个SIMD寄存器（或一个SIMD寄存器数组）实现单个大整数。

考虑128位相加。 128位整数由高64位值和低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位数字只需六条指令。

vpaddq
vpaddq
vpxor
vpxor
vpcmpgtq 
vpsubq

标量寄存器需要八条指令，而AVX512只需一条指令 vpcmpuq 即可进行64位无符号比较。因此，使用四条指令就可以添加八对128位数。

vpaddq
vpaddq
vpcmpuq
vpsubq

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

下表总结了添加一定数量的128位数对时所需的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表示高64位，一个128位整数的数组被存储为下面这样的结构体数组：

lhlhlhlhlhlhlhlh

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

SSE2:   llhhllhhllhhllhh
AVX2:   llllhhhhllllhhhh
AVX512: llllllllhhhhhhhh