GoldbachGPU 技术总结

本文介绍了一个名为 GoldbachGPU 的开源框架，旨在利用消费级 GPU 硬件大规模验证哥德巴赫猜想（Goldbach's Conjecture）。该框架解决了以往基于 GPU 的验证方法中存在的显存（VRAM）瓶颈问题，成功在单张 NVIDIA RTX 3070（8 GB 显存）上完成了对 $10^{12}$ 范围内所有偶数的穷举验证，且未发现反例。

以下是该论文的详细技术总结：

1. 问题背景与挑战

• 哥德巴赫猜想：断言任何大于 2 的偶数都可以表示为两个素数之和。尽管已有理论进展（如陈氏定理），但该猜想仍未被证明。
• 计算验证的局限：
  • 传统的分布式计算（如 Oliveira e Silva 等人的工作）已验证至 $4 \times 10^{18}$，但依赖大规模集群。
  • 在消费级硬件（单卡 GPU）上，现有的 GPU 实现面临显存墙（VRAM Ceiling）。由于需要存储庞大的素数表，传统方法在 $10^{10}$ 到 $10^{11}$ 之间就会耗尽显存（例如，存储 $10^{11}$ 的素数表若使用字节数组需 95 GB，即使优化后也需数 GB）。
  • 缺乏能在单张消费级 GPU 上完成 $10^{11}$ 以上范围穷举验证的开源框架。

2. 核心方法论

GoldbachGPU 通过五种互补的验证工具构建了一个从 CPU 基准到任意精度验证的完整链条，核心创新在于**分段双重筛法（Segmented Double-Sieve）**架构。

2.1 内存优化：密集位打包（Dense Bitset）

• 技术细节：利用偶数（除 2 外）非素数的特性，仅存储奇数。将素数映射为位索引（Bit Index），使用 64 位字数组存储。
• 效果：相比传统的“每数一字节”存储，实现了 16 倍的内存压缩。
  • 在 $N=10^{11}$ 时，位打包仅需约 5.96 GB 显存（RTX 3070 为 8 GB），而字节数组需 95 GB。
  • 这解决了 $10^{11}$ 范围内的显存限制，但 $10^{12}$ 仍需更大显存。

2.2 架构突破：分段双重筛法（Segmented Double-Sieve）

这是该框架的核心贡献（goldbach_gpu3），彻底移除了显存上限：

• 循环反转（Loop Inversion）：借鉴 Oliveira e Silva 的策略，不再遍历偶数 $n$ 寻找素数 $p$，而是遍历候选素数 $p$，标记所有 $n = p + q$（其中 $q$ 为素数）的偶数。
• 分段处理：
  • 将验证范围划分为固定大小的段（例如 $10^7$ 个偶数）。
  • CPU 端：对当前段进行分段埃拉托斯特尼筛法，生成该段的素数位图（Bitset），大小固定（约 14 MB）。
  • GPU 端：将当前段的位图加载到显存中。对于段内的每个偶数 $n$，GPU 线程遍历小素数 $p$，计算 $q = n - p$，并判断 $q$ 是否为素数。
• 三阶段素数判定 Oracle：为了在不加载全量素数表的情况下判定 $q$ 的素性，设计了优先级链：
  1. 小素数表（$q \le 10^6$）：常驻显存的小素数位图（约 122 KB），$O(1)$ 查找。
  2. 当前段位图（$q \in [A, B]$）：当前加载的 14 MB 段位图，$O(1)$ 查找。
  3. 确定性 Miller-Rabin 测试（$10^6 < q < A$）：针对过渡区域使用 64 位确定性 Miller-Rabin 测试。
• 内存复杂度：无论总范围 $N$ 多大，显存占用恒定为 O(1)（每段约 14 MB），实现了 $O(N)$ 的时间复杂度。

2.3 辅助工具

• CPU 基准（cpu_goldbach）：作为真值参考（Ground Truth）。
• 单数检查器（single_check）：针对 64 位大整数，使用 GPU 并行进行 Miller-Rabin 测试。
• 任意精度检查器（big_check）：基于 GMP 库，支持验证高达 $10^{10000}$ 的整数。采用同步批处理策略防止线程跑飞，平衡负载。

