长整数例程可以从SSE中受益吗？

Question

我还在研究C++中任意长整数的例程.到目前为止,我已经为64位Intel CPU实现了加/减和乘法.

一切正常,但我想知道我是否可以通过使用SSE来加快速度.我浏览了SSE文档和处理器指令列表,但我找不到任何我认为可以使用的内容,原因如下:

• SSE有一些整数指令,但大多数指令处理浮点.看起来它不是设计用于整数(例如,是否有较小的整数比较？)

• SSE的想法是SIMD(相同的指令,多个数据),因此它提供了2或4个独立操作的指令.另一方面,我希望有一个像128位整数加(128位输入和输出)的东西.这似乎不存在.(但是？在AVX2中可能？)

• 整数加法和减法既不处理输入也不处理输出.因此,手动操作非常麻烦(因而也很慢).

我的问题是:我的评估是正确的还是有什么我忽略的？长整数例程可以从SSE中受益吗？特别是,它们可以帮助我编写更快的添加,子或mul例程吗？

Answer 1

在过去,这个问题的答案是坚实的,"不".但截至2017年,情况正在发生变化.

但在我继续之前,有时间为一些背景术语:

1. 全字算术
2. 部分字算术

全字算术:

这是标准表示,其中使用32位或64位整数数组将数字存储在base 2 ³²或2 ^64中.许多bignum库和应用程序(包括GMP)都使用此表示形式.

在全字表示中,每个整数都具有唯一的表示.比较等操作很简单.但是由于需要进行传播,因此添加之类的东西更加困难.

正是这种进位传播使得bignum算术几乎不可能进行矢量化.

部分字算术

这是一种较少使用的表示,其中数字使用小于硬件字大小的基数.例如,在每个64位字中只放置60位.或者使用1,000,000,00032位字大小的基数进行十进制算术运算.

GMP的作者称之为"钉子",其中"钉子"是该词的未使用部分.

过去,部分字算法的使用主要限于在非二进制基础上工作的应用程序.但是现在,它变得越来越重要,因为它允许延迟传输传播.

全字算术的问题:

向量化全字算术历来是一个失败的原因:

1. SSE/AVX2不支持进位传播.
2. SSE/AVX2没有128位的add/sub.
3. SSE/AVX2没有64 x 64位整数乘法.*

*AVX512-DQ增加了一个64x64位下半部分.但仍然没有上半部分指令.

此外,x86/x64有很多专门用于bignums的标量指令:

• 添加与-进:adc,adcx,adox.
• 双字乘法:单操作数mul和mulx.

鉴于此,SIMD在x64上难以击败标量,因此bignum-add和bignum-multiply都很难.绝对不是SSE或AVX.

对于AVX2,如果重新排列数据以使4个SIMD通道中每个相同长度的4个不同(和独立)乘法的"垂直矢量化",SIMD几乎与标量bignum-multiply竞争.

假设垂直矢量化,AVX512将更多地支持SIMD.

但是在大多数情况下,bignums的"水平矢量化"在很大程度上仍然是一个失败的原因,除非你有很多(相同大小),并且可以承担转置它们以使它们"垂直"的成本.

偏序算术的矢量化

使用部分字算法,额外的"钉子"位使您可以延迟进位传播.

所以只要你没有溢出这个词,SIMD add/sub就可以直接完成.在许多实现中,部分字表示使用有符号整数来允许单词变为负数.

因为(通常)不需要执行进位,所以可以在垂直和水平矢量化的bignums上同等有效地完成部分单词的SIMD加/减.

在水平矢量化的bignums上进行仍然很便宜,因为你只是将钉子移到下一个车道上.除非您需要对两个几乎相同的数字进行比较,否则通常不需要完全清除指甲位并获得唯一表示的完整进位.

由于需要处理指甲位,因此乘法对于部分字算法更复杂.但是与add/sub一样,它仍然可以在水平矢量化的bignums上有效地完成.

AVX512-IFMA(配备Cannonlake处理器)将具有指令,可提供52 x 52位乘法的全部104位(可能使用FPU硬件).对于每个字使用52位的部分字表示,这将非常有效.

使用FFT的大型乘法

对于非常大的bignums,使用快速傅里叶变换(FFT)可以最有效地完成乘法.

FFT完全可矢量化,因为它们在独立的doubles 上工作.这是可能的,因为从根本上说,FFT使用的表示是 部分单词表示.

总而言之,可以对bignum算术进行矢量化.但必须做出牺牲.

如果您希望SSE/AVX能够在不对表示和/或数据布局进行基本更改的情况下加速某些现有的bignum代码,则不太可能发生这种情况.

但是,bignum算术可以进行矢量化.

披露:

我是y- cruncher 的作者,它有很多大量的arihmetic.