A Lock-Free, Fully GPU-Resident Architecture for the Verification of Goldbach's Conjecture

Each language version is independently generated for its own context, not a direct translation.

この論文は、数学の長年の謎である**「ゴールドバッハの予想」**を、最新の GPU（グラフィックボード）を使って超高速で検証する新しい仕組みについて書かれたものです。

一言で言うと、**「これまでの方法では、計算する『工場（GPU）』が、材料を届ける『トラック（CPU）』の遅さに待たされすぎていたが、今回は工場の中で材料を自分で作れるようにし、トラックを完全に不要にした」**という話です。

以下に、専門用語を避け、日常の例えを使ってわかりやすく解説します。

1. 何をやろうとしているの？（ゴールドバッハの予想）

まず、この研究の目的は「ゴールドバッハの予想」を証明することです。
これは**「2 より大きいすべての偶数は、2 つの素数の足し合わせで表せる」**という簡単なルールです。
（例：4=2+2, 10=3+7, 100=3+97 など）

このルールが「無限の数字」まで正しいかどうかを確認するために、コンピューターで数字を一つずつチェックしています。これまでの記録は「400 京（4×10^18）」まででしたが、もっと大きな数字まで確認したいというのが目標です。

2. 以前の「ボトルネック」問題

以前の研究（この論文の前のバージョン）では、GPU という「超高速な計算マシン」を使っていましたが、**「トラックが追いつかない」**という問題がありました。

以前の仕組み：
- CPU（トラック）： 計算に必要な「材料（素数のリスト）」を一つずつ作って、GPU に送ります。
- GPU（工場）： 材料が届くと、一瞬で計算して結果を出します。
- 問題点： GPU は「一瞬で終わる」のに、CPU が材料を届けるのが遅すぎました。GPU は「材料待ち」でずっと待機し、トラックが渋滞しているような状態でした。特に GPU を 2 台、4 台と増やしても、CPU が材料を運ぶ速度が限界なので、速くなりませんでした。

3. 今回の「革命」：工場の中で材料を自給自足

今回の新しい仕組み（GoldbachGPU v2.0）は、この「トラック待ち」を完全に解消しました。

新しい仕組み：
- GPU（工場）： 材料（素数）を、工場の中（GPU の高速なメモリー）で自分で作ってしまいます。
- CPU（トラック）： もう材料を運ぶ必要はありません。GPU に「次はどの数字から計算していいよ」という**「スタート地点の番号」**だけを送れば OK です。
- 結果： GPU は待たされずに、ずっとフル回転で計算を続けます。

【例え話】
以前のやり方は、**「料理人（GPU）が料理をするたびに、助手（CPU）が食材を買いに行って運んでくる」という状態でした。料理人が待っている時間が長すぎました。
今回のやり方は、「料理人の目の前に巨大な冷蔵庫（GPU のメモリー）があり、必要な食材を自分で取り出して調理する」**状態です。助手は「次は 100 番目の料理から作って」と一言言うだけで、料理人は止まることなく働き続けます。

4. 複数の GPU を使うときの「盗賊（Work-Stealing）」

GPU を 2 台、4 台使うとき、それぞれの GPU の性能が少し違ったり、熱で少し遅くなったりすると、全体の速度が「一番遅い GPU」に引っ張られてしまいます。

そこで、この論文では**「盗賊（Work-Stealing）」**という仕組みを導入しました。

仕組み： 「誰が空いてるか？」を監視するリーダーはいません。GPU 同士が「次のタスク（数字の塊）を誰がやるか」を、「誰が先に手を挙げたか」で勝手に決めます（ロックフリー）。
メリット： 高速な GPU はどんどんタスクを奪って働き、遅い GPU は自分のペースで働きます。誰かが休むことなく、全員が最大限の効率で動きます。
結果： GPU を 2 台使うとほぼ 2 倍速、4 台使うとほぼ 4 倍速になりました（98% 以上の効率）。

5. すごい成果（数字で見る速さ）

この新しい仕組みを使えば、どれくらい速くなるのでしょうか？

