組み合わせ最適化問題を解くCMOSアニーラ(4) 日立が開発を進めるCMOSアニーラの概要

日立のCMOSアニーラ

日立は2015年のISSCCに20K SpinのCMOSアニーラチップを発表しており、開発の開始という点では日本のメーカーの中でも一番早かったのではないかと思われる。このチップは次の図に示すように、65nmプロセスで作られ、4mm×3mmのチップに合計20個の1Kbitのブロックを収容している。消費電力は約50mWである。

スピンを記憶するメモリは1bitであるが、相互作用の強さを記憶するメモリとしてスピン1個に付き10bitのメモリを持つ。そして、各スピンに与える外部磁界の係数として、2bitのメモリを持つ。つまりスピン1個に13bitのメモリを持ち、チップ全体では260Kbitのメモリを持っている。

日立のIsingチップのダイ写真と諸元。65nmプロセスで作られ、12mm²のチップに20K-spinを集積している (出典:ISSCC 2015 論文24.3 20k-spin Ising Chip for Combinational Optimization Problem with CMOS Annealing)

細かい図で見難くて申し訳ないが、1つのスピンの回路は次の図のようになっており、6本の入力を持っている。そして、隣接するスピンが(+1、+1)あるいは(-1、-1)と揃っている数をaとし、スピンが逆向きの数をbとし、a>bの場合は新しいスピンの値を+1としNを1増し、b>aの場合は新しい、スピンの値を-1としNを1減ずる。aとbが同数の場合は新しいスピンの値とNの増減をランダムに決める。というやり方で、スピンの値を更新してアニールを進める。

スピン部分の回路図。スピンが揃った数aと逆方向の数bを数え、その大小で次のスピン状態を決定する (出典:ISSCC 2015 論文24.3)

次の図の左側の図は画像からノイズを取り除く処理を行った場合のもので、上のグラフは系のエネルギーを示している。大局的にはエネルギーは減少して行っているが、細かく見れば、増減のあるギザギザのグラフになっている。

下の3つの画像の(a)はノイズが載った最初の画像、(b)は5msアニールした時の画像で、かなりエネルギーは小さくなっているが、まだ、最低点には達していないときの画像である。そして(c)は10msの画像で、エネルギーがほぼ最低になった時点の画像である。この画像では、ノイズが無くなりABCの文字がくっきり読み取れるようになっている。

右側のグラフは、Core i5 CPUでSG3というアルゴリズムを実行させた場合との性能比を示すものである。スピンの数が増えるにつれて差が大きくなり、20kスピンの場合に日立のIsingチップは1800倍速いという結果になっている。

Isingチップで画像からノイズを除去する例。10msでノイズが消えてABCの文字がクリアに見える。左上のグラフは、ノイズ除去のエネルギーの減少の様子を示す (出典:ISSCC 2015 論文24.3)

この65nmプロセスで作った第1世代のIsingチップはbit数は20kと大きかったが、配線を柔軟に変えることができず、Isingモデルの相互作用の係数のbit数やトポロジを変更することができないという問題があった。

このため、日立はFPGAを使って第2世代のプロトタイプチップを作った。このチップは1024スピンである。

2016年のSC16において、日立ブースで展示されたFPGAベースの第2世代Isingチップのプロトタイプ

Isingチップを使って離散的最適化問題を解くにはチップができただけではだめで、次のような一連の処理が必要になる。

交通システムであれば、アプリケーションの課題は交通渋滞の解消、サプライチェーンであれば課題は物流コストの最小化であったりする。これらの課題をIsingモデルの評価関数の形で表すことが第1のステップである。そして、交通システムであれば、系のエネルギーの最小状態が最短経路に対応し、サプライチェーンであれば、系の最小エネルギーの状態が巡回セールスマン問題になるようにする。

そして、IsingモデルをIsingコンピュータのハードウェアにマッピングする。日立のチップのようにスピン間の接続本数が少ないハードウェアの場合は、スピンを分割して入力数を増やしたり、遠くのスピンに接続するためには中継のためのスピンが必要になるので、どこにどのスピンを置くかの配置配線が問題になる。

このIsing計算機ハードウェアへの埋め込みが終われば、最適化計算を行うことができる。しかし、そのためにはこれらの仕事を行うツールを開発する必要がある。この開発には、単にソフトウェアを書けるだけでなく、統計力学などの数学の素養も必要であり、日立は2016年に、北海道大学と日立北大ラボを開設して開発にあたっている。