GPUの計算性能を最大限活用する組合せ最適化問題の新解法を公開 ～1兆探索/秒を超えるアダプティブ・バルク・サーチ～
2020年8月17日
株式会社NTTデータ
株式会社NTTデータ（以下：NTTデータ）は、広島大学大学院先進理工系科学研究科（以下：広島大学）の中野浩嗣教授らの研究チームと共同で、組合せ最適化問題の解を高速に探索する新しい計算方式「アダプティブ・バルク・サーチ」を開発しました。本計算方式は、二次無制約二値最適化（以下：QUBO）問題注1の解を、複数のGPU（グラフィクス向けプロセッサ）注2を用いて効率よく並列に探索します。本計算方式を用いることで、従来の技術では解くことが困難であったさまざまな問題を効率的に解き、量子コンピューターや次世代アーキテクチャーの適用分野を拡張することを目指します。
背景
近年、量子アニーリングやGPU・FPGA注3を用いて、組合せ最適化問題を高速に解くアーキテクチャーの研究開発が活発に行われています。組合せ最適化問題はさまざまな分野の問題を表現することができるため、問題を高速に計算することが可能になると、多くの社会課題の解決につながります。こうした新たなアーキテクチャーに対する取り組みは、さまざまな組合せ最適化問題をQUBO問題という統一的な問題に帰着させて、QUBO問題を高速に解くことを目的としています。
今回、公開する新解法は、「さまざまなQUBO問題に柔軟に対応」し、「大規模計算システムの利用により台数に比例した計算速度の向上が可能」という特長を備えています。この特長により、柔軟性と拡張性を兼ね備えた計算が可能となり、特定の問題を一定の速度で解くことにとどまらず、本技術領域の可能性を大きく拡張できるものと考えています。
NTTデータでは、2019年1月より量子コンピュータ/次世代アーキテクチャ・ラボ注4のサービスを開始し、さまざまな分野における量子コンピューターをはじめとする次世代アーキテクチャーの適用検証を進めてきました。今回発表する新解法は、これらの活動から見えてきた適用事例や評価方法および現状の課題をNTTデータが示し、広島大学の有する専門性により解決したものです。今後、研究開発を加速し、これまで解くことが困難であった問題を効率的に解くことで、コンピューティングの技術革新による社会課題解決を目指します。
新解法の概要
新解法「アダプティブ・バルク・サーチ」は、複数のアルゴリズムを用いて大量の解からコストが最小となる最適解をGPUで並列に探索します。この解法は以下のような特長を備えています。
- 探索手法を柔軟に変化させることで、さまざまなQUBO問題に対応することが可能です。
- より大規模な計算機システムやスーパーコンピューターを用いることで台数に比例した計算速度のスピードアップが可能です。
- GPUのアーキテクチャーの特性を考慮した解の探索手法を設計し、最新のNVIDIA社製GPU注5を4基搭載した計算サーバーで1秒間に1兆を超える解を探索する計算速度を達成しました。
実験では、最大カット問題、巡回セールスマン問題、ランダム問題に対する「アダプティブ・バルク・サーチ」の高速性を示しています。また、現状では、32,768変数のQUBO問題まで扱うことができます。
本研究成果の詳細は、広島大学の安戸僚汰特任助教が8月17日から8月20日に開催される国際会議International Conference on Parallel Processing（以下：ICPP）にて発表します。ICPPは並列処理に関する伝統ある国際会議で、今回が49回目の開催となります。
図：アダプティブ・バルク・サーチの動作イメージ
今後について
NTTデータでは、本解法を活用し、流通、金融、製造分野における諸問題ならびにAI・機械学習の高性能化に取り組んでいきます。また、これまで解くことが困難であった問題を効率的に解くことで、エネルギー利用の効率化やスマートな物流網などの、社会課題解決に向けた適用可能性を拡大するとともに、広島大学と共同で本手法のさらなる改善に取り組んでいきます。
発表情報
| 国際会議名 | 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 |
注釈
- 注1二次無制約二値最適化（以下：QUBO）問題とは、二次形式で表現され各変数が01を取る無制約最適化問題です。
- 注2Graphics Processing Unitの略で、元々はグラフィック処理のための集積回路です。計算処理能力の高さから、グラフィック処理以外のさまざまな処理を高速化することができるため、多くのスーパーコンピューターに搭載されています。
- 注3Field Programmable Gate Arrayの略で、利用者が論理回路の構成を設定・変更できる集積回路です。
- 注4量子コンピュータ／次世代アーキテクチャ・ラボのサービス開始
https://www.nttdata.com/jp/ja/news/release/2019/012501/ - 注5NVIDIA GeForce RTX 2080 Ti GPU
本件に関するお問い合わせ先
報道関係のお問い合わせ先
株式会社NTTデータ
広報部
田中
TEL：050-3644-3022
製品・サービスに関するお問い合わせ先
株式会社NTTデータ
技術革新統括本部
技術開発本部
先進コンピューティング技術センタ
矢実
TEL：050-5546-9320