GraphLeap: Decoupling Graph Construction and Convolution for Vision GNN Acceleration on FPGA

技術概要：GraphLeap

問題定義
ビジョン・グラフ・ニューラルネットワーク（ViG）は、画像をパッチ・トークンのグラフとして表現し、動的かつ特徴量駆動型の近傍関係を活用することで、Vision Transformer（ViT）と比較して計算効率を維持しつつ競争力のある精度を達成します。しかし、ViGの中核メカニズムである「現在のパッチ特徴量に基づいて各層で $k$ 最近傍（$k$NN）グラフを再構築する」処理は、重大な性能ボトルネックを生み出しています。この動的なグラフ構築は、CPU および GPU における総推論時間の 50〜95% を消費し、パッチ数に対して二次的（$O(N^2)$）にスケーリングします。重要なのは、この処理が厳密な逐次依存関係を強制することです。すなわち、層 $\ell$ のグラフが完全に構築されるまで、その層の特徴量更新（畳み込み）を開始できません。この直列化は効率的な並列化を阻害し、リアルタイム展開を困難にしています。さらに、既存のハードウェアアクセラレータは主に静的グラフや規則的なグリッド操作（CNN/ViT）を対象としており、動的な画像グラフ構築および完全な ViG パイプラインに特有の課題には対応していません。

手法：GraphLeap の再定式化
著者は、層間におけるグラフ構築と特徴量更新を分離して逐次依存関係を打破する新しいアルゴリズム的再定式化「GraphLeap」を導入します。

• 1 層先読み（One-Layer Lookahead）： 層 $\ell$ のグラフを層 $\ell$ の特徴量（これは前層の更新を待つ必要がある）を用いて構築する代わりに、GraphLeap は現在の層 $\ell$ の特徴量を用いて層 $\ell+1$ のグラフを構築し、同時に、前層（$\ell-1$）の特徴量から構築されたグラフを用いて層 $\ell$ の特徴量更新を実行します。
• アルゴリズム的転換： 標準的な ViG では $G^{(\ell)} = G(U^{(\ell)})$ となりますが、GraphLeap では、ブロック $\ell$ におけるメッセージパッシングに $\hat{G}^{(\ell)} = G(U^{(\ell-1)})$ を使用し、$U^{(\ell)}$ は同時に $\hat{G}^{(\ell+1)}$ の構築に用いられます。
• 精度回復： 著者は、「古くなった（stale）」グラフ（前層からのもの）を使用することが軽微な精度低下をもたらす可能性を認めています。しかし、軽量な微調整（30 エポック）によって元の精度を回復でき、しばしば基準となる ViG の性能に匹敵するかそれ以上になることを実証しています。

システムアーキテクチャ：エンドツーエンド FPGA アクセラレータ
GraphLeap アルゴリズムに基づき、本論文は AMD-Xilinx Alveo U280 上で実装された、ビジョン GNN 向け初のエンドツーエンド FPGA アクセラレータを提示します。この設計は、2 つの主要エンジンをオーバーラップさせるストリーミング型、層パイプライン化アーキテクチャを特徴とします。

1. グラフ構築エンジン（GCE）： 拡張 $k$NN グラフを計算する高スループットエンジンです。ノード特徴量をタイル単位で処理し、ペアワイズ距離計算のために処理要素（PE）のメッシュを使用し、近傍ノードを抽出するために最小ヒープを維持します。重要なのは、オフチップメモリに完全なエッジ特徴量を具体化することなく、近傍インデックスを次のステージへストリーミングすることです。
2. 特徴量更新エンジン（FUE）： このエンジンはストリーミングされたグラフデータを消費し、ViG Grapher およびフィードフォワードネットワーク（FFN）操作を実行します。これには以下が含まれます：
   • ギャザモジュール（GM）： 近傍特徴量の取得のために、インターリーブされたバンキングとプリフェッチを介して不規則なメモリアクセスパターンを処理します。
   • グラフ畳み込みモジュール（GCM）： シンクロトロン配列を使用して最大相対集約と線形変換を実装し、ノード特徴量とメッセージの明示的な連結を回避します。
   • FFN モジュール（FM）： ノードごとの更新のための専用 MLP データパスです。

• データフロー戦略： GCE は FUE より 1 層先を進んで動作します。これにより、層 $\ell+1$ のグラフ構築が、層 $\ell$ の特徴量更新と並行して進行することが可能になります。この設計は、$O(NK)$ のエッジ特徴量の明示的な具体化を回避し、ノード特徴量と小さなラインバッファのみをオンチップに保持します。

主要な貢献

1. GraphLeap アルゴリズム： 動的グラフ構築とグラフ畳み込みを分離し、グラフ構築と特徴量更新の並行実行を可能にする一般的な再定式化。
2. 初のエンドツーエンド ViG アクセラレータ： 専用の $k$NN グラフ構築エンジンと専用の特徴量更新エンジンを備え、ビジョン GNN 向けに特別に設計されたストリーミング型パイプライン化 FPGA アーキテクチャの開発。
3. ストリーミング $k$NN 構築： 特徴量更新より 1 層先を進んで動作し、近傍インデックスを直接計算パイプラインへストリーミングする、拡張 $k$NN 画像グラフ向けの高スループットハードウェア設計。
4. 効率的な特徴量更新パイプライン： グラフ畳み込みおよび FFN ステージの両方に共有されたシンクロトロン型 MLP ファブリックを利用し、ストリーミングバッファを介して接続された混合された不規則および規則的なワークロードを処理するハードウェアエンジン。

実験結果
著者は、Alveo U280 FPGA に展開された等方性（Ti, S, B）およびピラミッド型（Py-Ti, Py-S, Py-M, Py-B）ViG モデル上で GraphLeap を評価しました。

• 速度向上： このアプローチは、エンドツーエンド推論において、64 コア CPU ベースラインに対して最大 95.7 倍、NVIDIA RTX A5000 GPU ベースラインに対して 8.5 倍 の速度向上を達成します。
• レイテンシ： 224×224 解像度の ViG-B モデルにおいて、アクセラレータはエンドツーエンドレイテンシ 2.77 ms を達成します。
• 最先端技術との比較： 同様の FPGA プラットフォーム上の最先端 ViT アクセラレータ（DRViT, UbiMoE）と比較して、GraphLeap は同等の精度で 3 倍低いレイテンシ を達成します。
• 精度： 微調整後、GraphLeap モデルは元の ViG の Top-1 精度の 1.4% 以内に回復します（例：ViG-Py-B は 82.34% に到達）。

意義と主張
本論文は、動的グラフ構築の逐次ボトルネックを根本的に解決することで、リアルタイムなビジョン GNN 推論の実現可能性を GraphLeap が実証していると主張しています。著者は、アルゴリズム的再定式化が従来の CPU/GPU アーキテクチャ上では modest な gains（1.03〜1.23 倍）しかもたらさない一方で、結果として生じる生産者 - 消費者のストリーミング関係を活用できるハードウェアと共同設計される場合、大幅な性能ポテンシャルを解放すると論じています。この研究は、グラフベースのビジョンモデルにおけるハードウェアとアルゴリズムの共同設計の将来を鼓舞しており、構築と畳み込みを分離することが、ViG の適応的近傍の利点を犠牲にすることなく、効率的かつ低レイテンシな推論を可能にすることを示しています。