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

処理 GPU 並列 用い

異常検知機構 実現

^{鈴村 豊 郎}

東京 業大学 〒_152-8550 東京都目黒区大岡山 _2-12-1 IBM^{東京基礎研究所 〒}242-8502 ^{神奈川県大和市 鶴間} 1623-14 E-mail: [email protected], [email protected]

あ 処理 蓄積 処理 本論文

処理 ン ₁ あ 変化 検知 _GPU 高速化 扱う．変化 検

知 大 対 規模 計算 繰 返 場合 多 _GPGPU 手法 高

速化 ． _GPU 並列 高速化 提案 ．変化 検知 １ あ

特異 変換 計算 多 特異値 解 占 い 特異値 解 計算 う 二 対角化

GPU ^{並列 実装 行列} 320 ^数256 CPU 1 ^対 17.22^{倍 高速}

化 遉 ．

キ ワ 処理 異常検知 _{SST GPGPU GPU} 並列 特異値 解

Scalable Anomaly Detection on Data Stream Processing

with GPU Task Parallelism

Koji UENO and Toyotaro SUZUMURA

Tokyo Institute of Technology 2-12-1 Ookayama, Meguro-ku, Tokyo, 152-8550 Japan IBM Research - Tokyo 1623-14 Shimotsuruma, Yamato-shi, Kanagawa, 242-8502 Japan

E-mail: [email protected], [email protected]

Abstract Recently data stream processing has been extensively studied as the new computing paradigm for processing a massive amount of streaming data in real time without storing them on the secondary storage. In this paper we propose a new task parallelism method on GPGPU to improve the performance and scalability of a real-time anomaly detection algorithm called SST (Singular Spectrum Transformation) for a massive amount of sensor data. Since the main computationally dominant part of SST is a singular value decomposition, we successfully implemented the bidiagonalization with the proposed task parallelism. Our experimental result demonstrates that our optimization achieves 17.22 times performance gain on GPU against 1 core CPU when the number of tasks is 256 and the matrix size is 320.

Keyword Data Stream Processing, Anomaly Detection, SST, GPGPU, GPU Task Parallelism, SVD

1.

近 用途 多様化 伴い 大

容易 入手 う 知

識発見 要 課題 い ．知識発見 １

異常 変化 検知 あ ． ン

ッ ッ ニ ン ッ

ワ 異常 検知 や ン ン 観測

ッ ッ 監視 株 引

や 場 生産 ン 監視 広範 応用 需

要 高 い ． 対 処

理 う 処理 可能 計算

あ 昨 活発 研究 い ．

近 一般向 _PC 搭載 ッ

処理 ニッ Graphics Processing Unit, GPU ^高い計

算性能 注目 _GPU ッ 外 汎用計

算 利用 技術 General-Purpose computing on Graphics Processing Units, GPGPU ^{研究 盛 行わ}

い _CPU 比較 _GPU ン

多数集積 ッ 高速 特徴 あ

特徴 活 _CPU 数倍 性

能 発揮

本論文 _GPU 用い 変化 検知 高速化 考

え ． 章 ₂章 処理 変

化 検知 特異 変換 概要 ₃章

変化 検知 _GPGPU 適用 問題 _GPU

並列 解決方法 ₄章 特異値 解 _GPU 並列実装 詳細 ₅章 性能評価 ₆章 関連研究

7^{章 後 展望 い 述 ．}

本論文 貢献 示 ．

1. ^{多数 系列 同 処理} GPU

並列 提案 ．

2. _GPU ^{並列 ン 変化}

検知 特異 変換 扱い 特異

値 解 計算 う 二 対角化 実装 ．

GPGPU ^{手法 高速化 行}

列 ₃₂₀ 場合 数_{256 CPU}

1 ^対 17.22^{倍 高速化}

GPU ^{並列 用性 示 ．}

3. _GPU ^{並列 変化 検知 高 速化 場}

合 問題 や 一般的 _GPGPU 異

い 特異値 解 _GPU 並列実装 例

示 ．

2. ^{処理 変化 検知}

章 処理 概要

処理 ン １ あ 変化