3. 关键实验结果

实验环境：Intel i7-12700H CPU, NVIDIA RTX 3070 (8 GB VRAM)。

• 验证范围：
  • 在单张 RTX 3070 上完成了 $10^{12}$ 的穷举验证。
  • 耗时：约 41 分钟（2,457,040 ms）。
  • 结果：未发现任何反例。
• 性能对比：
  • 速度提升：在 $10^9$ 处，GPU 全局位图方案比 CPU 快 16 倍；在 $10^{10}$ 处快 12 倍。
  • 分段方案优势：虽然 goldbach_gpu3 因分段开销在低范围略慢于全局方案，但它是唯一能突破 $10^{11}$ 显存限制的方案。
• 最小哥德巴赫素数（$p_{min}$）验证：
  • 所有 $N \le 10^{12}$ 的偶数均在 Phase 1（GPU 快速路径）中找到解，零次触发 CPU 穷举回退。
  • 实证表明：对于 $N \le 10^{12}$，最小素数 $p_{min}(n) \le 2 \times 10^6$，这与理论预测的上界（$H(10^{12}) \approx 2000$）一致且留有巨大余量。
• 任意精度验证：
  • 成功验证了 $10^{10000}$ 量级的数字（耗时约 182 秒）。
  • 瓶颈在于 GMP 的 $O(d^3)$ 素性测试成本。
• 多卡扩展性：
  • 在 6 张 RTX 3090 上，$N=10^{10}$ 的并行效率达到 80.1%。
  • 在 H100 集群上，由于 CPU 分段筛法成为瓶颈，单卡性能提升不明显，但在 $N \ge 10^{11}$ 时开始显现优势。

4. 主要贡献

1. 消除显存天花板：通过分段双重筛法，实现了在单张消费级 GPU 上验证 $10^{12}$ 范围，突破了以往 $10^{11}$ 的硬件限制。
2. 内存效率优化：提出 16 倍压缩的密集位素数表示法，使 $10^{11}$ 范围内的 GPU 驻留成为可能。
3. 数学完备性保证：设计了严格的 CPU 回退机制（尽管实验中未触发），确保验证结果的数学正确性。
4. 任意精度扩展：结合 GMP 和 OpenMP 同步策略，将验证能力扩展至 $10^{10000}$。
5. 开源与可复现：所有代码开源，支持从消费级显卡到数据中心硬件的部署。

5. 意义与局限性

• 意义：
  • 证明了 GPU 验证哥德巴赫猜想的瓶颈是架构设计（如全量素数表存储）而非硬件本身。
  • 为个人研究者和小型实验室提供了低成本、高性能的验证工具，无需依赖超算集群。
  • 实证数据进一步支持了哥德巴赫猜想中“小素数解丰富”的统计特性。
• 局限性：
  • CPU 瓶颈：当前架构中，CPU 负责生成每段的素数表并传输给 GPU，导致 GPU 经常处于等待状态（Idle）。在 $N=10^{10}$ 时，GPU 计算时间仅占几百毫秒，大部分时间花在 CPU 筛法上。
  • 算法差距：目前的 GPU 实现仍包含逐数的素性查找和 Miller-Rabin 测试。相比之下，Oliveira e Silva 的 CPU 全量双重筛法使用位运算批量标记，复杂度为 $O(N \log \log N)$ 且常数极小。未来的方向是将这种位运算批量标记逻辑移植到 GPU 上。
  • 数据带宽限制：分段大小受限于主机内存带宽，过大的分段会导致 GPU 饥饿。

结论

GoldbachGPU 是一个里程碑式的框架，它通过创新的内存管理和分段策略，将哥德巴赫猜想的单卡验证范围从 $10^{11}$ 提升至 $10^{12}$，并证明了在消费级硬件上进行大规模数论验证的可行性。未来工作将集中在消除 CPU-GPU 依赖（GPU 加速筛法构建）以及实现位运算批量标记内核，以进一步突破 $10^{15}$ 的验证边界。