組み合わせ最適化問題を解くCMOSアニーラ(5) ビジネス展開で先行する富士通のディジタルアニーラ

富士通のディジタルアニーラ

富士通もCMOSを使うIsingマシンの開発を行っており、2017年9月に「Fujitsu Science Technical Journal(FSTJ)」に論文が発表された。

このIsingチップは1024スピンのフルコネクトになっており、Arria 10 GX FPGAで作られていた。動作クロックは100MHzで、5サイクルで1回のアップデートを行っていた。

Isingモデルによる最適化の原理図。現在の状態Xに対して右下の円で表した隣接状態のエネルギーの変化を計算し、エネルギーの低下が大きいものをSelectorで選択して状態を更新する (出典:FSTJ Vol.53 No.5(Sep. 2017)Sanroku Tsukamoto et.al., An Accelerator Architecture for Combinatorial Optimization Problems)

次の図はIsingチップの構造を示すもので、重みWiとΔEiを計算する部分が1024個並んでいる。その先にΔEiとEoffを比較して、値を更新するかどうかを判断するブロックがある。詳細は省略するが、Eiが大きくなるにつれて採用確率が減少する回路となっている。そして、ADB(Acceptance Decision Block)と呼ぶブロックがあり、それぞれの項が採用基準を満たすかを並列に判定する。そして、Update Selectorで、次のサイクルに状態を更新する項を選び出して、状態の更新を行う。

このように、採用確率の計算を並列に行うことにより収束までの繰り返し回数が並列に処理するスピンの数に逆比例して減少する。一方、実際のスピン状態の更新は1項ずつ順番に行うので、並列に多数の項を更新するやり方と比べて収束性が高いというメリットがあるという。

富士通のIsingチップのアーキテクチャ。1024bitのそれぞれの変化に対するエネルギー変化ΔEを並列に計算する。そして、ADBでスピン状態を変化させる基準を満たすかを判定する (出典:FSTJ Vol.53 No.5)

もう1つの工夫は、局所最適値に捕まって状態が変化しなくなったときには、正のオフセット値のEoffを差し引いて採用確率を高めるDynamic Offsetという方法である。これは局所最適点に捕まった場合は、ある程度再加熱して逃げ出すことに相当している。

次の図は32都市のTSPのケースの実測結果である。左側のグラフ(a)は横軸が並列に評価するスピン数、縦軸が収束までにかかる繰り返し回数で、並列に処理するスピン数にほぼ逆比例して回数が減少し、収束が速くなっている。

一方、グラフ(b)の横軸は逆温度でアニール開始時には左側で、冷却が進むにつれて右に動いていく。縦軸は局所最適点に捕まっている時間である。3本のグラフの一番上は並列評価を行わず、ダイナミックにEoffも変えない場合、2番目は並列評価は行うがダイナミックEoffは行わない場合、一番下は並列評価とダイナミックEoffの両方を行った場合である。

このグラフに見られるように、並列評価とダイナミックEoffで局所最適点に捕まってウロウロしている時間が大幅に減少している。

左は並列評価の数に対する収束までの繰り返し回数を示す図で、ほぼ、並列度に逆比例して繰り返し回数が減少している。右の図は、縦軸は局所最適点に捕まっている平均時間である。横軸は逆温度で、冷却が進むと右に移動する。3本のグラフは、上から順に、並列評価を行わず、ダイナミックEoffも行わない場合、2番目は並列だけは行った場合、一番ウロウロ時間が短いのは、並列評価とダイナミックEoffを使った場合

次の図は最終結果で、左から順に、通常の順次評価でダイナミックEoff無し、順次評価でダイナミックEoffあり、並列評価でダイナミックEoff無し、並列評価でダイナミックEoffありの場合の解を得るまでの時間を示している。左端のナイーブなやり方に比べて、富士通のやり方では12,000倍のスピードで解が得られるという結果になっている。