メディア

汎用CPUの1800倍、近似アルゴリズム特化の「CMOSアニーリング」とは?5分で分かる最新キーワード解説(2/4 ページ)

» 2015年04月01日 10時00分 公開
[土肥正弘ドキュメント工房]

どうやって大規模計算を高速化するのか?

大規模な組合せ最適化問題を解くための近似アルゴリズムは数々あるが、汎用的に使えて効果的な1つに「焼きなまし法(Simulated Annealing」がある。

 「焼きなまし」とは、金属材料などで結晶性をよくするために熱した後、徐々に冷やす方法のことだが、焼きなまし法はその概念を計算法に応用したものだ。問題に応じてあるコスト関数を定義し、そのコスト関数が最低値となった場合の変数の値が求めるべき解になるようにする。

 この方法なら、変数を徐々に変化させコスト関数の最低値が探せる。ただし、途中でコストがガクンと下がったところを最小値だとしてしまう(本当は違うのに、局所的な最小値に落ち込む)可能性があるので、コスト関数が大きくなる変化もランダムに取り入れて全体最適解に近づける。いつも正しい全体最適解が得られるとは限らず、基本的に近似解となる。

 焼きなまし法の考え方を、量子状態の計算に当てはめたのが、D-Waveが採用した量子アニーリングという計算法だ。焼きなまし法が温度を変数にしているのに対して、量子アニーリングでは変数として磁場を使う。

 コスト関数を構成する変数を磁性体のモデルである「イジングスピン」とし、コスト関数が磁場に依存するようにする。スピンの向きをz軸方向とすれば磁場はその垂直方向(x軸かy軸)にかける。

 この場合、数式上磁場が焼きなまし法の場合の温度のような働きをすることになる。量子系ではトンネル効果により局所的最低値状態から抜け出せるために、焼きなまし法よりも正確な解を得やすい。D-Waveのマシンでは、スピンに相当する変数を超電導磁束量子とした。

イジングモデルによる最適化問題の解法 図3 イジングモデルによる最適化問題の解法(出典:日立製作所)

組み合せ最適化計算をCMOSでハードウェア化

 今回日立が試作したのは、焼きなまし法とほぼ同様の手法を実現する半導体(CMOS)だ。図4に見るように、チップ上にはスピンに見立てたメモリ(RAM)が格子状に並び、メモリにはスピンの上向き、下向きに対応する「1」「0」が書き込まれ、保持される。

 相互作用の係数は別のメモリに設定され、スピン値の更新に当たる書き込み操作はデジタル回路が行う仕組みだ。1スピンごとに値を変化させていきながら、外部からの特殊な回路からのノイズによりランダム性を加えて、系全体としてエネルギーが最小になるようなスピン配列を見つけ出す(図4)。

イジングモデルを半導体回路でシミュレート 図4 イジングモデルを半導体回路でシミュレート(出典:日立製作所)

Copyright © ITmedia, Inc. All Rights Reserved.

会員登録(無料)

製品カタログや技術資料、導入事例など、IT導入の課題解決に役立つ資料を簡単に入手できます。