東工大ら、全結合型アニーリングプロセッサ開発：組み合わせ最適化問題を高速に解く

東京工業大学は、北海道大学や日立北大ラボ、東京大学と共同で、組み合わせ最適化問題を高速に解くことができる新しいアニーリング処理方式と、これを実行するための全結合型アニーリングプロセッサを開発した。

[馬本隆綱，EE Times Japan]

SCAで全疑似スピン値を並列に更新

　東京工業大学科学技術創成研究院の本村真人教授らは2020年2月、北海道大学や日立北大ラボ、東京大学と共同で、組み合わせ最適化問題を高速に解くことができる新しいアニーリング処理方式と、これを実行するための全結合型アニーリングプロセッサを開発したと発表した。

　組み合わせ最適化問題は、変数の数が多くなるとその組み合わせが膨大となり、最適な組み合わせの解を効率的に得ることが難しくなっていた。組み合わせ最適化問題の近似的な計算技法として、「局所型」や「全結合型」と呼ばれるアニーリング処理方式がある。全結合型は応用範囲が極めて広いという特長がある半面、高速に解くことが難しいといわれてきた。

　そこで研究チームは、全疑似スピンの値を並列に更新することで、組み合わせ最適化問題を高速に解くことができる新しいアニーリング処理モデル「SCA（Stochastic Cellular Automata）」を構築した。従来の「SA（Simulated Annealing）」あるいはこれに類似した計算手法をベースとしたアニーリングマシンでは、疑似スピンの値を逐次的に変更するしかなかったという。

SAとSCAの比較 出典：東京工業大学他

　SCAを用いて疑似スピン値を並列更新する方法はこうだ。更新したい疑似スピンにかかる相互作用係数をメモリに記憶させる。このメモリから並列に相互作用係数を読み出し、メモリに付随したロジック回路で並列演算する。研究チームが「STATICA」（Stochastic Cellular Automata Annealer）と呼ぶ、このニアメモリ型アーキテクチャにより、SCAの計算を効率よく実行することができた。

STATICAアーキテクチャ 出典：東京工業大学他

　研究チームは、開発したアーキテクチャをベースに、512疑似スピンの並列更新ができるように構成した、全結合型アニーリングプロセッサ「STATICA」を開発した。TSMCの65nmプロセスを用いて試作したチップは、外形寸法が3×4mmで、消費電力は約600mWである。

アニーリングプロセッサ「STATICA」のチップ写真 出典：東京工業大学他

　研究チームは、試作したプロセッサと既存技術を用いた全並列型アニーリングマシンとの性能比較を行った。この結果、STATICAはアニーリング速度が少なくても数倍、エネルギー効率は2桁以上も優れていることが分かった。

STATICAと既存の全並列型アニーリングマシンの性能比較 出典：東京工業大学他

　研究チームによれば、STATICAは疑似スピン数をスケーラブルに拡大しても対応できるアーキテクチャであり、より大規模な疑似スピンシステムでも並列更新を実現できるという。ディープラーニングなど知識情報処理システムとの統合により、開発したチップの早期の実用化を目指す考えである。