japan

東芝トップページ > 企業情報 > 研究開発・技術 > 研究開発センター > 研究開発ライブラリ > 世界最速・最大規模の組合せ最適化計算機「シミュレーテッド分岐マシン」の速度・精度・規模を大幅に向上させる新アルゴリズムを開発 −疑似量子効果などによって大規模問題の約10倍の高速化、最適解の獲得、100万変数への規模拡大を実現し、創薬や金融など幅広い社会課題の解決に貢献−

ナノ材料
情報通信プラットフォーム

世界最速・最大規模の組合せ最適化計算機「シミュレーテッド分岐マシン」の
速度・精度・規模を大幅に向上させる新アルゴリズムを開発
−疑似量子効果などによって大規模問題の約10倍の高速化、最適解の獲得、
100万変数への規模拡大を実現し、創薬や金融など幅広い社会課題の解決に貢献−

2021年2月4日
株式会社東芝
東芝デジタルソリューションズ株式会社

概要

株式会社東芝(以下、東芝)および、東芝デジタルソリューションズ株式会社(以下、TDSL)は、新薬の開発、配送ルート計画や投資ポートフォリオの作成など、様々な社会課題に現れる組合せ最適化問題を解く東芝独自の「シミュレーテッド分岐マシン」の速度・精度・規模を大幅に向上させることができる2つの新アルゴリズムを開発しました。新アルゴリズムは、東芝が2019年4月に発表した「シミュレーテッド分岐アルゴリズム」(注1)を疑似量子トンネル効果(注2)などにより発展させたもので、短時間で良解(高精度な近似解)を見つける高速アルゴリズムと、より高精度な解を見つける高精度アルゴリズムの2種類です。
新アルゴリズムにより、発表当時世界最速を記録した従来アルゴリズム(注1)に比べて約10倍の高速化を達成するともに、より大規模な問題の最適解獲得に成功しました。また、16台のGPU(注3)から成る世界最大規模の100万変数のマシンを実現し、通常の計算機で約1年2か月かかる大規模な計算を約30分で行うことに成功しました。
本技術は、例えばコロナ禍において必要となる治療薬の開発や医療従事者の最適な勤務シフトの作成など、今まさに求められている社会課題への応用が期待されます。
本技術の成果は、2021年2月3日付(米国東海岸時間)の米国オンライン科学雑誌「Science Advances」に掲載されました(注4)

開発の背景

社会や産業における様々な活動を効率的に行うためには、膨大な数の選択肢から最適なものを見つけ出す必要があります。例えば昨今のコロナ禍においては、治療薬に最適な候補物質の選定、医療従事者の最適な勤務シフト作成、患者の最適な搬送先選定などが挙げられます。こうした問題の多くは、数学的には組合せ最適化問題と呼ばれるものに帰着します。組合せ最適化問題は、問題の規模によって解の候補の数が指数関数的に増加する、いわゆる組合せ爆発のために解くことが大変難しい問題として知られており、組合せ最適化専用計算機の研究開発が国内外で活発に行われています。大規模な組合せ最適化問題を高速に解くことができる計算機を開発できれば、より効率的な社会や産業の実現に貢献できるものと期待されています。
東芝は2019年4月、シミュレーテッド分岐アルゴリズムという独自の組合せ最適化アルゴリズムを発表しました(注1)。本アルゴリズムを搭載した「シミュレーテッド分岐マシン」は、本アルゴリズムが有する高い並列性を活かすことで大規模な組合せ最適化問題の良解を非常に高速に得ることができます。しかし、古典力学における断熱過程(注5)に基づく従来のアルゴリズム(「断熱的シミュレーテッド分岐アルゴリズム(aSB)(注6)」)は、大規模問題の最適解(厳密解)が得られない場合がありました。

本技術の特徴