検知 及び変化 検知 １ あ 特異

変換_[5] い 述 ．

2.1 ^処理

処理 処 生

情報 流 び 蓄

積 逐次処理 い いう新 い計算

あ ． ッ 処理 計算対象 全

蓄積 計算 従来 手法 遊

い 応答 要求 場合や 系列

前後 僅 参照 い計算や

全 蓄積 物理的 困難 処理 適 い ．

う 手法 音声や動画 ン 一

部 処理 利用 い 処

理 抽象 汎用化 幅広い 処理 対 適用

う洗練 処理系 い

従来 異 い ．

散環境 実行可能 処理系

M.I.T. Borealis[15]^や IBM Research System

S[16] ^存在

後述 _GPGPU 開発環境_CUDA 処

理 連続性 保証 いう概念 あ

処理

異 ．

2.2 ^{変化 検知} SST

系列 変化 生 機構 あ

変化 生 定義 ．

処理 扱う 様々

ン 中 異常 変化 検知 最 ン

視 ン １ あ ．変化 検

知 何種類 存在 計算処理 軽い単

純 や計算 多 複雑 変化

検出 多様 あ

最適 ン依存 あ ． 本論文

特 環境 動的 異常 害検知

行う 計算 多い 知

変 化 検 知 特 異 変 換_[5]

Singular Spectrum Transformation, SST ^扱う．

SST ^{他 手法 異 特定 確率 仮}

定 い 入力 系列 多様性 比較的頑強 あ

局所解 心配 い．実用例 自動車 ン

監視や 群 エ 検知 ン

や機械 用い い ．

示 ．

1. ^{系列 実数全体 考え ．ウ}

ン ウ 長 部 系列 列

^．

2. ^{部 系列 本並 行列}

定義 ． 整数 あ ．

3. ^{特 異 値 解}(Singular value decomposition, SVD) ^{特 異 値 大 い 順 特 異}

^{個求 過去 表}

ン ．

4. ^{特異値 解 最大 特異 現}

在 表 ン ．

5. ^変化

⁽¹⁾

計算 ． あ

．

SST SVD ^使う SVD ^{非常 計算 多い}

演算 あ 素直 _SVD 計算 実装 計算

間 合わ 処理 い ． 何

高速化手法 適用 必要 あ ．

例え ン 複数あ 各 ン

一定間隔 得 場合 う 複数

系列 扱う場合 あ ．_SST

系列 独立 扱い計算 ．変化

検知 い 多数 系列 扱う 多

高速化 望 い ．

3. _GPU ^{並列 変化 検知 高速化}

変化 検知 大 対 同 処理 繰

返 多 _GPU 使 高 速化 期待 ．

3.1 SST^高速化 GPGPU^{適用 問題}

SST ^{計算 い} SVD ^{高速化 要 ．}

GPU ^用い SVD ^{高速化 い}

Sheetal Lahabar ^研究[3]^{や 深谷 研究}[6]

あ ． 数値計算 _{LAPACK CUDA[2]}

移植 _{CULA[7] SVD} 計算 関数 用

意 い ． 森 _SVD 計算 _CULA 使う _SST計算 高速化_[1] 試 い ．

研究や

変化 検知 適用 問題 あ ．_SST 場合

大 対 _SVD 繰 返

処理 計算 関係 行

列 数十～数百 抑え い．

GPU ^{高速化 研究 非常 大}

行列 対象 い ． _SST 高速

化 適用 い．

実 森 _{[1] CULA} 用い _GPU 高速

化 研究 ウ ン ウ _{400 GPU}

CPU ^{遅い いう結果 ． 同様 森}

研究 ウ ン ウ ₄₅₀

GPU CPU ^{速い いう結果 ウ ン}

ウ _{450 GPU SST} 計算 間 _1.68

あ ． 間

処理 い．行列 大 _GPU

優 性 大 _SST 計算 間 増

自明 あ ． ン 数 高々１

実験 複数 ン 対 性能向

見 い い．

行列 高速化 い理 行列

い _GPU 性能 引 出 十 並列性

確保 い あ ．

SVD ^{高 速 化 関 他 研 究 同 様 あ ．}

