組合せ最適化問題のための確率セルオートマトン向けハードウェアアクセラレータの開発
南條 大志
2018 年度 卒 ／学士（工学）
卒業研究の概要
本研究は組み合わせ最適化問題を既存のものより高速に解決することができるハードウェアの実装を目指したものである。
組み合わせ最適化問題は人間の社会活動において様々な場面で登場するが、制御すべきパラメータ数が増えると候補が指数関数的に増えるという特性上、一般的に高速解決することのできるハードウェアの実装は容易ではない。
近年ではナチュラルコンピューティングという新しい手法が注目を集めている。これは、解くべき問題を自然現象に写像し、自然現象の収束動作を観測して、最終的な状態を、問題の解として得るという手法である。これを用いたハードウェアの開発研究は広く行われており、その代表的な例が、イジングモデルという磁性体のふるまいを記述するためのモデルを使ったものである。これには、系全体の持つエネルギーが低くなるような状態へ遷移するという性質があり、そのエネルギーを組み合わせ最適化問題における評価指標に対応するように設定するものである。
このようなハードウェア研究には依然として課題が残されており、並列度および問題表現能力向上などが代表的である。スピン間の結合がスパースであれば、スピン同士の依存関係が少なくなるため、スピンの状態を並列更新しやすくなるが、その分問題表現能力が落ちる。逆に、スピン間の結合が密であれば、スピン間の相互作用を詳細に表現することができるため、問題表現能力が向上するが、その分スピン間の依存関係が増え、各スピンの状態を並列に更新することが困難になる。
こうした課題に解決の糸口を見出すため、本研究では、イジングモデルにおけるスピンの状態更新のために確率セルオートマトンを使った新しい機構を備えた組み合わせ最適化問題のためのハードウェア開発研究を行った。そして、実装したハードウェアを使ってMax - Cut問題のテストデータのシミュレーションを行い、およそ90%の精度で解を求められることを確認した。