シミュレーテッド分岐アルゴリズム専用の大規模並列処理回路を開発――大規模で複雑な組合せ最適化問題の高精度な近似解を短時間で取得東芝

東芝は2019年9月11日、大規模な組合せ最適化問題の近似解を短時間で得られる「シミュレーテッド分岐アルゴリズム」専用の大規模並列処理回路を開発したと発表した。

金融ポートフォリオやロボットの動作の最適化、物流や経路の最適化による配送効率の向上や渋滞の緩和、創薬のための分子設計など、社会／産業システムの課題の多くは、組合せ最適化によって解決できる。しかし、組合せ最適化問題は、規模が大きくなるにつれて組合せパターンの数が指数関数的に増大していく。そのため、既存の計算機で解くことは困難だった。そこで、東芝は今年4月20日、独自の量子計算機「量子分岐マシン」やその理論に基づく、世界最速で最大規模の最適化を可能にするシミュレーテッド分岐アルゴリズム（SBアルゴリズム）を発表していた。

そして、東芝は今回、SBアルゴリズムに含まれる演算のうち同時に実行できる演算を解析。空間並列化と時間並列化の回路手法を用いて、SBアルゴリズムをハードウェア処理する専用回路を開発した。1ビットデータごとの回路最適化を施しており、高速処理性能だけでなく省電力性能も両立している。また、同回路は市販のFPGAに実装可能で、冷凍機などの特殊な設備も不要だ。目的システムの要求性能やコストに応じて、回路規模も変更できる。

さらに、この回路は、20nm世代FPGAに実装した場合、4096変数で変数間を全結合（約800万結合）のサイズまでの組合せ最適化問題を扱うことが可能。4000変数で全結合の良解を51Wの消費電力、0.211ミリ秒で得られる。これは、SBアルゴリズムをGPUで実行した場合よりも、速度で11倍、エネルギー効率で26倍高い。また、標準手法とされるシミュレーテッドアニーリング法と比べると、速度で313倍、エネルギー効率では828倍高い。

東芝は、この回路を搭載することで、金融取引において高収益な取引を瞬時に見つけ出すことや、産業用ロボットがリアルタイムに効率的な動作を選択することなどが期待できるという。また、今後の予定として、特定分野の組合せ最適化問題を高速に解き、リアルタイムに応答できる実験機の研究開発を進め、2019年中の発表を目指すとしている。

シミュレーテッド分岐アルゴリズム専用の大規模並列処理回路を開発――大規模で複雑な組合せ最適化問題の高精度な近似解を短時間で取得　東芝