使用GPU加速BigInteger计算

我几乎完成了一个处理一些非常大的整数（大约2次提高到100,000,000次）的算法。由于该算法不是内存密集型的，因此在16核心服务器上需要花费几个小时的高度并行代码才能获得足够的内存。我利用BigInteger类在.NET 4使用GPU加速BigInteger计算

算法的细节并不重要，但对于背景下，以下是对这些整数和算法的一些显着特征进行操作的一个非常详尽的列表：

加法/减法。
大数乘以小数。
大数除以非常小的数字（例如2）。
Base 2 Log。
基地2电源。
比较两个或更多的大数字（最小/最大）。
不涉及素数。
该算法的具体设计不是内存密集型，因为内存访问的性能高于一些智能即时计算。尽管如此，如果内存访问得到改善，算法可以合理地受益。

我已经优化了代码尽可能现在分析仅示出了两个瓶颈：

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

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

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

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

来源

2012-08-17 Raheel Khan

您是否考虑过使用CUDAfy.NET？ http://cudafy.codeplex.com/（请注意，这是NVIDIA特定的，因此可能对您无用） – 2012-08-17 07:12:26

我正在四处寻找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类是不可变的，根据我的经验，这是不方便的。如果你的尺寸有两个整数（大约100MB），那么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

来源

2012-08-17 07:49:16 IvoTops

谢谢。下载三个包括你建议的库后，我似乎没有找到任何地方的日志功能。这是有意而且难以实施的吗？ – 2012-08-17 09:34:08

@RaheelKhan你需要一个浮点记录还是最高位置的位？ – harold 2012-08-17 10:42:07

我需要两个都取决于情况。无论如何BigInteger最高位设置是微不足道的。浮点花费我太多时间。 – 2012-08-19 18:42:36

如果有人发现它有帮助，这里是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-04 17:16:19

谢谢。非常古老的问题，但我仍然想回去做一个性能比较。 – 2018-01-17 14:07:22

使用GPU加速BigInteger计算

回答

相关问题