卒業生とその進路

大規模組合せ最適化問題のためのアニーリングプロセッサに関する研究


山本 佳生

2019 年度 卒 /博士(工学)
平成30年度〜令和元年度 日本学術振興会特別研究員

博士論文の概要

本研究は、組合せ最適化問題を効率良く解くためのアニーリングプロセッサに関するものである。

スマート社会の実現には、交通網、電力網、人的資源の割り当てや経路といった人と物の最適化が必要不可欠である。これらの問題の多くは組合せ最適化問題と呼ばれ、現代社会においても非常に重要な問題として位置付けられている。しかし、組合せ最適化問題はNP困難であり、従来のノイマン型コンピュータで効率良く解くのは困難であることが知られている。近年は半導体チップを製造するプロセスの微細化も物理的な限界を迎えようとしている。したがって、特に全探索による求解は、コンピュータの計算速度による速度改善は見込めない。そのような背景から、組合せ最適化問題を専用回路を用いて高速かつ低消費電力で解くアプローチが注目を浴びている。

アニーリングプロセッサは、組合せ最適化問題の最適解とイジングモデルを用いて表現された最適化問題の基底状態が一致する性質を利用した汎用組合せ最適化ソルバーである。イジングモデルは、上向き下向きの状態を持つスピンとそのスピン間に生じるスピン間相互作用と各スピンに作用する外部磁場によって表現される統計物理における強磁性体のモデルである。これらのパラメータを用いて、制御対象やコストを表現することで、イジングモデルは組合せ最適化問題を表現することが可能である。アニーリングプロセッサは、再現するイジングモデルの形状によって最近傍型と全結合型の2つに分類される。最近傍型は、スピン間結合が近接スピン間のみに限定され、全結合型は、任意のスピン間に結合が存在する。最近傍型は、近接スピンを減らすことでシミュレーテッドアニーリングが要請するデータの依存関係を減らすことで高い並列処理を実現する。また、データ転送が隣接スピンに限定されるため、スケーラビリティに優れるという特徴を持つ。しかし、スピン間相互作用が疎であるため、対応可能な組合せ最適化問題のクラスが限定される、あるいは問題をハードウェアのイジングモデルに合うように変形処理を要するという問題点がある。全結合型は、スピン数が許す限りあらゆるクラスの問題を解くことが可能であるが、任意のスピン間を接続する必要があるため、スケーラビリティが低く、全てのスピンに対して依存関係が存在するため、一度に更新できるスピン数が全スピン数に依らず常に一つのみに限定される。そのため、基底状態への収束時間がかかる。

