![19
?多数決回路の前の段階での乱数の挙動は第1世代と同様
?グラウバーダイナミクスの確率的な挙動とは異なる
第2世代の動作アルゴリズム
◆Signals to inverters
n+ : number of signals with “1” at red dots
n? : number of signals with “0” at red dots
◆Glauber dynamics
P+ : probability that the spin state is +1
through spin update in accordance with
Glauber dynamics
N
H[1] Inverter
H[0] Inverter
J1[1] Inverter
J1[0]
N1 Inverter
JL-1[1] Inverter
JL-1[0]
NL-1 Inverter
……
Majorityvotercircuit](https://image.slidesharecdn.com/aitc-190718055824/85/2019-7-3-AITC-20-320.jpg)
![[20170922 Sapporo Tech Bar] 地図用データを高速処理！オープンソースGPUデータベースMapDってどんなもの？？ by 株式会社...](https://cdn.slidesharecdn.com/ss_thumbnails/20170922mapd-170926064811-thumbnail.jpg?width=560&fit=bounds)
More Related Content
What's hot (20)
Similar to 2019年7月3日 AITCオープンラボ 量子コンピューティング シリーズ第３回 ～日立製作所様における取り組み紹介～ (20)
More from aitc_jp (20)
2019年7月3日 AITCオープンラボ 量子コンピューティング シリーズ第３回 ～日立製作所様における取り組み紹介～
- 2. 1 概要 ? CMOSアニーリングマシンの概要 ? プロトタイプの開発状況 ? 実用化に向けた周辺技術開発状況 ? まとめ
- 3. 2 概要 ? CMOSアニーリングマシンの概要 ? プロトタイプの開発状況 ? 実用化に向けた周辺技術開発状況 ? まとめ
- 4. 3 ?IoT環境によりモノやシステムを連携協調させ新しい価値を創造 ?連携協調のためのデータ処理はクラウド?エッジ双方とも必要 解析 制御 クラウド (データ処理) ストレージ (データ蓄積) サイバー 空間 ? 大規模化 ? 省電力 実社会 （フィジカル空間） エッジ (データ処理) セキュリティ （データ保護） ? リアルタイム ? 省電力 解析/制御 センサ （データ収集） IoT時代の社会システム
- 5. 4 スマート社会に向けたシステム最適化 膨大なパラメータ数に対するシステム最適化が必要 「組合せ最適化問題」をリアルタイムで解く計算技術が必要 交通渋滞の解消 物流コスト最小化 ??????安定供給 分野 交通システム サプライチェーン 電力送電網 課題 最適化対象 入力?????? 制御?????? 最適化問題 計算量 交通量、移動コスト 交通状況 各車の目的地 信号、各車 最大????最短経路 2n回: nは制御対象のパラメータ数 総移動コスト 拠点間の移動コスト 移動経路 巡回セールスマン 蓄電量、等 発電?消費電力量 経路容量 発電量、流路 最大フロー
- 7. 6 量子コンピュータ関連の整理 ?量子アニーリングで実用化が先行 ●ゲート型量子コンピュータの研究が盛ん 古典コンピュータ 量子コンピュータ ゲート型 アニーリング 量子アニーリング (断熱量子計算) ゲート型 量子コンピュータ 特徴 逐次処理 (長時間) 並列処理 一括(超並列)処理 (極短時間) 用途 汎用 最適化 最適化 多目的(アルゴリズム 要) 基本 単位 (古典)ビット 量子ビット - 約100,000 (2018) 約2,000 (2017) 約70 (2018) ソフト 多様なプログラム 限られたアルゴリズム 代表例 CPU, GPU, 等 CMOS アニーリングマシン (日立) デジタルアニーラ (富士通) コヒーレント イジングマシン (ImPACT/NTT) 量子 アニーリング マシン (D-Wave) 量子コンピュータ (IBM, Google, 日立ケンブリッジ, 等)
- 8. 7 アニーリングマシンの原理 J1 2 J14 J4 7 s1 s 4 s7 h2 h3 h7 s2 s5 s8 s3 s6 s9 h1 h4 J7 8 J4 5 J2 3 J3 6 J2 5 J5 6 J89 J6 9 J5 8 h5 h8 h9 h6 組合せ 最適化問題 イジングモデル コスト関数: KPI エネルギー ? ? 入力パラメータ ?相互作用係数: ??? ?外部磁場係数: ?? 制御パラメータ スピン値 ?? +1/選択される -1/選択されない 組合せ最適化問題のコスト関数 イジングモデルに定式化 ? ? = ? ? ?,?=?,?<? ? ?? ??? ?? ? ? ?=? ? ?? ?? イジングモデルの基底状態＝組合せ最適化問題の最適解 ?エネルギーを最小（基底状態）とするスピンの状態が組合せ最適化問題の最 適解に対応 ?問題に応じて係数値を適切に設定することで、様々な分野に展開可能
- 10. 9 エッジ向け : 低コスト、 リアルタイム動作、 室温動作、低消費電力 クラウド向け : 高速動作、 低電力、スケーラビリティ大、 拡張性あり アニーリングマシンの比較 計算手法 従来計算機 量子 アニーリングマシン ＣＭＯＳ アニーリングマシン アプローチ 汎用CPU 超伝導素子 半導体(CMOS) スピンの構成 デジタル 量子ビット (重ね合わせ有) デジタル 解の種類 近似解 近似解 近似解 計算時間 (解精度) × ◎ ○ 動作温度 室温(冷却必須) 15mK 室温 動作時電力 10-1,000W 15,000W (冷却電力含 む) 0.05W スケーラビリティ (スピン数/チップ) 可能 512 ('12) → 2048 ('17) 20,480 (‘15) → 100,000 (‘18) 拡張性 可能 不明 複数チップ接続可
- 11. 10 半導体を用いたアプローチでめざす性能 ? 拡張性 ?スピン数の大規模化 ?多数スピンから少数スピンを同じ構造で提供 ? 省電力性 ?エッジデバイスで使えるレベルの省電力化 ? 使いやすさ ?どんな環境でも動作 ?小型化 ? 製造容易性 ?大量生産可能な形態 ? そこそこの精度 (最適解は別の手法に期待)
- 12. 11 ? イジングモデルをCMOS回路で模擬 ? 製造が容易, 使いやすい, 高いスケーラビリティ CMOSアニーリングマシン CMOS回路イジングモデル J12 J23 J14 J25 J36J45 J56 J47 J58 J69 J78 J89 s1 s2 s3 s4 s5 s6 s7 s8 s9 イジングモデル スピンの状態si , +1/-1 相互作用 Jij s1 J12 J23 J45 J56 J78 J89 J14 J25 J36 J47 J58 J69 s2 s3 s4 s5 s6 s7 s8 s9 CMOS メモリ "1"/"0" 相互作用係数: メモリ スピン値の更新: デジタル回路 CMOS circuit mimicking Ising model +1 / -1 "1" / "0"
- 13. 12 ? スピン間相互作用によりイジングモデルのエネルギーはランドスケープに沿って減少 ? 局所解を避けるためランダムにスピン値を破壊 ? 必ず最適解が求まるわけではない (工学的にはOK) CMOSアニーリング ?Transition to lower energy (interaction as in previous slide) ?Avoidance of local minimum solution by randomness Energyofsystem H(KPI) Spin status (2n patterns) Solution n: number of spins
- 14. 13 概要 ? CMOSアニーリングマシンの概要 ? プロトタイプの開発状況 ? 実用化に向けた周辺技術開発状況 ? まとめ
- 15. 14 65nmプロセスを用い、20kbit対応のCMOSアニーリングチップを試作 4mm 3mm 項目 値 製造プロセス 65nm チップサイズ 4x3=12mm2 スピン数: n 80x128x2=20kスピ ン メモリIF 100MHz 相互作用動作 100MHz 動作電流 (1.1V) Write: 2.0 mA Read: 6.0 mA 相互作用: 44.6 mA 第1世代 試作チップ
- 16. 15 ? 2Uのラックマウント型のイジングノード ? 2チップのイジングコンピュータをFPGAで制御 ? PC/サーバよりLAN経由でアクセス 第1世代 試作ノード 開発したイジングノード 形状 2Uラックマウント型 動作速度 100MHz スピン数 40k (2チップ) OS Linux アニーリングチップ
- 17. 16 ? 乱数列をジグザグの経路で入力 ? 乱数列に含まれる”1”の数を調整することでSAの温度の効果を再現 1-bit PRNG 1-bitPRNG PRNG: Pseudo Random Number Generator Zigzag paths Spin inversion using random pulse ? Output of the interaction circuit will be inverted if both of the random pulses are ‘1’ Majority voterSpin unit XORSpin Random pulse 1 Randompulse2 M. Hayashi et al., "An Accelerator Chip for Ground-state Searches of the Ising Model with Asynchronous Random Pulse Distribution," 6th International Workshop on Advances in Networking and Computing 乱数列入力によるランダム動作(1) AND
- 18. 17 Mark ratio during ground-state search ?Decreasing mark ratio has similar effect to cooling schedule in Simulated Annealing PRNG Controlling mark ratio of 1bit PRNG Comparator Threshold e.g. LFSR 0 (r < Threshold) 1 (Otherwise) 1bit PRNG output @High threshold (0.75) 1bit PRNG output @Low threshold (0.25) r 1bit PRNG 0 1 0 1 0 0.2 0.4 0.6 0.8 1 Mark ratio Expected spin flip rate Time Aggressively escape from local minima Settle to nearby low energy solution Time Time 乱数列入力によるランダム動作(2) ? スピン値がフリップする確率を調整 ? 計算が進むにしたがってフリップ率を低下させる
- 19. 18 ?実応用に向けた検討を推進するため、新型半導体コンピュータを様々な構成で 試行することが可能なプロトタイプ環境を構築 ?プロトタイプ(第2世代)にて組合せ最適化問題を処理させることが出来た 第2世代 プロトタイプ 制御用PC ?FPGAの制御 ?グラフ埋め込みアルゴリズム FPGAと制御用PCを接続 再構成可能な半 導体素子FPGA を用いてプロトタ イプを構築 FPGA: Field Programmable Gate Array
- 20. 19 ?多数決回路の前の段階での乱数の挙動は第1世代と同様 ?グラウバーダイナミクスの確率的な挙動とは異なる 第2世代の動作アルゴリズム ◆Signals to inverters n+ : number of signals with “1” at red dots n? : number of signals with “0” at red dots ◆Glauber dynamics P+ : probability that the spin state is +1 through spin update in accordance with Glauber dynamics N H[1] Inverter H[0] Inverter J1[1] Inverter J1[0] N1 Inverter JL-1[1] Inverter JL-1[0] NL-1 Inverter …… Majorityvotercircuit
- 24. 23 スケーラブルなFPGA間接続 伝送回路 伝送回路 伝送回路 FPGAボード 伝送回路 … … … ケーブル ケーブル ケーブルケーブル 要素(パラメータ) 要素間のつながり ?チップ端のパラメータ値を伝送することで一体の大規模なコンピュータとして動作 ?局所的な伝送のため、多数のFPGAボードをスケーラブルに接続可能 FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA FPGA
- 25. 24 100kbit CMOSアニーリングマシン緒元 項目 内容 パラメータ数 102,400 イジングモデルの結合 部分結合型 FPGA枚数 25枚 (1枚あたり4,096) FPGA動作周波数 82.5MHz パラメータ分解能 5bit (±15) 使用FPGA Xilinx? UltraScale? FPGA間インターコネクト Xilinx? Aurora?
- 26. 25 性能比較 ? 100Kパラメータ時従来計算機に対して156倍の速度向上を確認 ? パラメータ数が大きいほど速度向上が大きくなる 評価条件 従来計算機との速度比較 ランダムに生成したイジングモデルの基底状態探索をCMOSアニーリングマシン及び従来計算機 (CPU)上のSAで実行し、既存のアルゴリズムで得られる基準精度に到達するまでの時間を比較 CMOSアニーリング(4K) CPU(4K) CMOSアニーリング(100K) CPU(100K) 0 0.2 0.4 0.6 0.8 1 1.2 0.1 1 10 100 1000 相対精度 経過時間(msec) 10.527msec 1648.9msec 156.38倍速
- 27. 26 ? Map of annealing machine and algorithms さらなる高性能化に向けて Digital Analog Quantum(-inspired)Non-Quantum Quantum annealing machine New CMOS annealing machine with SQA Coherent Ising machine Software SQASoftware SA Optoelectr onic silicon chip CMOS annealing machine
- 28. 27 ?性能を向上させるためにSQAアルゴリズムを取り込み ?擬似的に量子効果を組み込むことで解精度を向上 Value Algorithm Simulated Quantum Annealing (SQA) Implementation FPGA Topology King graph # of spins 2500 (50×50) # of replicas 32 Coefficient 8 bits (0, ±1, …, ±127) Interaction 50 MHz Xilinx VCU108 Evaluation Board FPGA Xilinx UltraScale XCVU095 PCI Express Extension Cable Host PC (Linux) 第3世代 プロトタイプ
- 29. 28 Simulated Quantum Annealing monotonically increasing Hamiltonian for Simulated Quantum Annealing 1st replica 2nd replica Strength of coupling between replicas J+ Mth replica … ?SQA方式により量子重ねあわせ効果を再現 ?デジタル回路でSQA方式を実装
- 30. 29 最適化問題計算時の速度比較 ?従来方式(シミュレーテッドアニーリング: SA)と比較して40倍高速に最適化処 理を実行 Note: ? Total annealing time means a time to obtain 99.9% solution with a probability of 99% ? 200 different random Ising models on a king graph are used ? We run the optimized SA program on a state-of-the-art CPU (Intel Core i7-6700K, 8 threads) x40 x15
- 31. 30 さらなる用途の拡大に向けて サイズ ビット数 ラック カード ノード 1k 10k 100k 第1世代 (ASIC) 2015/02発表 第2世代 (FPGA) 2016/06発表 大規模第2世代 (FPGA) 2018/06発表 第3世代 (FPGA) 2017/10発表 小型マシン (ASIC) 2019/02発表 クラウド エッジ
- 34. 33 性能比較（計算時間） ? アニーリング処理高速化（二十数マイクロ秒で収束）を確認 ? 2?30Kパラメータ時従来計算機に対して約2万倍の速度向上を確認 評価条件 従来計算機との速度比較 ランダムに生成したイジングモデルの基底状態探索をCMOSアニーリングマシン及び従来計算 機(CPU)上のSAで実行し、既存のアルゴリズムで得られる基準精度に到達するまでの時間を 比較 ただし、CMOSアニーリングマシンはI/Oの処理時間を含んでいない イジングモデルの エネルギー値 計算時間 (sec) 1m 10m 100m 1100?10?1?100n 5.0?104 0 ?5.0?104 ?1.0?105 ?1.5?105 ?2.0?105 ?2.5?105 CMOS アニーリング マシン 従来計算機（CPU*） 約２万倍高速化 22 ?s
- 35. 34 性能比較（２チップ接続動作） ? 最大カット問題（”ABCDパターン“）で２チップ動作を確認 ? 計算終了時にチップ境界が計算結果に影響を与えていないことを確認 4.0?105 2.0?105 ?2.0?105 ?4.0?105 ?6.0?105 ?8.0?105 0 5 10 15 2520 0 (iii) (ii) (i) (iii) 21.8 ?s (最終状態) (ii) 7.7 ?s (i) 0 ?s (初期状 態) Chip A Chip B イジングモデルの エネルギー値 計算時間 (?sec) 1ピクセルが１パラメータに対応
- 36. 35 性能比較（エネルギー効率） ? 2?30Kパラメータ時に約17万倍の電力効率向上を確認 ? パラメータ数が大きいほど電力効率向上が大きくなる 評価条件 従来計算機とのエネルギー効率の比較 ランダムに生成したイジングモデルの基底状態探索をCMOSアニーリングマシン及び従来計算機(CPU) 上のSAで実行し、既存のアルゴリズムで得られる基準精度に到達するまでの時間で比較 CMOSアニーリングマシンはI/Oの処理時間も含む 電力効率 ? Τ問題のサイズ 計算時間 消費電力 Energy-efficiencyratio (annealingprocessor/CPU*) Number of activating spins 256 1024 4096 16384 65536 1.0?105 1.0?104 1.0?102 1.75?105 times improved 1.0?103 2200 times improved Previous work This work
- 37. 36 概要 ? CMOSアニーリングマシンの概要 ? プロトタイプの開発状況 ? 実用化に向けた周辺技術開発状況 ? まとめ
- 38. 37 交通渋滞の解消 アプリ 課題抽出 イジングモデル 実用化に向けて J12 J23 J14 J25 J36J45 J56 J47 J58 J69 J78 J89 s1 s2 s3 s4 s5 s6 s7 s8 s9 J12=x, J23=y, ... 計算機技術 交通渋滞の解消物流コスト最小化 ポートフォリオ最適化 分野 交 通金 融 ソフトウェア 問題 マッピング 埋め込み 最短経路最大フロー ナップザック問題 イジング計算機 電 力 コミュニティを形成し新型計算機の潮流形成 ユーザー連携でPoC実施 大学連携等オープンに開発を推進
- 39. 38 2. ドローン通信 順序最適化 1. 無線基地局の 周波数割り当て 3. 通信網の 堅牢性確保 4. 画像修復 6. 画像ノイズ除去 8. コミュニティの コア検出 7. 施設配置 9. 機械学習 (ブースティング) 5. 爆発物 探知の高速化 検出 検出 アプリ実行例
- 40. 39 問題マッピングの難しさ 従来計算 ナチュラル コンピュー ティング 最 適 化 問 題 近 似 解 物理現象に 問題を写像 問題 入力 プログラム に分解 ? 従来は長年培ったプログラムで問題を記述 ? 多くの優秀なプログラマ ? コンパイラへの技術の蓄積 ? 問題の写像により実問題を解ける形に ? 問題写像の技術蓄積未 ? コンパイラのような技術も立ち上げ未 基底/平衡状態遷移 (アニーリング) 観測 解を繰返し探索
- 41. 40 数分割問題(Number Partitioning) S = { 3, 1, 4, 15, 92, 65, 35, 89, 79, 32, 38, 46, 26, 43, 38, 32, 79, 50, 28, 84} 1, 65, 35, 38, 46, 26, 38, 79, 28, 84 3, 4, 15, 92, 89, 79, 32, 43, 32, 50 440 439 ? 与えられた数の集合を出来るだけ和が同じになるように分割する ? 係数値を考える必要あり
- 42. 41 Original formulation Ising formulation of NPP wi : value of i-th element of the set S σi : label of i-th element 数分割問題(Number Partitioning) ? Formulation of NPP mapped to Ising model formulation
- 43. 42 Ising formulation of constrained NPP Original formulation wi : value of i-th element of the set S σi : label of i-th element Same number of items for each group 数分割問題(Number Partitioning) ? Formulation of NPP mapped to Ising model formulation
- 45. 44 北大?日立で実問題への適用を検討（実用化に向けた研究開発を加速） 問題１ One-to-One マッピング 問題２ マイナー埋め込み 組織の枠を超えて幅広くアイデアを募集（プロコンを活用） 北大日立共同プログラムコンテスト ? 北大?日立で構想?作問?評価基準を策定（課題を抽象化し、これまでイジングを知らなかった国内外 の優秀なプログラマからアイデアを募集） ? グラフ変換アルゴリズムにフォーカスしたプロコンを開催 ? 本コンテスト参加をきっかけに、実際にイジング計算機を使ってみたいなど、本研究全体に興味をもって もらえるユーザが増えることを期待
- 46. 45 ?2017年: グラフ埋め込みに関するコンテスト ?2018年: 高次の多項式を2次の多項式に置き換える技術に関するコンテスト プログラムコンテストの実施 組合せ最適化問題 前処理【定式化?グラフ変換】 入力パラメータ(???, ??)の書込み CMOSアニーリングマシン スピン状態の読出し(??) 最適解 CPU CPU 2018年度：定式化 ? ? = ? ?=? ? ?? ? ?? + ? ?<? ??? ? ?? ?? + ? ?<?<? ???? ? ?? ?? ? ? + ? 追加する変数、項の数、係数幅を 可能な限り最小な形で変換せよ? ? = ? ? ?,?=?,?<? ? ?? ??? ?? ? ? ?=? ? ?? ?? 【イジングモデル(2次)】 201７年度：グラフ変換 定式化後（複雑で不規則） ハードウェア（単純で規則的） 接続関係を 保持して変換 【最適化したいコスト関数(高次)】
- 47. 46 ? CMOSアニーリングマシンへアクセスする環境を構築 ? 豊富なチュートリアルとデモおよび実験環境を提供 クラウド環境の提供 https://annealing-cloud.com/ ? 3月中旬に機能アップしました(相互作用係数Jij 8bit版をリリース)
- 48. 47 まとめ ? IoT時代の到来から新しい計算手法を提案 ? 組合せ最適化問題を解くためのCMOSアニーリングマ シンを開発 ? 技術の拡がりをめざしてエッジ?クラウド双方に向けた技 術開発を継続中 ? 実用化に向けてアプリケーションやソフトウェアの開発が 必須 ? 新しい技術の立ち上げには、さまざまなレイヤ?分野の 技術者との協創が必要