さくらインターネットにおけるアニーリングシステム評価の取り組みのご紹介
＠ CMOSアニーリングマシンワークショップ

2019/08/30

さくらインターネット株式会社

さくらインターネット研究所

上級研究員 菊地 俊介(C) Copyright 1996-2019 SAKURA Internet Inc

本資料（本発表）の構成• さくらインターネット、同研究所について• さくら（研究所）におけるCMOSアニーリングマシン
評価・検討の位置づけ• 評価結果• アニーリングマシン活⽤事例のご紹介• 今後の展開予定• 本資料は、さくらインターネット研究所ブログで公開予定です。
• https://research.sakura.ad.jp/

2

話者紹介

菊地 俊介

（東京都出⾝、品川区在住）
所属 さくらインターネット研究所
学歴 早稲⽥⼤学⼤学院 理⼯学研究科
電⼦・情報通信学専攻 修⼠課程修了
早稲⽥⼤学⼤学院 国際情報通信研究科 博⼠課程単位取得退学

職歴 富⼠通（株）富⼠通研究所に就職
ネットの研究やったり、SEやったり、@kikuzokikuzo
NICTに出向したり、トイレIoT作ったり
https://note.mu/kikuzokikuzo
さくらインターネットに転職
https://www.facebook.com/
データ流通実証実験、OpenFogコンソーシアム、
kikuzokikuzo
AR/VR、量⼦（アニーリング）コンピュータ
専⾨ エッジ・Fogコンピューティング（分散系システムのあたり）
趣味 新技術調査、家庭内IoT、⾞、鉄道
3さくらインターネットの主要サービス構成

4

新規サービスが成⻑を牽引


6-0/2577777672
17148
311777)1

115

293826

1PT26)) 1

41V77)))(3)(15⾼⽕⼒コンピューティングサービス

6さくらインターネット研究所のフォーカス2019版

さくらの現業ビジネスの先にあるものを⾒ていく。
新技術・研究領域
量⼦
コンピューティング

機械学習

新ビジネス領域

⾳声インタフェース

分散システム（エッジ・フォグ）

コンテナ・サービスメッシュ

スマートシティ・スマートビル

データ流通
衛星データPFさくら
現業ビジネス

AR・VR・ウェアラブル

IoT

モビリティ・ロボティクス

セキュリティ

⾼⽕⼒

クラウド・VPS

サーバネットワークストレージデータセンター
ファシリティ

インフラ領域7

さくらインターネット研究所では昨年より⽇⽴さんと共同で研究活動を推進

8

さくらインターネット研究所では昨年より⽇⽴さんと共同で研究活動を推進

9

なぜ、さくらでCMOSアニーリングマシンを評価するのか︖

次のさくらのビジネスを⽀える（かもしれない）
要素技術へのキャッチアップ
これまでも、新しい技術に⽀えられた新しいサービスが、会社を成⻑させてきた︓「クラウド」「⾼⽕⼒」

新しい需要の創出への⽀援
NVIDIAが様々なGPU関連製品を出し、使い⽅セミナーを開催するのと同様。その⽴場にある⽇⽴さんの⽀援。

⾃社内サービスへの適⽤の可能性（後ほど紹介）10

今回のプロダクトの⽴ち位置に関する理解 （1/2）

ソリューションとしての位置づけ
消費電⼒
エッジ（現場）側にインストール

ネットワーク越しに使うGPGPU

D-Wave ?

による解法

FPGA
2000スピン

⽇⽴
クラウド
CMOS

10000スピン〜対応できる問題の⼤きさ11

今回のプロダクトの⽴ち位置に関する理解 （2/2）

ビジネスソリューションの構成（想定、可能性）• フルサポート・フルマネージドサービスとして︓• ⽇⽴さんによる対応• ⾃社開発向けソリューションとして︓• さくらで環境準備のお⼿伝い︖

12

アニーリングマシンの使い⽅

解きたい問題をエネルギー関数（コスト関数）として表現問題をイジング模型（QUBO）に変換

pyQUBOを利⽤する

今回の評価では、ランダムグラフを利⽤

イジング模型をアニーリングマシンのハードウェア（トポロジー）に合わせて変形

ソフトウェア定義でフルメッシュ結合のため、変形不要

アニーリングマシンで解く

さくらの⾼⽕⼒環境で評価
13

問題をコスト関数にする問題を定式化する（アニーリングマシンを使う上で⼀番難しいネックとなるポイントがここ）

数式は⽇⽴サイト（ https://annealingcloud.com/tutorial/1.html ）より借⽤（ここはツールなどのソリューションがあまりなく、⾃⼒でやらなければならないところ）

参考サイト• QUANTUM COMPUTING SOLUTIONS : フィックスターズ社の解説サイト• https://quantum.fixstars.com/introduction_to_quantum_computer/quantum_annealing/ising_model/• T-Wave : 東北⼤学量⼦アニーリング研究センターが運営するナレッジベース• https://qard.is.tohoku.ac.jp/T-Wave/?p=43
14

イジング模型の変形

イジング模型を、アニーリングマシンのハードウェア構成に合わせて変形する必要がある（今回のソリューションでは、フルメッシュ結合となっているため、対応不要。）（すばらしい︕）

キンググラフの場合

図はいずれもhttps://quantum.fixstars.com/introduction_to_quantum_computer/quantum_annealing/
programming/graph_mapping/ より借用

15

評価についてさくらの「⾼⽕⼒コンピューティング」（GPGPU搭載ホスト時間貸し環境）でMAソフトウェアを使⽤した場合の、使い勝⼿を⾒出すことを⽬的に評価評価した内容• 評価1: 計算量と計算時間の特性• 評価2: 精度の特性

費⽤⽬安
今回の評価の対象外• 性能の上限• 既存⼿法（SAや⽇⽴製作所の既存ソリューション）との⽐較
16

評価環境

• さくらインターネット⾼⽕⼒コンピューティング環境を利⽤
今回評価対象Tesla P40モデル

Tesla P100モデル

NVIDIA Tesla P40 x1
24GB メモリ
単精度性能：約12.0TFLOPS
倍精度性能： - (実装なし)

NVIDIA Tesla P100 x1
16GB メモリ
単精度性能：約9.3 TFLOPS
倍精度性能：約4.7 TFLOPS• ⼊⼒イジングモデルとして、ランダムグラフを利⽤• ランダムグラフ⽣成には”rudy”を使⽤• 汎⽤グラフジェネレータとして広く⽤いられている• https://web.stanford.edu/~yyye/yyye/Gset/

17評価１︓計算量と計算時間の特性評価1-1:⼀つのイジングモデルに対して、アニーリング処理のステップ数、試⾏回数を変化させて計算時間を観測（⽇⽴製）アニーリング処理の構成
イジングモデル、ステップ数(S)、試⾏回数(R)をパラメータとして与え、計算開始

アニーリング処理（1試⾏）
状態

エネルギー

試⾏回数分の結果をまとめて（ヒストグラム化、平均値等を計算等）、出⼒とする

動かす細かさの単位＝ステップ(s)試⾏回数(r)18

評価１︓計算量と計算時間の特性評価1-1:⼀つのイジングモデルに対して、アニーリング処理のステップ数、試⾏回数を変化させて計算時間を観測
d=2007456 .
- (026, -)- (,,(- ( ,-,),, -,- ))) --,,, ,- ) 


