問題に応じて計算手法を選択・最適化するアニーリングマシンを開発

東京工業大学 科学技術創成研究院の本村真人教授（情報通信コース 主担当）、川村一志特任助教らは、北海道大学、京都大学と共同で、スマート社会の発展に不可欠な組合せ最適化問題^[用語1]を高効率に解決するアニーリングプロセッサ^[用語2]LSI^[用語3]を新規に開発した。

国内外でのアニーリングマシン研究開発競争が激化する昨今、求解対象の組合せ最適化問題をどの計算原理・マシンで解くのがベストであるのかを明確にし、アニーリングマシンの早期実用化を進めることが求められている。本研究では、問題の性質と最適な計算原理の相関を調査するとともに、複数の計算原理を選択的に利用可能な計算機構造、ならびに、それを具現化したプロセッサLSI「Amorphica」を開発した。求解対象の問題に合わせて計算原理を選択できるようにすることで、多様な問題に対して最適な計算原理を適用することが可能になる。さらに、本LSIを複数個接続することで大規模な問題を求解可能である。AmorphicaをGPU（画像処理半導体）と比較したところ、最大58倍の高速化を達成するとともに、およそ3万倍の電力効率を達成した。

研究成果の詳細は2月19日～23日に米国サンフランシスコで開催される「ISSCC 2023（国際固体素子回路会議）」にて発表される（発表者：川村一志）。ISSCCは集積回路に関する最難関国際会議で、世界中から最高峰の研究成果が発表される。

組合せ最適化問題とは、無数の選択肢（変数の値の組）の中から最良の解を探し出す問題であり、金融、物流、創薬、人工知能といったさまざまな分野に登場する問題であることから、その解決は今後のスマート社会の発展に不可欠である。数ある組合せ最適化問題を高速、高効率に解くための方法として、アニーリングマシン（イジングマシン）が注目されている。アニーリングマシンはナチュラルコンピューティング技術のひとつで、自然現象を応用した計算手法により組合せ最適化問題を解く。より具体的には、求解対象の問題を磁性体の性質を表すモデル（イジングモデル^[用語4]）に見立て、そのモデルが持つスピンの挙動を計算機上で擬似的に再現するという発想のもと開発されてきた計算機である。実用化の観点からは特に、全結合型^[用語5]のイジングモデルを扱うアニーリングマシンが求められている。

現在までにさまざまなアニーリングマシンが開発され、実用化に向けた競争が激化している。中でも本研究チームがISSCC 2020で発表したSTATICA^[注1]や、富士通が開発するデジタルアニーラは、全結合型のイジングモデルを扱うことのできるアニーリングプロセッサLSIであり、高い電力効率で高速に組合せ最適化問題を解く。しかし、実用化の観点からは計算効率、電力効率、スケールアップの面でさらなる進歩が求められる。

本研究では、既存のアニーリングマシンが異なる計算原理に基づいて動作し、それぞれの求解速度や動作の安定性が問題の性質によって変化しうる点に注目した。すなわち、求解対象の問題をどの計算原理・マシンで解くのがベストであるかを解明し、問題に応じて計算原理を最適化することができれば、より実用的なアニーリングマシンが実現できるものと考えた。この考えのもと、本研究チームは（1）組合せ最適化問題の性質と最適な計算原理の相関を調査し、（2）複数の計算原理を選択的に利用可能な計算機構造を設計した。さらに、（3）LSIを設計・試作することでアニーリングプロセッサを具現化し、GPUとの比較により計算の高速化と省エネ化を実証した。

本研究ではまず、既存の計算原理であるSA（Simulated Annealing）とSCA（Stochastic Cellular Automata Annealing）を用いて性質の異なる問題（図1a）を複数解き、問題と計算原理の相関を調査した。図2に示すように、SAが1ステップに1スピンのみを更新するのに対し、SCAは1ステップで全スピンを並列に更新できるため、SCAの方が少ないステップ数で高速に収束することが期待される。ところが、問題によってはSCAの収束が安定せず、SAの方が結果として高速に収束するような事例が観測された（図1b）。さらに調査を進めていくと、更新対象を全スピンから一部スピンへと制限することで収束が格段に安定することを発見した。この発見を基に、並列スピン更新による高速性と収束の安定性とを兼ね備えた新しい計算原理RPA（Ratio-controlled Parallel Annealing）を構築した（図2）。RPAは更新対象のスピン数を調整するためのパラメータεを持ち、問題に合わせてスピン更新の並列度を最適化可能な計算原理となっている。

