NVIDIA、cuOpt向けマルチGPUソルバーmPDLP発表

米NVIDIAは、GPUアクセラレーションを活用した意思決定最適化基盤「NVIDIA cuOpt（サプライチェーンや経路探索を高速化するGPU最適化基盤）」において、大規模な線形計画法（LP）問題を複数GPUへ分散処理する新ソルバー「mPDLP（cuOpt向けのマルチGPU主双対ハイブリッド勾配線形計画法ソルバー）（multi-GPU Primal-Dual hybrid gradient for Linear Programming）」の提供を開始しました。1億（100 Million）変数を超える超大規模な最適化問題をNVLink接続されたGPU群で並行処理し、単一GPU比でピークメモリ消費量を最大6分の1に抑制します。

最小カットグラフ分割によるGPU間通信の最小化

線形計画法を高速に解くアルゴリズムである主双対ハイブリッド勾配法（PDLP）は、1次勾配降下法をベースとした並列計算に適した手法です。その中心的な処理は疎行列ベクトル積（SpMV）であり、メモリアクセス帯域が計算速度の上限を決定づけます。

従来の分散PDLP手法（D-PDLP）は制約行列を2次元ブロックに分割してSpMVを個別に実行していましたが、cuOpt mPDLPは入出力ベクトルの依存関係に着目した「最小カットグラフ分割（Min-cut partitioning）」を採用しました。制約行列を二部グラフとして捉え、GPUを跨ぐ切断エッジ（通信を必要とする接続）が最小となるように各GPUへ行と列を割り振ります。これにより、連続するSpMVの反復処理においてGPU間のデータ転送オーバーヘッドを最小限に抑えています。

ハードウェア面ではNVLinkおよびNVSwitchの広帯域相互接続と、通信ライブラリNCCLを活用することで、複数GPUを1台の巨大な共有メモリ空間のように機能させています。

DGX B200での検証とパートナー企業での導入効果

NVIDIA DGX B200システム（8基構成）を用いた100種類以上のベンチマーク評価では、非ゼロ要素数（nnz）が1,000万を超える大規模問題において顕著な高速化を確認しました。代表的なベンチマークである「tsp-gaia-10m」では、純粋なPDLP反復ステップ単体で最大11.4倍、全体処理時間で4.2倍の高速化を達成しました。また、1億400万非ゼロ要素を持つ難関ベンチマーク「zib03」では、1年前と比較して約10倍の求解速度を記録しました。

パートナー企業の実環境でも導入成果が報告されています。

• Kinaxis: サプライチェーン計画プラットフォーム「Maestro」において、8基のNVIDIA H100 GPUを用い、1億3500万変数の消費財サプライチェーンモデルで3.3倍の高速化を達成。
• PSR: エネルギー計画分野において、8基のNVIDIA B200 GPUを用い、1億8500万変数の確率的エネルギー拡張計画モデルで5倍以上の高速化を実証。

独自価値の整理（性能特性の比較と未確認事項の整理）

mPDLPの性能特性および今後の改善課題を以下のように整理します。

評価軸	確認済みの事実・強み	制約および未確認の課題
問題規模と効果	非ゼロ要素数1000万超で単一GPUやD-PDLPを凌駕	小規模問題では同期オーバーヘッドにより単一GPUが有利
行列構造の依存性	二部グラフ分割で通信削減可能な構造で効果大	切断エッジ比率が高い特殊な超大規模問題では速度低下の例あり
メモリ消費量	単一GPU比でピークメモリを最大6分の1に抑制	21億非ゼロ要素が現状の理論上限（整数表現制約）
今後の改善予定	実行ロードバランスを考慮したハイパーグラフ分割	通信とSpMV計算の非同期オーバーラップ処理の実装待ち

日本の製造業や物流、エネルギー事業者においても、全国規模の配送計画やリアルタイム需給管理など、従来は数時間から一晩を要していた大規模な最適化計算を実務時間内に収める手段として有用です。

分析・展望

編集部注: サプライチェーンの複雑化や再エネ電源の系統連系など、現実世界の最適化問題は変数の爆発的増加に直面しています。単一GPUのVRAM容量（メモリの壁）を突破し、NVLinkによって複数GPUのメモリと計算力を線形計画法に動員できるようになったことは、数理最適化の産業実装における大きな前進です。今後、計算と通信の非同期重複や近似解を素早く求めるFeasibility polishingが実装されることで、実務現場での適用範囲はさらに広がるとみられます。

引用元：NVIDIA Technical Blog