Sheetal Lahabar ^研究[3]^{や深谷 研究}[6]

数値計算 _{BLAS CUDA}実装

あ _CUBLAS[8] 使用 い ．_CUBLAS 非常

大 行列 対象 い 中 規模 行列

高速化 い．

3.2 ^{並列 解決}

前述 通 手法 変化 検知 高 速

化 _GPU 適用 問題 あ ．

並列 解決 提案 ．_GPU い 中 規

模 問題 高速化 並列性 確保 課題

． 複数 系列 並列計算

並列 入 ． 並列 並列性

高 _GPU 性能 十 引 出

う ．

3.3 ^{並列 実現方法}

CUDA[2] NVIDIA ^開発 GPGPU ^開発環境

あ 本論文 _CUDA 使用 ．_NVIDIA

GPU ^{関数 同 １ 実}

行 い 並列 実現

必要 ．

GPU ^{並列 い} Marisabel Guevara

研究_[9] あ ．彼 _CUDA

CUDA ^{ッ 独立 動作 着目}

並列 い ． 原理 理解

NVIDIA GPU ^{キ い 理解}

必要 あ ．

NVIDIA GPU ^多数 Streaming Multiprocessor (SM)

SIMD ^{ニッ 構 各}

SM ^{独立 発行 ニッ 持 い ．１}

SM ^最大24~32^個 warp ^{同 実行}

．_{warp 32} ッ _SIMD ニッ

実行単 ． 同 _SM 割 当

warp ^各 warp ^{独立 ン 持}

擬似的 並列実行 い ．

CUDA ^{ッ いう概念 あ} 1 ^ッ

あ 最大₅₁₂個 ッ 実行 ．

ッ 同期 ン 作 ．

ン 通過 ッ 内 全

ッ 同期 ン 前 実行

操作 結果 ッ 内 他 全 ッ

見え う いう あ ．

通常 各_SM 複数 ッ 割 当 ．

１ _warp 複数 ッ い

各 ッ 独立 動作 ．

ッ 条件 岐 異 動作

う 単一_GPU内 異 並列実

行 ．

々 関数 引数 渡 ン

ッ _ID 使 各 ッ 異 ッ

あ 処理 並列

実現 ．各 ッ 独立 動作

間 異 動作 可能 あ ．

各 共 い 数

条件 岐や引数 数 一定

．変化 検知 う 大 対 同 処

理 繰 返 場合 手法 特 効 あ ．

1 CUDA ^{例 あ ．実装 あ}

見や ッ _ID 次元

ID ^{統一 使用 ． ッ} ID ^次

元 最大_65,536 ッ _{ID 1}

次元 最大 _65,536個 処理

．

NVIDIA ^{開発 最新} GPU(Fermi) ^複数

同 実行 同 実行可能

数 ₁₆ あ ．変化 検知 数十～数百

系列 同 処理 ．_{Fermi GPU}

1 GPU ^{並列 関数 例}

__global__ void kernel_func(float* A, int bda_{, … ){}

/* ^ッ ID ^{使 識} */

float* bA = &A[bda*blockIdx.y];

/* ^{何 実行} */

}

々 提案手法 最大_{128 1SM}あ 最大₈ ッ 並列処理可能 _{SM 16}個あ

並列処理 同 実行

機能 々 手法 使 方 効率

計算 ．

並列 実現 あ

関数 変更 必要 あ 公開

い い_CUBLAS[8]や_CULA[7] 利用

関数 新 実装 必要 あ ．

4. _SVD GPU ^並列実装

GPU ^{並列 ン} SST ^扱い

SVD ^{計算 う 二 対角化 実装 ． 章}

SVD GPU ^{並列実装 詳細 述 ．}

4.1 SVD

SST ^密行列 SVD ^{必要 ．}

^行列 SVD

⁽²⁾

解 あ ． 直交行列 ^{直交行列 対角行列 あ ．}

SVD GPU ^実装 Sheetal Lahabar ^研

究_[3] 参考 ．彼 _LAPACK 使わ い

Golub-Reinsch ^使 GPU ^用い

高速化 い ． ₂