10 億（10^9）までの確認： 以前の仕組みより13 倍速い。
100 億（10^10）までの確認： 以前の仕組みより45 倍速い。
- （※数字が大きくなるほど、CPU が材料を運ぶ遅さが問題になるため、差が広がります）
10 兆（10^12）までの確認： 最新の GPU 1 枚で36.5 秒で完了。
10 兆（10^13）までの確認： GPU 4 枚で133.5 秒（約 2 分半）で完了。

これは、これまで何年もかかっていた計算を、数分間で終わらせる驚異的な速さです。

6. 安全性と限界

間違いがないか？
巨大な数字を計算すると、コンピューターが「桁あふれ（オーバーフロー）」を起こして間違った答えを出すリスクがあります。このシステムは、数学的な厳密なルール（ガード）を設けて、1840 京（1.84×10^19）までなら絶対に間違えないことを保証しています。
限界は？
64 ビットの計算限界（1840 京）を超えると、また別の技術が必要になります。しかし、今のところはこの限界までなら完璧に動きます。

まとめ

この論文は、**「GPU という超高速な計算機を、CPU という遅い配送業者のせいで待たせないようにし、GPU だけで完結する仕組みを作った」**という画期的な成果です。

これにより、ゴールドバッハの予想を、これまで考えられないほど速く、かつ多くの GPU を使って効率的に検証できるようになりました。すべてのコードは公開されており、誰でも同じような高性能な PC で再現できるそうです。

**「待たされることのない、完全な自給自足の計算工場」**が完成したのです。

Each language version is independently generated for its own context, not a direct translation.

以下は、提示された論文「A Lock-Free, Fully GPU-Resident Architecture for the Verification of Goldbach's Conjecture（ゴールドバッハ予想の検証のためのロックフリーかつ完全 GPU 常駐アーキテクチャ）」の技術的な要約です。

1. 問題定義と背景

ゴールドバッハ予想（2 より大きいすべての偶数は 2 つの素数の和として表せる）の検証は、計算機科学における重要な課題です。従来の CPU ベースの検証（Oliveira e Silva らによる $4 \times 10^{18}$ までの記録）は高度に最適化されていますが、大規模な計算には大規模クラスターと長期間を要します。

著者の先行研究（GoldbachGPU v1）では、VRAM 容量の制約を解決するために「セグメント化されたダブルソイブ（区切り篩）」を採用し、単一の消費向け GPU で $10^{12}$ までの検証を可能にしました。しかし、v1 には重大なボトルネックが存在しました：

ホスト - デバイス間の通信遅延: 各セグメントの素数ビットセットを CPU が生成し、PCIe バスを介して GPU に転送する必要がありました。
スケーラビリティの欠如: GPU 演算速度が非常に速いため、GPU は CPU が次のセグメントを準備するのを待機する状態（アイドル）になり、マルチ GPU 環境での並列化効率が極端に低下しました（2 枚の GPU を追加しても速度向上が見られませんでした）。

2. 提案手法：GoldbachGPU v2.0 のアーキテクチャ

本論文では、ホスト（CPU）とデバイス（GPU）の依存関係を完全に排除し、完全なデバイス常駐（Fully Device-Resident）かつロックフリーなアーキテクチャを提案します。

2.1 GPU ネイティブなセグメント篩（L1 共有メモリ活用）

CPU からの完全分離: セグメントの素数ビットセット生成（篩）処理を GPU 内部に移行しました。
L1 共有メモリによるタイル化: セグメントを 32,768 個の奇数（4KB ビットセット）のタイルに分割し、これらを GPU の L1 共有メモリ（Ada Lovelace/Blackwell アーキテクチャでは 48KB 利用可能）にロードして処理します。
結果: 各セグメントの処理中に PCIe 転送が発生せず、GPU は独立して演算を完了できます。

2.2 ロックフリー非同期ワーク・スチリング・プール

静的分割の廃止: GPU 間の処理速度差（サーマルスロットリングやシリコンバインディングによるもの）による待機を避けるため、静的な負荷分割を廃止しました。
アトミック操作による動的割り当て: ホストメモリ上の 64 ビットアトミックカウンター（g_next_seg_start）を使用し、各 GPU ワーカーが完了したセグメントごとに原子操作（fetch_add）で次のセグメントを「奪う（スチールする）」方式を採用しました。
効果: どの GPU が速くても遅くても、システム全体が効率的に稼働し、デッドロックやロック競合を排除します。

