情報処理学会創立50周年記念（第72回）全国大会

2L-7
データストリーム処理を用いた変化点検知の実装と GPU による性能最適化
森田 康介†

高橋 俊博‡

東京工業大学†鈴村 豊太郎†‡IBM 東京基礎研究所‡

1. はじめに
近年、工場の生産ラインにおける機械の故障やエラーの監視の為に熱や速度を常に計測するセンサーデータの普及や、ボットネットなどサイバーテロの監視に使われるサーバのオンラインデータの観測など、リアルタイムに複数のデジタルデータからの情報を抽出し、変化点・異常検知を実現する需要が高まっている。本稿ではデータストリーム処理システム System S を用いたリアルタイムの異常検知アルゴリズムの実装と GPU による高速化について述べる。
2. 変化点検知 の データストリーム
データ ストリーム処理
ストリーム 処理と処理 と GPUを用いた高速化
いた高速化
本稿では変化点検知のアルゴリズムとして特異スペクトル変換 SST(Singular Spectrum Transformation)[1]を対象にする。
2.1 変化点検知
変化点検知アルゴリズム
検知アルゴリズム SST
SST は古典的な変化点検知の一つである。
観測される時系列データの背後にあるデータ生成機構を想定した際にその生成機構の構造的な変化の検出を扱うので、特にヘテロな動的システムに非常に適した特徴を持つ。また、他の手法とは異なり特定の確率モデルを仮定しない為、入力時系列の多様性に比較的頑強であり局所解の心配がない。実用例として自動車のセンサーデータの監視やサーバ群のエラー検知などがある。この SST においては特異値分解 SVD(singular value decomposition)が実行時間全体の多くを占める為、ウィンドウ幅を大きく取ると従来の計算環境では実時間内にスコアを得る事が出来ない。
2.2 データストリーム処理系
データストリーム処理系 System
System S
データストリーム処理とは、多様なセンサーから時々刻々到着する大量データをオンメモリ上で処理することにより、従来のバッチ処理と比較してリアルタイム性及び処理の効率化を実現する計算パラダイムである。昨今、このようなデータストリーム処理を汎用化した並列分散ミドルウェア及びプログラミングモデルの研究
Implementation of Change-Point Detection by Data
Stream Processing and Optimization via GPU.
Kosuke Morita †, Toshihiro Takahashi ‡ andToyotaro Suzumura † ‡.
† Tokyo Institute of Technology‡ IBM Tokyo Research

1-79