本論文では、上記のアニーリングプロセッサに対して、(1) 疎結合型をベースにとした空間展開型時分割処理機構アーキテクチャによるスピン数増大手法, (2) 疎結合型イジングネットワークを利用したより複雑なイジングネットワークへの適用手法と並列更新可能なアニーリング手法における疎結合型イジングネットワークを完全結合適用するためのアルゴリズム、および(3) 並列更新なアニーリングにおける全結合型のアニーリング プロセッサのアーキテクチャに関する研究を実施した。その概要と成果を以下にまとめる:

  1. 疎結合型に基づくスピン数増大手法は、初のCMOS型アニーリングプロセッサであるCMOS Annealingマシンをベースに研究を行った。CMOSアニーリングでは、スピンの状態とスピン間相互作用を保持するために分散メモリを用いているため、LUT数がネックとなりスピン数のスケーラビリティが低いという問題が存在した。その欠点に着目し、より密度の高いFPGAのブロックRAMに保存することを前提とした時分割処理機構を持つアーキテクチャを創出した。結果として、従来手法より大規模なスピン数によって形成される疎結合イジングネットワークを高密度で実装可能なことを示した。
  2. 前述の大規模組合せ最適化問題向けアーキテクチャをベースに、疎結合型の持つ対応可能な問題のクラスが限定されてしまうという問題を解決する手法に関して研究を行った。疎結合型イジングネットワークは、問題のネットワークとハードウェアグラフとの間にミスマッチが生じた場合、埋め込み処理と呼ばれる、アニーリングプロセッサのイジングモデルの形状に組合せ最適化問題のネットワークに合わせるグラフ変形が必要となる。しかし、グラフ変形により本来問題からは生じない強い強磁性接続を持つスピンが追加されるため、アニーリングの精度や収束速度に悪影響を与えることが問題点として考えられる。そこで、上記(1)の時分割アーキテクチャをベースに、仮想的にハードウェア上のイジングネットワークの複雑度を向上させる技術を開発し、精度と速度の低下無しで対応可能な問題のクラスを増やす手法を検討した。結果として、従来の疎結合型イジングネットワークで精度が低下する問題に対して、埋め込み処理によるアニーリングの精度と収束速度の低下を解消することが可能であるという結果を得た。しかし、疎結合イジングモデルを時分割アーキテクチャを用いて全結合イジングネットワークを再現しようとした場合、データの依存関係を解決するために、分割されたネットワークが時間方向に増えてしまい処理速度が低下してしまうという問題が存在することも明らかになった。そこで、全結合型イジングモデルにおいてもスピン状態を並列に更新可能な確率的セルオートマトンによりスピン状態をサンプリングし基底状態探索を行う新しいアニーリング技術と疎結合イジングネットワークで全結合イジングネットワークを再現するアルゴリズムに関する研究を行った。これらの研究により、疎結合イジングモデルと時分割アーキテクチャを用いて少ない分割数で全結合イジングネットワークの基底状態探索を高速に実現可能であることが明らかになった。
  3. 上記の並列更新アニーリングをベースに全結合型アーキテクチャに関する研究を行った。このアーキテクチャでは、並列に全てのスピンを更新した場合、更新毎に多くの積和演算が必要であるという問題点を解決するため、変化したスピンの相互作用のみに注目した処理により、他の手法と比較して高速に基底状態を得ることが可能である。また、実際に創出したアーキテクチャを元に専用回路を作成し、他のアニーリングプロセッサに対して、収束速度、消費電力といった指標における優位性を実際に確認した。

学術論文

  1. Yamamoto K., Kawamura K., Ando K., Mertig N., Takemoto T., Yamaoka M., Teramoto H., Sakai A., Takamaeda-Yamazaki S., and Motomura M., "STATICA: A 512-Spin 0.25M-Weight Annealing Processor With an All-Spin-Updates-at-Once Architecture for Combinatorial Optimization With Complete Spin–Spin Interactions," IEEE Journal of Solid-State Circuits, vol. 56, no. 1, pp. 165-178 (2020).
  2. Yamamoto K., Ikebe M., Asai T., Motomura M., and Takamaeda-Yamazaki S., "FPGA-based annealing processor with time-division multiplexing," IEICE Transactions on Information and Systems, vol. E102-D, no. 12, pp. 2295-2305 (2019).
  3. Yamamoto K., Ikebe M., Asai T., and Motomura M., "FPGA-based stream processing for frequent itemset mining with incremental multiple hashes," Circuits and Systems, vol. 7, no. 10, pp. 3299-3309 (2016).

招待講演/セミナー

  1. 山本 佳生, "FPGA/CPU 混載システムにおけるストリーム型頻出アイテムセットマイニングの実装," NECグリーンプラットフォーム研究所セミナー, 日本電気株式会社 玉川事業場, Kawasaki, Japan (Oct. 2, 2015).

国際会議

  1. Yamamoto K., Ando K., Mertig N., Takemoto T., Yamaoka M., Teramoto H., Sakai A., Takamaeda-Yamazaki S., and Motomura M., "STATICA: A 512-spin 0.25M-weight full-digital annealing processor with a near-memory all-spin-updates-at-once architecture for combinatorial optimization with complete spin-spin interactions," 2020 International Solid-State Circuits Conference (ISSCC 2020), San Francisco Marriott Marquis, San Francisco, USA (Feb. 16-20, 2020).
  2. Yamamoto K., Ikebe M., Asai T., Motomura M., and Takamaeda-Yamazaki S., "Time-Division Multiplexing ," GI-CoRE GSQ, GSB, & IGM Joint Symposium -Quantum, Informatics, Biology, & Medicine -, Hokkaido University, Sapporo, Japan (Jul. 10-11, 2017).
  3. Yamamoto K., Huang W., Takamaeda-Yamazaki S., Ikebe M., Asai T., and Motomura M., "A Time-Division Multiplexing Ising Machine on FPGAs," International Symposium on Highly-Efficient Accelerators and Reconfigurable Technologies (HEART 2017), Ruhr University, Bochum, Germany (Jun. 7-9, 2017).
  4. Yamamoto K., Takamaeda-Yamazaki S., Ikebe M., Asai T., and Motomura M., "A scalable ising model implementation on an FPGA," COOL Chips 20, Yokohama Media & Communications Center, Yokohama, Japan (Apr. 19-21, 2017).
  5. Yamamoto K., Asai T., and Motomura M., "Hardware architecture for online frequent items mining with memory-efficient data structure," COOL Chips XIX, Yokohama Media & Communications Center, Yokohama, Japan (Apr. 20-22, 2016).
  6. Yamamoto K., Fukuda E.S., Asai T., and Motomura M., "An accelerator for frequent Itemset mining from data stream with parallel item tree," The 19th Workshop on Synthesis And System Integration of Mixed Information Technologies, Evergreen Resort Hotel, Yilan, Taiwan (Mar. 16-17, 2015).

