東京工業大学(東工大)と科学技術振興機構(JST)の両者は2月18日、従来にない複数の計算原理を使い分ける仕組みを持ち、「組み合わせ最適化問題」を高速・高効率で解決するアニーリングプロセッサを新たに開発したことを共同で発表した。

同成果は、東工大 科学技術創成研究院の川村一志特任助教、同・劉載勲准教授、同・小此木大輝大学院生、同・神保聡大学院生、同・井上源太大学院生、同・兵藤旭大学院生、同・Ángel López García-Arias大学院生、北海道大学の安藤洸太助教、同・Bruno Hideki Fukushima-Kimura大学院生、京都大学の安戸僚汰助教、東工大のThiem Van Chu助教、同・本村真人教授らの共同研究チームによるもの。詳細は、米国サンフランシスコで2月23日(現地時間)まで開催中の国際固体素子回路会議「ISSCC 2023」にて発表される。

組み合わせ最適化問題を高速・高効率で扱えるアニーリングマシンの開発において、現在は実用化の観点から、全結合型のイジングモデルを扱える性能が求められている。それが可能なプロセッサとしては、同研究チームがISSCC2020で発表した「STATICA」や、富士通の「デジタルアニーラ」などがある。これらは、高い電力効率で高速に組み合わせ最適化問題を解けるが、実用化の観点では計算効率、電力効率、スケールアップの面でさらなる進歩が求められているという。

そこで今回の研究では、既存のアニーリングマシンが異なる計算原理に基づいて動作し、それぞれの求解速度や動作の安定性が問題の性質によって変化しうる点に注目したとする。そして、求解対象の問題をどの計算原理・マシンで解くのがベストであるかをまず解明し、問題に応じて計算原理を最適化することで、より実用的なアニーリングマシンを実現するというものである。

まず、既存の計算原理である「SA」(1ステップで1スピンのみ更新)と「SCA」(1ステップで全スピンを並列に更新可能)の2種類を対象に、問題と計算原理の相関が調査された。この結果、SCAの方が少ないステップ数で高速に収束することが期待されたが、問題によってはSCAの収束が安定せず、SAの方が結果として高速に収束するような事例も観測されたという。

さらに調査が進められた結果、更新対象を全スピンから一部スピンへと制限することで、収束が格段に安定することが発見された。この発見を基に、並列スピン更新による高速性と収束の安定性を兼ね備えた新しい計算原理「Ratio-controlled Parallel Annealing(RPA)」が構築された。RPAは、更新対象のスピン数を調整するためのパラメータε(イプシロン)を持ち、問題に合わせてスピン更新の並列度を最適化することが可能な計算原理となっているとする。

続いて、上述の3種類に富士通デジタルアニーラの計算原理「Digital Annealing(DA)」も加えて調査が行われた。DAは、SA同様の1ステップ1スピン更新型だが、全スピンに対する並列フリップ判定後にフリップ可能なスピンを選択することで、SAの弱点である収束の遅さが改善されている。こうした調査の結果、最適な計算原理は求解対象の組み合わせ最適化問題によって異なることが確認されたとした。

  • (上)組み合わせ最適化問題(イジングモデル)と最適計算原理の相関調査。128スピンイジングモデル(a)、SAとSCAの比較(b)、SA・DA・SCA・RPAの比較(c)。(下)SAとSCAから導かれる新しい計算原理RPA

    (上)組み合わせ最適化問題(イジングモデル)と最適計算原理の相関調査。128スピンイジングモデル(a)、SAとSCAの比較(b)、SA・DA・SCA・RPAの比較(c)。(下)SAとSCAから導かれる新しい計算原理RPA(出所:JSTプレスリリースPDF)

4種類の計算処理に着目すると、全スピンを並列にフリップ判定した後、計算原理に応じて実際にフリップさせるスピンを選択するような処理の流れとすることで、フリップ判定回路を共通化することができるという。また、フリップスピン選択回路も、乱数生成器付き循環シフタ、マスカ、プライオリティエンコーダの組み合わせにより同一構成で実現できることが発見された。