哪种处理器架构最适合大整数算术？

Question

如果我要编写用于大整数计算的汇编代码（例如，素因子分解，模数计算等），重点关注速度，哪种架构最适合这种：x86（-64），ARM，PowerPC，MIPS或其他？

Answer 1

如果您使用少量可变大小的数字，我认为POWER 6最适合您的需求（虽然我没有使用这种架构）因为它提供高IPC和非常高的频率（高达5GHz）。

它使用大量固定大小的数字，x86-64将是最佳选择，因为它具有可处理64位数字的SIMD操作，并且您可以使用这些操作来加速多个数字的长算术运算。您可能需要一个支持SSE 4.2的CPU（Intel Nehalem / Westmere / Sandy Bridge，或即将推出的AMD Bulldozer），因为64位比较指令PCMPGTQ仅在SSE 4.2中添加

此外，these GMP benchmark results可能对你有意思

Answer 2

IMO没有什么胜过x86-64，因为没有人关心更高精度的算术

许多RISC架构（如MIPS，DEC Alpha或RISC-V）没有标志寄存器，因此您需要单独的指令来获取进位。因此，他们是糟糕的选择，并立即消除。例如，你需要在MIPS中做a += b

addu aLow, aLow, bLow     # aLow += bLow
sltu tmp, aLow, bLow      # carry: tmp = (aLow < bLow)
addu aHigh, aHigh, bHigh  # aHigh += bHigh
addu aHigh, aHigh, tmp    # aHigh += carry

使用进位标志，您只需要2条指令：add aLow, bLow; adc aHigh, bHigh

MIPS设计师could have done it better，但他们没有

较高的时钟有助于Marco van de Voort said，但这些架构的时钟速度比同等的x86快50％-100％。他说的剩下的事情是不正确的。值得注意的是，任意精度数学都不是平凡的并行化

• 超标量（更多ALU）对依赖链没有多大帮助，这会阻止指令并行运行
• 出于同样的原因，多个核和/或多个插座也相对无用。
• SIMD也通常不会帮助‡，因为它用于处理多个单独的数据而不是一个大的大整数。你没有任何办法将携带从下肢传播到下一个。看到 Is it possible to use SSE and SSE2 to make a 128-bit wide integer? Is there hardware support for 128bit integers in modern processors? Is __int128_t arithmetic emulated by GCC, even with SSE?

简而言之：你真的想要并行计算进位非常困难

---

在x86世界中，您从一开始就拥有进位标志。但后来英特尔推出了带有新指令ADX instruction set和MULX的ADOX, ADCX，以进一步加速大整数运算。英特尔的论文New Instructions Supporting Large Integer Arithmetic on Intel Architecture Processors解释了他们如何提供帮助

但不仅仅是ADX让x86变得更快。正如我之前提到的（‡）SIMD并没有真正帮助，但是现在x86上的东西可能会有所不同。我们在x86中有很长的向量（AVX2为256位，AVX512为512位，未来可能更长）所以如果使用各种技巧，比如使用部分字算法来延迟进位传播，或者以奇怪的方式排列单词（如llhhllhhllhhllhh）而不是像普通大整数算术（llllllllhhhhhhhh）那样的线性，那么SIMD可能比标量运算更快。有关更多信息，请阅读

• Can long integer routines benefit from SSE?
• practical BigNum AVX/SSE possible?
• Kogge-Stone Vector Addition

当然，AVX512只有在数量非常大的情况下才有用。否则，对于512位数字，您可以使用标量代码获得更好的结果

目前没有其他架构的SIMD寄存器长于128位，因此即使您可以在它们上使用SIMD，计算进位的成本也远远超过并行加法的成本。这也是x86打败它们的原因