開 発 が 活 発 に 行 わ れ て お り 、 我 々 は IBM
Research によって開発された処理系 System S[4] を用いる。
System S は SPADE [4] と呼ばれるストリーム処理に特化したデータフロー型の言語とそれを支える分散処理系から構成される。SPADE ではデータの流れをストリーム、処理ロジックをオペレータと呼び、これらをデータフローグラフとして表現することで記述する。オペレータは射影処理を行う Functor, ウィンドウ処理を行う
Aggregate, セ ン サ ー デ ー タ の 受 信 を 行 う
Source, データの送信を担当する Sink など 10
数種類の組込みオペレータと、ユーザが独自にC++ や Java によって定義したユーザ定義のオ
ペ レ ー タ UDOP (User-Defined Operator) から構成される。また、マルチコア、メニーコアで構成されるクラスタ上で稼動し、ユーザがSPADE プログラムのオペレータに属性を付加することによって、オペレータのノード割り当てや複数オペレータの融合などを自動的に行う。
2.3 System S/S
S/SPADE による SST の実装
System S/ SPADE による SST 実装のコード断片を図 1 に示す。
#define WINDOWSIZE 100
stream InputData(data : Float):= Source{file:///input.csv,nodelay,csvformat}
stream SubsequenceData(datalist : FloatList):= Aggregate(InputData){count(WINDOWSIZE),count(1)}[Col(data)]
stream SST(score : Float):= UDOP(SubsequenseData)[SSTComputation] {GPUEnabled=false}-> node(ComputeNodePool,0)
Nil := Sink{file:///score.out,nodelay,csvformat}[図 1] SPADE プログラム（一部）Source：センサーからの時系列データを読み込
Sourceみデータストリームとして排出,
Aggregate：決められたウィンドウサイズ分の部
Aggregate
分データをバッファリングしてリスト型のデー
タストリームに加工,パラメータとしてはウィン
ドウサイズとスライドさせるサイズを指定(図 1
ではそれぞれ、100 と 1 が指定されている)
UDOP（UDOP （ ユーザ定義
ユーザ 定義オペレータ定義 オペレータ）
オペレータ ） ：Aggregate に情報処理学会創立50周年記念（第72回）全国大会

1-80

sec60

GPUCPU

SST on System S

50

CPU(compression)

4030

20

10

1000

window_size

500

050

よってバッファリングされたある範囲のデータに対して SST を実行し、変化度合いのスコアを計算。SST における SVD 演算は C++の線形代数
ライブラリ newmat10[6] を使用。
Sink：UDOPから受け取ったスコアを外部に出力
Sink
2.4 GPU による高速化による高速化
前章では C++ の行列演算ライブラリを CPU上で実行することによって System S の SST を実装したが、SVD は計算量 が O(n3)のため重く、ウィンドウサイズの増加に比例して実行時間も指数関数的に増大する。そのため、応答時間が重要視される変化点・異常検知のアプリケーシ
ョンにおいては、比較的長期間の異常パターンを検出することが困難になる。我々はこの問題に対して、SVD の計算部分を、近年科学技術計算において様々な高速化が検証されている GPU上で計算を行うことによって高速化を実現する。
SVD 演算の GPU による高速化にあたっては深谷らなどの研究[3]もあるが、今回は線形代数ライ
ブラリ LAPACK を CUDA (Version 2.3) 上に移植した CULA Basic (Version 1.0) [5]の SVD 関数を用いた。System S 上では、ユーザ定義のオペレータ UDOP において、CULA ライブラリのSVD 演算 を呼び出すように改変することで実装した。但し、SPADE プログラムのレベルでは、図１の SPADE プログラムを再利用することがで
き 、 UDOP オ ペ レ ー タ に 渡 す パ ラ メ ー タ
GPUEnabled を true にすることで、SVD 計算がGPU 上で行われる。
3. 性能評価
評価環境としては 単一ノード上で計測し、CPU は Athlon X2 (2 コア, 2.6 Ghz), メモリ4GB, OS は CentOS 5.2(kernel 2.6.18)を用い,
GPU は NVIDIA 社 の Tesla C1060(240 コ ア ,1.296 Ghz, 4 GB)を用いた。
SVD の 対 象 と な る 行 列 の サ イ ズ を 50 か ら
1,000 まで 50 刻みで SST のスコア算出にかかる時間を計測したところウィンドウサイズ w が400 の時には CPU : GPU が 0.92 秒 : 1.49 秒であるが、w が 450 の時には 2.21 秒 : 1.68 秒となり GPU の方が高速にスコアを算出している結果が得られた。さらに w が 1,000 の場合では55.12 秒 : 4.44 秒 と 約 12.44 倍の高速化が実現できた。
GPGPU においてはメモリ転送などのオーバーヘッドが生じるため小さなウィンドウサイズでは CPU に劣るが、 450 以上の大きなウィンドウサイズで SST スコア を算出する場合に GPUは有効と言える。また、グラフより、ウィンドウサイズの増加に伴って CPU 版では計測時間が450 付近以降は指数関数的に増加しているのに対して、GPU を用いた際には実行時間の増加を抑えることができ、ウィンドウサイズ 1000 においても 4 秒台とアプリケーションによってはリアルタイムな異常検知、変化点検知を実現することが可能になることが示された。
尚、グラフの▲で表されるデータは SVD の行列圧縮[2]を用いて高速化を行った際のデータであるが、この結果に対しても GPU を用いることによる優位性が見て取れる。
4. まとめと今後
まとめと今後の今後の課題
本稿では 変化点検知アルゴリズム SST のデータストリーム処理を System S 上で実装し、また更に GPU を用いて高速化を実現した。その結果、ウィンドウサイズ 1,000 の SST の計算において、従来の計算機環境であれば 55.12 秒 を要していた所を GPU で高速化する事で 4.44 秒 に抑え、大きなウィンドウサイズにおいてもリアルタイム性を実現できることを示した。
今後は、現在の CUDA の仕様により、同時に 1カーネルのみしか実行できない制約の為、センサーデータの 1 次元のみの SST の計測を扱ったが、マルチ GPU の利用や、NVIDIA が開発する複数 カ ー ネ ル を 同 時 実 行 可 能 な 次 世 代 GPU(Fermi) によって多次元の同時計算と性能向上を図る。
参考文献[1] T. Ide and K. Inoue. Knowledge Discovery fromTimeseries Data using Nonlinear Trans-formations,
The 4th Data Mining Workshop of JSSST, 2004.
[2] T. Ide. Speeding up Change-Point Detection
using Matrix Compression. IBIS, 2006.
[3] 深谷 猛, et. al. 正方行列向け特異値分解の CUDAによる高速化. HPCS, 2009.
[4] Bugra Gedik, et. al. SPADE: The System S Declarative Stream Processing Engine, SIGMOD 2008.
[5] CULAtools. http://www.culatools.com/.
[6] newmat: Matrix Library inC++.