2.3 フェーズ 2 の最適化された CPU フォールバック

Phase 1 (GPU): 候補となる小規模な素数（ $p \le 10^6$ ）のみを用いて検証。
Phase 2 (CPU): 仮に検証に失敗した場合（実際には $10^{13}$ までの範囲では発生しない）のみ、CPU がフォールバック処理を行います。
- 事前計算された $10^8$ までの素数配列に対する二分探索。
- 必要に応じて 128 ビット整数演算を用いた決定論的 Miller-Rabin 素性判定（12 個のウィットネスセット使用）を実行します。

2.4 数学的厳密性とオーバーフロー対策

64 ビット整数の限界: 検証範囲を $1.84 \times 10^{19}$ まで引き上げるため、64 ビット整数のオーバーフローを厳密に防ぎます。
対策: 乗算による境界計算を除算ベースのガードに置き換え、uint128_t を使用した 128 ビット中間積計算を実装。決定論的 Miller-Rabin 判定の保証範囲内（ $n < 2^{64}$ ）でのみ動作することを数学的に保証しています。

3. 主要な成果と結果

実験は NVIDIA RTX 5090（Blackwell アーキテクチャ）を搭載したワークステーションで行われました。

3.1 アルゴリズム的な速度向上

同一ハードウェア比較: RTX 5090 単体において、先行研究（v1）と比較して、 $N=10^{10}$ で45.6 倍、 $N=10^9$ で 13.2 倍の速度向上を達成しました。
原因: 速度向上はハードウェアの進化ではなく、PCIe 転送オーバーヘッドの排除によるものです。 $N$ が大きくなるほど（セグメント数が増えるほど）速度向上率は高まり、v1 が I/O 束縛（I/O-bound）であったことを証明しています。

3.2 マルチ GPU スケーリング効率

並列効率:
- 2 GPU: 99.7% の並列効率
- 4 GPU: 98.6% の並列効率
記録: 4 枚の RTX 5090 を使用して、ゴールドバッハ予想を $10^{13} $まで**133.5 秒**で検証完了しました（単一 GPU での$ 10^{12}$ 検証は 36.5 秒）。
通信量: 正常な検証パス（Phase 1）では、ホストからデバイスへの転送は素数バッチ（約 628KB）のみ、デバイスからホストへの転送は未検証数のスカラー値（4 バイト）のみであり、ゼロコピー高速パスが機能しています。

3.3 プロファイリング結果

Nsight Systems による解析により、GPU の利用率が 96%〜98% 以上で維持され、初期化オーバーヘッドと最終セグメントの処理を除けば計算効率が 100% に近いことが確認されました。
熱的なスロットリングも最小限に抑えられ、安定した動作が確認されました。

4. 意義と将来展望

アーキテクチャ的革新: 従来の「CPU が管理し GPU が計算する」モデルから、「GPU が自律的に計算し、最小限の通信で協調する」モデルへの転換を成功させました。これにより、異種混合 GPU クラスタや大規模クラスターでのスケーリングが現実的なものとなりました。
再現性とオープンソース: 全コードはオープンソース化されており、市販のハードウェアで再現可能です。
将来の課題:
- 64 ビット限界の突破: $10^{19}$ 超の検証には、256 ビット演算や Baillie-PSW 素性判定などの導入が必要です。
- ビット単位バulk マーキング: 現在の「1 スレッド=1 偶数」アプローチから、CPU 版のようにビットセットを操作する「1 スレッド=32〜64 偶数」のアプローチへの移行が、さらなる性能向上の鍵となります。

結論

本論文は、ゴールドバッハ予想の検証において、PCIe 通信ボトルネックを完全に解消し、ロックフリーなワークスチリングによりマルチ GPU 環境でほぼ理想的な並列効率（98.6% 以上）を実現した画期的なアーキテクチャを提示しました。これにより、単一コンシューマー GPU での高速検証と、大規模クラスターでの効率的な拡張が可能となり、数論的検証の新たな基準を確立しました。