# 疎行列ベクトル積 ## 定義 疎行列ベクトル積（Sparse Matrix-Vector Multiplication; SpMV）は、成分の大半がゼロである疎行列 $A \in \mathbb{R}^{m imes n}$ と密ベクトル $x \in \mathbb{R}^n$ の積 $y = A x$ を計算する数値線形代数の基本的演算である。偏微分方程式（PDE）の有限要素法（FEM）や有限差分法（FDM）による離散化、グラフ解析、機械学習の埋め込みモデルなど、科学技術計算の広範な反復解法（Conjugate Gradient法やGMRES法などのクリロフ部分空間法）において最も計算時間を消費する中核カーネルである。 ## 特徴と性能ボトルネック ### 1. 低演算強度とメモリバウンド特性 SpMV は非ゼロ要素 1 個あたり 1 回の乗算と 1 回の加算（計 2 FLOP）を行うが、非ゼロ要素の値に加えて行ポインタや列インデックスの読み込みが必要となる。倍精度（FP64）の場合、8 バイトの値に対して 4〜8 バイトのインデックスが付随するため、算術強度（Arithmetic Intensity; FLOP/Byte）は通常 0.1〜0.25 程度と極めて低い。現代の GPU やアクセラレータ上では、演算器の理論ピークに達する前にメモリ帯域幅に完全に律速される典型的なメモリバウンド（memory-bound）カーネルである。 ### 2. データ格納フォーマット 非ゼロ要素の規則性やアクセス効率に応じて多様な格納形式が用いられる： - **CSR（Compressed Sparse Row）**: 行ポインタ配列、列インデックス配列、非ゼロ要素値配列の 3 配列で表現する最も一般的な形式。行ごとの非ゼロ数が揃っている問題に適する。 - **COO（Coordinate）**: 行・列・値の 3 つ組を並べる形式。要素の挿入や不規則な通信バッファの扱いに優れる。 - **ELL / SELL-C-$\sigma$**: スレッドワープ内での列方向の揃えを意識し、GPU のメモリコアレッシングと[[分岐発散]]の抑制を図った形式。 ### 3. 次世代アクセラレータにおける「命令レイテンシ」の壁 高帯域幅メモリ（HBM3 等）を搭載した最新プロセッサ（例: [[NVIDIA GH200]]）では、メモリ帯域幅の増加ペースに対して命令実行サイクル遅延が相対的に重くなる現象が報告されている。混合精度変換や多ベクトル対応（SpMM への一般化）などの柔軟な境界判定命令が挟まれると、演算器が未飽和であるにもかかわらずグローバルメモリからのストリーミングが阻害され、性能低下を引き起こす。単一ベクトルに特化したカーネルオーバーロードとスレッドオーバーサブスクリプションの調整が有効な対策となる。 ## 分散メモリ環境における SpMV マルチノード・マルチ GPU 環境では、行列とベクトルを行方向に分割して各プロセス（ランク）に配置する。ランク $I$ の計算は以下のように局所行列と非局所行列に分解される： $y_I = A_{I,I} x_I + A_{I,O} x_O$ - **局所 SpMV（$A_{I,I} x_I$）**: 自ランクが所有するベクトル要素のみを参照するため通信不要。 - **非局所 SpMV（$A_{I,O} x_O$）**: 他ランクが所有する $x_O$ の要素をネットワーク経由で受信（All-to-All 通信等）した後に計算。 この構造を利用して、通信中に局所 SpMV を実行することで通信遅延を隠蔽する手法（[[通信隠蔽]]）が不可欠となる。 ## 未編纂の観察 - [GH200上の命令レイテンシ阻害] JUPITER スーパーコンピュータ上の GH200 において、Ginkgo の汎用 SpMV カーネルが cuSPARSE に劣る現象をプロファイラで解析した結果、混合精度変換や多ベクトル対応のための境界判定・インデックス計算処理が長い命令サイクル遅延を生み、メモリバウンドであるはずのカーネルがメモリストリーミングを維持できなくなっていた。単一ベクトル特化オーバーロードの適用により CSR で 1.13 倍（cuSPARSE 比 +4%）、COO で 1.3 倍の高速化が達成された(Source: [[@2026__HPCAsia__What Will the Grace Hopper-Powered Jupiter Supercomputer Bring for Sparse Linear Algebra?]])。 - [エクサスケール弱スケーリング] 8,192 基の GH200 を用いた 27 点ステンシルの分散 SpMV では、局所サイズ $10^7$ において 80% の並列化効率を保ち、実効スループット 1.9 PFLOPS を達成した(Source: [[@2026__HPCAsia__What Will the Grace Hopper-Powered Jupiter Supercomputer Bring for Sparse Linear Algebra?]])。 - [性能特性] 2009 年の 4 種のマルチコア(Xeon、Opteron X4、Sun T2+、Cell)で、SpMV の演算強度は 0.17(レジスタブロッキング前)〜0.25 Flops/Byte と、4 機すべてのリッジポイント(0.33〜6.7)より低く、全機でメモリ律速だった。最適化の大半はメモリ系(データ構造の圧縮、プリフェッチ、メモリアフィニティ)に関わり、従来実装は単一プロセッサでピークの 10% 未満で動くことが多いと報告される。2026 年の GH200 での分析とも、メモリ律速という結論が 17 年を隔てて一致する。(Source: [[@2009__CACM__Roofline - An Insightful Visual Performance Model for Multicore Architectures]]) ## 未解決の問い - 不規則な非ゼロ分布（非ゼロ数の分散が大きいグラフ等）を持つ行列に対して、GH200 のような大容量 HBM3/DDR 密結合システムではどのような動的負荷分散およびフォーマット選択が最適か。 - 単一ベクトル特化による命令数削減効果は、コンパイラによる自動ループ展開や命令スケジューリングでどこまで一般的に自動化できるか。 ## 関連 - ソース: [[@2026__HPCAsia__What Will the Grace Hopper-Powered Jupiter Supercomputer Bring for Sparse Linear Algebra?]] / [[@2009__CACM__Roofline - An Insightful Visual Performance Model for Multicore Architectures]] - 概念: [[Rooflineモデル]] / [[GPU-Aware MPI]] / [[通信隠蔽]] / [[GPU最適化]] / [[集合通信]] / [[演算強度]] - エンティティ: [[Ginkgo]] / [[NVIDIA GH200]] / [[JUPITER (スーパーコンピュータ)]] ## 出典 - [[@2026__HPCAsia__What Will the Grace Hopper-Powered Jupiter Supercomputer Bring for Sparse Linear Algebra?]] — JUPITER 上の GH200 における SpMV の Roofline 分析、命令レイテンシによるボトルネック解明、および 8,192 GPU スケーリング。 - [[@2009__CACM__Roofline - An Insightful Visual Performance Model for Multicore Architectures]](4 機種マルチコアでの SpMV の演算強度と律速)