使用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计算 的相关文章

  • 使用预编译头减少 clang 编译时间

    我正在开发一个数据库项目 该项目将查询 以某种高级语言表示 编译为 C 代码 这段代码由数据库编译并执行 那部分工作得很好 现在 我正在尝试减少 C 查询代码的编译时间 我想知道是否可以使用预编译头来提高性能 该查询被转换为一个名为 Que
  • 宏可以按参数数量重载吗?

    如何this https stackoverflow com q 9183993 153285工作 如何实现 C99 C 11 可变参数宏以仅根据为其提供多少个参数来扩展到不同的事物 编辑 请参阅末尾以获得现成的解决方案 要获得重载的宏 首
  • 将 Python 控制台集成到 GUI C++ 应用程序中

    I m going to add a python console widget into a C GUI below some other controls 许多类将暴露给 python 代码 包括一些对 GUI 的访问 也许我会考虑 P
  • 在不使用 ncurses 的情况下用 C/C++ 编写“真正的”交互式终端程序,例如 vim、htop...

    不 我不想使用ncurses 因为我想了解如何 终端可以工作 并且我自己编程也很有趣 没有 必须是可移植的 它必须只能在基于 linux xterm 的终端仿真器上工作 我想做的是编写一个交互式终端应用程序 例如 htop 和 vim 我的
  • StreamReader,C#,peek

    我有一个 StreamReader 它偶尔会检查它是否有更多内容可以从简单的文本文件中读取 它使用 peek 属性 问题是 当我使用 peek 时 位置发生了变化 尽管不应该发生 FileStream m fsReader new File
  • 求一个数的因数。无法得到准确的结果

    有人可以帮助纠正我的算法吗 我已经对几个数字进行了测试 但它没有输出完整的因式分解 对于具有大量因子的数字 它完全失败 int num 20 for int i 2 i lt num i if num i 0 cout lt lt i lt
  • 在 C++ 中使用表达式模板进行符号微分

    如何在 C 中使用表达式模板实现符号微分 一般来说 您需要一种表示符号的方法 即编码的表达式模板 例如3 x x 42 以及一个可以计算导数的元函数 希望您对 C 中的元编程足够熟悉 知道这意味着什么和需要什么 但可以给您一个想法 This
  • WinForms - 表单大小错误

    我们有以下代码 private void MainForm Shown object sender EventArgs e RepositionForm private void RepositionForm Rectangle rect
  • C for 循环索引:新 CPU 中的前向索引更快吗?

    在我订阅的邮件列表上 两位知识渊博的 IMO 程序员正在讨论一些优化的代码 并说了以下内容 在 5 8 年前发布的 CPU 上 向后迭代 for 循环稍微快一些 e g for int i x 1 i gt 0 i 因为比较i归零比将其与其
  • 如何强制用户仅使用“new”创建从我派生的类的对象?

    为了实现引用计数 我们使用IUnknown http msdn microsoft com en us library ms680509 VS 85 aspx类接口和智能指针模板类 该接口具有所有引用计数方法的实现 包括Release vo
  • DotNET 应用程序中的 GDI 句柄

    我的纯 DotNET 库作为非托管桌面应用程序中的插件运行 我收到了稳定的 虽然低 崩溃报告流 这些报告似乎表明 GDI 句柄存在问题 错误消息中的字体等 恢复为系统字体 各种控件的显示崩溃 不久后发生大规模崩溃 我的窗体几乎没有控件 但我
  • 按值返回的函数的返回语句中的初始化

    我的问题源于深入研究std move in return语句 例如以下示例 struct A A std cout lt lt Constructed lt lt this lt lt std endl A A noexcept std c
  • 只读有运行时开销吗?

    出于某种原因 我一直认为readonly字段有与其相关的开销 我认为这是 CLR 跟踪是否存在readonly字段是否已初始化 这里的开销是一些额外的内存使用量 用于跟踪状态以及分配值时的检查 也许我这么认为是因为我不知道readonly字
  • 数组与映射的性能

    我必须循环一个大数组中的元素子集 其中每个元素都指向另一个元素 问题来自于检测大图中的连接组件 我的算法如下 1 考虑第一个元素 2 将下一个元素视为前一个元素所指向的元素 3 循环直到没有发现新元素 4 考虑1 3中尚未考虑的下一个元素
  • 非静态类中的静态方法和静态类中的静态方法有什么区别?

    我有两个班级A级和B级 static class ClassA static string SomeMethod return I am a Static Method class ClassB static string SomeMeth
  • 从 exit() 和 fork() 返回的结果奇怪地发生了位移

    我有一个 C 代码 有时会自行分叉 每个分叉都会执行一些操作 然后返回一个错误代码 目前 每个子进程返回其 ID 0 n void other int numero exit numero int main for int i 0 i lt
  • 如何使用 xamarin 表单提示用户进行地理定位

    我正在 Xamarin Forms 应用程序中开发一个应用程序 需要请求地理位置权限 如果获得许可 它需要从设备获取地理位置数据 然后将地理位置坐标放入 Forecast io URL 我正在使用 James 的 Geolocator 插件
  • OpenGL 计算着色器调用

    我有一个与新计算着色器相关的问题 我目前正在研究粒子系统 我将所有粒子存储在着色器存储缓冲区中 以便在计算着色器中访问它们 然后我派遣一个一维工作组 define WORK GROUP SIZE 128 shaderManager gt u
  • 从 STL 列表中删除项目

    我想创建一个函数 如果符合特定条件 则将项目从一个 STL 列表移动到另一个列表 这段代码不是这样做的方法 迭代器很可能会被擦除 函数失效并导致问题 for std list
  • 如何在用户空间程序中使用内核 libcrc32c (或相同的函数)?

    我想在我自己的用户空间程序中进行一些 CRC 检查 我发现内核加密库已经在系统中 并且支持 SSE4 2 我尝试直接 include

随机推荐

  • 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 类 算法的细