ッ 構 ． 行列 ウ

変換 二 対角化 ．次 二 対角行列

shifted QR iteration ^{対角化 ．}

本論文 ₂ ッ う 二 対角化

並列 _GPU 実装 ． 行列 方行列

512 ^{比較的 規模 対応 ．}

計算 単精 _(float) 行 い ．

二 対角化 ッ ウ 変換

繰 返 行列

⁽³⁾

解 ． 二 対角行列 直交

行列 あ ．

^{方 行列 二 対 角化 い}

明 ．

後述 計 算方法

_係数

求 ．

_{係数 求 ．}

⁽⁴⁾

． 最初 行 列 消去 あ ． 次 , ^{着目 同様 変換}

2^{番目 行 列 消去 ． 繰 返}

最終的 二 対角行列 計算 ． 行

列 消去

⁽⁵⁾

．

(6)

, ^行,^{列 消去 使用 ウ}

行列 あ

⁽⁷⁾ あ ．

^{対応 係数}

次 う 求 ．

(8)

う ^．

4.2 ^{二 対角化 実装}

ウ 変換 二 対角化 一般 的

高速化 ッ 化_[4] いう手法 用い ．

局所的 方 高速 キ

場合 行列 積 行列積 方 高速 ．

ッ 化 行列 積 減 行列積 置

換え 高速化 いう あ ．

ッ 化 計算 減

複雑化 ．非常 大 行列

対 効 中 規模 行列 対

効 う い． 並列 実現

関数 新 実装 必要

あ 複雑化 実装

増大 ．

う 理 ッ 化 い

実装 ． 番目 行 列 消去

⁽⁹⁾

表 ．

(10)

あ ．

1 ^{う ．}

1 ^{二 対角化}

1: for to do 2: ^計算

3: ^{変換 適用 後 計算} 4: ^計算

5: ^更新 6: _{end for}

4.3 ^{実装 詳細}

1 ^{行列 二 対角化} 1 ^並

列化 ．

変化 検知 使用 ン

い．_GPU-CPU間

転送 ン 増 二 対角化

演算 _GPU 実装 ．_GPU-CPU 間

転送 行列 _GPU 転送 結果 得

二 対角行列 帯要素 _CPU 転送 あ ．

関数 替え

ッ 行列 無視

や共 関数

静的 確保 ₁ 関数 大

無駄 発生 や ．

関数 替え回数 減 や共

無駄 う 望 い．

１ 関数 大

使用 数や共 大 変化

ン 関数 ． 結果 関数

び出 回数 ₁ １ あ ３回

．

4.3.1 ^{行列 積}

行列 列 展開 い

行列 転置 い場合 素直 ッ 内積

求 _Coalesced

効率 良い行列 積 ．

行列 転置 場合 手法

Coalesced ^{効率 悪 ．行列}

転 置 場 合 次 う 手 法

Coalesced ^．

2 ^{行列 転置 積} 1:

^{{ 16 Coalesced 単 }}

2: for to do

3: ^共 4: ^共

5: ^積

計算 結果 え

6: _{end for}

実装 あ Tesla C1060 ^使用

GPU ^{念頭 置 い 他} GPU ^対

微調整 最適化 ．

共 ン ン 発

生 い う 共 行列

16 ^{倍数 数 同 ウ}

確保 い ．

手法 共 制限 行列 ₂₅₆

場合 ₁ ッ 計算 い．

行列 大 い場合 複数 ッ

使用 計算 ．

手法 Partition camping[10] ^高い

発生 速 後 明 ．

Partition camping ^あ

Partition ^{集中 結果 書 効率}

あ ．共 _32bit幅 ₁₆個 _Fermi

32 ^{個 ン い 同 う}

64byte ^{幅 い} Partition

い ．あ _Partition 集中

ッ う．

行列 積 関 手法

結果 Tesla C1060 ^{最悪 ン 幅}

1/8 ^{速 出 い あ ．}

4.3.2

計算 和 演算 あ ． 演算

実装 あ Mark Harris Parallel Reduction[11]

参考 ．

4.4 ^{ッ 化}

