Publication 論文 鈴村研究室 大規模データ処理・ストリームコンピューティング

ータ ー 処理 ける GPU タ 並列を用いた

ー 異常検知

司

_†

鈴村 豊太郎

_‡

Scalable Anomaly Detection on Data Stream Processing with GPU Task

Parallelism

_K

OJI

_U

ENO

_and

_T

OYOTARO

_S

UZUMURA

†^{東京 業大学}

Tokyo Institute of Technology

‡ IBM^{東京基礎研究所} IBM Research - Tokyo

1. ^め

近年 ン 技術や ッ ワ 技術

発遉 _IT 高度化 伴

大 ン 得

到来 い ． 伴い 入力

処理 処理 近年活発

研究 産業界 利用 始 い ．

処理 処 く生

情報 流 び

蓄 積 く 逐 次 処 理 い く い う 新

い計算 あ ． ッ 処理 計

算 対 象 全 蓄 積 計 算

従来 手法 遊い 応答 要求

場合や 系列 前後 僅 参

照 い計算や 全 蓄積 物理的 困

難 処理 適 い ．

処 理 ン

ン 処 理 異

常 変化点検知 あ ． 場 生産 ン

監視や 群 検知 ン

得 処 理

解析 異常 検出 いう あ ．異常検知 い 多様 入力 柔 軟 扱 え 変 化 点 検 出 求

処理 蓄積 く 処理 いう新 い

計算 あ ．変化点検知 SST(Singular Spectrum Transformation) ^使

異常検知 処理 一辺 長 ₅₀₀ 行列 演算 必要 ．_GPU

使 高速化 既存手法 い行列 計算 高速化 い． _GPU

並列 解決 ．_GPU 並列 実装 特異値分解 行列 _300-500

４ _CPU 対 ４倍程度 高速化 _IKA-SST ウ ン ウ _{20-500 CPU}

対 ₂₀倍 高速化 遉 異常検知機構 実現 示 ．

Stream computing has emerged as a new processing paradigm that processes incoming data streams in a real-time fashion. On the other hand, many recent efforts have shown the suitability of GPGPU to high performance computing. By bringing two new trends, this paper proposes new innovative method called GPU task parallelism to optimize stream computing with GPGPUs. In this paper we implement the proposed approach over SVD (Singular Value Decomposition) and IKA-SST, a powerful algorithm of change point detection. The experimental results show that the proposed implementation of SVD provides performance gain by around 4 times order against quad-core and the proposed implantation of IKA-SST provides around 20 times order against single-core. This result validates the scalability of our proposed approach.

例え ン 中 常 一定 値 出

続 あ 常 状態 値 変化 続

あ 値 変化 常 変化

異 常 変 化 検 出 い 場 合

あ 単純 対応 い．

SST[1] (Singular Spectrum Transformation) 比較的最近提案 手法 少 い

設定 多様 入力 対応 いう特徴

持 優 変化点検出 あ 最初

提 案 _SST 特 異 値 分 解 (Singular Value Decomposition, SVD) ^{使 計} 算 特異値分解 計算 大 く

多く 処理 い ．

高速 計算 能 近似 _IKA-SST[2] 提案 い ．

近似 使 計算 能

限界 あ ．異常検知 応用例 あ

場 生産 ン 管理 ン 数 数

万 あ 考え 多く

処理 求 い ．

近年 一般向 _PC 搭載

ッ 処理 ニ ッ _GPU 高 い 計算 性能 注 目 GPU ^{ッ 外 汎用計算 利用} 技術 General-Purpose computing on Graphics Processing Units, GPGPU ^{研究 盛}

行わ い ．_CPU 比較 _GPU ン

多 数 積 ッ 高 速

特徴 あ 特徴 活

CPU ^{数倍 性能 発揮 ．}

本論文 _GPU 使 _SST 性能最適化 行う． 々 先行研究_[20] い 特異値分解 使 わ ウ 変 換 二 対 角 化 GPU ^{並列 高速化 行い} GPU 並列 有効性 示 本論文 _GPU 部分 並列化 加え _CPU 計算 部分 連携方

