富士通研究所は2016年10月20日、組み合わせ最適化問題を解く非ノイマン型の新たな計算機アーキテクチャーを、トロント大学と共同で開発したと発表した。数千の拠点がある物流の効率化や、災害時の復旧計画、投資ポートフォリオの最適化といった問題を高速に計算できる。

基本回路を実装したFPGAで巡回セールスマン問題を解くデモ
基本回路を実装したFPGAで巡回セールスマン問題を解くデモ
[画像のクリックで拡大表示]

 富士通研らは、最小構成要素となる基本回路を設計し、FPGA(回路を再構成可能な半導体チップ)で動作させたところ、一般的なマイクロプロセッサと比べて約1万倍高速に計算できることを確かめた。メモリーからデータを読み出す頻度が少ない非ノイマン型アーキテクチャーのため、大幅な低消費電力化も見込めるという。

データの移動を最小化できる非ノイマン型アーキテクチャーを採用
データの移動を最小化できる非ノイマン型アーキテクチャーを採用
[画像のクリックで拡大表示]

 組み合わせ問題は、全ての組み合わせの中から、組み合わせの関数である「評価値」が最小になるものを探す問題である。例えば、複数の拠点を回る最短の経路を探す「巡回セールスマン問題」であれば、経路の長さが評価値となる。

 組み合わせ問題を解く専用ハードウエアとしては、量子ビット間の相互作用を応用したカナダD-Waveの量子アニーリング型量子コンピュータがあり、通常のマイクロプロセッサより「1億倍高速」であることをうたう(関連記事:D-Waveの量子コンピュータは「1億倍高速」、NASAやGoogleが会見)。

 ただしD-Waveの場合、エラー訂正で複数のビットを使うなど複雑な構成のため、現状では高速性を発揮できる組み合わせ問題が一部に限られている課題がある。富士通研の方式では、より汎用的に組み合わせ問題を解ける可能性があるという。

1024の演算を同時に実行

 今回富士通研らが開発したのは、1024ビットで表現できる組み合わせ問題の最適解を算出する基本回路である。

1024回分の演算を同時に実行できる並列機能、局所解に陥ったことを検知して脱出できる機能を備える
1024回分の演算を同時に実行できる並列機能、局所解に陥ったことを検知して脱出できる機能を備える
[画像のクリックで拡大表示]

 この基本回路は、1024のビットのうち1つのビットのみを反転させた場合の評価値を、1024個分同時に算出できる。つまり、1ビット目だけを反転させた場合、2ビット目だけを反転させた場合、…、1024ビット目だけを反転させた場合、計1024通りの計算を並列して行える。ここから、1024個のビットのうち、どのビットを反転させると評価値が最小になるかを割り出せる。