用GPU加速BigInteger计算

Question

我几乎完成了一个处理一些非常大的整数的算法(大约是2阶到100,000,000幂)。这需要几个小时的高度并行的代码在一个16核心服务器上，有超过足够的内存，因为该算法不是内存密集型。我使用了BigInteger 4中的.NET类。

算法的细节并不重要，但对于上下文来说，下面是对这些整数执行的操作的非常详尽的列表，以及算法的一些显著特性：

• 加/减
• 大数乘小数。
• 将大数除以非常小的数(例如2)。
• 基地2日志。
• 基地2力量。
• 两个或两个以上大数的比较(最小/最大)。
• 与素数无关。
• 该算法是专门设计的，不需要内存密集型，因为内存访问的性能比一些智能的实时计算要好得多。然而，如果对内存访问进行改进，则该算法可以获得合理的效益。

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

• 计算这样大的数字的基数2日志。
• 检查这些数字中预定义的二进制数字模式。这是因为访问BigInteger底层数据的唯一方法是首先使用ToByteArray而不是就地操作。此外，在字节大小的块上操作无助于性能。

考虑到内存访问和日志操作，我开始考虑GPU以及是否能够有效地卸载一些工作。我对GPU知之甚少，只是它们是为浮点操作而优化的。

我的问题是，使用像GPU .NET这样的库，我如何在GPU上处理这么大的数字？我能否以某种方式利用浮点优化来计算如此大的数字的日志？

寻找一个起点来形成一个战略。

Answer 1

我四处寻找GPU在C#的工作，并正在考虑Tidepowerd.com，GPU.NET和CUDAfy.NET。当我上次检查时，Nvidia和CUDAfy都不支持mono。但是它们都允许在运行在GPU上的C#中有相当正常的代码。

另外，你考虑过使用3d派对图书馆吗？有几个非常好的BigInteger库，也是开源的。GMP非常好而且免费；http://gmplib.org/，至少有一个C#包装器(我没有经验) http://www.emilstefanov.net/Projects/GnuMpDotNet/。

BigInteger类在.NET中是不可变的，根据我的经验，这是不方便的。如果您有两个您大小的in (大约100 in)，那么Add操作将产生第三个100 in的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

Answer 2

如果有人认为它有帮助，下面是一个用于BigInteger的Log 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;
}