我几乎完成了处理一些非常大的整数(大约 2 的 100,000,000 次方)的算法。由于该算法不是内存密集型的,因此需要在内存充足的 16 核服务器上编写几个小时的高度并行代码。我使用 .NET 4 中的 BigInteger 类。
算法的细节并不重要,但就上下文而言,以下是对这些整数执行的操作的相当详尽的列表以及算法的一些显着特征:
- 加法/减法。
- 大数乘以小数。
- 大数除以小数(例如 2)。
- 基数 2 日志。
- 基础 2 电源。
- 比较两个或多个大数(最小/最大)。
- 没有任何质数的参与。
- 该算法经过专门设计,不占用内存,因为内存访问对性能的影响大于某些智能即时计算的性能影响。然而,如果内存访问得到改善,该算法可以合理地受益。
我已经尽可能地优化了代码,现在分析仅显示两个瓶颈:
- 计算如此大的数字以 2 为底的 Log。
- 检查这些数字中二进制数字的预定义模式。这是因为访问 BigInteger 基础数据的唯一方法是首先使用 ToByteArray 而不是就地操作。此外,对字节大小的块进行操作对性能没有帮助。
考虑到内存访问和日志操作,我开始考虑 GPU 以及是否可以有效地卸载一些工作。我对 GPU 知之甚少,只知道它们针对浮点运算进行了优化。
我的问题是,使用 GPU .NET 这样的库,如何在 GPU 上处理如此大的数字?我可以以某种方式利用浮点优化来计算如此大的数字的 Log 吗?
寻找制定策略的起点。
我正在寻找 C# 中的 GPU 工作,并正在考虑 Tidepowerd.com GPU.NET 和 CUDAfy.NET。当我上次检查时,Nvidia 特定的和 CUDAfy 都不支持单声道。但它们都允许在 GPU 上运行的 C# 中看起来相当正常的代码。
另外,您是否考虑过使用 3d 方库?有几个非常好的 BigInteger 库,也是开源的。 GMP很好而且免费;http://gmplib.org/ http://gmplib.org/,至少有一个 C# 包装器(我对此没有经验)http://www.emilstefanov.net/Projects/GnuMpDotNet/ 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
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)