受賞

  1. 山本 佳生, "高次数イジングネットワークの時分割処理方式の検討," 情報処理学会 - コンピュータサイエンス領域奨励賞, 2019年1月30日.
  2. 山本 佳生, "高次数イジングネットワークの時分割処理方式の検討," 情報処理学会システム・アーキテクチャ研究会 - 若手奨励賞, 2017年11月7日.

国内学会

  1. 山本 佳生, 熊澤 輝顕, 池辺 将之, 浅井 哲也, 本村 真人, 高前田 伸也, "高次数イジングネットワークの時分割処理方式の検討," 電子情報通信学会コンピュータシステム研究会 (CPSY), 秋田アトリオンビル, (秋田), 2017年7月26-28日.
  2. 山本 佳生, 池辺 将之, 浅井 哲也, 本村 真人, 高前田 伸也, "時分割多重機構を用いた高密度FPGAイジングマシン," 基盤(S)離散構造処理系プロジェクト「2017年度初夏のワークショップ」, 北海道大学VBL棟, (札幌), 2017年6月23-24日.
  3. 山本 佳生, 高前田 伸也, 池辺 将之, 浅井 哲也, 本村 真人, "時分割多重機構を用いた高密度FPGAイジングマシン," 電子情報通信学会コンピュータシステム研究会 (CPSY), 登別温泉第一滝本館, (登別), 2017年5月23日.
  4. 山本 佳生, 池辺 将之, 浅井 哲也, 本村 真人, 高前田 伸也, "時分割多重機構を用いたイジングプロセッサの解精度向上手法の検討," LSIとシステムのワークショップ2017, 東京大学, (東京), 2017年5月15-16日.
  5. 山本 佳生, 定久 紀基, 浅井 哲也, 本村 真人, "FPGAによる多重ハッシュを用いた頻出アイテムセットマイニングのストリームプロセッシング," 電子情報通信学会リコンフィギャラブルシステム研究会, 富士通研究所, (川崎), 2016年5月19-20日.
  6. 定久 紀基, 山本 佳生, 浅井 哲也, 本村 真人, "二重ハッシングによる類似検索ハードウェアアーキテクチャのFPGA実装," LSIとシステムのワークショップ, 北九州国際会議場, (北九州市), 2015年5月11-13日.
  7. 山本 佳生, 定久 紀基, 金 多厚, 福田 駿 エリック, 浅井 哲也, 本村 真人, "頻出アイテムセットマイニング高速化のためのストリームプロセッサ," LSIとシステムのワークショップ, 北九州国際会議場, (北九州市), 2015年5月11-13日.
  8. 定久 紀基, 山本 佳生, 金 多厚, 福田 駿 エリック, 浅井 哲也, 本村 真人, "Locality-Sensitive HashingのスケーラブルなハードウェアアーキテクチャのFPGA実装," 電子情報通信学会総合大会, 立命館大学びわこ・くさつキャンパス, (草津), 2015年3月10-13日.
  9. 定久 紀基, 山本 佳生, 金 多厚, 福田 駿 エリック, 浅井 哲也, 本村 真人, "類似検索を行うLocality-Sensitive Hashingのスケーラブルなハードウェアアーキテクチャ," 電子情報通信学会集積回路研究会・コンピュータシステム研究会合同 平成26年度若手研究会, 機械振興会館, (東京), 2014年12月1-2日.