-

1
3, ,,()-  ,)),,),

  

凡例︓

1試⾏あたり
[ms]
全試⾏合計
[ms]
コマンド実⾏
時間 [s]

19

評価１︓計算量と計算時間の特性評価1-1:⼀つのイジングモデルに対して、アニーリング処理のステップ数、試⾏回数を変化させて計算時間を観測
試⾏回数、ステップ数と試⾏時間の関係

1800

1,000

1600

10,000100,000

1620.013

実行時間 [sec]

1400
1200
1000

809.244

800
600
400
200
0

157.569
16.395
2.634
100

3.753
200

4.898
300

6.419
400

75.6947.143
500

161.316
8.241
600

9.406
700

10.585800

12.234900

13.7991000

試行回数 (r)ステップ数、試⾏回数に対して計算時間はリニアに変化する。
20

評価１︓計算量と計算時間の特性評価1-1:⼀つのイジングモデルに対して、アニーリング処理のステップ数、試⾏回数を変化させて計算時間を観測
試⾏回数、ステップ数と試⾏時間の関係
s=1,000

s=10,000

s=100,000

実⾏実感 [sec]1000

1620.013

809.244161.316157.569
100

75.69416.395
10

4.898

3.753

2.634

9.406

8.241

7.143

6.419

12.234

10.58513.799

1100200300

4005006007008009001000

試⾏回数(r)

ステップ数あたりの効率は、試⾏回数が増えると悪化する。

21

評価１︓計算量と計算時間の特性評価1-2:⼊⼒イジングモデルのサイズ（スピン数）をパラメータに、試⾏回数を変化させて計算時間を観測
s=1000014(,,( 52
34()) )(,,,,)))(,,,, )

 



.

,,,() ())

 (,()

   )(),(  )

(()))
(,))

  

(,),(,,(,,)) ()(,,           )), )))()(,)

        , 

凡例︓



