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

Question

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

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

SSE 有一些整数指令，但大多数指令处理浮点数。它看起来不像是为与整数一起使用而设计的(例如，是否有整数比较less？)

SSE的思想是SIMD(同一个指令，多个数据)，所以它提供了2个或4个独立操作的指令。另一方面，我想要一些类似 128 位整数加法的东西(128 位输入和输出)。这似乎不存在。 (然而？在 AVX2 中？)

整数加法和减法既不处理输入也不处理输出进位。所以手工完成非常麻烦(因此很慢)。

我的问题是:我的评估是正确的还是我忽略了什么？长整数例程可以从 SSE 中受益吗？特别是，他们可以帮助我编写更快的 add、sub 或 mul 例程吗？

Answer 1

过去，这个问题的答案是肯定的，“不”。但到了 2017 年，情况正在发生变化。

但在我继续之前，是时候了解一些背景术语了:

全字算术

部分字算术

全字算术:

这是使用 32 位或 64 位整数数组以 232 或 264 为基数存储数字的标准表示形式。
许多 bignum 库和应用程序(包括 GMP)使用这种表示。

在全字表示中，每个整数都有唯一的表示。比较之类的操作很容易。但是由于需要进位传播，诸如加法之类的东西更加困难。

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

部分字算术

这是一种较少使用的表示，其中数字使用的基数小于硬件字长。例如，在每个 64 位字中只放置 60 位。或使用基础 1,000,000,000具有用于十进制算术的 32 位字长。

GMP 的作者将其称为“钉子”，其中“钉子”是该词未使用的部分。

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

全字算术问题:

向量化全字算术在历史上一直是一个失败的原因:

SSE/AVX2 不支持进位传播。

SSE/AVX2 没有 128 位加/减。

SSE/AVX2 没有 64 x 64 位整数乘法。*

*AVX512-DQ 添加了一个下半部分 64x64 位乘法。但是仍然没有上半部分的指令。

此外，x86/x64 有大量专门用于 bignum 的标量指令:

带进位:adc , adcx , adox .

双字乘法:单操作数 mul和 mulx .

有鉴于此，对于 SIMD 而言，bignum-add 和 bignum-multiply 都难以在 x64 上击败标量。绝对不是 SSE 或 AVX。

使用 AVX2，如果您重新排列数据以在 4 个 SIMD channel 中的每一个中启用相同长度的 4 个不同(和独立)乘法的“垂直向量化”，则 SIMD 几乎可以与标量 bignum-multiply 竞争。

假设垂直矢量化，AVX512 将再次倾向于 SIMD。

但在大多数情况下，bignum 的“水平向量化”在很大程度上仍然是一个失败的原因，除非你有很多(相同大小)并且能够负担得起将它们转置以使其“垂直”的成本。

部分词算术的向量化

使用部分字算法，额外的“钉子”位使您能够延迟进位传播。

所以只要你不溢出这个词，SIMD加/减就可以直接完成。在许多实现中，部分词表示使用有符号整数来允许词变为负数。

因为(通常)不需要执行结转，所以可以在垂直和水平向量化的 bignum 上同样有效地对部分字进行 SIMD 加/减。

在水平矢量化的 bignum 上执行仍然很便宜，因为您只需将钉子移到下一条车道上即可。除非您需要比较两个几乎相同的数字，否则通常不需要完全清除钉子并获得唯一表示的完整执行。

部分字算术的乘法更复杂，因为您需要处理钉子。但是与添加/订阅一样，仍然可以在水平矢量化的 bignum 上有效地执行此操作。

AVX512-IFMA(与 Ca​​nnonlake 处理器一起提供)将具有提供 52 x 52 位乘法的完整 104 位的指令(大概使用 FPU 硬件)。这对于使用每字 52 位的部分字表示非常有效。

使用 FFT 的大乘法

对于非常大的 bignum，使用 Fast-Fourier Transforms (FFTs) 最有效地完成乘法。 .

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

总而言之，bignum 算法的矢量化是可能的。但必须做出牺牲。

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

但是尽管如此，bignum 算术还是可以向量化的。

披露:

我是 y-cruncher 的作者它做了大量的大数运算。