連載
» 2015年04月01日 10時00分 公開

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

組み合せ最適化問題を従来の1800倍のエネルギー効率で計算可能な新型半導体コンピュータが登場した。汎用CPUとの違いを徹底解説。

[土肥正弘,ドキュメント工房]

 今回のテーマは、組み合せ最適化問題を従来の1800倍のエネルギー効率で計算し、室温で動作する新型半導体コンピュータで利用される「CMOSアニーリング」という技術だ。世界初の商用量子コンピュータといわれ話題を振りまいた「D-Wave」と同様に組み合せ最適化問題の計算を一般的なCMOS製造プロセスで作れるチップで実現する。

「CMOSアニーリング」って何?

 CMOSアニーリングは、物流など社会インフラの各領域で求められる「組み合せ最適化問題」をスピーディーに解決(近似解の導出)する、半導体を用いた新しい手法だ。2015年2月に日立製作所が、この手法を採用したCMOS半導体回路を試作し、2万0480のパラメータ(組み合せパターンとしては約1兆の500乗通り)の中から最適に近い、実用的に用いられるパターン(近似解)をわずか数ミリ秒で求められることを実証した。処理に要する電力は0.05ワットで、これは汎用(はんよう)コンピュータによる従来手法に比べ約1800倍のエネルギー効率だ。

試作CMOSアニーリング専用LSIチップ 図1 試作CMOSアニーリング専用LSIチップ(出典:日立製作所)

 組み合せ最適化問題を迅速に解く量子アニーリング手法を用いる超電導素子を使用したコンピュータ(D-Waveが開発、製品化した商用量子コンピュータ)で必須だった極低温までの冷却が不要で、一度に処理可能なパラメータ数が40倍(量子コンピュータは現在512、今回の試作機では20480)という特長がある。

 しかも、一般的なLSIのほとんどが採用するCMOS構造をとるため、製造プロセスのさらなる微細化やチップの超並列化が容易で、圧倒的に大規模な組合せ最適化問題に対応できると期待される。

 従来型のコンピュータでは「どこまで計算すれば最適解が見つかるのか分からない」ような組み合せ最適化問題の解決は難しい。有名な組合せ最適化問題に「巡回セールスマン問題」がある。これは複数都市を1回ずつ訪問して最初の出発地に戻るための最短経路を求めるという問題だ。巡回する都市が5〜6都市程度ならそう大変でもないが、30都市となるとどうだろうか。巡回経路の数は「(30-1)!/2」になるので、約4.42×(10の30乗)という途方もない数になる。

 このような組み合せ最適化問題では、決定するパラメータがn個あれば、図2に示すように計算は2のn乗回繰り返すことになる。仮にnを100としても、1.27×(10の30乗)回の計算が必要だ。このような「組み合せ爆発」が起きると、全ての組合せを計算していては現在のスーパーコンピュータでも年単位の時間がかかってしまう。

従来型の計算手法では計算量が爆発的に増加する 図2 従来型の計算手法では計算量が爆発的に増加する(出典:日立製作所)

 そこで、正攻法で最適解を求めるのではなく、何らかの「裏ワザ」を使って、本当に最適解とは限らないが実用に供するのに十分な解を現実的な時間内で求める必要がある。

 現実的な問題になぞらえるなら、トラックの一番低コストな荷物集配経路を探すのに、何時間もかけてはいられない。集配地点が決まった時点で、正解ではなくてもいいからそれに近い経路(近似解)を示してほしい。

 このような需要は、例えば交通システムで渋滞解消をするために最適な交通量や移動コストの見極め、電力システムが電力を安定供給するために必要な蓄電量の想定など、大規模なパラメータでの計算が必要な多くの社会インフラ課題に共通するものだ。

       1|2|3|4 次のページへ

Copyright © ITmedia, Inc. All Rights Reserved.

会員登録(無料)

ホワイトペーパーや技術資料、導入事例など、IT導入の課題解決に役立つ資料を簡単に入手できます。