情報通信プラットフォーム

シミュレーテッド分岐アルゴリズムの専用大規模並列処理回路を開発
-高速に変化する環境にリアルタイムで応答できる組合せ最適化ソリューションを提供し、
金融、ロボティクス、物流、創薬などの社会課題を解決-

2019年09月11日
株式会社東芝

当社は、大規模で複雑な組合せ最適化問題の高精度な近似解(良解)を短時間で得る当社独自の「シミュレーテッド分岐アルゴリズム(Simulated Bifurcation アルゴリズム。以下、SBアルゴリズム)」の高速性を最大限引き出す専用大規模並列処理回路(注1)を開発しました。当社は本年4月20日にSBアルゴリズムの開発について公表しており、今回の回路の開発によって、金融取引など超高速で良解を選び反応することが必要な分野にSBアルゴリズムを適用することができます。
本回路を搭載することで大規模並列計算が可能となり、より高速に良解を算出できることができます。また、汎用プロセッサで実行されるソフトウェアの制御を受けないため、0.001秒未満レベルの極めて短い時間で外部環境の変化を検知し、膨大な選択肢の中から変化に応じた良解を選ぶことが可能な瞬時最適応答システム(図1)を構築することができます。
例えば、刻々と市況が変化する金融取引において、膨大な組合せパターンの中から収益性がより高い取引を瞬時に見つけ出すことや、産業用ロボットが周辺状況に応じて最も効率的な動作をリアルタイムに選択することなどが期待できます。
本回路技術の詳細は、バルセロナで開催されるIEEE国際会議「FPL2019」(注1)において、現地時間の9月9日(日本時間9月9日)に発表しました。

金融ポートフォリオの最適化、産業用ロボットの動作の最適化、物流・移動経路の最適化による配送効率の向上・渋滞の緩和、創薬のための分子設計など、社会・産業システムの生産性を高めるための課題の多くは、組合せ最適化によって解決することができます。組合せ最適化は古くから経済的に重要な問題ですが、問題の規模が大きくなるにつれて組合せパターンの数が指数関数的に増大する「組合せ爆発」のため、既存の計算機で解くことが困難になっています。このため、組合せ最適化問題を解く手段として、量子計算機(注2)や光学計算機(CIM(注3))などの新しい技術が次々と開発されており、当社も独自の量子計算機「量子分岐マシン」(注4)およびその理論を古典力学系へ展開した、世界最高速度・最大規模の最適化を可能にする「SBアルゴリズム」(注5・6)を発表しています。
組合せ最適化問題の解法の革新に伴って、金融取引や産業ロボットなどの超高速なリアルタイム応答を要求されるシステムにおいても、最も合理的な判断を瞬時に下して次のアクションを決定することが出来るという新しい可能性が出てきています。その実現には、問題を解く計算処理時間のみならず、データの入出力やシステム制御の時間を含めて応答時間を大幅に短縮する超低遅延性が重要となる他、省電力性、安定性、柔軟性などの厳しいシステム要件に応える組合せ最適化ソリューションが求められます。