ッ 化 い方法 実装

結果 ン 幅 ッ

い ． ッ 化 方

書 減 高速化

考え ッ 化 実装 ．

[4] ^{提案 い あ ． ッ}

GPU ^特性 32 ^．

3 ^{二 対角化 ッ 化}

1: ^ッ 2: for to do

3: 4: ^{転置 作} 5: ^計算

6: ^{変換 適用 後 計算} 7: ^計算

8: for to do 9:

10: ^{最 新 組 使 計算}

11: ^計算

12: ^{変換 適用 後 計算} 13: ^計算

14: _{end for}

15: ^更新 16: _{end for}

4.5 ^{ッ 化 実装 詳細}

ッ 化 い 場 合 同 様 演 算

GPU ^{実装 ．}GPU-CPU^{間 転送 行列}

GPU ^{転送 結果 得 二 対角行列}

帯要素 _CPU 転送 あ ．

数 い場合 性能 引 出

3 10: ^計

算 条件 岐 使 並列 並列化 並列

高 ．

関数 び出 回数 ₃ 内

側 １ あ ₇回 抑え ．

行列 積 い 行列転置 積 計算

場合 う 行列 転置 い場合 遅

う． ッ 化

ッ 先頭 行列 転置

展開 高速化 ．

4.5.1 ^{行列 積}

行列 転置 い場合 ッ 化 い場合

同様 手法 使 展開 _unroll 使

実行 数 減 高速化 ． 行

列 積 書 ッ

実行 数 減 意 速 変化

見 ．

行列 転置 場合 Partition camping ^{発生 抑え}

新 手法 考案 ． 実装 詳細 割愛

手法 行列 転置 い場合 同

等 ₈割 速 遉 ．

4.5.2 ^行列転置

行列転置 入力行列 転置 出力行列 書 込

操作 あ ．必要 計算 い ン

幅 ッ ． 場合 Partition camping

減 要 _[10] 行列転置 い

Partition camping ^{減 方法 示 い ．}

Partition camping ^{減 ッ 実行順序}

制御 必要 あ ．_CUDA 式 定義

１次元 ッ _ID 使 値 い

ッ _SM 割 当 ．

(11)

blockIdx gridDim ^ッ ID

ッ 次元 表 _CUDA 記法 あ _blockIdx.x

blockIdx.y ^ッ ID ^値 gridDim.x

関 数 起 動 使 用 ッ 方 向

数 あ ． 列 行列 展開 い 場合

複 数 ッ 同 行 _Partition

camping ^{発 生 う． 行列 転置 場合 入 力行}

列 出力行列 方 同 行 複数 ッ 同

防 い． 実現

１次元 ッ _ID 順番 行列 対角方向 振

う い． _[10] ッ _ID

実 ッ 処理 ッ 標 算出

式 用い い ．

bx,by ^{実 処理 ッ 標 あ ．}

々 ッ _ID 次元 並列 使

用 い 手法 使用

い． _bx,by 共 初期値_blockIdx.x 開始

bx ^{関数内 ン ン}

．

並列 複数 行列 同 計算

間 実 行 順 序 考 慮 い ．

Partition camping ^ッ

間 渉 言う 式₍₁₁₎ ッ _ID

次 元 同 ッ 渉 大 影 響

． 々 ッ _ID 次元 _ID

使用 次元 １ 内 並列処理 使

用 方法 １ 内 ッ 間 渉

減 全体 渉 減 いう

優 い ． 逆 う 複雑

間 渉 考え ．

4.5.3 ^行列積

行列積 _CUBLAS 使え 十 大 持 行

列 場合 Tesla C1060 330GFLOPS ^{速 出}

NVIDIA Programming Guide[2] ^{あ 手法}

200GFLOPS^{弱 出 ．}

Yi Yang GPGPU ^{最適化 ン 研究}[12]

行 い ．彼 _GPU 最適化 意識 い

い ン 最 適 化

CUBLAS ^{同等 速 動作}

生 い ． 行列積 最適化後 例

示 い 利用 ．彼

使え Programming Guide[2]

あ 手 法 数 １ 程 減