1試⾏あたり
[ms]
全試⾏合計
[ms]
コマンド実⾏
時間 [s], ,(, ,( 

22評価１︓計算量と計算時間の特性評価1-2:⼊⼒イジングモデルのサイズ（スピン数）をパラメータに、試⾏回数を変化させて計算時間を観測
試⾏回数と計算時間の関係
120

d=200d=300
d=400d=500
d=600
d=700
d=800
d=900
d=1000d=1200d=1500
d=2000

計算時間 [s]100806040200100200

300

400500

600

700

800

900

1000

試⾏回数 (r)試⾏回数に対して計算時間はリニアに変化する。
それはスピン数を変えても変わらない。

23評価１︓計算量と計算時間の特性評価1-2:⼊⼒イジングモデルのサイズ（スピン数）をパラメータに、試⾏回数を変化させて計算時間を観測

スピン数と計算時間の関係（比率）10.9

計算時間比 (d=200を1として)

0.8
0.7
0.6
0.5
0.40.3d=200
d=8000.2

d=300
d=900

d=400
d=1000d=500
d=1200d=600
d=1500d=700
d=2000700

800

9000.1
0100

200

300

400500600

1000

試行回数 (r)スピン数が⼤きくなると計算効率は上がる

24

評価2︓精度の特性

評価2:d=200のイジングモデルにおいて、試⾏回数とステップ数を変化させて最⼩エネルギー到達までの変化を確認
d=200 平均エネルギー値と最⼩エネルギー値 d=2007456 .

- )2((3),6),

凡例︓,- - ))

16345
()
0

【参考】計算時間),1),)(),
平均エネル
ギー値
最省エネル
ギー値,),( )),)), (5.

,)02, () (,)

  )(()
 )))( 

（ステップ数・試⾏回数と計算時間の関係表より抜粋）

試⾏回数よりもステップ数を増加させたほうが、求解には有利

凡例︓

1試⾏あたり
[ms]
全試⾏合計
[ms]
コマンド実
⾏時間 [s]25

評価2︓精度の特性

評価2:d=200のイジングモデルにおいて、試⾏回数とステップ数を変化させて最⼩エネルギー到達までの変化を確認
算出エネルギー値ヒストグラム
0.3

r=100, s=1000
r=500, s=1000

0.25

0.2

出現頻度

r=1000, s=1000
r=100, s=10000
r=100, s=100000

0.15

0.1

0.05

0-2058

-2008

-1958

-1908

-1858

-1808

最小エネルギー値

試⾏回数よりもステップ数を増加させたほうが求解には有利

26

評価結果（まとめ）特性• 試⾏回数とステップ数に関して、計算時間は線形に増加する• ⼊⼒するイジングモデルのサイズに対して、計算時間はほぼ線形に増加する• むしろ、⼊⼒サイズが⼤きくなるほど効率が上がる

計算時間（速度）• 200ノード、1000ステップ100試⾏で2.6秒• 200ノード、1000ステップ1000試⾏で13.8秒• 200ノード、10000ステップ100試⾏で16.4秒• 1000ノード、1000ステップ1000試⾏で36.9秒• クエリに対してリアルタイムで応答させるようなタイプの処理には（まだギリギリ）向かない。バッチ処理に組み込む分には⼗分⾼速。
• （SAに対しては1000倍くらい⾼速な模様。）
27

【参考】評価結果（SAとの⽐較）

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.100.012111

28

費⽤について

⾼⽕⼒コンピューティング Tesla P40モデルの場合• 時間貸しの場合• 環境セットアップ︓10分弱• アニーリング計算︓〜15分程度（⽬安、解かせたい問題サイズに依存）• 結果の回収︓1分• →349円 (1時間分)• 1ヶ⽉借りっぱなしで251,280円• ⽉額課⾦契約で借りる場合（最低3ヶ⽉以上）• 初期費875,000円＋⽉額97,000円 x3 = 1,166,000円〜

29アニーリングマシン応⽤検討

Fogコンピューティング試作

現場とクラウドを連携させて業務改善（倉庫オペレーション改善を想定）
データ処理・現場制御
アプリケーション

最適配備計算Cloud

アニーリング
クラウド↑データ送信棚への荷物の最適な格納の仕⽅を解く

フィールドに現れた
荷物の⼤きさを検出

制御指⽰↓

荷物を収める倉庫を明⽰
Fog

Fog

データ処理・
現場制御
アプリ

ToFカメラ
現場デバイス

センサ+LED表⽰

現場デバイス30

アニーリングマシン応⽤検討• さくらのクラウドにおける、VMの配備計画• エッジノードへのジョブ配備計画• 画像処理フィルタへの適⽤• 検討中...

31

今後の展開予定（案であり本決まりのものではありません）• アニーリングマシン（GPGPU版）利⽤トライアルユー
ザ募集• アニーリングマシン（GPGPU版）社内適⽤（VM最適配備への適⽤）• エッジコンピューティング・Fogコンピューティング
試作（実際に動かして使う、デモシステム）への適⽤• 「現場で⼩問題を⾼速に解く」で、使っていきながら評価を進める⽅向性を重視している。
32

ありがとうございました。

33