法 示 ン 異常検

知機構 処理系 実装 ．本論文

貢献 示 ．

1. SST ^計算処理 GPU ^{高速化 手} 法 提案 ．

2. GPU ^{利用効率 高} GPU ^並列 手法 提案 ．

3. SST GPU^{処理 処理系} 実装 実適用 能 状態 性能評価

．

降 章 _{SST 3}章 既

存手法 問題点 説明 ．₄章 解決方法 あ _GPU 並列 説明 ₅章 _SST GPU ^{並列 い 説明 ．}6^{章 性能評}

価 ₇章 関連研究 ₈章 後 展望 い 説明 ．

2. ^{変化点検知ア} SST

SST[1] ^{計 算 方 法 簡 単 説 明 次 う}

．_SST 各 刻 い 過去 現 部分

系列 特異値分解 いう行列演算

特徴抽出 行い 抽出 特徴 同士

差異 変化度 ．

SST ^{計算 特異値分解 必要 あ ．} 特異値分解 非常 計算 多い演算

確 求 近 似 使 高 速 化 IKA-SST[2] ^{い う 手 法 提 案 い ．} IKA-SST ^{特異値分解 計算 単純}

比 数十倍～数百倍高速 あ ．本論文 特異値分解 確 計算 _{SST IKA-SST} 区別 _SVD-SST 記述 ．

2.1 _SVD-SST ^ア

SVD-SST ^{説明 ．}

系 列

_

_{x t}

_

t

^|

 {

^{(実 数 全 体)}

^}

^{考 え}

．ウ ン ウ

_w

長

_w

部分

系 列 列

T t t w

t ^{x x}

x t

s

( ) _ (

_{ 1}

,  ,

_1

, )

^{く．部分系列}

w

本並 行列

)]

1

(

,

),

(

[

)]

1

(

),

2

(

,

),

