使用GPU加速BigInteger计算

2024-01-22

我几乎完成了处理一些非常大的整数(大约 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(使用前将#替换为@)

使用GPU加速BigInteger计算 的相关文章

随机推荐

  • Android - 用 @IntDef 替换参数化枚举

    如何避免参数化枚举与 IntDef 我想保留一些与每个枚举 类型关联的静态详细信息 例如关联的 URl 关联的可绘制对象等 TYPE ONE R string res Urls URL1 TYPE TWO R string res Urls
  • 如何防止Xcode每次都重建项目

    我有一个 Mac OS X 应用程序 由一个主要目标和一个依赖框架组成 自从在我的 Mac OS X 应用程序上启用代码签名后 我注意到每次运行 Xcode 时都会重建主要目标 即使我没有触及任何代码行 这是一个问题 因为依赖框架需要知道主
  • 如何更改多处理模块使用的序列化方法?

    如何更改Python使用的序列化方法multiprocessing图书馆 特别是 默认的序列化方法使用pickle具有该版本 Python 的默认 pickle 协议版本的库 默认的pickle协议在Python 2 7中是版本2 在Pyt
  • 为什么是24位寄存器?

    在我的工作中 我处理不同的微控制器 微处理器和 DSP 处理器 其中许多都有 24 位寄存器和计数器 我知道如何使用它们 这不是我的问题 我的问题是为什么他们有 24 位寄存器 为什么不把它做成32位的呢 据我所知 这不是大小的问题 因为寄
  • 根据另一个参考数组从一个数组中选择密切匹配

    我有一个数组A和一个参考数组B 尺寸为A至少和B e g A 2 100 300 793 1300 1500 1810 2400 B 4 305 789 1234 1890 B实际上是指定时间信号中峰值的位置 并且A包含稍后时间的峰值位置
  • 序列化代码示例中的无限循环

    看看下面的代码here https web archive org web 20151025040111 http blogs msdn com 80 b sowmy archive 2006 03 26 561188 aspx 它是关于在
  • 如何使用 Jest 运行单个测试?

    我在文件 fix order test js 中有一个 适用于嵌套子项 的测试 运行以下命令会运行文件中的所有测试 jest fix order test 如何只运行一个测试 下面的代码不起作用 因为它搜索指定的正则表达式的文件 jest
  • Windows:检测右 alt 是否在当前布局中生成 Ctrl+Alt (AltGr)

    Windows 中的某些键盘布局 例如 US QWERTY 将右 Alt 视为常规 Alt 键 而其他键盘布局 例如 US International 将其视为 AltGr 并在按下时同时生成 Ctrl 和 Alt 键 Microsoft
  • 通过身份验证从 https 下载文件

    我有一个 Python 2 6 脚本 可以从 Web 服务器下载文件 我希望这个脚本传递用户名和密码 用于在获取文件之前进行身份验证 并且我将它们作为 url 的一部分传递 如下所示 import urllib2 response urll
  • android 中如何导航到另一个页面?

    我是安卓新手 请告诉我如何在 android 中导航到新页面 提前致谢 编辑 如何从现有活动开始新活动 在 Android 中 导航到另一个页面意味着您必须启动另一个 Activity 要开始新活动 请使用此 Intent intent n
  • 使用 postgres 表序列而不是共享 hibernate_sequence

    当我对表执行任何操作时 它总是显示错误 Hibernate select nextval hibernate sequence 2019 07 20 16 15 44 877 WARN 58376 nio 9000 exec 1 o h e
  • 按修改日期而不是发布日期对 Jekyll 帖子进行排序?

    对于经常更新帖子的人来说 有必要根据帖子从新到旧进行排序最后修改日期而不是 Jekyll 默认按发布日期排序 似乎没有简单的方法可以实现这一点 我已经阅读并测试了几乎所有的方法 这是有效的 部分符合预期 用过这个宝石https github
  • 在linux中安装jdk 1.7时出错[关闭]

    Closed 这个问题是无关 help closed questions 目前不接受答案 当我使用以下命令在 Oracle Linux 中安装 jdk 1 7 时 rpm ivh jdk 7u9 linux i586 rpm 但是我收到以下
  • 使用正则表达式捕获两个单词之间的文本

    我正在尝试使用 CSharp 中的正则表达式获取两个关键字之间的文本 虽然我已经找到了一个具有相同标题的主题 但该主题是关于查找方括号之间的文本 这相当容易 因为您可以使用
  • 为什么 SQLAlchemy count() 比原始查询慢得多?

    我正在使用 SQLAlchemy 和 MySQL 数据库 我想计算表中的行数 大约 300k SQL炼金术count http docs sqlalchemy org ru latest orm query html sqlalchemy
  • 警告:在此函数中使用未初始化的“”[-Wuninitialized]

    以下程序编译时没有警告 O0 include
  • GitHub Action:如何从表达式求值中获取值并将其分配给环境变量

    环境表达式通常直接赋值 如下例所示 name set up env var env TAG v1 2 3 run echo TAG 但是如何从 shell 脚本评估中获取值呢 例如 在我的终端中 我可以通过以下方式获取当前标签git des
  • CMake rpm 在 /etc/init.d 中安装文件

    我想安装一个文件 etc init d 目录 我已经写了代码 INSTALL FILES CMAKE SOURCE DIR app script appd DESTINATION etc init d appd 但是当我使用 cmake 运
  • Facebook SDK 4.5 iOS 9

    我遇到了新 FBSDK 的问题 每当我尝试调用登录方法 logInWithReadPermissions 时 我都会收到以下错误消息 错误 canOpenUrl url fbauth2 失败错误 null 我的配置 plist 文件遵循 i
  • 使用GPU加速BigInteger计算

    我几乎完成了处理一些非常大的整数 大约 2 的 100 000 000 次方 的算法 由于该算法不是内存密集型的 因此需要在内存充足的 16 核服务器上编写几个小时的高度并行代码 我使用 NET 4 中的 BigInteger 类 算法的细