線形計画法 (LP: Linear Programming) ソルバーの進化は、シンプレックス法から内点法 (IPM: Interior Point Method) まで、過去 1 世紀にわたってに重要な節目で特徴づけられてきました。主双対線形計画法 (PDLP: Primal-dual Linear Programming) の導入は、さらなる大きな進歩をもたらしました。
NVIDIA cuOpt は現在、GPU アクセラレーションで PDLP を実装しています。最先端のアルゴリズム、NVIDIA ハードウェア、専用の CUDA 機能、NVIDIA GPU ライブラリを使用して、cuOpt LP ソルバーは、CPU ベースのソルバーと比較して 5,000 倍以上の高速パフォーマンスを実現しています。
この投稿では、LP ソルバー アルゴリズムの主要コンポーネント、LP における GPU アクセラレーション、Mittelmann のベンチマークと最小費用フロー問題のインスタンスにおける cuOpt 性能を検証します。
最先端のイノベーションを大規模な LP に活用
LP は、一連の線形制約の対象となる線形目的関数を最適化する手法です。
例えば、こんなシナリオを考えてみてください。農家は、土地、種、肥料に制約がある中で、利益を最大限に高めるために、どの野菜をどれくらい栽培するかを決めなければなりません。目標は、あらゆる制約を満たしながら、できるだけ迅速に最適な収益を決定することです。
NVIDIA が開発した LLM エージェントの例は、LP ソルバーを使用して問題をモデル化し、解決するのに役立ちます。LP は最適化に不可欠なツールであり、リソースの配分、生産計画、サプライチェーン、混合整数計画問題 (MIP: Mixed-integer Programming) ソルバーのバックボーンとして応用されています。数百万もの変数や制約がある数学的問題を数秒で解くことは、不可能ではないにせよ、難しい場合もあります。
GPU で効率的に LP 問題を解決するには、以下の 3 つの要件があります。
- 効率的で大規模な並列アルゴリズム
- NVIDIA GPU ライブラリと CUDA 機能
- 最新鋭の NVIDIA GPU
効率的で大規模な並列アルゴリズム
1947 年に Dantz 氏によって導入されたシンプレックス法は、現在でもほとんどの LP と MIP ソルバーの中核をなしています。これは、実現可能な領域の端を追って最適値をを求めるものです。
次の大きな進歩は、1967 年に I. I. Dikin 氏が発見した内点法 (IPM: Interior Point Method) でした。多面体の内部を最適値の方向に移動する IPM は、現在では CPU 上で大規模な LP を解く最先端技術だと考えられています。しかしながら、いずれの手法も大規模な並列化には限界があります。
2021 年に、大規模 LP を解く新しい画期的な技術として、Google Research チームによって発表されましたのが、PDLP です。PDLP は、問題の導関数を使用して、目的を繰り返し最適化し、制約違反を最小限に抑える一次法 (FOM: First-order Method) です。
PDLP は、プレソルバー、対角線の前提条件、適応的なリスタート、動的な主双対ステップ サイズ選択など、収束を改善するツールを導入することで、主双対ハイブリッド勾配 (PDHG: Primal-dual Hybrid Gradient) アルゴリズムを強化します。プレソルバーと前提条件により、入力問題がより簡素化され、数値安定性が向上します。一方、リスタートと動的ステップ サイズ計算により、ソルバーは最適化中に適応することができます。
FOM が従来の手法よりも優れている点として、大規模な並列化が容易であり、GPU の実装に適しています。
PDLP は、Map 演算と疎行列ベクトル積 (SpMV: Sparse Matrix-Vector Multiplications) の 2 つの高度に並列化可能な計算パターンを採用しています。このアプローチにより、PDLP は数百万もの変数と制約を効率的に並列処理することができ、GPU に対して非常に効果的になります。
Map は、PDLP で広く使用されており、数百万の要素に及ぶすべての変数と制約に対して加算や減算などを行います。これは、GPU 上では極めて並列処理が可能でかつ効率的です。
SpMV は、疎行列 (多くのゼロを含む) とベクトルの乗算に相当します。この行列のサイズは数百億に達しますが、有用な値ははるかに少なくなります。例えば、野菜の植え付け問題では、「3.5 kg 以上のジャガイモを植えることができない」といった制約には、数百万の変数の中で有用な値が 1 つしか含まれないことになります。
SpMV アルゴリズムは、GPU 向けに広範囲に最適化されており、CPU 実装よりも桁違いに高速です。
NVIDIA GPU ライブラリと CUDA 機能
最高のパフォーマンスを得るために、NVIDIA の GPU PDLP 実装では、最先端の CUDA 機能と以下の NVIDIA ライブラリを使用しています。
- cuSparse
- Thrust
- RMM
cuSparse は、疎線形代数の NVIDIA GPU 対応ライブラリです。これは、GPU では難しいとされる SpMV を効率的に実行します。cuSparse は、NVIDIA の巨大な並列アーキテクチャをフル活用するように設計された独自のアルゴリズムを採用しています。
Thrust は、NVIDIA CUDA コア コンピューティング ライブラリ (CCCL) の一部であり、高いレベルの C++ 並列アルゴリズムを提供します。GPU の実行にパターンとイテレーターを使用して、複雑なアルゴリズムの表現を簡素化します。私は、Map 演算とキーで値をソートするリスタートのプロセスに Thrust を使用しました。これは、GPU に負荷がかかる作業ですが、Thrust で効率的に最適化できます。
RMM は、高速かつ柔軟な NVIDIA メモリ管理システムで、メモリ プールを使用することで、GPU メモリの安全で効率的な処理を実現します。
最後に、高度な CUDA の機能を利用しました。GPU 上で PDLP を並列化する際の最も重要な課題の 1 つは、本来反復的であり、並列実行には適していないリスタート手順です。これに対処するために、私は CUDA Cooperative Groups を使用しました。これは、さまざまなレベルで GPU アルゴリズムを定義でき、最も大きなのものはすべてのワーカーを網羅するグリッドになります。協調的なカーネル起動を実装し、グリッド同期を利用することで、GPU 上で反復的なリスタート手順を効率的かつエレガントに表現できます。
最先端の NVIDIA GPU
GPU は、数千ものスレッドを使用して多くの問題を同時に解決することで、高速計算を実現します。しかし、処理する前に、GPU はまずメイン メモリからワーカー スレッドにデータを転送する必要があります。
メモリ帯域幅とは、1 秒間に転送できるデータ量のことです。CPU では通常、数百 GB/秒を処理できますが、最新の GPU である NVIDIA HGX B100 の帯域幅は 8 TB/秒で、2 桁も大きい値です。
この PDLP 実装のパフォーマンスは、Map や SpMV のようなメモリ負荷の高い計算パターンに大きく依存しているため、メモリ帯域幅の増加に応じて、直線的に拡大します。将来的に NVIDIA GPU の帯域幅が増加すれば、他の CPU ベースの LP ソルバーとは異なり、PDLP は自動的に高速化されます。
cuOpt は、Mittelmann のベンチマークで最先端の CPU LP ソルバーを上回る性能を発揮
LP ソルバーの速度を評価する業界標準が、Mittelmann のベンチマークです。その目的は、制約を満たしながら LP 関数の最適値を可能な限り最短時間で決定することです。ベンチマークの問題は、さまざまなシナリオを示しており、数十万から数千万の値を含んでいます。
比較のために、私は最新の CPU LP ソルバーを実行し、この GPU LP ソルバーと比較しました。同じ閾値である 10-4 を用いて、クロスオーバーを無効にしました。詳細については、この投稿の後半にある PDLP 改良の可能性のセクションを参照してください。
どちらのソルバーも float64 の精度で動作しました。
- CPU LP ソルバーの場合、推奨される CPU 設定である、16 コアと 256 GB の DDR4 メモリを備えた AMD EPYC 7313P サーバーを使用しました。
- cuOpt LP ソルバーの場合、高帯域幅のメリットを活用するため、NVIDIA H100 SXM Tensor コア GPU を使用し、プレソルバーなしで実行しました。
両方のソルバーのスケーリングと CPU LP ソルバーのプレソルバーなど、I/O なしの完全な解決時間を考慮しました。正しい目標値を持つ両方のソルバーの場合、収束したインスタンスのみを図 4 で示しています。cuOpt は、60% のインスタンスで高速化し、20% のインスタンスで 10 倍以上高速化しました。最大の高速化は、大規模な多品種流問題の最適化のうちの 1 つのインスタンスで 5,000 倍の高速化が達成されました。
また同じ設定と条件を使用して、最新の CPU PDLP の実装と cuOpt を比較しました。cuOpt は常に高速化し、10 倍～ 3000 倍も高速化します。
多品種流問題 (MCF: Multi-commodity Flow Problem) では、ネットワークの容量制約を超えないように、さまざまな出発点からそれぞれの目的地までネットワークを介して複数のさまざまな物をルーティングする最も効率的な方法を見つけることができます。MCF 問題を解決する 1 つの方法は、LP に変換することです。一連の大規模な MCF インスタンスでは、PDLP は一貫して 10 倍から 300 倍の間で高速になります。
PDLP 改良の可能性
NVIDIA cuOpt LP ソルバーは、驚異的なパフォーマンスを発揮しますが、将来的に強化される余地もあります。
- より高い精度への対応
- 高帯域幅の必要性
- 一部の問題に対する収束問題
- 小規模な LP に対する限定的な効果
より高い精度への対応
LP を解決したかどうかを判断するには、以下の 2 点を測定します。
- 最適性のギャップ: 目的関数の最適値からの距離を測定します。
- 実現可能性: 制約をどのくらい満たしているかを測定します。
LP は、両方の値がゼロになった時、解決したとみなされます。厳密にゼロの値に到達することは困難であり、不要なことも多いため、LP ソルバーは精度を維持しながら収束をより高速化する閾値を使用します。両方の値が、この閾値以下であることが要求されるため、問題の値の大きさに対して相対的なものになります。
ほとんどの LP ソルバーは、特に解決するのが非常に困難な大きな問題に対して、閾値を使用します。これまでの業界標準では、10-8 を使用していました。PDLP は 10-8 を使用して問題を解決することもできますが、通常はかなり時間がかかります。高い精度が求められる場合、これは問題になります。実際には、多くの場合 10-4 で十分な精度であると考える人も多く、場合によってはそれよりも低い値でも十分であると考える人もいます。これは、PDLP には大きな利点となりますが、他の LP 解決アルゴリズムの大きな差別化要因にはなりません。
高帯域幅の必要性
PDLP のパフォーマンスはメモリ帯域幅に比例して拡張し、新しい GPU アーキテクチャではより効率的になります。前述したパフォーマンス分析のセクションで示した結果を再現するには、最近のサーバー グレードの GPU が必要です。
一部の問題に対する収束問題
PDLP は、ほとんどの LP を迅速に解決できますが、収束するまでにかなりのステップ数が必要になることがあり、その結果、実行時間が長くなることがあります。Mittelman のベンチマークでは、cuOpt LP ソルバーは、49 の公開インスタンスのうち 8 つで、収束率が遅いため、1 時間後にタイムアウトしました。
小規模な LP に対する限定的な効果
小規模な LP が、GPU の高帯域幅から利益を得ることは少なく、CPU ソルバーと比較して PDLP を拡張できません。cuOpt LP ソルバーは、このようなシナリオに対応するバッチモードを用意しており、数百もの小規模な LP を並行して提供し、解決できます。
まとめ
cuOpt LP ソルバーは、CUDA プログラミング、NVIDIA GPU ライブラリ、および最新鋭の NVIDIA GPU を使用して、LP を解決します。これは、CPU よりも桁違いに高速で、10 億を超える係数にまで拡大される可能性があります。その結果、大規模な問題に取り組む上で特に有益であり、その利点はさらに顕著になります。
- GTC セッション: Advances in Optimization AI (最適化 AI の進歩)
- NGC コンテナー: cuOpt
- SDK: cuOpt
- SDK: cuSOLVERMp
- SDK: cuSOLVER
従来のシンプレックス法や IPM を用いたほうが上手くいくユース ケースもありますが、将来的には、GPU と CPU の技術を組み合わせたソルバーが主流になるでしょう。
登録すると、cuOpt LP を試せるようになった際に、通知を受け取ることができます。NVIDIA API カタログで、NVIDIA が提供する最新の AI モデル向けの NIM マイクロサービスを使用して、NVIDIA の cuOpt 車両経路問題 (VPR: Vehicle Routing Problem) を今すぐ無料でお試しください。
