大規模組合せ最適化問題のためのアニーリングプロセッサに関する研究
山本 佳生
2019 年度 卒 ／博士（工学）
平成30年度〜令和元年度 日本学術振興会特別研究員
博士論文の概要
本研究は、組合せ最適化問題を効率良く解くためのアニーリングプロセッサに関するものである。
スマート社会の実現には、交通網、電力網、人的資源の割り当てや経路といった人と物の最適化が必要不可欠である。これらの問題の多くは組合せ最適化問題と呼ばれ、現代社会においても非常に重要な問題として位置付けられている。しかし、組合せ最適化問題はNP困難であり、従来のノイマン型コンピュータで効率良く解くのは困難であることが知られている。近年は半導体チップを製造するプロセスの微細化も物理的な限界を迎えようとしている。したがって、特に全探索による求解は、コンピュータの計算速度による速度改善は見込めない。そのような背景から、組合せ最適化問題を専用回路を用いて高速かつ低消費電力で解くアプローチが注目を浴びている。
アニーリングプロセッサは、組合せ最適化問題の最適解とイジングモデルを用いて表現された最適化問題の基底状態が一致する性質を利用した汎用組合せ最適化ソルバーである。イジングモデルは、上向き下向きの状態を持つスピンとそのスピン間に生じるスピン間相互作用と各スピンに作用する外部磁場によって表現される統計物理における強磁性体のモデルである。これらのパラメータを用いて、制御対象やコストを表現することで、イジングモデルは組合せ最適化問題を表現することが可能である。アニーリングプロセッサは、再現するイジングモデルの形状によって最近傍型と全結合型の2つに分類される。最近傍型は、スピン間結合が近接スピン間のみに限定され、全結合型は、任意のスピン間に結合が存在する。最近傍型は、近接スピンを減らすことでシミュレーテッドアニーリングが要請するデータの依存関係を減らすことで高い並列処理を実現する。また、データ転送が隣接スピンに限定されるため、スケーラビリティに優れるという特徴を持つ。しかし、スピン間相互作用が疎であるため、対応可能な組合せ最適化問題のクラスが限定される、あるいは問題をハードウェアのイジングモデルに合うように変形処理を要するという問題点がある。全結合型は、スピン数が許す限りあらゆるクラスの問題を解くことが可能であるが、任意のスピン間を接続する必要があるため、スケーラビリティが低く、全てのスピンに対して依存関係が存在するため、一度に更新できるスピン数が全スピン数に依らず常に一つのみに限定される。そのため、基底状態への収束時間がかかる。
本論文では、上記のアニーリングプロセッサに対して、(1) 疎結合型をベースにとした空間展開型時分割処理機構アーキテクチャによるスピン数増大手法, (2) 疎結合型イジングネットワークを利用したより複雑なイジングネットワークへの適用手法と並列更新可能なアニーリング手法における疎結合型イジングネットワークを完全結合適用するためのアルゴリズム、および(3) 並列更新なアニーリングにおける全結合型のアニーリング プロセッサのアーキテクチャに関する研究を実施した。その概要と成果を以下にまとめる：
- 疎結合型に基づくスピン数増大手法は、初のCMOS型アニーリングプロセッサであるCMOS Annealingマシンをベースに研究を行った。CMOSアニーリングでは、スピンの状態とスピン間相互作用を保持するために分散メモリを用いているため、LUT数がネックとなりスピン数のスケーラビリティが低いという問題が存在した。その欠点に着目し、より密度の高いFPGAのブロックRAMに保存することを前提とした時分割処理機構を持つアーキテクチャを創出した。結果として、従来手法より大規模なスピン数によって形成される疎結合イジングネットワークを高密度で実装可能なことを示した。
- 前述の大規模組合せ最適化問題向けアーキテクチャをベースに、疎結合型の持つ対応可能な問題のクラスが限定されてしまうという問題を解決する手法に関して研究を行った。疎結合型イジングネットワークは、問題のネットワークとハードウェアグラフとの間にミスマッチが生じた場合、埋め込み処理と呼ばれる、アニーリングプロセッサのイジングモデルの形状に組合せ最適化問題のネットワークに合わせるグラフ変形が必要となる。しかし、グラフ変形により本来問題からは生じない強い強磁性接続を持つスピンが追加されるため、アニーリングの精度や収束速度に悪影響を与えることが問題点として考えられる。そこで、上記(1)の時分割アーキテクチャをベースに、仮想的にハードウェア上のイジングネットワークの複雑度を向上させる技術を開発し、精度と速度の低下無しで対応可能な問題のクラスを増やす手法を検討した。結果として、従来の疎結合型イジングネットワークで精度が低下する問題に対して、埋め込み処理によるアニーリングの精度と収束速度の低下を解消することが可能であるという結果を得た。しかし、疎結合イジングモデルを時分割アーキテクチャを用いて全結合イジングネットワークを再現しようとした場合、データの依存関係を解決するために、分割されたネットワークが時間方向に増えてしまい処理速度が低下してしまうという問題が存在することも明らかになった。そこで、全結合型イジングモデルにおいてもスピン状態を並列に更新可能な確率的セルオートマトンによりスピン状態をサンプリングし基底状態探索を行う新しいアニーリング技術と疎結合イジングネットワークで全結合イジングネットワークを再現するアルゴリズムに関する研究を行った。これらの研究により、疎結合イジングモデルと時分割アーキテクチャを用いて少ない分割数で全結合イジングネットワークの基底状態探索を高速に実現可能であることが明らかになった。
- 上記の並列更新アニーリングをベースに全結合型アーキテクチャに関する研究を行った。このアーキテクチャでは、並列に全てのスピンを更新した場合、更新毎に多くの積和演算が必要であるという問題点を解決するため、変化したスピンの相互作用のみに注目した処理により、他の手法と比較して高速に基底状態を得ることが可能である。また、実際に創出したアーキテクチャを元に専用回路を作成し、他のアニーリングプロセッサに対して、収束速度、消費電力といった指標における優位性を実際に確認した。