続いて、先に紹介したSA、SCA、RPAに加え、富士通デジタルアニーラの計算原理であるDA（Digital Annealing）を対象に、問題の性質と最適な計算原理の相関を調査した。DAは1ステップに1スピンを更新する点でSAと共通するが、全スピンに対する並列フリップ^[用語6]判定の後にフリップ可能なスピンを選択することでSAの弱点である収束の遅さを改善している。この調査の結果、図1cの結果が得られ、最適な計算原理は求解対象の組合せ最適化問題によって異なることを確認した。

SA、SCA、RPA、DAの計算処理に着目すると、その処理過程には共通化できる部分が存在する。具体的には、全スピンを並列にフリップ判定した後、計算原理に応じて実際にフリップさせるスピンを選択するような処理の流れとすることで、フリップ判定回路を共通化できる。また、フリップスピン選択回路も、乱数生成器付き循環シフタ、マスカ、プライオリティエンコーダの組み合わせにより同一構成（図3）で実現できることを発見した。今回の研究で設計したAmorphica（Metamorphic Annealer）は、図3の構成を核に持ち、求解対象の問題に応じて4種の計算原理を使い分けることのできるアニーリング計算機構造である。Amorphicaは全結合型のイジングモデルに対し、スピンを逐次的にも並列にも更新可能であり、安定性と高速性のバランスを保ったアニーリング処理を実現する。

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

1. 図3.Amorphicaアーキテクチャの核となるフリップスピン選択回路。 循環シフタで入力配列要素を乱数分だけ左に移動（あふれた要素は右端に移動）させ、マスカでマスク配列との要素積を計算する。最後に、プライオリティエンコーダを用いて最も左に位置する値1の要素のインデックスを抜き出す。

本研究チームは、アニーリングプロセッサLSI「Amorphica」をTSMC社の40 nmプロセスを用いて設計・試作した（図4）。チップサイズはわずか3 mm×3 mmで、単チップでは512スピンに対するアニーリング処理を4レプリカ並列で実行できる。その際の消費電力は最大でも500 mWに満たない。また、本チップはFPGAを介して最大4チップを接続可能であり、最大2,048スピンに対するアニーリング処理を実現する。

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

昨今、アニーリングマシンの実用化に向けて国内外での研究開発競争が活発化している。2011年に商用化に成功した超伝導量子アニーリングマシンD-Waveを火付け役として、量子アニーリングマシンとそれにインスパイアされた非量子アニーリングマシンが数多く開発されてきた。そのような中で、今回開発した複数の計算原理を使い分けることのできるアニーリングプロセッサLSI「Amorphica」は、従来の枠組みにはない発想に基づいて設計された、多様な組合せ最適化問題を解くことができる点をこれまで以上に強化する新しい計算機である。今後、Amorphicaを小型IoT機器などに組み込むことで、低電力ながら高速に解を探し出す汎用組合せ最適化ソルバとしての活躍が見込まれる。

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

• 付記

• 用語説明

• 注釈

• 発表情報

発表会議 :	International Solid-State Circuits Conference (ISSCC) 2023
講演セッション :	Session 2 – Digital Processors
講演日時 :	現地時間2月20日午後2時30分
講演タイトル :	Amorphica: 4-Replica 512 Fully Connected Spin 336MHz Metamorphic Annealer with Programmable Optimization Strategy and Compressed-Spin-Transfer Multi-Chip Extension
著者 :	川村一志（共同主著、発表者、東工大 特任助教）、劉載勲（共同主著、同 准教授）、小此木大輝（同 修士課程2年）、神保聡（同 修士課程2年）、井上源太（同 修士課程1年）、兵藤旭（同 学士課程4年）、Ángel López García-Arias（同 博士後期課程2年）、安藤洸太（北海道大学 助教）、Bruno Hideki Fukushima-Kimura（同 博士研究員）、安戸僚汰（京都大学 助教）、Thiem Van Chu（東工大 助教）、本村真人（同 教授）
ISSCC会議情報 :	2023 International Solid-State Circuits Conference (ISSCC)
タイムテーブル :	Conference Timetable | ISSCC