【研究成果】GPUの計算能力を最大限活用する組合せ最適化問題の新解法〜1兆探索/秒を超えるアダプティブ・バルク・サーチ〜

本研究成果のポイント

二次無制約二値最適化(QUBO)^※2問題に対し、複数のGPU^※1を用いてコストが最小となる最適解を探索する新しい探索フレームワーク「アダプティブ・バルク・サーチ」を開発しました。
GPUのアーキテクチャの特性を活かし計算性能を最大限に引き出す解探索手法により、最新のNVIDIA GPUを4基搭載した計算サーバーで1秒間に1兆を超える解を探索する計算速度を達成しました。
探索手法を適応的に変化させることが可能で、幅広い問題に有効です。
より大規模な計算機システムやスーパーコンピュータを用いることで台数に比例した計算速度のスピードアップが可能です。

概要

広島大学大学院先進理工系科学研究科の中野浩嗣教授らの研究チームは、株式会社NTTデータと共同で、組合せ最適化問題の解を高速に探索する新しい計算方式「アダプティブ・バルク・サーチ」の開発に成功しました。その計算方式は、二次非制約二値最適化(QUBO)問題の解を複数のGPU(グラフィクス向けプロセッサ)を用いて効率よく並列に探索します。

巡回セールスマン問題など多くの組合せ最適化問題は、QUBO問題として記述することができ、幅広い応用があります。そのため多くの大学や企業が専用集積回路や量子効果に基づいた量子アニーリングマシンなどを用いてQUBO問題を解くシステムや手法の開発を競っています。組合せ最適化問題を解く従来手法のシミュレーテッド・アニーリング^※3などでは、同じ解を何度も探索するなど無駄が多く、良い解が得られない場合があります。また、手法によってうまく解ける問題と解けない問題が存在します。そこで本研究では、重複がないように大量の解を並列に探索する新しいフレームワークを開発しました。さらに、探索アルゴリズムを問題に応じて適応的に変化させることが可能で、幅広い問題を解くことができます。

本研究成果の詳細は、広島大学大学院先進理工系科学研究科の安戸僚汰特任助教が国際会議International Conference on Parallel Processing (ICPP)にて発表します。

アダプティブ・バルク・サーチのコンセプトは、ホストCPUによる遺伝的アルゴリズム^※4とGPUによる近傍探索をシームレスにつなぎ、膨大な数のコアを持つGPUによる並列計算でなるべく重複がないように大量の解を探索するというものです(図)。

用語解説

(※1) GPU
Graphics Processing Unitの略で、グラフィック処理のための集積回路です。計算処理能力の高さから、グラフィック処理以外の様々な処理を高速化することができるため、多くのスーパーコンピュータに搭載されています。

(※2) QUBO問題
nビットの変数をもつ二次式の値が最小になるように各変数に0と1の割り当てを求める組合せ最適化問題。

(※3) シミュレーテッド・アニーリング
金属の焼きなましにヒントを得た組合せ最適化問題の解法。最適解の探索範囲を温度に依存して決定することで最適解を見つける確率が高くなります。

(※4) 遺伝的アルゴリズム
生物の進化にヒントを得た最適解探索アルゴリズム。解を遺伝子とみなして、交叉と突然変異を繰り返しながら適応度が高い解を残していくものです。

論文情報

国際会議名: International Conference on Parallel Processing (ICPP) 2020
論文タイトル: Adaptive Bulk Search: Solving Quadratic Unconstrained Binary Optimization Problems
　　　　　　 on Multiple GPUs
著者名: Ryota Yasudo, Koji Nakano, Yasuaki Ito, Masaru Tatekawa, Ryota Katsuki, Takashi Yazane,
　　　 Yoko Inaba
DOI: 10.1145/3404397.3404423