東工大とJST、複数の計算原理を使い分けるアニーリングプロセッサを開発

●
東京工業大学(東工大)と科学技術振興機構(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の弱点である収束の遅さが改善されている。こうした調査の結果、最適な計算原理は求解対象の組み合わせ最適化問題によって異なることが確認されたとした。

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

●
そして求解対象の問題に応じて4種類の計算原理を使い分けられるアニーリング計算機構造として、「Metamorphic Annealer(Amorphica)」が設計された。Amorphicaは全結合型のイジングモデルに対し、スピンを逐次的にも並列にも更新可能であり、安定性と高速性のバランスを保ったアニーリング処理を実現できたという。

さらにAmorphicaのもう1つの大きな特長に、スケールアップが可能な点がある。全結合型のイジングモデルを分散アニーリングする場合、その過程で頻繁に同期処理が必要となり、その際の通信コストが大きな課題となる。今回の研究では、スピン更新情報を転送する過程に圧縮符号化を導入することで同課題が解決された(Amorphicaは復号回路を搭載)。

その後、TSMCの40nmプロセスを用いてAmorphicaが設計・試作された。チップサイズは3mm×3mmで、単チップでは512スピンに対するアニーリング処理を4レプリカ並列で実行可能。その際の消費電力は最大でも500mWに満たないとする。また、同チップはFPGAを介して最大4チップを接続可能であり、最大2048スピンに対するアニーリング処理を実現するとしている。

実際に同チップを4個接続したアニーリングシステムを用いて、4種類の「最大カット問題」を解いた結果、対GPU比で最大58倍の高速化が達成され、約3万倍の電力効率で同品質の解が得られることが確認された。

研究チームは、Amorphicaを小型IoT機器などに組み込むことで、低電力ながら高速に解を探し出す汎用組み合わせ最適化ソルバとしての活躍が見込まれるとした。

また同研究チームは今後、Amorphicaチップに基づくアニーリングシステムの早期実用化を目指すという。その中で、今回の研究で扱われた「組み合わせ最適化問題の性質と最適な計算原理の相関調査」をより広域な実応用問題へと拡張し、多様な組み合わせ最適化問題に適応できるようにすることが求められるとした。