使用GPU加速BigInteger计算

Question

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

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

• 加法/减法.
• 大数乘以小数.
• 通过非常小的数字划分大数(例如2).
• 基地2日志.
• 基地2力量.
• 两个或多个大数字的比较(最小/最大).
• 没有涉及素数的任何参与.
• 该算法专门设计为不占用大量内存,因为内存访问的性能损失超过了一些智能的即时计算.然而,如果要改进内存访问,算法可以合理地受益.

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

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

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

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

寻找形成战略的起点.

Answer 1

我正在寻找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),则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