![研究の背景
センシング技術の普及などに伴って
大量のデータが生成され続けている
4
今後センサデータはますます増加する
[1]
9000 [EB]
6000
3000
2005 2010 2015
Sensor
Social media
Voice
Enterprise
Data reuse & repurposing
make innovations
Information
explosion
Sensor Data
温度
湿度
振動(地震)
放射能
イメージジャイロ
ガス
赤外線
[1]](https://image.slidesharecdn.com/hayashifpgax-150202033138-conversion-gate01/85/FPGAX6_hayashi-4-320.jpg)
More Related Content
What's hot (20)
Similar to FPGAX6_hayashi (20)
![[DL Hacks]FPGA入門](https://cdn.slidesharecdn.com/ss_thumbnails/dlhacksfpgabeginner-180627050145-thumbnail.jpg?width=560&fit=bounds)
FPGAX6_hayashi
- 2. 2 はじめに 慶應義塾大学理工学部 ４年 松谷研究室 林 爱美（はやし あみ） 2014年 2月 ハードウェアの研究室に強制的に配属 7月 FPGAと出会う 12月 外れ値検出FPGA NICが完成！ 2015年 1月29日 リコンフで研究会デビュー 1月30日 卒論提出 1月31日 卒論発表 2月1日 fpgaxに呼んでもらった！ 祝！学部卒業決定！（多分）
- 3. 3 はじめに 慶應義塾大学理工学部 ４年 松谷研究室 林 爱美（はやし あみ） 2014年 2月 ハードウェアの研究室に強制的に配属 7月 FPGAと出会う 12月 外れ値検出FPGA NICが完成！ 2015年 1月29日 リコンフで研究会デビュー 1月30日 卒論提出 1月31日 卒論発表 2月1日 fpgaxに呼んでもらった！ 昨日発表した卒論の研究 ＋ 今後どうやって研究を広げようかな 祝！学部卒業決定！（多分）
- 4. 研究の背景 センシング技術の普及などに伴って 大量のデータが生成され続けている 4 今後センサデータはますます増加する [1] 9000 [EB] 6000 3000 2005 2010 2015 Sensor Social media Voice Enterprise Data reuse & repurposing make innovations Information explosion Sensor Data 温度 湿度 振動(地震) 放射能 イメージジャイロ ガス 赤外線 [1]
- 5. 今回の研究目的 Storage 5 NIC Host CPU 気温 20.0, 20.0, 20.0, 20.0, 20.0, 20.1, 20.0, 20.0, 20.0, 20.0, 20.0, … 20.1 20.020.0 20.0 19.9 20.0 20.0 20.0 20.0 20.0 20.0 20.0 20.0 20.0 20.0 センサデータは ストレージに全部置くと 非効率になる場合がある
- 6. 今回の研究目的 6 センサデータは ストレージに全部置くと 非効率になる場合がある NIC Host CPU Data Mining アプリケーションレベルで 選択処理をすると負荷が高くなる 気温 20.1 20.020.0 20.0 19.9 20.0 20.0 20.0 20.0 20.0 20.0 20.0 20.0 20.0 20.0 Storage
- 7. 今回の研究目的 7 StorageNIC Host CPU Data Mining Storage 気温 20.1 20.020.0 20.0 19.9 20.0 20.0 20.0 20.0 20.0 20.0 20.0 20.0 20.0 20.0 NIC内で選択処理 をする！ センサデータは ストレージに全部置くと 非効率になる場合がある アプリケーションレベルで 選択処理をすると負荷が高くなる FPGA NIC の利用
- 8. NetFPGA-10G ? Xilinx Virtex-5 XC5VTX240TFFG1759 -2 - HDL(Verilogなど)でNICが実装されている - GitHubでフリーのライブラリもダウンロード可能 - 10G MACはXilinx のIPコア(商用) ? 4 SFP+ interfaces ? PCI Express Gen 2 x8 8
- 9. 9 FPGA NIC向けデータマイニング StorageNIC Host CPU Data Mining Storage 気温 20.1 20.020.0 20.0 19.9 20.0 20.0 20.0 20.0 20.0 20.0 20.0 20.0 20.0 20.0 通常の「FPGAによるデータマイニングの高速化」と何が違うのか？ FPGA NIC内で不必要なデータを捨てることで ホストのネットワークプロトコルスタック上の処理による負担を 軽減することができる ホストは入力データセットの全体を知ることができない
- 10. 10 FPGA NIC向けデータマイニング ホストは入力データセットの全体を知ることができない という条件によって新たな問題が起こるか？ モデルの更新が逐次的 モデルの更新は別途 既存手法でOK 更新はホストに まかせたい 更新もFPGA上に 構築可能 既存手法でOK 既存手法が使えない！ 高頻度で更新 資源が十分 高速化しやすい 低頻度で更新 オフロードの コストが高い 教師あり学習 Random forest ナイーブベイズ 異常検出
- 11. 選択的取得のための手法 ? 外れ値検出 - マハラノビス距離の利用 - LOF法 ? 変化点検出 ? 異常行動検出 - ナイーブベイズ 今回のターゲット 11 ? k-means ? Random forest ? Apriori ? FP-Tree アイテムセットマイニング クラスタリング 異常検出 頻出するアイテムセット 特定のクラスタに属する データ 異常なデータ
- 12. 0 2 4 6 8 10 12 0 2 4 6 8 10 12 マハラノビス距離 大 マハラノビス距離 小 分散 小 分散 大 マハラノビス距離を用いた外れ値検出 特徴ごとの分散の相関を考慮した距離 New Sample 1 New Sample 2 Center of Gravity マハラノビス距離が 大きいほど 外れ値の可能性が 高い！ 12
- 13. ? = 1 ? ?=1 ? ?? ? ? ? ?Σ?1 ? ? ? > ? マハラノビス距離を用いた外れ値検出 Σ = 1 ? ?=1 ? ?? ? ? ?? ? ? ? ?? ∶ サンプル ? ∶ 平均ベクトル マハラノビス距離 ? : データセット内のサンプル数 ? 共分散行列 - 各特徴の分散を相関づけるための行列 - ホストから定期的に与えられる 13
- 14. Client Packet (sample) generate Packet header check Outlier detection using Mahalanobis distance Packet filtering Packet Sample Data Outlier Bit FIFO Buffer for Packet Selective Packet Packet Packet Outlier Filtering FPGA NIC Sample DataCovariance Matrix User Application Host Covariance Matrix Calculation Packet dump システムの全体図 14 Σ = 1 ? ?=1 ? ?? ? ? ?? ? ? ? Σ?1 掃き出し法
- 15. 実装方法（マハラノビスの部分） FIFO Operation Total Value Calculate Multiply Start Temporally Add Multiply Start Total Add Outlier Check FIFO Buf (深さ?) Multiplexer Multiplexer 2 cycle 2 cycle 2 cycle 2 cycle 2 cycle 2 cycle Target Data 2 cycle 2 cycle2 cycle 2 cycle Outlier Bit ? = 1 ? ?=1 ? ?? Ⅰ tmp = ? ? ? ?Σ?1 Ⅱresult = tmp ? ? ? ? = ? ? ? ? Σ?1 ? ? ? Ⅲ result = ? ? ? ? Σ?1 ? ? ? > ?2 Ⅳ Host 15
- 16. Smp 1 Smp 2 Smp 1 Smp 3 Smp 2 Smp 1 Smp 3 Smp 2 Smp 1 Smp 3 Smp 2 Smp 1 Smp 3 Smp 2 Smp 1 Smp 3 Smp 2 Smp 1 Smp 3 Smp 2 Smp 1 Smp 3 Smp 2 Smp 1 Smp 3 Smp 2 Smp 3 Packet Header check FIFO Op Multiply Cal Tmp Add Total Cal Multiply Cal Total Add Outlier check Packet Filtering clock cycle 2 FPGA NIC 内のサンプルの流れ 1サンプルあたり2サイクルで選択的取得が可能 NetFPGA-10Gは160MHzで動作しているので… （理論上）秒間8000万サンプルを処理可能 16
- 17. 評価：最大スループット 評価環境 サンプルデータ ? 64ByteのUDPパケットにサンプルデータが1つ ? 特徴は32bitの整数型 FPGA NIC ? NetFPGA-10G - Xilinx Virtex-5 XC5VTX240TFFG1759 -2 (160MHz) - 4 SFP+ interfaces - PCI Express Gen 2 x8 ? Xilinx ISE 13.4 ホスト ? Intel Core i5-3470S (2.9GHz, 32GB, 4 cores) ? CentOS 6.5 17
- 18. 64 128 192 256 320 384 448 512 0 2000000 4000000 6000000 8000000 10000000 12000000 14000000 16000000 パケット長(Byte) 送信可能パケット数(packet/sec) 外れ値フィルタリングNICによるサンプル処理数 NetFPGA-10Gからホストへの最大サンプル転送数 95.8% 5.6% 評価：最大スループット 外れ値フィルタリングNICの実機評価による最大スループット 10GbEにおけるパケット受信数の理想値 FPGA NIC - ホスト間の帯域に制限されない 18
- 19. 評価：面積 19 16 32 64 128 256 512 1024 2048 0 50000 100000 150000 200000 250000 300000 350000 400000 450000 2 3 4 5 2 3 4 5 0 20 40 60 80 100 120 140 24 48 80 120 Register Slice CLB使用個数 DSP48Eスライス使用個数 特徴数 FIFOバッファの深さ 特徴数 DSP 149760 96 NetFPGA-10G(Virtex-5 XC5VTX240TFFG1759 -2)の資源 {特徴数×(特徴数 + 1)} × 4 のDSPが必要 BRAMを利用しなくても 512 ~ 1024 の深さの32bit幅FIFOを用意することは可能
- 20. 本来のマハラノビス距離を用いた外れ値検出との違い によって、精度がどの程度低下するか？ 外れ値フィルタリングNICにおいて何を“精度”とするか ? 外れ値と検出されなかったパケットは捨ててしまう ?100％～99％の外れ値を外れ値として検出できる時に、 どの程度外れ値以外のサンプルを外れ値と判定してしまうか 外れ値フィルタリングNICと本来のアルゴリズムとの違い 本来のアルゴリズム 外れ値検出NIC 浮動小数点で計算 整数型で計算 1サンプルが入力されるごとに 共分散行列を計算 共分散行列は定期的にホストCPU が計算する 平均値、共分散行列を求めるために、 ある程度大きなデータセットを扱う 計算に用いることの出来るデータ セットは、FPGA上のFIFOバッファに 入るだけのもの 20 評価：精度
- 21. 評価環境（データセットの生成） 評価：精度 ? 特徴数 ２ （相関 0.8） ? 各特徴はガウス分布に沿って生成 ? x = 1 2??2 exp ? ? ? ? 2 2?2 ? = 30 ? = 3 ? = 300 ? = 10 通常値 （外れ値以外） 外れ値 ? 1000万サンプルをソフトウェアによるマハラノビス距離を用いた 外れ値検出により分類 ? 外れ値の割合は1％ ? 上式 x や外れ値の分布はrand関数により生成 21
- 22. 16 32 64 128 256 512 1024 2048 0 20 40 60 80 100 Int, 0 Int, 30000 Double, 0 Double, 30000 16 32 64 128 256 512 1024 2048 0 20 40 60 80 100 Int, 0 Int, 30000 Double, 0 Double, 30000 評価：精度 FIFOバッファの深さ(マハラノビス距離を計算するために 使うサンプルデータの数）による精度の変化 外れ値は通常値の10倍、データセットは純粋なガウス分布に基づく 外れ値検出率100％ 外れ値検出率99％ 誤認率（％） FIFOバッファの深さ FIFOバッファの深さを十分に確保できれば、精度に差は出ない 22
- 23. 0 1000 10000 20000 30000 40000 50000 100000 0 0.2 0.4 0.6 0.8 1 1.2 評価：精度 共分散行列の計算頻度による精度の変化 誤認率（％） 整数型アルゴリズムの精度の変化 外れ値検出率100％ 浮動小数点型の時は計算頻度に かかわらず誤認率0％ 共分散行列の計算頻度 （サンプルn個ごとに計算） 外れ値は通常値の10倍、データセットは純粋なガウス分布に基づく 整数型でも誤認率は最大でも １％強に留まり、 外れ値検出率を99.999％まで 下げると誤認率は0％になる 理想的なデータセットを扱う場合、 共分散行列の計算頻度はほぼ 精度に影響しない 23
- 24. まとめと今後の研究 フィルタリング FPGA NICは様々な選択的取得のための アルゴリズムに適応可能 LOF法, k-means, etc… ネットワークからサンプルをストリームデータとして受信、 そのまま選択的取得処理を行いたい場合に向けた研究 マハラノビス距離を用いた外れ値検出により パケットをフィルタリングするFPGA NIC を提案 計算上、1秒間に最大8000万サンプルを処理可能 実機評価でも10GbEラインレートに近い値を観測 今後の研究 24
- 26. 26 FPGA NIC向けデータマイニング ホストは入力データセットの全体を知ることができない という条件によって新たな問題が起こるか？ モデルの更新が逐次的 モデルの更新は別途 既存手法でOK 更新はホストに まかせたい 更新もFPGA上に 構築可能 既存手法でOK 既存手法が使えない！ 高頻度で更新 資源が十分 高速化しやすい 低頻度で更新 オフロードの コストが高い 教師あり学習 Random forest ナイーブベイズ 異常検出
- 27. 選択的取得のための手法 ? 外れ値検出 - マハラノビス距離の利用 - LOF法 ? 変化点検出 ? 異常行動検出 - ナイーブベイズ 27 ? k-means ? Random forest ? Apriori ? FP-Tree アイテムセットマイニング クラスタリング 異常検出 頻出するアイテムセット 特定のクラスタに属する データ 異常なデータ 主成分分析（次元削減）
- 28. 28 LOF法 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 外れ値 特徴 1 特徴2 ? 密度ベースの外れ値検出 ? ノンパラメリック 例えば… FPGA上に大きなデータセットを保持する ためのメモリを確保したくない（忘却が早い） ↓ 比較的小さな集合は集合として見れない （外れ値と判定されてしまう） LOF法とは別にフィルターを用意して、 外れ値としてホストに送られてくるパケット が高頻度だった場合、 ホストがフィルターを更新して小集合を フィルター
- 30. 30 k-means 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 大 小 大 小 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 クラスタ更新前 クラスタ更新後 クラスタの重心 A B A B ?1 ?3?2 ?1′ ?3′?2′ 特徴 1 特徴2 ? クラスタリングアルゴリズム ? k-means++, k-means # など ? オンライン処理なので、 一度クラスタに配属されたら 後からの変更なしとする （重みで更新する） 例えば… 古いサンプルは忘却したいので、 サンプルの順序を覚えておく必要 ↓ FPGA内で全部データセットを保持し たくない
- 31. 31 k-means FPGA NIC ホスト 順番どおりに データセットの情報を管理 特定クラスタの サンプルデータ クラスタの重心を 更新 新たにクラスタ1に配属されたサンプル{個数, 重心}, 新たにクラスタ2に配属されたサンプル{個数, 重心}, … 特定個数 が溜まっ たら
- 32. 32 主成分分析 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 特徴空間の再構成をするための手段 次元削減 ? 画像認識、マーケティングなど 幅広く利用される ? データマイニングの前処理にも 低頻度でも行えば精度向上するかも？ マハラノビス距離を用いた外れ値検出 も含めて、データマイニングアルゴリズム の前処理として載せてみたい やり方はまだ考えてません… でも卒論の手法でできるかな？
- 33. Client Packet (sample) generate Packet header check Outlier detection using Mahalanobis distance Packet filtering Packet Sample Data Outlier Bit FIFO Buffer for Packet Selective Packet Packet Packet Outlier Filtering FPGA NIC Sample DataCovariance Matrix User Application Host Covariance Matrix Calculation Packet dump システムの全体図 33 Σ = 1 ? ?=1 ? ?? ? ? ?? ? ? ? Σ?1 掃き出し法