東工大ニュース

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

対GPU比3万倍の電力効率を達成

RSS

公開日:2023.02.22

要点

  • 組合せ最適化問題の性質と最適なアニーリング計算原理の相関を調査
  • 複数の計算原理を選択的に利用できる計算機構造を設計
  • アニーリングプロセッサLSIを試作し、計算の高速化と省エネ化を実証

概要

東京工業大学 科学技術創成研究院の本村真人教授、川村一志特任助教らは、北海道大学、京都大学と共同で、スマート社会の発展に不可欠な組合せ最適化問題[用語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との比較により計算の高速化と省エネ化を実証した。

(1)組合せ最適化問題の性質と最適な計算原理の相関調査

本研究ではまず、既存の計算原理である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の結果が得られ、最適な計算原理は求解対象の組合せ最適化問題によって異なることを確認した。

図1 組合せ最適化問題(イジングモデル)と最適計算原理の相関調査

図1. 組合せ最適化問題(イジングモデル)と最適計算原理の相関調査

図2 SAとSCAから導かれる新しい計算原理RPA

図2. SAとSCAから導かれる新しい計算原理RPA

(2)計算機構造設計

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

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

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

(3)LSIの試作とその評価

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

図4 アニーリングプロセッサLSI「Amorphica」

図4. アニーリングプロセッサLSI「Amorphica」

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

図5 AmorphicaとGPUの比較

図5. AmorphicaとGPUの比較

社会的インパクト

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

今後の展開

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

付記

本研究開発は、以下の助成事業により推進されたものである。
科学技術振興機構(JST)戦略的創造研究推進事業CREST「Society5.0を支える革新的コンピューティング技術」
研究総括:坂井修一(東京大学 教授)
研究課題名:「学習/数理モデルに基づく時空間展開型アーキテクチャの創出と応用」(JPMJCR18K3)
研究代表者:本村真人(東京工業大学 科学技術創成研究院 教授)

用語説明

[用語1] 組合せ最適化問題 : 一例として、倉庫から各顧客にどの順番で荷物を配送すれば最も効率的かを決める「配送計画問題」があり、物流分野に必要不可欠な問題である。変数の数(顧客数や使用するトラックの台数など)が増えると選択肢が爆発的に増加するため、従来型の計算機では効率的に解くことが難しい。

[用語2] アニーリングプロセッサ : アニーリング計算を活用して組合せ最適化問題を解く計算機のことで、計算原理の違いから「量子型」と「非量子型」が存在する。本研究では一般的な集積回路で実現される非量子型を対象としている。非量子型のアニーリングプロセッサでは、金属工学焼きなまし法(=時間をかけて冷却することで、金属原子の並び方を最適にする)に着想を得た計算技法に基づいて近似的に組合せ最適化問題を解く。

[用語3] LSI : Large-Scale Integration(大規模集積回路)の頭文字で、多数の回路素子を1枚の基盤に集積したもの。LSIチップないしはチップとも呼ぶ。

[用語4] イジングモデル : アニーリングマシンの入力形式であり、+1または-1を取る二値の変数(スピンと呼ばれる)の集合体とそれらスピン間の相互作用群から成るモデルである。上向きのスピンが+1、下向きのスピンが-1を表す。変数の値(スピンの向き)の組に応じて系のエネルギーが一意に定まる。多くの組合せ最適化問題はイジングモデルのエネルギー最小化問題に等価変換できることが知られている。

[用語5] 全結合型 : イジングモデルにおいて、スピン集合体の中で制限なく相互作用を許すものを「全結合型」と呼ぶ。対して、相互作用が近接するスピン間に限られているものを「局所型」と呼ぶ。組合せ最適化問題をイジングモデルに変換する際に、局所型では十分な表現能力がないため、現実社会の複雑な問題に対応することが難しい。そのため、全結合型のイジングモデルを扱えるアニーリングマシンが強く求められる。

[用語6] フリップ : スピンが上向きから下向き、または、下向きから上向きに変化する動作を指す。

[用語7] 最大カット問題 : 重み付きグラフのノードを2グループに分割するとき、カットされるエッジの重みの総和が最大となるような分割を求める問題である。本問題はイジングモデルの最小エネルギーを与えるスピンの組を探し出す問題と等価であるため、アニーリングマシンの標準的なベンチマークによく用いられる。

発表情報

発表会議 :
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会議情報 :
タイムテーブル :

お問い合わせ先

東京工業大学 科学技術創成研究院 AIコンピューティング研究ユニット

教授 本村真人

Email motomura@artic.iir.titech.ac.jp
Tel / Fax 045-924-5654

取材申し込み先

東京工業大学 総務部 広報課

Email media@jim.titech.ac.jp
Tel 03-5734-2975 / Fax 03-5734-3661

科学技術振興機構 広報課

Email jstkoho@jst.go.jp
Tel 03-5214-8404 / Fax 03-5214-8432

JST事業に関する問い合わせ先

科学技術振興機構 戦略研究推進部 ICTグループ

前田さち子

Email crest@jst.go.jp
Tel 03-3512-3526 / Fax 03-3222-2066

RSS