PyTorch: LinkedIn が DuaLip ソルバーを GPU で 75 倍高速化

PyTorch Foundation は、LinkedIn が極端なスケールの最適化問題を解くために分散線形計画ソルバー DuaLip を PyTorch 上に再構築した方法についてのケーススタディを公開した。元のツールはプロセッサに結びついた Scala/Spark スタックに依存していたが、新しい GPU アクセラレーション版は DuaLip-GPU という名前を持つ。

LinkedIn では線形計画は何を解いていたのか?

線形計画 (LP) は、与えられた制約のもとで最良の決定を見つけるための数学的手法である。LinkedIn では次の問いを解く。数百万あるいは数十億の選択肢の中から、制約下で最良の行動の組み合わせはどれか? 具体的な例としては、求人と潜在的な候補者のマッチング、ランキングやレコメンデーションにおける複数のビジネス指標のバランス調整、送信されるメール量の最適化などが含まれる。こうした問題は数億のユーザーと最大で数兆の決定変数を対象とする。

高速化はどのように達成されたのか?

PyTorch 実装は 3 つの技術に基づいている。数十億から数兆の変数を扱うための疎 (sparse) テンソル演算、変数を GPU 間で分割し集合通信 (all-reduce、broadcast) で同期する分散最適化、そして行の正規化や加速勾配降下法 (AGD/FISTA のバリアント) といった収束の改善である。

結果はどうだったのか?

ケーススタディは、8 基の GPU 上で元の Scala 実装と比べて実時間で反復が最大 75 倍高速 であること、CPU システムに対しては桁違いの高速化、そして複数 GPU にわたるほぼ線形のスケーリングを挙げている。その際に精度は維持されており、これにより LinkedIn は「以前は実現不可能だったスケールでの本番最適化」が可能になった。この実装はオープンソースとして公開されている。