实用的BigNum AVX/SSE可能吗？

Question

SSE/AVX寄存器可以被视为整数或浮点BigNums.也就是说,人们可以忽视存在通道.是否有一种简单的方法可以利用这种观点并将这些寄存器单独或组合用作BigNum？我问,因为我从BigNum库中看到的很少,它们几乎普遍存储并对数组进行算术运算,而不是SSE/AVX寄存器.可移植性？

例:

假设您将SSE寄存器的内容存储为a中的键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位数字可以使用六条指令完成

vpaddq
vpaddq
vpxor
vpxor
vpcmpgtq 
vpsubq

而标量寄存器需要8条指令.

AVX512有一条指令用于进行64位无符号比较vpcmpuq.因此,应该可以仅使用四个指令添加八对128位数字

vpaddq
vpaddq
vpcmpuq
vpsubq

使用标量寄存器,需要16条指令才能添加8对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

Answer 2

从上面的评论中移开

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

对于简单的添加任务,使用x86 EFLAGS/RFLAGS'寄存器的进位标志从最低的"肢体"向上传播添加的进位(使用GMP术语),并在任意数量的肢体上循环,这是微不足道的.在数组中.

相反,SSE/AVX寄存器的通道没有进位标志,这意味着必须以不同的方式检测溢出,包括比较以检测环绕​​,这在计算上更加强烈.此外,如果在一个分支中检测到溢出时,它必须通过一个丑陋洗牌"向上"传播,然后相加,该相加可以引起另一个溢流和结转,高达N-1倍用于N-limb BIGNUM.然后,一旦总和带来超过128位/ 256位(或超过128位x#寄存器)的bignum,您无论如何都必须将它移动到数组.

因此,需要许多特殊情况代码,并且它不会更快(实际上,更慢),仅用于添加.想象一下乘法需要什么？或喘气,分裂？