プロジェクトはオープンソース化されました！GitHub（github.com/latentcat/graphpu）にアクセスして、GraphPU のソースコードを入手したり、ソフトウェア（Windows / macOS）をダウンロードしたりできます。
研究動機
大学の授業で、Barabási のスケールフリーネットワークに関する研究を学び、複雑ネットワークやソーシャルネットワークに強い興味を持ちました。当時、私は自分の WeChat の 1000 人の友達の「いいね」データを収集し、Mathematica で友人関係のネットワークを描画しました。
最も驚くべきことは、Mathematica の可視化で、私の友達が色分けされたグループに分類され、各クラスターの友達の名前を確認すると、小学校・中学校の同級生、高校の同級生、大学の同級生、インターネットの友人、個別に知り合った友人というように、ぴったりと分類されていたことです。入力したグラフの可視化データには、そのようなラベルは含まれておらず、ある人が誰かに「いいね」をしたというデータしかありませんでした。
これをきっかけにグラフ可視化に興味を持ち、より大規模なグラフがどのように見えるのか気になり始めました。例えば、10 億人の WeChat ユーザーが形成するネットワークはどのような形をしているのか？数億人の Xiaohongshu（小紅書）や Weibo のネットワークとはどう違うのか？
このような好奇心から、私と数人の同級生（
CPunisher、
Shichen、
KirinoMizu）は、100 万ノードを可視化できる 3D GPU 加速グラフ可視化ツール、GraphPU を開発することになりました。
既存のツール
Gephi、Cytoscape、前述の Mathematica など、多くのグラフ可視化ソフトウェアがありますが、通常 1 万ノード以上のグラフデータを処理できません。これは、分布シミュレーションアルゴリズムが通常 CPU マルチスレッドベースであり、シミュレーション時に多くの直列依存関係が発生するだけでなく、レンダリング時に CPU、メモリ、VRAM、GPU 間で大量のデータ転送が発生し、大きなフレーム遅延を引き起こすためです。
さらに、これらのソフトウェアは通常、データサイエンティストが具体的な分析や研究を行うことを目的としているため、通常は 2D 空間でのみシミュレーションを行います。しかし、私は視聴者にグラフをより直感的に理解してもらいたかったため、3D 空間でリアルタイムシミュレーション、リアルタイムレンダリングができる必要がありました。
Unity での実装
Unity でプロトタイプの構築を完了しました。Unity は Compute Shader に対して優れた抽象化とカプセル化を提供し、アルゴリズムの開発とデバッグを柔軟に行うことができます。
1 ヶ月の徹夜作業の後、以下のような非常に印象的な可視化画像を得ることができました。
Rust での実装
開発が進むにつれて、Unity の問題点が徐々に表面化してきました。例えば、ツール UI の開発が難しく、フレームレートの制限が非常に厳しいなどです。
最終的に、Rust で GraphPU を構築することを選択しました。以下がそのスクリーンショットの一部です。
技術的なアプローチ
印象的な視覚効果の裏には、極めて複雑な最適化が施されています。これらの技術的なアプローチがなければ、GraphPU は 60FPS ではなく、おそらく 0.1FPS しか達成できなかったでしょう。
浮動小数点数の原子加算
グラフ可視化の核心は、2 つの力の計算にあります：斥力を表す電子力と引力を表すばね力です。これらの力が相互に作用し、最終的にグラフが空間内で安定した状態に分布します。
GPU でばね力（本質的には疎行列）を計算するには、各ノードに加わるばね力の合計を計算する必要がありますが、これには GPU の特性が関係してきます。複数の GPU スレッドが同時に同じデータに対して演算を行う場合、同時読み取り・同時書き込みの状況が発生する可能性が極めて高く、複数のスレッドが同じノードにばね力を加算する際、同時に読み取った結果が全て 0 となり、最終的に書き込まれる結果が単一のばね力の値になってしまう可能性があります。
この問題を解決するには、各ノードの x、y、z の 3 次元それぞれに対して浮動小数点数の原子加算を行う必要があります。原子加算とは、加算を行う際にその数値をロックして他のスレッドからのアクセスを禁止し、書き込み完了後にロックを解除する操作です。ほとんどの GPU プログラムは整数型の原子加算を提供していますが、浮動小数点数の原子加算はソフトウェアによるシミュレーションが必要です。
Unity では、ユーザーが記述した HLSL シェーダーは ShaderLab 内で HLSLcc に送られ、Metal や OpenGL などのバックエンド用のシェーダープログラムにコンパイルされます。一方、Rust wgpu では、シェーダーの変換作業は naga が行います。
WebGPU と WGSL の標準が草案段階にあり、頻繁に更新されるため、naga はまだ WGSL の最新標準における atomicCompareExchangeWeak（3 つのパラメータを受け取り、元の値と変更の有無を示すブール値を含む構造体を返す）を実装していませんでした。また、当時 atomicExchange は Metal 側でバウンドチェックのエラーが存在していました。
そのため、私たちは wgpu の依存関係を Rust crate からローカルに移行し、カスタム開発を行いました。HLSL に似た標準を使用して atomicCompareExchangeWeak 関数を記述し、Metal と Vulkan の両方で効果的に動作することを確認しました。
この実践により、シェーダーコンパイラについてより詳細な理解を得ることができ、貴重な経験となりました。
ばね力のマージソート加速
浮動小数点数の原子加算はばね力の計算に有効ですが、グラフの規模が大きくなると、1 つのノードに非常に多くのエッジが接続されている状況が発生する可能性があります。その場合、そのノードのばね力計算には大量の直列依存関係が存在し、複雑度は O(n) となります。そこで、私たちはばね力に対する新しいマージソートを考案し、ばね力の計算を大幅に加速することができました。
マージソートは GPU での累積加算演算によく使われるアルゴリズムで、2 つずつ加算し、徐々にマージすることで累積加算を高速化します。私たちのアルゴリズムでは、各ノードに対して個別にマージ計算を行う方法が大きな課題でしたが、ソートとアライメントの方法を設計することで、このプロセスを非常に効率的なものにすることができました。
最適化後、1 つのノードに 100 万本のエッジが接続されている場合でも、シミュレーション速度を 60 倍以上向上させることができます。
Barnes-Hut アルゴリズムの並列版
グラフ可視化アルゴリズム全体で最も重要な部分は、ノード間の電子力の計算です。電子と電子は二体間で相互作用し、電子力は「至る所に存在する」ため、複雑度は実質的に O(n^2) となります。Barnes-Hut アルゴリズムは、Barnes-Hut ツリー（四分木や八分木に似た構造）を構築することで、N 体シミュレーション（電子力は実際には逆向きの万有引力です）において、距離が遠く影響が小さいノードをマージし、作用力の近似値を得ることで、シミュレーションプロセスを大幅に高速化し、O(n^2) の複雑度を O(n log n) に削減することができます。
Barnes-Hut の古典的な実装では、アルゴリズムはほとんど全て CPU 上で実行されます。最大の理由は、Barnes-Hut ツリーの構築時に再帰的な方法を使用するためです。GPGPU には再帰の概念がなく（CUDA などを除く）、ループやデータ駆動の方法でシミュレーションするしかありません。
したがって、GPU 並列の Barnes-Hut アルゴリズムの実装は非常に複雑で、実装のために 1000 行のコンピュートシェーダーを書きました。これらのアルゴリズムは極めてデバッグが難しく、数え切れないほどの問題に遭遇しました。
バイトニックマージソートによるパーティクル深度ソート、オフスクリーンレンダリング raycast
最後に、レンダリングにもいくつかの工夫を加えました。バイトニックマージソートでパーティクルの深度ソートを解決し、オフスクリーンレンダリングの手法でマウスとパーティクルの raycast インタラクションを実現し、コントローラーのインタラクションで卒業設計展示の会場設営を完成させました。
おわりに
これは非常に時間のかかる、大規模なプロジェクトでした。ビジネス展開は全く考慮せず、純粋に興味関心からの時間投資でした。CPunisher、Shichen、KirinoMizu との共同努力に感謝します。プロジェクトは github.com/latentcat/graphpu でオープンソース化され、Windows / macOS の実行可能プログラムをダウンロードできます。皆様のいいねとブックマークをお待ちしております！
ありがとうございました！