左側の7つの変数はお互いにつながらないが、それぞれが右側の7つの変数とつながる。左側の変数を同時に更新し、その値を受けて右側の変数を同時に更新する──この2ステップで全変数の更新が終わるという。
SAでは、7変数であれば7ステップの計算が必要だった。奥山さんらのアプローチでは変数がいくつになっても2ステップで更新が可能になるため、特に大規模な全結合問題を解くのに向いている。
奥山さんらは大規模な問題の例として、10万変数・全結合問題をSAとMAで比較した。SAは米IBMのハイパフォーマンスサーバ「IBM Power 8」に載せて計算。MAはNVIDIAの「Tesla P100」を4台つないだGPUクラスタに載せて計算した。
結果、精度の良い近似解を導くのに、MAは1秒未満、SAは約50秒程度かかった。ある計算精度の基準で比較したとき、「MAはSAに比べ約250分の1の時間で計算できる」(奥山さん)という。
10万変数・全結合という大規模な組合せ最適化問題を解けるアルゴリズムとしては、東芝が4月に発表した「シミュレーテッド分岐アルゴリズム」(SB)が挙げられる。SBもGPUによる並列計算で高速化を図っているという点では、MAと似ている。
奥山さんらが発表したMAの論文には、SAとの比較はあるがSBとの比較はない。比較しなかった理由を記者が聞いたところ、「組合せ最適化問題を解くアルゴリズムはいろいろあるが、比較の基準となるのはSA。SAとの比較を示せば、他のアルゴリズムとの比較もできるものと考えている」(奥山さん)と語った。
「SBも10万変数・全結合問題を解けるという点ではMAとできることは同じ。しかし、われわれは100スピン程度ではあるが、良いパフォーマンスでMAが厳密解を求められることを調べている。(それをしていない東芝に比べ、)より良い答えを得ようとしている努力がお分かりいただけると思う」(同)
さくらインターネットの菊地俊介上級研究員は、「MAはGPUで計算できるアルゴリズム。さくらの『高火力』の出番ではないか」と話す。
さくらインターネットは、「高火力コンピューティング」としてGPUリソースを時間単位でレンタルするサービスを行っている。
菊地さん自身でも、さくらの高火力でMAの性能評価の計算をしてみたところ、計算自体は15分程度で終わったという。「高火力上に環境をセットアップするのが約10分。問題サイズにもよるが、アニーリングの計算は15分程度。計算結果の回収は1分。1時間以内には終わる。高火力の1時間の料金は349円(税別)なので、ポケットマネーで検証できる」(菊地さん)
菊地さんは「決定ではなく案だが」と前置きした上で、「今後、高火力上でのMA利用のトライアルユーザー募集などの展開を考えていきたい」と話した。
【訂正履歴:2019年9月2日午前11時40分 初出時、菊地俊介さんのお名前の漢字を誤って紹介しておりました。おわびして訂正いたします】
Copyright © ITmedia, Inc. All Rights Reserved.
Special
PR