24

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

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

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

  • SSE 的思想是 SIMD（同一指令，多数据），因此它提供了 2 或 4 个独立操作的指令。另一方面，我想要一个 128 位整数加法（128 位输入和输出）。这似乎不存在。（然而？也许在 AVX2 中？）

  • 整数加法和减法既不处理输入也不处理输出进位。所以手工操作非常麻烦（因此很慢）。

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

4

1 回答 1

32

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

但在我继续之前，是时候介绍一些背景术语了：

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


全字算术：

这是使用 32 位或 64 位整数数组以基数 2 32或 2 64存储数字的标准表示。许多 bignum 库和应用程序（包括 GMP）使用这种表示。

在全字表示中，每个整数都有唯一的表示。比较之类的操作很简单。但是像加法这样的东西比较困难，因为需要进行传播。

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


部分字算术

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

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

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

全字算术问题：

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

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

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

此外，x86/x64为 bignums提供了大量专门的标量指令：

  • 带进位：adc, adcx, adox.
  • 双字乘法：单操作数mul和mulx。

鉴于此，对于 SIMD 来说，bignum-add 和 bignum-multiply 都很难在 x64 上击败标量。绝对不是 SSE 或 AVX。

使用 AVX2，如果您重新排列数据以在 4 个 SIMD 通道中的每个通道中启用相同长度的 4 个不同（和独立）乘法的“垂直矢量化”，那么 SIMD 几乎可以与标量 bignum-multiply 竞争。

假设垂直矢量化，AVX512 将再次支持 SIMD。

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


部分词算术的向量化

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

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

因为（通常）不需要执行进位，所以对部分单词的 SIMD 加/减可以在垂直和水平向量化的 bignums 上同样有效地完成。

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

部分字算术的乘法更复杂，因为您需要处理指甲位。但是与 add/sub 一样，仍然可以在水平向量化的 bignums 上有效地完成它。

AVX512-IFMA（与 Ca​​nnonlake 处理器一起提供）将具有提供 52 x 52 位乘法的全部 104 位的指令（可能使用 FPU 硬件）。这对于每个字使用 52 位的部分字表示非常有效。


使用 FFT 的大乘法

对于非常大的 bignum，使用快速傅里叶变换 (FFT)最有效地完成乘法。

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

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

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

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

披露：

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

于 2012-01-15T02:05:51.577 回答