【東芝】オンプレミス版のシミュレーテッド分岐マシン（ＴＭ）を開発し、研究用途向けに提供を開始
災害時緊急対応や金融取引等のリアルタイムシステムに組込める世界初の量子インスパイア最適化計算機
概要
当社グループは、量子コンピュータ理論から生まれた、組合せ最適化問題を解く量子インスパイア(*1)最適化計算機である「シミュレーテッド分岐マシン™」において、オンプレミス版(*2)を開発し、研究用途向けに提供を開始しました。本マシンは、低遅延インターフェースを備え、決められた時間内（デッドラインまで）に処理を完了させる「リアルタイムシステム」への組込みが可能な世界初の量子インスパイア最適化計算機です。金融をはじめ産業ロボットや災害時緊急対応システムなど高速なリアルタイム応答が要求されるシステムに本マシンを組み込むことで、刻々と変化する状況において瞬時にすべての選択肢の中から最良な１つを選び、それに基づく最適な応答をすることが可能となります。
情報処理システムの構築において、「オンプレミス」は自社内でシステムを保有・運用することを指します(*2)。外部サーバーを経由する「クラウド」がビッグデータの処理に適している一方で、「オンプレミス」はインターネット回線に接続する必要がないため、より高速な応答が求められるシステムへの適用が期待されます。
今回開発したオンプレミス版は、運転支援・災害時等の最短巡回経路表示・金融取引の3つの参照例（リファレンスデザイン）(*3)を予めパッケージしており、ユーザーは自身のシステム開発を効率的に進めることができます。
なお、開発したオンプレミス版のシミュレーテッド分岐マシン™は、東芝デジタルソリューションズ株式会社を販売窓口として、お客様が革新的なリアルタイム応用システムを試作・実証するために、研究用途向けに提供を開始しています。
開発の背景
金融取引の最適化(*4)、産業用ロボットの動作の最適化、移動経路や送電経路の最適化など、社会や産業における課題の多くは、膨大な選択肢から最適なものを選び出す組合せ最適化に帰着します。組合せ最適化は、問題の規模が大きくなるにつれて組合せパターンの数が指数関数的に増大するため、既存の計算機で高速に解くことは困難です。このため、組合せ最適化専用計算機の開発が国内外で活発に行われています。
当社グループは、独自の量子コンピュータ理論から生まれ、全く新しい解の探索原理で組合せ最適化問題を解く量子インスパイア最適化計算理論として、シミュレーテッド分岐アルゴリズム（以下、SBアルゴリズム）を2019年4月に初めて発表 (*5)しました。その後、2019年7月に、本SBアルゴリズムを搭載したシミュレーテッド分岐マシン™のクラウド版をAWS Marketplace上に公開し(*6)、実証を進めるとともに、2021年2月には、SBアルゴリズムの速度・精度・規模を大幅に向上させた、第二世代となるSBアルゴリズムの開発を公表しました(*7)。
シミュレーテッド分岐マシン™を利用する方法は、「クラウド」に加え、「オンプレミス」があります。クラウドは導入が容易で、ビッグデータを扱う大規模計算に適していますが、インターネット回線で接続するため、オンプレミスと比較すると応答スピードが遅くなります。より瞬時の計算が求められる運転支援や金融取引といった分野においては、わずかな時間でも結果に影響が出るため、リアルタイムの応答性が実現できるオンプレミス版の開発が求められていました。
従来技術と課題
解決すべき組合せ最適化問題の中には、高速な最適化の計算能力に加え、高速・リアルタイムな応答性が求められるものがあります。特に運転支援、災害時緊急避難経路、金融取引などは、刻々と変化する外部環境や状況を継続的にセンシング・モニタリングし、変化に応じた対応アクションの決定、そのアクションの実行といった一連の作業の時間（応答時間）を短縮することが不可欠です。
オンプレミス化（組込みシステム化）によりリアルタイムの応答性の実現が可能ですが、既存のリアルタイムシステムの機能を阻害せずシミュレーテッド分岐マシン™を組み込む必要があります。また、高速な組合せ最適化とリアルタイム応答性を両立させ、周囲の変化に応じて最も合理的な判断を瞬時に下すリアルタイムシステムはこれまでにない新しいコンセプトであり、広く社会実装するためには実証実験を重ねる必要があります。
開発した技術
そこで当社は、既存のリアルタイムシステムの機能を阻害することなく組込み可能なオンプレミス版のシミュレーテッド分岐マシン™を開発しました。本マシンはSBアルゴリズムを高速に処理する専用回路(*7,8)の構成データとして提供され、ユーザーはその回路構成データで市販のFPGA（Field-Programmable Gate Array、書換え可能論理回路）ボードを再構成する（書換える）ことで本マシンを容易に完成させることができます(*9)。
ユーザーは、FPGAボードを搭載した様々な機器（Linux OSの汎用計算機)上で、シミュレーテッド分岐マシン™を搭載したリアルタイムシステムを構築することができます。ユーザーが取り組む社会課題に含まれる様々な組合せ最適化問題を、シミュレーテッド分岐マシン™を用い高速・低遅延に処理することが可能です。アプリケーション開発のために、多くのシステム開発者に馴染みが深いC言語およびPython言語向けのAPI(Application Interface)関数が提供されます。ユーザーはソフトウェア記述だけで本マシンを活用したリアルタイムシステムを開発することが可能です。
オンプレミス版のシミュレーテッド分岐マシン™は、2021年2月に米国オンライン科学雑誌「Science Advances」に論文が掲載され、同月当社が公表した、最新版の第二世代のSBアルゴリズム(*7)を実装しており、同論文に掲載された世界最速実証データ(*7)と同等(*10)の速度性能を有します（図2）。また、本マシンはリアルタイムシステム内部に組み込む形態で搭載されるためにホストシステムと本マシンとの間の通信遅延時間も最小化されます。
図2： オンプレミス版のシミュレーテッド分岐マシン™の速度性能
さらに、今般、当社はユーザーによるシステム開発を促進するため、運転支援・緊急時等における最短巡回経路表示・金融取引の3つの参照例を合わせて開発しました。これらの参照例を予めパッケージすることでユーザーは革新的なリアルタイムシステムの開発を効率的に進めることができます。
具体的には参照例は以下の3つです（図3）。
当社グループは、量子コンピュータ理論から生まれた、組合せ最適化問題を解く量子インスパイア(*1)最適化計算機である「シミュレーテッド分岐マシン™」において、オンプレミス版(*2)を開発し、研究用途向けに提供を開始しました。本マシンは、低遅延インターフェースを備え、決められた時間内（デッドラインまで）に処理を完了させる「リアルタイムシステム」への組込みが可能な世界初の量子インスパイア最適化計算機です。金融をはじめ産業ロボットや災害時緊急対応システムなど高速なリアルタイム応答が要求されるシステムに本マシンを組み込むことで、刻々と変化する状況において瞬時にすべての選択肢の中から最良な１つを選び、それに基づく最適な応答をすることが可能となります。
情報処理システムの構築において、「オンプレミス」は自社内でシステムを保有・運用することを指します(*2)。外部サーバーを経由する「クラウド」がビッグデータの処理に適している一方で、「オンプレミス」はインターネット回線に接続する必要がないため、より高速な応答が求められるシステムへの適用が期待されます。
今回開発したオンプレミス版は、運転支援・災害時等の最短巡回経路表示・金融取引の3つの参照例（リファレンスデザイン）(*3)を予めパッケージしており、ユーザーは自身のシステム開発を効率的に進めることができます。
なお、開発したオンプレミス版のシミュレーテッド分岐マシン™は、東芝デジタルソリューションズ株式会社を販売窓口として、お客様が革新的なリアルタイム応用システムを試作・実証するために、研究用途向けに提供を開始しています。
オンプレミス版のシミュレーテッド分岐マシン™を搭載したデスクトップ型アプリケーション開発機
開発の背景
金融取引の最適化(*4)、産業用ロボットの動作の最適化、移動経路や送電経路の最適化など、社会や産業における課題の多くは、膨大な選択肢から最適なものを選び出す組合せ最適化に帰着します。組合せ最適化は、問題の規模が大きくなるにつれて組合せパターンの数が指数関数的に増大するため、既存の計算機で高速に解くことは困難です。このため、組合せ最適化専用計算機の開発が国内外で活発に行われています。
当社グループは、独自の量子コンピュータ理論から生まれ、全く新しい解の探索原理で組合せ最適化問題を解く量子インスパイア最適化計算理論として、シミュレーテッド分岐アルゴリズム（以下、SBアルゴリズム）を2019年4月に初めて発表 (*5)しました。その後、2019年7月に、本SBアルゴリズムを搭載したシミュレーテッド分岐マシン™のクラウド版をAWS Marketplace上に公開し(*6)、実証を進めるとともに、2021年2月には、SBアルゴリズムの速度・精度・規模を大幅に向上させた、第二世代となるSBアルゴリズムの開発を公表しました(*7)。
シミュレーテッド分岐マシン™を利用する方法は、「クラウド」に加え、「オンプレミス」があります。クラウドは導入が容易で、ビッグデータを扱う大規模計算に適していますが、インターネット回線で接続するため、オンプレミスと比較すると応答スピードが遅くなります。より瞬時の計算が求められる運転支援や金融取引といった分野においては、わずかな時間でも結果に影響が出るため、リアルタイムの応答性が実現できるオンプレミス版の開発が求められていました。
従来技術と課題
解決すべき組合せ最適化問題の中には、高速な最適化の計算能力に加え、高速・リアルタイムな応答性が求められるものがあります。特に運転支援、災害時緊急避難経路、金融取引などは、刻々と変化する外部環境や状況を継続的にセンシング・モニタリングし、変化に応じた対応アクションの決定、そのアクションの実行といった一連の作業の時間（応答時間）を短縮することが不可欠です。
オンプレミス化（組込みシステム化）によりリアルタイムの応答性の実現が可能ですが、既存のリアルタイムシステムの機能を阻害せずシミュレーテッド分岐マシン™を組み込む必要があります。また、高速な組合せ最適化とリアルタイム応答性を両立させ、周囲の変化に応じて最も合理的な判断を瞬時に下すリアルタイムシステムはこれまでにない新しいコンセプトであり、広く社会実装するためには実証実験を重ねる必要があります。
開発した技術
そこで当社は、既存のリアルタイムシステムの機能を阻害することなく組込み可能なオンプレミス版のシミュレーテッド分岐マシン™を開発しました。本マシンはSBアルゴリズムを高速に処理する専用回路(*7,8)の構成データとして提供され、ユーザーはその回路構成データで市販のFPGA（Field-Programmable Gate Array、書換え可能論理回路）ボードを再構成する（書換える）ことで本マシンを容易に完成させることができます(*9)。
ユーザーは、FPGAボードを搭載した様々な機器（Linux OSの汎用計算機)上で、シミュレーテッド分岐マシン™を搭載したリアルタイムシステムを構築することができます。ユーザーが取り組む社会課題に含まれる様々な組合せ最適化問題を、シミュレーテッド分岐マシン™を用い高速・低遅延に処理することが可能です。アプリケーション開発のために、多くのシステム開発者に馴染みが深いC言語およびPython言語向けのAPI(Application Interface)関数が提供されます。ユーザーはソフトウェア記述だけで本マシンを活用したリアルタイムシステムを開発することが可能です。
図1：オンプレミス版のシミュレーテッド分岐マシン™
オンプレミス版のシミュレーテッド分岐マシン™は、2021年2月に米国オンライン科学雑誌「Science Advances」に論文が掲載され、同月当社が公表した、最新版の第二世代のSBアルゴリズム(*7)を実装しており、同論文に掲載された世界最速実証データ(*7)と同等(*10)の速度性能を有します（図2）。また、本マシンはリアルタイムシステム内部に組み込む形態で搭載されるためにホストシステムと本マシンとの間の通信遅延時間も最小化されます。
図2： オンプレミス版のシミュレーテッド分岐マシン™の速度性能
さらに、今般、当社はユーザーによるシステム開発を促進するため、運転支援・緊急時等における最短巡回経路表示・金融取引の3つの参照例を合わせて開発しました。これらの参照例を予めパッケージすることでユーザーは革新的なリアルタイムシステムの開発を効率的に進めることができます。
具体的には参照例は以下の3つです（図3）。
- 複数物体追跡（運転支援等）
自動運転やロボット制御システム等への適用を想定した複数物体追跡です。周囲の物体を追跡する事で自動車やロボットの最適な制御へとつなげます。1秒間に30フレーム以上の画像を含むリアルタイム動画を処理し、複数の物体を区別し追跡します。本マシンは、1フレームごとに組合せ最適化問題を解いて、フレーム間の複数オブジェクトのマッチング問題（最も尤もらしい対応関係の特定問題）を解決します。
- ユーザーインタラクティブな最短巡回経路表示（緊急時避難経路最適化等）
配送ルート探索をはじめ災害時の緊急対応システム等への適用を想定した、ユーザーとインタラクティブな最短巡回経路表示です。組合せ最適化問題として有名な「巡回セールスマン問題」(*11)を解き、すべての訪問ポイントを1度だけ通る経路の内、距離が最短のものを見つけます。ユーザーはマウス操作で訪問ポイントを移動させることができ、位置を決定した瞬間に、その新しい状況に最適な経路を即座に見つけます。このように刻々と変化する状況のなかで、常に最適な経路を表示することが可能です。
- ストリームデータ処理型の最大独立集合検出(リアルタイム金融ポートフォリオ最適化等)
金融取引システム等への適用を想定しています。多くの株式を含む集合の中から互いに相関が低い株式の集合を見つけ出す学術問題(*12)を具体例に、相互に相関が低いために個別の銘柄の値動きに全体が左右されない安定な株式ポートフォリオを算出します。刻一刻と変化する株式市場のデータを逐次取り込み、その都度安定なポートフォリオを出力することが可能となります（ストリームデータ処理）。本参照例は、従来手法（近似解ソルバ）よりも高速かつ高精度な解を連続的に算出します。
図3： オンプレミス版のシミュレーテッド分岐マシン™により可能となるリアルタイムシステムの参照例（リファレンスデザイン）
動画1： オンプレミス版のシミュレーテッド分岐マシン™セットアップデモ
動画2： 自動運転やロボット制御システム等への適用を想定した複数物体追跡の説明
動画3： 配送ルート探索をはじめ災害時の緊急対応システム等への適用を想定した、ユーザーとインタラクティブな最短巡回経路表示の説明
動画4： 個別の銘柄の値動きに全体が左右されない安定な株式ポートフォリオの算出等を想定したストリームデータ処理型の最大独立集合検出の説明
今後の展望
今回開発したオンプレミス版のシミュレーテッド分岐マシン™は、東芝デジタルソリューションズ株式会社を販売窓口として、お客様が革新的なリアルタイム応用システムを試作・実証するために、研究用途に限定して2021年3月から順次提供を開始しています。当社および東芝デジタルソリューションズ株式会社は、オンプレミス版のシミュレーテッド分岐マシン™の提供を通じて、様々な分野で革新的な瞬時最適応答システムをパートナー様・お客様と共創し、効率的で持続可能な社会の実現に貢献していきます。
*1 量子力学の原理に基づく計算手法から導出もしくは直接的な着想を得て開発された新しい古典力学的手法のこと。疑似量子と呼ばれることもある。
*2 現場設置もしくは所有の可能な形態。遠隔設置・共有であるクラウドコンピューティングの形態としばし対比される。
*3 参照例（リファレンスデザイン）：本マシンは応用システムの部分を構成するモジュールとなる。本マシンを活用する応用システムの構成例（サンプルコード）のこと。
*4 東芝プレスリリース(2019年10月)：http://www.toshiba.co.jp/rdc/detail/1910_02.htm; K. Tatsumura et al., IEEE Int’l Symp. on Circuits and Systems (ISCAS), 1-5 (2020). https://doi.org/10.1109/ISCAS45731.2020.9181114
*5 東芝プレスリリース(2019年4月)：https://www.toshiba.co.jp/rdc/detail/1904_01.htm; H. Goto et al., Science Advances 5, eaav2372 (2019)： https://advances.sciencemag.org/content/5/4/eaav2372
*6 東芝デジタルソリューションズ株式会社プレスリリース(2019年7月)：https://www.toshiba-sol.co.jp/news/detail/20190717.htm
*7 東芝プレスリリース(2021年2月)：http://www.toshiba.co.jp/rdc/detail/2102_02.htm; H. Goto et al., Science Advances 7, eabe7953 (2021)：https://advances.sciencemag.org/content/7/6/eabe7953
*8 東芝プレスリリース(2019年9月)：http://www.toshiba.co.jp/rdc/detail/1909_03.htm; K. Tatsumura et al., IEEE Int'l Conf. on Field-Programmable Logic and Applications (FPL), 59-66 (2019). https://doi.org/10.1109/FPL.2019.00019
*9 当社グループはオンプレミス版シミュレーテッド分岐マシンTMの規模と速度をさらに向上させるマルチFPGA実装技術を既に発表しています。今回提供を開始するオンプレミス版はシングルFPGA実装の構成に限ります。東芝プレスリリース(2021年3月)：https://www.toshiba.co.jp/rdc/detail/2103_01.htm; K. Tatsumura et al., Nature Electronics 4, (2021). https://doi.org/10.1038/s41928-021-00546-4
*10 論文[H. Goto et al., Science Advances 7, eabe7953 (2021)]掲載のFPGA実装のシミュレーテッド分岐マシンTM のデータと比べて80%以上の速度性能
*11 巡回セールスマン問題：訪問すべき地点が複数ある時に、すべての訪問地点を1度だけ通る経路の内、距離が最短のものを見つける問題。この問題は、巡回セールスマン問題と呼ばれ、計算困難問題クラスに属す最も有名な組合せ最適化問題である。
*12 S.Butenko, Maximum independent set and related problems, with applications, Doctor Dissertation, 2003.
