使用GPU加速BigInteger计算

Question

我快要完成一个处理非常大的整数（约为2的100,000,000次方）的算法。这需要在一个16核服务器上运行几个小时的高度并行代码，由于该算法不需要太多内存，因此内存充足。我在.NET 4中使用了BigInteger类。

算法的具体细节并不重要，但为了提供背景，以下是对这些整数执行的操作以及算法的一些显着特点的相当详尽的列表：

• 加法/减法。
• 将大数乘以小数。
• 用非常小的数字（例如2）除以大数。
• 基于2的对数。
• 基于2的幂。
• 比较两个或多个大数（最小值/最大值）。
• 完全没有涉及质数。
• 该算法专门设计为不占用太多内存，因为内存访问的性能损失超过了某些智能即时计算的性能损失。然而，如果内存访问得到改善，算法可以受益。

我已经尽可能地优化了代码，现在分析显示只有两个瓶颈：

• 计算如此大的数字的基于2的对数。
• 检查这些数字中二进制位的预定义模式。这是因为访问BigInteger底层数据的唯一方法是首先使用ToByteArray而不是原地操作。此外，操作字节大小的块并不能提高性能。

考虑到内存访问和对数运算，我开始思考GPU以及是否可以有效地卸载一些工作。我对GPU知之甚少，除了它们针对浮点运算进行了优化。

我的问题是，使用类似GPU .NET的库，我如何在GPU上处理如此大的数字？我是否可以利用浮点优化来计算这么大的数字的对数？

寻找一个起点来制定策略。

- Raheel Khan

---

你考虑过使用CUDAfy.NET吗？http://cudafy.codeplex.com/（请注意，这是NVIDIA特定的，所以可能对你没有用） - Tom Chantler

Answer 1

我正在寻找使用C#进行GPU工作的解决方案，正在考虑Tidepowerd.com GPU.NET和CUDAfy.NET。两者都是Nvidia特定的，而且在我上次检查时CUDAfy尚未支持mono。但它们都允许在C#中编写看起来比较正常的代码，并在GPU上运行。

此外，您是否考虑使用第三方库？有几个非常好的BigInteger库，也是开源的。GMP非常好且免费；http://gmplib.org/，至少有一个C#包装器（我没有经验）http://www.emilstefanov.net/Projects/GnuMpDotNet/ .NET中的BigInteger类是不可变的，根据我的经验，这并不方便。如果您有两个大小为100MB的int，则Add操作会导致第三个100MB BigInt。如果修改其中一个原始值，则可以更快地完成操作。

C = A + B means allocating 100MB for C (this is what BigInt does)
A = A + B means you no longer have the original A, but a much faster calculation

- IvoTops

---

谢谢。在下载了包括您建议的三个库之后，我似乎找不到任何日志功能。这是有意为之的吗？还是很难实现？ - Raheel Khan

@RaheelKhan，您需要浮点对数还是最高位的位置？ - harold

根据情况，我需要两者。无论如何，使用BigInteger设置最高位是微不足道的。浮点数让我花费了太多时间。 - Raheel Khan

有一个基于GNU MP的库，用于处理非常大的浮点数，其中包含log()函数。请参见http://www.mpfr.org/。 - IvoTops

Answer 2

如果有人觉得有用的话，这里是一个针对BigInteger的Log Base 2实现，比使用内置函数更快。

private static BigInteger LogBase2(BigInteger num) {
    if (num <= Zero)
        return MinusOne; //does not support negative values.
    BigInteger i = Zero;
    while (!(num >>= 1).IsZero)
        i++;
    return i;
}

- MathuSum Mut

---

谢谢。这是一个非常老的问题，但我仍然想回去做性能比较。 - Raheel Khan