10

我几乎完成了一个处理一些非常大的整数的算法（大约 2 的数量级为 100,000,000 次方）。这需要在具有足够内存的 16 核服务器上花费几个小时的高度并行代码，因为该算法不是内存密集型的。我在 .NET 4 中使用 BigInteger 类。

该算法的细节并不重要，但对于上下文，以下是对这些整数执行的操作的详尽列表以及该算法的一些显着特征：

  • 加法/减法。
  • 大数乘以小数。
  • 大数除以非常小的数（例如 2）。
  • 基数 2 日志。
  • 基数 2 电源。
  • 两个或多个大数的比较（最小值/最大值）。
  • 没有任何素数的参与。
  • 该算法专门设计为不是内存密集型的，因为内存访问的性能影响超过了一些智能的即时计算。然而，如果要改进内存访问，该算法可以合理地受益。

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

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

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

我的问题是，使用 GPU .NET 之类的库，如何在 GPU 上处理如此大的数字？我可以以某种方式利用浮点优化来计算这么大的数字的 Log 吗？

寻找起点，形成战略。

4

2 回答 2

5

我正在四处寻找 C# 中的 GPU 工作，并正在考虑 Tidepowerd.com GPU.NET 和 CUDAfy.NET。我上次检查时，Nvidia 特定和 CUDAfy 都不（还）支持单声道。但它们都允许在 GPU 上运行的 C# 中看起来相当正常的代码。

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

.NET 中的 BigInteger 类是不可变的，根据我的经验，这并不方便。如果您有 2 个整数（大约 100MB），则添加操作会产生第三个 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
于 2012-08-17T07:49:16.913 回答
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;
}
于 2017-07-04T17:16:19.657 回答