今回、東芝とTDSLは、従来の断熱的シミュレーテッド分岐アルゴリズムを発展させることにより、より高速に、より高精度に組合せ最適化を実行できる2つのアルゴリズムを新たに開発しました。
1つ目は、短時間で良解を見つける高速アルゴリズム「弾道的シミュレーテッド分岐アルゴリズム(bSB)(注7)」です。従来のaSBで生じるエラーを低減する工夫により、シミュレーテッド分岐マシンの高速化と高精度化を実現しました。これをFPGA(注8)で高速実装することで、2,000変数問題の良解を従来のシミュレーテッド分岐マシン(注1)に比べて約10倍高速に得ることができます(図1)。
2つ目は、他のマシンを凌ぐ計算速度でより高精度な解を見つける高精度アルゴリズム「離散的シミュレーテッド分岐アルゴリズム(dSB)(注9)」です。疑似量子トンネル効果によって古典力学の限界を打破してさらなる高精度化を実現し、同じ2,000変数問題の最適解(厳密解の推定値)を得ることができます。これをFPGAで高速実装した2,048変数対応シミュレーテッド分岐マシンは、最適解を得るのにかかる計算時間で量子アニーラやコヒーレントイジングマシンなど他のマシンを凌駕する高速性を達成しました(図2)。また、16台のGPU(注3)からなるGPUクラスタを用いることで100万変数という世界最大規模のマシンを実現し、約30分で最適解にほぼ到達できました(図3)。これは、最適化問題を解くための一般的な手法であるシミュレーテッドアニーリングを通常の計算機(CPU)上で実行した場合およそ1年2か月かかる計算を30分という現実的な時間に短縮したこと(約2万倍の高速化)を意味します。
実社会の問題に適用する際は、即時に良解が必要な場合はbSB、時間をかけてでも極めて精度の高い解が必要な場合はdSB等といった用途に応じた使い分けが想定されます。

図1:今回開発したシミュレーテッド分岐マシンbSBM(注7)と従来のシミュレーテッド分岐マシンaSBM(注3)(CIM(注10)の約10倍高速)を2,000変数問題で比較(注4)

図2:dSBM(注7)と他のマシンを様々な問題の最適解獲得にかかる計算時間で比較(注4)

図3:100万変数問題の計算時間測定結果(注4)

今後の展望

東芝とTDSLは、今回開発した新たなシミュレーテッド分岐アルゴリズムを活用して、FPGAを用いたオンプレミス版およびGPUを用いたクラウド版のシミュレーテッド分岐マシンを2021年中にサービス提供し、効率的で持続可能な社会の実現に貢献していきます。

(注1)東芝プレスリリース:https://www.toshiba.co.jp/rdc/detail/1904_01.htm; H. Goto, K. Tatsumura, A. R. Dixon, Science Advances 5, eaav2372 (2019). https://advances.sciencemag.org/content/5/4/eaav2372

(注2)量子力学で知られるトンネル効果(古典力学では越えられないポテンシャル障壁を透過する現象)を、古典力学のシミュレーションにおいてエネルギー保存則を意図的に破ることにより疑似的に実現したもの。

(注3)Graphics Processing Unitの略称。画像処理向け集積回路で,多数の演算処理部を含む。複数のGPUを相互接続したものをGPUクラスタと呼ぶ。

(注4)H. Goto et al., Science Advances Vol. 7, no. 6, eabe7953 (2021) https://advances.sciencemag.org/content/7/6/eabe7953

(注5)力学系において、系のパラメータがゆっくりと変化するとき、エネルギーの低い状態に留まり続ける現象。

(注6)adiabatic Simulated Bifurcation (aSB)。古典力学における断熱過程を原理として利用することから、このように呼ぶ。また、aSBをデジタル計算機上に実装したマシンを「aSB Machine (aSBM)」と呼ぶ。

(注7)ballistic Simulated Bifurcation (bSB)。力学的な振る舞いが弾道的であることから、このように呼ぶ。また、aSBをデジタル計算機上に実装したマシンを「bSB Machine (bSBM)」と呼ぶ。

(注8)Field-Programmable Gate Arrayの略称。演算処理集積回路の一種で,製造後にユーザーが用途に応じて機能を書き換えることが可能。

(注9)discrete Simulated Bifurcation (dSB)。運動方程式において連続値を離散値で置き換えることから、このように呼ぶ。また、dSBをデジタル計算機上に実装したマシンを「dSB Machine (dSBM)」と呼ぶ。

(注10)コヒーレントイジングマシン(Coherent Ising Machine)。T. Inagaki et al., Science 354, 603 (2016)。


  • 「研究開発センター」のトップへ
  • このページのトップへ