CUBLAS ^{同等 性能 出 ．彼 提案 い}

最適化手法 １ ッ あ ．行列積

例 示 い ₃₂ ッ

あ ． 々 ₃₂ ッ

16 ^ッ 2 ^{実装 比}

較 ₁₆ ッ 方 高速

採用 ．

5.^性能評価

評価環境 _CPU AMD Phenom X4 9850 (4

, 2.5GHz) 8GB OS CentOS 5.2 GPU Tesla C1060 ^{用 い ．}LAPACK[17](Version 3.2.1) ATLAS[18](Version 3.8.3) ^用い 1 ^実行

CPU ^{速 ．}

前章 通 １ 行列 二 対角化 ₁

．_CPU 各 行列 _LAPACK 二 対角関

数 あ _SGEBRD 二 対角化 全 行列 二 対角化 終了 間 計測 ．_GPU

CPU-GPU^{間 転送 含 間 計測 ．}

計測 ₅ 回実行 均 い

．行列 ン 値 生 _{CPU GPU}

計算 行列 同 単精 浮動 数 型 使用 い ．

2 ^数 256 GPU,CPU ^実

行 間 あ ．_X軸 行列 _Y軸 実行 間 対

数目盛 い ． 中_Simple ッ 化 い

い_GPU実装 _Block ッ 化 _GPU実装 示

い ．他 同様 あ ． _{3 GPU CPU} 対 高速化率 あ ．_X 軸 行列 _Y 軸

GPU CPU ^{対 高速化率 あ ． 数} 64

場合 ₂₅₆ 場合 計測 ．

場合 ッ 化 実装 方 ッ

化 い場合 速い いう結果 ．行列

320 ^数256 ^{場合 ッ 化 実装}

0.584 CPU 1 ^{実行 間} 10.06 17.22

倍 高速化 遉 ．

計測 全 場合 い 行列 ₂₅₆

512 ^{場 合 速 い ．} Partition

camping 4.3.1^{章 原因 思わ ．計測 使用}

GPU Tesla C1060 ^場合 Partition 8^個

行列 ₂₅₆や ₅₁₂ 場合 影響 出や い．

ッ 化 い実装 Partition camping ^影響

い う 見え 行列

Partition camping ^{影響 速 い}

行列 _{256 512} 場合 速 相対的

見 え あ ． ッ 化 実 装

Partition camping ^{減 力 あ 程 改}

善 行列 _{256 512 Partition}

camping ^{発生 抑え 速 発生}

．

4 ^行列 448 ^{固定 数 変え}

GPU CPU ^{対 高速化率 あ ．}X^軸

数 対数目盛 い ．_GPU 実装 ₁

1 ^{ッ 割 当 計算 い 部 多い．}

Tesla C1060 SM^数 30 ^{あ 数} 30

十 性能 引 出 い．

数₃₂ 良好 結果 得 ．

6.^関連研究

6.1 SST^{高速化 関 研究}

特異 変換 SST (Singular Spectrum

Transformation) ^{発案者 あ 井手氏 高速}

化 研究_[14] い ．彼 _FELIX-SST いう

手法 次 う 高速化 い ．_SST

2.2^{章 過去 現在} 2 ^行列 SVD

求 い ．過去側 特異 大 い方

個使用 現在側 最大 特異 使用 ．

最大 特異 変 方程式 復法 解

法 使 効率 求 ．過去側

0.001 0.01 0.1 1 10 100

0 64 128 192 256 320 384 448 512 576

実行時間秒

行列サイ _n

Simple Block CPU

2 ^数256 ^場合 GPU CPU ^{二 対角化}

実行 間

0 2 4 6 8 10 12 14 16 18 20 22

0 64 128 192 256 320 384 448 512 576

Speed up ( CPU / GPU )

行列サイ n

Simple(64) Block(64) Simple(256) Block(256)

3 ^数64 ^場合 256 ^場合 GPU CPU

対 高速化率

0 4 8 12 16 20 24

1 2 4 8 16 32 64 128 256 512

Speed up ( CPU / GPU )

タ ク数

Simple Block

4^行列 448^{固定 数 変え} GPU

