1兆探索/秒を超えるアダプティブ・バルク・サーチ

　NTTデータは8月17日、広島大学大学院先進理工系科学研究科（以下：広島大学）の中野浩嗣教授らの研究チームと共同で、組合せ最適化問題の解を高速に探索する新しい計算方式「アダプティブ・バルク・サーチ」を開発したと発表した。
　同計算方式は、二次無制約二値最適化（以下：QUBO）問題の解を、複数のGPU（グラフィクス向けプロセッサ）を用いて効率よく並列に探索する。同計算方式を用いることで、従来の技術では解くことが困難であった様々な問題を効率的に解き、量子コンピュータや次世代アーキテクチャの適用分野を拡張することを目指すという画期的な技術となる。

背景

　近年、量子アニーリングやGPU・FPGAを用いて、組合せ最適化問題を高速に解くアーキテクチャの研究開発が活発に行われている。組合せ最適化問題はさまざまな分野の問題を表現することができるため、問題を高速に計算することが可能になると、多くの社会課題の解決に繋がる。こうした新たなアーキテクチャに対する取り組みは、様々な組合せ最適化問題をQUBO問題という統一的な問題に帰着させて、QUBO問題を高速に解くことを目的としている。
　今回、公開される新解法は、「様々なQUBO問題に柔軟に対応」し、「大規模計算システムの利用により台数に比例した計算速度の向上が可能」という特長を備えている。NTTデータは「この特長により柔軟性と拡張性を兼ね備えた計算が可能となり、特定の問題を一定の速度で解くことにとどまらず、本技術領域の可能性を大きく拡張できるものと考えている」としている。
　NTTデータでは、2019年1月より量子コンピュータ/次世代アーキテクチャ・ラボのサービスを開始し、さまざまな分野における量子コンピュータをはじめとする次世代アーキテクチャの適用検証を進めてきた。今回発表する新解法は、これらの活動から見えてきた適用事例や評価方法および現状の課題をNTTデータが示し、広島大学の有する専門性により解決したものだという。NTTデータは「今後、研究開発を加速し、これまで解くことが困難であった問題を効率的に解くことで、コンピューティングの技術革新による社会課題解決を目指す」としている。

新解法の概要

新解法「アダプティブ・バルク・サーチ」は、複数のアルゴリズムを用いて大量の解からコストが最小となる最適解をGPUで並列に探索する。この解法は、次のような特長を備えている。

•探索手法を柔軟に変化させることで、さまざまなQUBO問題に対応することが可能

•より大規模な計算機システムやスーパーコンピュータを用いることで台数に比例した計算速度のスピードアップが可能

•GPUのアーキテクチャの特性を考慮した解の探索手法を設計し、最新のNVIDIA社製GPUを4基搭載した計算サーバで1秒間に1兆を超える解を探索する計算速度を達成

　実験では、最大カット問題、巡回セールスマン問題、ランダム問題に対する「アダプティブ・バルク・サーチ」の高速性を示している。また、現状では、32,768変数のQUBO問題まで扱うことができる。
　同研究成果の詳細は、広島大学の安戸僚汰特任助教が8月17日から8月20日に開催される国際会議International Conference on Parallel Processingで発表するという。

今後について

　NTTデータは「本解法を活用し、流通、金融、製造分野における諸問題ならびにAI・機械学習の高性能化に取り組んでいく。また、これまで解くことが困難であった問題を効率的に解くことで、エネルギー利用の効率化やスマートな物流網などの、社会課題解決に向けた適用可能性を拡大するとともに、広島大学と共同で本手法のさらなる改善に取り組んでいく」としている。