そこで当社は、SBアルゴリズムをハードウェア処理する専用回路を開発しました。本回路は、SBアルゴリズムに含まれる演算のうち同時刻に実行可能な演算を解析した結果に基づき、空間並列化と時間並列化の回路手法を用い設計された大規模並列処理回路です(図2)。さらに、クロックサイクルごと、1ビットデータごとの最も細かいレベルでの回路最適化を施すことで、高速処理性能と省電力性能を両立します。
本回路は、応答時間の増大および変動の要因となるソフトウェア処理による制御を必要とせず、解くべき問題の入力ののち設計時に決定される一定の計算時間の後、算出した良解を出力します。0.001秒未満レベルの超低遅延性を実現するためは、高速な最適化ソリューション回路のみならず、目的に応じた専用の外部インタフェース回路/その他アプリケーション回路が必須となります。本回路は、従来の回路記述言語よりも抽象度が高い高位合成言語で記述されているため、インタフェースをより柔軟に変更し、周辺の専用回路と直接接続することが可能です。
本回路は、市販の再構成可能論理回路(FPGA)(注7)に実装することが可能であり、冷凍機などの特殊な付帯設備を必要としません。また、本回路は、処理性能(回路規模)もより柔軟に変更することが可能で、目的システムの要求遅延性能に応じて最適なコストの実装手段を選択することが可能です。このように本回路は、柔軟性の高いシステムコンポーネントです。
本回路を20nm世代FPGA(注7)に実装した場合(本実装)、4,096変数・全結合(約800万結合)のサイズまでの組合せ最適化問題を扱うことが可能です。これは、従来当社が発表したFPGA実装(注5)のサイズの4倍に相当します。また本実装は、従来当社が発表していたFPGA実装(注5)よりも11%高速です(図3)。本実装は、4,000変数・全結合の問題の良解を51ワットの消費電力、0.211ミリ秒で得ることができます(図3)。その良解を得るのに必要なエネルギーは10.8ミリジュールです。これは、SBアルゴリズムを並列汎用プロセッサであるGPU(注8)で実行した場合よりも、11倍高速で、26倍高いエネルギー効率です(注1)。また、従来の標準手法であるシミュレーテッドアニーリング法よりも313倍高速、828倍高いエネルギー効率です(注9)
本技術により、金融取引や産業用ロボットの分野において、高速に変化する環境にリアルタイムに応答できる組合せ最適化ソリューションを構築することが可能になります。

当社は、本回路を応用した、組合せ最適化問題を高速に解くことを核とするリアルタイム応答システムのコンセプトを特定分野で実証する実験機(Proof-of-Concept)の研究開発を進め、2019年中の発表を目指します。

図1:開発したSB専用回路を応用した瞬時最適応答システム

図2:開発したSBアルゴリズムの専用回路とそのFPGA実装例

図3:開発した専用回路(FPGA-SB)の速度性能とエネルギー効率

(注1)K. Tatsumura, A. R. Dixon, H. Goto, "FPGA-based Simulated Bifurcation Machine," The International Conference on Field-Programmable Logic and Applications (FPL), pp.59-66 (2019)  https://ieeexplore.ieee.org/document/8892209 (IEEE)

(注2)M. W. Johnson et al., Nature 473, 194 (2011).

(注3)T. Inagaki et al., Science 354, 603 (2016).  https://www.jst.go.jp/impact/hp_yamamoto/en/overview/index3.html(国立研究開発法人科学技術振興機構)

(注4)H. Goto, Scientific Reports 6, 21686 (2016)で発表した、量子断熱定理と量子分岐現象に基づく量子計算機。

(注5)世界最速・最大規模の組合せ最適化を可能にする画期的なアルゴリズムの開発について -物流・創薬など社会課題を短時間で解決するサービスプラットフォームの構築に向けて-  https://www.global.toshiba/jp/technology/corporate/rdc/rd/topics/19/1904_01.html
  量子コンピューター研究から生まれた 組合せ最適化の新解法  https://www.toshiba-clip.com/detail/7685

(注6)[東芝デジタルソリューションズ] 大規模組合せ最適化を高速に実行するソフトウェア「シミュレーテッド分岐マシン」をAWS Marketplace上に公開 ~さまざまな分野での社会課題の解決に向けて実証実験を開始~  https://www.toshiba-sol.co.jp/news/detail/20190717.htm

(注7)Field-Programmable Gate Arrayの略称。演算処理集積回路の一種で、製造後にユーザーが用途に応じて機能を書き換えることが可能。20nm世代の半導体プロセスで製造されたIntel Arria10 GX1150 FPGAを使用した場合。

(注8)Graphics Processing Unitの略称。画像処理向け集積回路で、多数の演算処理部を含む。

(注9)当社によるCPUに実装されたシミュレーテッドアニーリング法の値。消費電力は使用したCPUの熱設計電力(TDP)の値。