CPU ^{対 高速化率}

い 特異 求 Implicit kernel^近似

使 効率 変化 求 ． 手法

ウ ン ウ ₂₅₀ い ₁₃₀倍 高速

化 い ．

6.2 GPU ^{並列 関 研究}

GPU ^{並 列 関} Marisabel

Guevara ^研究[9] ^{あ ． 修}

並列 実現 手法 提案 い ． 彼

手法 数 比例 条件 岐や引数

数 増え いう問題 あ ． 数

効 数 多い ッ 大

． 変化 検知 場合 各 大

多数 系列 処理 場合 あ

彼 手法 変化 検知 高速化

適用 い．

6.3 GPU ^{使 行列計算 高速化 関 研究}

SVD ^{高速化 い} Sheetal Lahabar, ^研

究_[3]や 深谷 研究_[6] あ ． 彼

手法 非常 大 行列 対 効

い行列 高速化 い．

GPU ^{使 行列計算 高速化 関 研究 非常}

多い． 研究 非常 大 行列

対象 い い行列 対 高速化 関

研究 い．

7. ^{後 展望}

本 論 文 大 対 変 化 検 知

GPU ^{適用 場合 手法 い 述 ．}

GPGPU ^{研究 非常 大 行列 大}

問題 対象 い 変化 検知 適用

い． _GPU 並列 高速

化手法 提案 ．

変化 検知 _{SST SVD} 使う

SVD ^{計算 う 二 対角化} GPU ^{並列 実装}

．性能評価 結果 行列 ₃₂₀ 数₂₅₆

CPU 1 ^対 17.22^{倍高速化 ．}

GPU ^{並列 変化 検知}

中 規 模 計 算 繰 返 ン

GPU ^{高速化 適用 示 ．}

本論文 _{SVD 2} ッ う 二 対角

化 実装 後 _SST 全体 _GPU 実装

GPU ^{並列 変化 検知 高速化 実証}

必要 あ ．

謝辞：

本研究 一部 学研究費補 金 挑戦的萌芽研 究

課題番 :22650017) ^{行わ ．}

参 考 文 献

[1] ^{森 康} ,^{鈴村豊 郎}. ^処理

用い 変化 検知 実装 _GPU 性能最適 化 _. 電子情報通信学会 学研究会_{, 2010}

6

[2] NVIDIA CUDA Programming Guide, Version 3.0, 2010.

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

[4] Jaeyoung Choi, Jack J. Dongrra, David W. Walker. The design of a parallel dense linear algebra software library: Reduction to Hessenberg, tridiagonal and bidiagonal form. Numerical Algorithms, Volume 10, Number 2, 379-399. 1995.

[5] Tsuyoshi Ide, et al, Knowledge Discovery from Time-series Data using Nonlinear Transformations, The 4th Data Mining Workshop of JSSST 2004 [6] ^深谷猛, ^{山本 作}, ^{畝山多 志}, ^中村佳 . ^方行

列向 特異値 解 _CUDA 高速化_{. HPCS,}

2009.

[7] CULA. http://www.culatools.com/.

[8] NVIDIA Corporation. NVIDIA CUBLAS Library. http://developer.download.nvidia.com/compute/cuda/3 _1/toolkit/docs/CUBLAS_Library_3.1.pdf

[9] 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). September 2009, pages 69-76.

[10] G. Ruetsch and P. Micikevicius. Optimizing Matrix Transpose in CUDA. NVIDIA, 2009.

[11] Mark Harris. Optimizing Parallel Reduction in CUDA. http://developer.download.nvidia.com/compute/cuda/1 _1/Website/projects/reduction/doc/reduction.pdf, 2008. [12] 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.

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

[14] T. Ide. Speeding up Change-Point Detection using Matrix Compression. IBIS, 2006.

[15] Daniel J. Abadi, etc., The Design of the Borealis Stream Processing Engine, 2nd Biennial Conference on Innovative Data Systems Research (CIDR’05), Asilomar, CA, January 2005

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

[17] LAPACK. http://www.netlib.org/lapack/. [18] ATLAS. http://math-atlas.sourceforge.net/.