(

[

2 1



  















t s w

t s

t s t s w t s





H

H

定義 ．

_

整数 あ ．

H

1,

H

₂

一辺 長

_w

方行列 あ ． 1.

H

₁ ^{特 異 特 異 値 大 い 順}

r

( _

w

)

^個求

u

⁽¹⁾,

u

⁽²⁾,



,

u

^(r) . 過去側 特徴 あ _.

2.

_H

₂ ^{最 大 特 異}

_μ

_t ^求 .

_μ

_t

現 特徴 あ _.

3. ^変化度 z

(

t

)



_





^r

i

t z

1

)

2

(

1

)

( _μ

^T

u

⁽ⁱ⁾ ₍₁₎

計算 ．

ウ ン ウ

_w

検 知 い 変 化 間

選択 ． _r 系列

性質 _3~5程度 選択 ． 変 化 度 計 算 長

₂

_w

_{1  }

系列 必要 ．

2.2 _IKA-SST ^ア

次 _IKA-SST 説明 ．

_

あ 定数

_a

規化 ン

a

0 ^{初期化 く．}

1.

_H

^T₂

_H

₂ ^最大固有

_{μ  H}

₂ ^最大

特異 乗法 反復法

求 ． 初期

_a

用

い ．

2.

a _ μ _{ } a

₀ ^{規化 ．}

a

ッ 次

_μ

求 使用 ．

3.

r

₀

_{ μ}

,

_{β 1}

₀

_

,

q

₀

_ 0

,s

_ 0

^初期化

Lanczos ^{反復 実 行}

_

₁

,  , _

_k

1 1

^{, ,} 

k_

 ^

^{求 ．}

s T s s

s s s s s s

s T s s

s s s

s s

r

r

q

q

q

H

r

q

H

q

q r

































1 1 1

1 1

1

(2)

4.

_{

a_i

_}

^{対 角 要 素}

{ _

_i

}

^{副 対 角 要 素 対}

称 対 角 行 列

T

k ^{固 有 固 有 値}

大 い順 _r 個求

) ( ) 1 (

, ,

x^r

x



^．

5. ^変化度 z



_





^r

i

xi

z

1 2 ) (

]

[

1

₍₃₎

得 ．_k う ．

 

  ^ 

 2 1 odd

even

2

r r

r

k r ₍₄₎

中 _Lanczos反復

H

1

q

_s

積 あ

H

1 ^{本 系列}

ン ウ ン ウ 行列

行列 保持 く 計算 能 あ ．同様

_μ

乗法 求 場合

_H

₂

積 行列 保持 く 計算 能 あ ．

3. ^{既存手法 適用とそ 問題点}

SST ^{高速化 あ 特異値分解}

容易 _GPU 計算

CULA[3] ^用い SVD-SST ^{高速化 試} [5]^．CULA LAPACK GPU^{実装 開発}

い あ ． ₁ 特異値分解

CULA ^{計算 場合} CPU ^{計算 場合}

SVD-SST ^{変化度 あ 計算 間} あ ． 実験 環境 詳 細 _[5] 参 照 い

い．結果 ウ ン ウ

_w

₄₅₀ GPU ^{方 高速} 400 CPU ^方 高速 あ ．_SVD-SST 計算 特異値分解 依 存 一辺 長 _w 行 列 特 異 値分 解 必

要 計算

_{( )}

w3

O ^{あ ．}w ^大

い 計算 大 く 計算 間

う

_w

₄₀₀ 十分 場合 多い．

多く ン 対 異常検知

行い い場合 計算 関係

_w

あ 大

く い． _CULA 利用

場合 _w

_{ 450}

_SVD-SST 高速化 実用 問題 あ ．

w

^{い場合 CULA 高速化}

い い行列 十分 並列性 得

い あ ．_GPU 効率 く利用 数 千 個 演 算 並 列 計 算

求 ．

_w

い場合 数千

並列性 遉 い 単

一 ッ 性能 劣 _GPU 計算 _CPU 遅い いう結果 う．_CULA 複

数 行列 並列 計算 い 変

化度 複数同 求 い場合 計算 間

ニ 増加 何 高速化 得

い．

1 CULA ^{利用 場合} SVD-SST ^{計算 間}

4. _GPU^{タ 並列}

前章 述 問題 解決 本論文

GPU ^{並列 提案 ．} 2 ^{あ う}

従来 計算手法 同 行列 計算

い い行列 _GPU 効率 く利

用 ． 対 _GPU

並列 い行列 複数 行列 同

計算 _GPU 効率 く利用

．同 行列 計算 い従来

計算手法 並列性 依存 並列計

算 あ ． 対 本論文 提案手法

並列性 加え 複数 行列 同 計算 いう 並列性 使 並列計算手法 あ ．

提案手法 _GPU 並列 ぶ． 章 既存 _GPU実装 あ 場合 実装 _GPU 並列 適用 方法 い 述

． 述 い 手法 行列計算 く 広範 応用 能 手法 あ ．本論文 NVIDIA ^{開 発} GPGPU ^{開 発 環 境 あ} CUDA[4] ^{使用 ．}CUDA ^{処理 連続性}

保証 _{CUDA [4]} いう概念 あ 処理

異 ．

大きい行列 小さい行列

利用率

小さい行列 小さい行列

小さい行列 小さい行列

小さい行列

GPUタ 並列 従来 計算手法

GPU ア

2 GPU ^{並列 効果} 4.1 _GPU ^ロ

CUDA ^使 GPU ^ン

い 簡単 説明 ．_GPU 計算

GPU ^{関 数 記 述 ．}

CUDA C^{言語 一部拡張 言語} GPU

記述 ．_GPU

CPU ^{実行 ッ 起動 ．}

CUDA GPU ^{起動 関数 び出}

う 記述 ． _GPU

見 _GPU

あ _{CPU GPU} 間 通信 明

示的 記述 必要 あ ．

ッ _CPU 動作 通常

変わ い． ッ

GPU ^{び出 や 転送}

順番 _CPU 計算 部分 記述 ．

GPU ^{使 ッ}

中 _GPU 関数 び出 う 入

い ．

4.2 _GPU^{実行 並列化}

n ^{個 並列 計算 方法 考え}

単純 ッ _n 個立 並列化

方法 思い く う． ッ 複数立

実行 場合 _CPU 計算 部分

OS ^{ン 並列化 ．}

GPU ^{部分 ン ン 機能}

並列化 ． 現 ン _CUDA

ン ン 適用 制約

厳 い．例え び出 順序 規則 必要 あ や最大₁₆個 並列化

い 制約 あ う 制約 あ

ン ン 機 能 利 用 方 法 計 算 効 率 悪い．

本論文 複数 計

算 方法 採用 ． 方法 _CUDA ッ ッ 独 立 性 利 用 あ ． CUDA ^{基本的 計算} SIMD ^実

行 処理

ッ _{CUDA Warp 32} ッ

単 あ ． _Warp 異

実行 能 あ ． ッ ッ い

く _Warp あ ッ ッ

異 割 当 計 算

能 あ ．

3 ^{ッ ッ 割 当}

例 あ ． 例

表 構造体 定義 構造体 配列

引数 渡 ． _CUDA

ッ _ID 使 識別 複数

並列 処理 ．

struct Task { int m, n; float* a; };

/*taskArray Taskへ ポインタ 配列 */

__global__ void kernel_func(struct Task* taskArray[]) { Task* task = taskArray[blockIdx.y];

int m = task ->m, n = task ->n; float* a = task ->a;

/*何 を実行 る*/ }

3 GPU ^{並列 例}

4.3 _CPU^{部分 並列化}

単一 ッ _GPU 起動

いう 実現 _CPU部分

計算 _n個 計算 ッ 計算 ッ

別 ッ 入 ．計算

ッ _GPU び出 ッ

委譲 ． ッ 複数 計算 ッ

GPU ^{び出 並}

列 実行 ．計算 ッ ッ

実行 い _GPU 終了 待 _GPU

終了 _CPU 部分 計算 再開

． う 方法 _GPU 並列 実現 能 あ ．

方法 数 _CPU 側

ッ 必要 ．_OS 提供 ッ

機能 利用 ッ 数 限 あ

大 生 ン ．_SST

異 常検 知 _GPU 数百 ～ 数 千

個 並列化 必要 ッ 数

制限 問題 ． 実装

効 率 い 軽 ッ あ

解決 ． 現 う

普及 い い 本論文 計算 ッ

ン 駆動型 書 換え ッ

使 計算 問題 解決 ．

解決方法 既存 _GPU

多く 変更 必要 望 い

い 将来 効率 い軽 ッ

出現 変更 必要 く ．

5. _SST GPU^{タ 並列実装}

章 紹 _GPU

並列 実装 ． 章 実装 詳細 説明 ． 5.1 _SVD-SST GPU^{タ 並列実装}

SVD-SST ^{特異値分解 使 変化度 計算}

． 特異値分解 _GPU 並列 実装

．

n

m _

^{行列A SVD} VT

U

A

_{ }

⁽⁵⁾

分解 あ ． _{U m}

_

_m 直

交行列 _{V n}

_

_n 直交行列

_

_m

_

_n 対角 行列 あ ．

_

対角要素 特異値 _U

特 異 _V 特 異 ぶ． 現

主流 特異値分解 前半 二

対角化 行い 後半 特異値 特異 計算

いう ッ 計算 あ ．

二 対 角 化 ウ 変 換 効 率 く 計算 能 あ ．特異値 特異

計 算 関 _QR 法_[6] 分 割 統 治 法_[7] MR³[8,9] I-SVD[10] ^様々

提案 い 本論文 _QR法 使用 ．

ウ 変換 二 対角化 _QR法

特異 計算部分 _GPU 計算 ．_QR 法 特異値 計算 部分 関 並列化

い _GPU 計算 効率 悪い．

部分 _CPU 計算 ．

QR ^{法 計算} CPU ^特異値

計算 次 _GPU 特異 計算 ．

必要 計算 _GPU 転送 い ． 4 CPU, GPU ^計算部分

転送 書い あ ．

行列 対 特異値分解

実装 ．_SVD-SST 変化度

計算 特異値分解 回行う

回 特異値分解 含 並列 計算

． _n個 変化度 同

計算 い場合 _2n個 行列 特異値分解

並列 計算 ．

CPU 通信 GPU

行列 ータ

二重対角化

左右 行列も同時に計算

二重対角要素 特異値を計算

(_{∑) 計算 ータ}

特異ベク ル を計算(U, V) 特異ベク ル

左右 行列

特異ベク ル 中間 ータ

4 ^{特異値分解} GPU ^並列実装 5.2 _IKA-SST GPU^{タ 並列実装}

IKA-SST 2.2^{章 中}1^～3 ^計算 大部分 占 ． 部分 行列 縮処理

行 縮前 行列 扱わ

い あ ． 中 ₄ 固有

求 い 一辺 長 _{k (=5~10)}

いう い行列 計算 計算 い．

い 並列 使 高速化

難 い． 中₁～_{3 GPU}

計算 固有値 求 変化度 計算

部分 _CPU 行う ．

_μ

乗

法 求 ．

H

1,

H

₂ w

_

w ^行列 GPU

1 ^{あ ッ 数 行列 同}

w ^．CUDA ^最大1024 ^{ッ 一}

部_{GPU 512} ッ _CUDA

ッ 扱う _w 最大

1024 ^{対応 ．}

CPU 通信 GPU

ータ

行列T
を計算 行列T

変化度スコア

zを計算 時系列 ータ、

ベク ルa GPU

5 IKA-SST GPU ^並列実装

変化度 計算 長

₂

_w

_{1  }

系列 必要 ． 系列 点

追加 び 変化度 計算 場合 長

1

1

2

w

_{   }

^{点 前回 計算 使用}

値 同 _GPU 記憶

転送 点 い． 長

w

a

^{ッ 利用}

次 計算 必要 ． い

用 _GPU 展開

必要 応 書 換 え いう手法 用い ．

6. ^性能評価

章 前 章 実 装 _SVD-SST IKA-SST GPU ^並列実装 CPU^{実装 比} 較 ．_CPU 実 装 ATLAS 3.8.3[11] LAPACK 3.3.0[12] ^{使 用 ．}CPU AMD Phenom X4 9850 4 , 2.5GHz 8GB OS CentOS 5.4 ^{あ ．}GPU GeForce 8800GTS 512, Tesla C1060, GeForce GTX460 使用 ．_CUDA ン _3.2 あ ． 6.1 ^{特異値分解 性能評価}

6,7,8 ^{特異値分解} GPU ^並列実装 性能評価結果 あ ．一辺 長 ₅₁₂ 行列

対 特 異値 分 解 計算 間 測 定 ．_CPU 実装 _{LAPACK SGESVD} 使用 行列 乱 数 生 演算 単精度 行 ．_CPU 実装

並列化 能 ₄ ッ

使 _{CPU 4} 使用 い ．_GPU

転送 間 含 ． 数_n個 _n

個 行列 特異値分解 計算 あ ． ₆ 特異値分解 計算 間 あ ． 特異値

特異 特異 求 い ．

7 CPU^{実装 対} GPU^{実装 高速化率 あ}

．_CPU 実装 性能 不 定

曲線 い い．全体的 行列 大

い _GPU 高速化率 高く 行列 ₄₁₆ 数₂₅₆ Tesla C1060 ^場合4.14^{倍 遉}

． ₈ Tesla C1060 ^動 GPU 並列実装 実行 間内訳 あ ．_GPU実装 対角化 _CPU計算 _GPU計算 完全 分 い

CPU^{計算 全 終わ} GPU ^{計算 開} 始 い _CPU計算 _GPU 計算

並列化 高速化 見

込 ．

6.2 _SVD-SST ^性能評価

特 異 値 分 解 _GPU 並 列 実 装 使 SVD-SST ^実装 IBM

処理系System S[13] ^{使用 分散処理} 能 異 常 検 知 機 構 実 装 ． System S SPADE ^言語

記述 ．各

入力 対 選別

や変換 処理 行う．_SPADE 多く 組

込 用意 い _C++や _Java

記 述 定 義 _(UDOP) 使

用 ． _{SVD-SST UDOP}

実装 ．

最大 ₄ 分散処理 _GPU 最大 ₁₆

使用 性能評価 行 ． ₉ 結果

あ ．使用 ン _{1 GeForce} 8800 GTS 512 4 ^{搭載 い ．}GPU ^外 6.1^{章 使用 ン 同 環境 あ ．} SST ^{ウ ン ウ} w=320 ^．



^{過 去 側 現 側 系 列}

間 ₈ う

_

₌

₂

_w

_{ 1  8}

．

_

計算 影響 い． _{r 3~5}

広範 適用 能 精度 近似 使わ 特異

値分解 求 い 高精度 計算

う大 _{r =12} ．入力 波長変

動 あ 弦波 使用 ． ₉ 横軸

使用 _{GPU CPU} 数 あ ．例え 横軸 _N 場合 _{GPU N GPU N}個 CPU ^{使 計算 い ．}CPU N^個 CPU ^{使 計算 い ．}N=1~4 1

使用 計測 ． _{9 16 GPU} 線 形 性 能 向 い 分 ．₁₆

GPU ^ッ 305 /^{秒 あ ．}

ン 対 変化度

計算 ₅秒 行う ₁₅₂₅ ン

同 処理 性能 あ ．

6.3 _IKA-SST ^性能評価

次 _{IKA-SST GPU} 並列実装 性能 CPU^{実装 比較 ．}CPU^実装 LAPACK ATLAS ^使用 IKA-SST ^{計算 ．}IKA-SST

k

k

_

^{対称 対角行列 固有 求}

演 算 あ _{k 10} い

LAPACK ^{複数あ 固有値 求 関数 う} simple driver ^あ SSTEV ^{使用 ．}

系 列 ン ウ ン ウ

行列

^H

1^,

^H

2 ^積

い 行列 保持 い 計算

BLAS ^{用い 実装 能 あ} BLAS ^{最 適 関 数 用 意 い い} SIMD ^{使 最 適 化 専用 ン 実装}

．性能評価 _BLAS 使 場合 専用 ン 使 用 場 合 両 方 い 性 能 測 定

． _CPU 実装 ッ 実行

CPU 1 ^{使用 ．}IKA-SST



^{SVD-SST 場合 同}



⁼

²

^w

 ¹  ⁸

． _r 系列 _3~5

選択 性能評価 表例 _{r =3}

．_{r Lanczos}反復 反復回数や行列

T

k

影響 _3~5 値 範 い

他 値 性能 傾向 変わ い

思わ ． 計算精度 単精度 _GPU 実装 並列数 ₅₀₀ ．

10 ^変化度 100^{万個 計算 間 測定} 結果 あ ．GeForce 8800 GTS

数 制限 ウ ン ウ ₄₀₀ 計測

い．GeForce GTX460 GeForce 8800 GTS

計 算 間 同 ． 対

Tesla C1060 ^{倍程度高速 あ ．}CPU^実装 ウ ン ウ _{80 70} 方 計算 間 長く い 原因 _ATLAS 長 ₇₀

対 最 適 化 い い あ 能性 高い．

11 12 CPU ^対 GPU ^高速化 率 あ ．_CPU実装 _SIMD 使 高速化

専用 ン 使用 い ． 前述 通

CPU ^{実装 実行 い ．ウ ン}

ウ ₉₀ 高速化率 Tesla C1060 21-26^倍 8800 GTS GTX460 11-14^{倍 ウ}

ン ウ 一定 あ ．ウ ン

ウ ₉₀ 高速化率 高く _Tesla C1060 ^最高76^倍(w

_ 60

) ^．

IKA-SST SVD-SST ^{同 う} System S 実装 性能評価 行 ． ₁₃ 結果 あ ． _GPU数 対 _GPU実装 同 数 _CPU 使用 _CPU実装 対 ₁₂ 倍 高速化 遉 ．_16GPU 用い 場合

ッ _88.9 万 _/秒 あ ． 毎秒_88.9万 処理 い

0.01 0.1 1 10 100

32 96 160 224 288 352 416 480

Running time in seconds

Matrix Size (w) Tesla C1060 GeForce 8800 GTX CPU

6 GPU CPU ^{特異値分解 実行} 間 秒 数₆₄

0 1 2 3 4 5 6 7 8 9

32 96 160 224 288 352 416 480

Speedup

Matrix Size (w) Tesla C1060 (タ 数64) Tesla C1060 (タ 数256) GeForce 8800GTS (^{タ 数}64) GeForce 8800GTS (^{タ 数}256)

7 ^{特異値分解} GPU CPU ^対 高速化率 数_{64, 256}

0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%

32 96 160 224 288 352 416 480

実行時間割合

Matrix Size (w)

二重対角化 特異値 特異ベ ータ転送

8 ^{特異値分解} GPU ^並列実 装 実行 間内訳 Tesla C1060

数₆₄

0 50 100 150 200 250 300 350

0 4 8 12 16

Throughput (scores/sec)

Number of GPUs/CPUs GPU

CPU

9 SVD-SST System S^実装 ッ

1 10 100 1000 10000

0 100 200 300 400 500

Running time in seconds

Matrix Size (w)

CPU CPU(SIMD)

GeForce GTX460 Tesla C1060 GeForce 8800 GTS

10 IKA-SST ^変化度 100^{万個 計算 間}

0 5 10 15 20 25 30

100 150 200 250 300 350 400 450 500

Speed up

Matrix Size(N x N)

GeForce GTX460 Tesla C1060 GeForce 8800GTS

11 IKA-SST GPU CPU ^対 高速化率 _{CPU 1} 比較

0 10 20 30 40 50 60 70 80 90

10 20 30 40 50 60 70 80 90 100

Speed up

Matrix Size(N x N) GeForce GTX460 Tesla C1060 GeForce 8800GTS

12 IKA-SST GPU CPU ^{対 高速化率} CPU 1 ^比較

0 100,000 200,000 300,000 400,000 500,000 600,000 700,000 800,000 900,000 1,000,000

0 4 8 12 16

Throughput(Number of scores/sec)

Number of GPUs/CPUs GPU

CPU

13 IKA-SST System S^{実装 ッ}

． _100ms 間隔 ン ン 対 異常検知 行 場合 ₈万

ン 処 理 性 能

あ ．

7. ^関連研究

GPGPU ^{近年活発 研究 い} [14,15,16] 処理 適用 関 研究 い ．_GPU 並 列 関 Guevara[17] ^{研究 あ ．彼}

変更 _GPU 並列化 手法 提

案 い 彼 手法 並列化 数個

程度 あ 数百 並列実行

い．

特異値分解 _GPU 高速化 関 研究 [18]^や[19] ^{あ ． 非常 大 行列 対}

高速化 遉 い い行列 対

高速化 い い．_GPU 使 行列計算

高速化 関 研究 非常 大

行列 対象 い ． い行列 並列処理 関 研究 い．

8. ^{まとめと今後 展望}

変化点検知 _SST 使 異常検知

処理 一辺 長 ₅₀₀ 行 列 計算 必要 ．_GPU 使 高速化 考

え 場合 既存手法 高速化

． _GPU 並列 解決

．特異値分解 行列 _300-500 ４ CPU ^{対 ４倍程度 高速化} IKA-SST ^ウ

ン ウ _{20-500 CPU} 対 ₂₀

倍 高速化 遉 ．

本 論 文 提案 _GPU 並 列 手法 SST ^{外 適用 能 問題 多くあ 思わ}

． 既存実装 _GPU 並列化

や 変 更 必 要

手動 行う ． 既

存実装 _GPU 並列化 自動 実行

ワ 後 課題 あ ．

参 考 文 献

[1] Tsuyoshi Ide, Keisuke Inoue, Knowledge Discovery from Heterogeneous Dynamic Systems using Change-Point Correlations, in Proc. 2005 SIAM International Conference on Data Mining (SDM 05), pp.571-576, Newport Beach, CA, USA, April 21-23, 2005.

[2] Tsuyoshi Ide, Koji Tsuda. Change-point detection using Krylov subspace learning. Proceedings of 2007 SIAM International Conference on Data Mining (SDM2007),

pp.515-520, Minneapolis, Minnesota, USA, April, 2007. [3] CULA. http://www.culatools.com/.

[4] NVIDIA, CUDA C Programming Guide, Version 4.1, 2011.

[5] ^森田康 , ^{鈴村豊太郎}. ^{処理 用}

い 変 化点 検 知 実 装 _GPU 性能 最 適化_. 電子情報通信学会 学研究会, Jun 2010 [6] G. J. F. Francis, The QR transformation, Parts I and II,

Computer Journal, Vol.4, pp.265-271, 332-345, 1961-62. [7] J. J. M. Cuppen, A divide and conquer method for the symmetric tridiagonal eigenproblem, Numerische Mathematik, Vol.36, pp.177–195, 1981.

[8] ^山本有作, ^{密行列固有値解法 最近 発展}(I), ^日本 応用数理学会論文誌, Vol.15, No.2, pp.181-208, 2005. [9] I. S. Dhillon, A New O(n2) Algorithm for the Symmetric

Tridiagonal Eigenvalue/Eigenvector Problem, Ph.D. thesis, Computer Science Division, University of California, Berkeley, California, May, 1997.

[10] ^{高 田 美}, ^{木 村 欣 司}, ^{岩 崎} , ^{中 村 佳} , ^{高 速 特}

異値分解 開発_, 情報処理学会論

文 誌 ン ン _,

47(SIG_7(ACS_14)), pp.81-90, 2006. [11] ATLAS. http://math-atlas.sourceforge.net/. [12] LAPACK. http://www.netlib.org/lapack/.

[13] J. L. Wolf, N. Bansal, et al, SODA : An Optimizing Scheduler for Large-Scale Stream-Based Distributed Computer Systems, Middleware 2008.

[14] N. Fujimoto. Faster matrix-vector multiplication on GeForce 8800GTX. IEEE International Parallel & Distributed Processing Symposium, 2008.

[15] Yi Yang, Ping Xiang, Jingfei Kong, Huiyang Zhou. A GPGPU compiler for memory optimization and parallelism management. ACM SIGPLAN Conference on Programming Language Design and Implementation, 2010.

[16] Victor W. Lee, Changkyu Kim, Jatin Chhugani, Michael Deisher, et al. Debunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU. ISCA, pp.451-460, Saint-Malo, France, June, 2010.

[17] Marisabel Guevara, Chris Gregg, Kim Hazelwood, Kevin Skadron. Enabling Task Parallelism in the CUDA Scheduler. Proceedings of the Workshop on Programming Models for Emerging Architectures (PMEA), pp.69-76, September 2009.

[18] Sheetal Lahabar, P. J. Narayanan. Singular value decomposition on GPU using CUDA. IEEE International Symposium on Parallel & Distributed Processing Symposium. 2009.

[19] ^{深 谷 猛}, ^{山 本 有 作}, ^{畝 山 多 加 志}, ^{中 村 佳} . ^{方 行} 列 向 特異 値 分 解 _CUDA 高 速 化_{. HPCS,} Jan 2009.

[20] ^司, ^{鈴村豊太郎}. ^処理

GPU ^{並列 用い 異常}

検 知 機 構 実 現_. ン ッ ン ン

2010.