在 GPU 上运行密集数学计算的最佳方式

Question

我正在做一些学术/教育研究（主题与布尔逻辑及其扩展有关），并且有一个数学算法，我想验证一些大的数字集，更具体地说，从 1 到 2 的每个整数^63。为了验证这一点，我必须对每个数字运行算法，对输出求和并将它们与一些已知的预定义值进行比较。所得总和不会大于数字本身的数量。

我有一个 C++ 主机程序和一个 OpenCL 内核来执行实际计算，并且在我租用了几个小时的按需 Pod 上的 NVIDIA RTX 3060 GPU 上，它对于 1 到 2^32 的值运行良好 - 计算使用所有 GPU 核心最多需要 10-20 秒。

但是，当然，当尝试对 2^63 数字使用相同的方法时，运行时间呈指数级增长，并且在我的有生之年不可能得到结果。

我现在正在寻找一种并行化或优化此任务的方法，但我有点卡住了：

1. 我应该使用哪些应用程序级工具来实现给定 OpenCL 内核的并行化？
2. 是否有在线服务可以提供 UI 或 API，以便以合理的价格在大型计算设备集群上运行此类程序？我知道一些大学有这样的集群，但似乎大多数都是私人解决方案，不向公众开放。

我正在寻找一种方法，将 2^63 整数的结果计算速度加快到最多几周的常数计算。

该算法本身是一种暴力算法，最坏情况下的时间复杂度为 O(n^2)，其中 n 是由其测试的单个整数的位数，并且 这无法改进或更改，它是故意对大量数字进行暴力破解，现在我的任务是证明它的正确性。内核本身包含尽可能多的优化，如果某些条件匹配，其中一些优化也会提前退出，从而尽可能避免计算量大的操作。

预先感谢您的帮助。

Answer 1

我建议您粗略估计执行测试所需的操作数量。

n = max no. of bits of argument

Assume Ops to test one integer = c*n^2 for some constant c

TotalOps = c*sum_{i=1 to 63} (2^(i-1))(i^2) approx. = c*1.83e+22

假设您可以在单个 GPU 上每秒执行 10 万亿次操作。那么需要 c*1.83e+9 GPU 秒，或者大约 58c GPU 年。除非你对此有相当大的预算，并且 c 非常小，否则这是不可能的。