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

データ トリーム処理による

イン リメンタル ラフ処理に向けて

東京工業大学 _西井俊介 東京工業大学 _{/ IBM}東京基礎研究所 _{鈴村豊太郎}

目次

1.

^背景

2.

^手法

3.

^設計

4.

^評価

5.

^議論

6.

^関連研究

7.

1. ^背景

1.

^背景

2.

^手法

3.

^設計

4.

^評価

5.

^議論

6.

^関連研究

7.

v₁ v₂

v₁ v₂

v₃ v₄

v₅

1.1. ^背景 : ^{ラフ処理について}



^フ構



^{点集合 (V) 辺集合 (E)}



^{辺 : 点対}



^{辺 点対 順序 意味 フ ( 向辺 フ )}

順序 意味 持 い フ ₍ 無向辺 フ ₎ 二種類 あ



^フ処理



^{例 : 路線 , Web フ , ソ フ} , …



^{解析例 : 最短経路問題} , PageRank,

協調フ ^{ン , ン , …}

向辺 _: 無向辺 _:

e₁₂

e₁₃ ^e24

e₃₄ e_{35 e}

54

v₁ v₂

e₁₂ (_≠e21) e₁₂ = e₂₁

1.2. ^背景 : ^{大規模 ラフ処理}



^{大規模 フ処理}



^{点数 : 数十億 (x1G)~, 辺数 : 数千億 (x100G)~}



^{一回 解析処理 多大 時間 要}

 Google PageRank ^更新 2~4 ^{一度 行わ い}



^{処理 効率化 研究 盛 行わ い}



^{既存 大規模 フ処理}



Pregel (Google Inc.)



^{PEGASUS ( ネ ン大学 )}



…

1.3. ^背景 : ^{既存シ テムの問題点}



^{問題点 : 解析 性}



^{既存手法 ， 蓄積 解析 々 行う ( ッ 処理 )}

， 発生 解析結果 得

生



^{そ ，非常 短時間 ン 加味 解析 い}



^{処理 高 化 ， ッ 処理 ン 間隔}

短く あ 程度 短く

1.4. ^背景 : ^データ トリーム処理による解決案



^処理



^{時々刻々 生成 流 (= )}

，蓄積 逐次処理 いく 処理方式



^{近 大規模 ン 増加 応}

研究 盛 行わ う



^{生成 ，そ 加味}

処理結果 得 時間差 ₍ ン ₎

短く 主眼 置い い

1.5. ^背景 : ^{データ トリーム処理系} System S



IBM System S



^{処理 行う}



^{処理言語 SPADE 実装}

，並列計算機 配置，通信処理 ，

全体 管理 担う



^{処理言語 SPADE}



^{処理 ， フ 簡単}

書 プ 言語



^{基本的 処理 組 込 用意 い}



^{固 複雑 処理 ，}

定義 _{(UDOP) C++} 実装

2. ^手法

1.

^背景

2.

^手法

3.

^設計

4.

^評価

5.

^議論

6.

^関連研究

7.

2.1. ^手法 : ^{計算モデルの提案}



^計算 : Incremental GIM-V



^{フ処理 計算}

提案



^{以 既存手法 基 い ( 次 以降 解説 )}

 GIM-V (from ^フ処理 PEGASUS)

 Incremental PageRank



^{自体 ッ 処理的 手法 あ}

 ^{今後， 処理 適 形}

改良 必要 あ

2.2. ^手法 :GIM-V (PEGASUS)



Generalized Iterative Matrix-Vector multiplication



^{行列× 乗算演算} (v’=M ^{× v) 一般化}

(n ^× n ^行列， n ^次 )

 ^{演算 復} (iterative) ^束 (or^規定回数)^実行

 ^{行列M フ 隣接行列， v 点 値}

見立 ，関数combine2, combineAll, assign ^実装

，様々 フ 実装 能

 PageRank, Random Walk with Restart, ^{直 推定}, ^{連結成 推定}

4 PEGASUS ^提供

v^′_i = _Mi,j × v_j

n

j=1

v^′_i = assign(v_i, combineAll(combine2(M_i,1, v₁),… , combine2(Mi,n^{, v}n⁾⁾⁾

combine2 : ^乗算 combineAll : ^総和 assign : ^更新

2.3. ^手法 :Incremental PageRank



Incremental PageRank



^{PageRank 計算 高 化手法 一}



^{あ 時点 フ (G}

^{) PageRank 計算結果 利用 ，}

そ 新 い ₍ 更新 ₎ フ _(G

2

^{) PageRank 計算}



^手順

1. _{G1 G2} ^{差 ，構 変化}

点 ，そ 到達 点

幅優先探索 求 _{( V}

Q⁾

2. V_Q^以外 V_Q ^{接続 点 求}

( V_b)^{，残 点} V_u

3. _{Vb Vu PageRank} ^{点数 変化}

応 調整₍×_|V(G

1^)|/|V(G2^)|)

4. PageRank^計算範 V_Q

V_Q V_b

V_u ^{変化 い 点，辺}

変化 点，辺

V_Q: (^{変化 点集合})

変化 点 到達 能

/ GIM-V ^計算対象 V_b: (^{無変化 点集合}:^境界)

V_Q^{以外 ，}V_Q ^{隣接 点}/ ^{計算対象外} V_u: (^{無変化 点集合})

V_Q : PageRank^{再計算 対象} V_b : V_Q ^{接 点}

V_u : ^{そ 以外 点}

2.4. ^手法 : ^{提案モデル} Incremental GIM-V



Incremental GIM-V



Incremental PageRank ^手順 GIM-V ^実行



^手順

1. ^{新規 追加 点 対}

初期値 設定 関数_init 実行

2. ^{既存 点 対 ，計算結果}

調整 関数_scale 実行

3. ^{前 同様}V_Q , V_b , V_u ^計算

4. ^計算範 _{VQ Vb} ^{絞 込 ，}

GIM-V ^{計算 実行}

(V_Q : combine2,combineAll,assign) (V_b : combine2 )

V_Q V_b

V_u ^{変化 い 点，辺}

変化 点，辺

V_Q: (^{変化 点集合})

変化 点 到達 能

/ GIM-V ^計算対象 V_b: (^{無変化 点集合}:^境界)

V_Q^{以外 ，}V_Q ^{隣接 点}/ ^{計算対象外} V_u: (^{無変化 点集合})

V_Q, V_b^以外/ ^{計算対象外}

V

: GIM-V ^{計算 対象}

V

: V

^{接 点}

V

: ^{そ 以外 点}

2.5. ^手法 : ^{アルゴリ ムインターフェー}



^{ン フ}



^フ

(PageRank ) ^，

以 ン フ

(C++) ^実装



^関数

 ^combine2(M_ij^,v_j^{) : 乗算}

 combineAll(list) : ^総和

 ^assign(v_i^{, v}_{i_new}^{) : 代入}

 ^{( 束 定) : assign内 実装}

 ^scale(v_i^{, i) : 計算結果 調整}

 ^init(v_i^{, i) : 初期値設定}



^型定義

 ^T_M ^{: 行列 要素}

(辺 ^{値) 型}

 ^T_v ^{: 要素}

( ^{点 値) 型}

 ^T_c : combine2 ^{戻 値 型}



^定数

 IT_LIMIT : ^復計算 限 復回数

2.6. ^手法 : ^{インターフェー 実装例} (PageRank)



^例 : PageRank



^関数

 ^combine2(M_ij^,v_j^{) = M}_ij^×v_j

 combineAll(list) = 0.85^×sum(list)+0.15/n

 ^assign(v_i^{, v}_{i_new}^{) = v}_{i_new}

 ^{( 束 定) : abs((v}_{i_new} ^-v_i^)/v_i^)<1.0×10-5

 ^scale(v_i^{, i) = v}_i^×n_G1^/n_G2

 ^init(v_i^{, i) = 1/n}_G2



^型定義

 ^T_M ^{, T}_v^{, T}_c ^{: double(倍精度浮動小数点数型)}



^定数

 ^{IT_LIMIT ( 限 復回数): 32}

3. ^設計

1.

^背景

2.

^手法

3.

^設計

4.

^評価

5.

^議論

6.

^関連研究

7.

3.1. ^設計 : ^{データフロー図}



IBM System S ^実装



^{UDOP 以外 組込}

 ^{UDOP( 定義 )}

今回実装 _(C++)



UDOP : Master

 ^{動作状態(次 ) 管理}



UDOP : Worker 1 ~ K

 ^{フ 各 点 処理 担当}

 ^{フ 散保持}

 ^{番号 i} (0, 1, 2, …) ^{点 ，} i mod K + 1 ^番 Worker ^担当

Source (M)

Source (G) Master (M)

[UDOP]

Split (G)

Sink (M) Bundle (M)

Worker(W1) [UDOP]

〃_(W2) [UDOP]

〃_(WK) [UDOP] Sink

(W1)

〃 (W2)

〃 (WK)

Split (W1) ^〃(W2) ^〃(WK)

Bundle (W1) ^〃(W2) ^〃(WK)

Master^⇔Worker^間 Worker^{プ 間}

K

フ入力

3.2. ^設計 : ^{シ テム動作状態}



^{初期状態 機状態}

Ｖ

^{計算 移行}



^{各状態，各 ップ 動作}

管理



^Ｖ

^{計算 GIM-V 計算}

1 ^{回 ップ 完了 限 ，}

復 ップ実行



^{ップ 終了}

機状態 戻

機状態 V_Q^計算

V_b^計算

GIM-V^計算

結果出力

V_Q : GIM-V^{再計算 対象} V_b : V_Q ^{接 点}

V_u : ^{そ 以外 点}

3.3. ^設計 : ^動作 : ^待機状態

Source (M)

Source (G) Master (M)

[UDOP]

Split (G)

Sink (M) Bundle (M)

Worker(W1) [UDOP]

〃_(W2) [UDOP]

〃_(WK) [UDOP] Sink

(W1)

〃 (W2)

〃 (WK)

Split (W1) ^〃(W2) ^〃(WK)

Bundle (W1) ^〃(W2) ^〃(WK)

Master^⇔Worker^間 Worker^{プ 間}

状態 フ入力

(^辺情報) ^{受け付け ．}

他 状態 フ入力

与え ， 機状態

戻 映 い．

辺情報 適 ワ

振 当 ．₍ ン ビン₎

解析開始 通知

外部 発行 ，

状態 _V

Q^{計算 移行 ．}

変化 辺 両端 _V

Q ^．

V_Q : GIM-V^{再計算 対象} V_b : V_Q ^{接 点}

V_u : ^{そ 以外 点}

3.4. ^設計 : ^動作 :V

^計算

Source (M)

Source (G) Master (M)

[UDOP]

Split (G)

Sink (M) Bundle (M)

Worker(W1) [UDOP]

〃_(W2) [UDOP]

〃_(WK) [UDOP] Sink

(W1)

〃 (W2)

〃 (WK)

Split (W1) ^〃(W2) ^〃(WK)

Bundle (W1) ^〃(W2) ^〃(WK)

Master^⇔Worker^間 Worker^{プ 間}

ワ 指示 送 ．

直前 ップ _V

Q ^追加

点 ，隣 合う 点

V_Q ^{追加 う指示 送 ．}

指示 受け 点 _V

Q ^{追加 ．}

V_Q ^{変更 け 次 状態 移行．} 変更 あ 場合 ， う一度

状態 一連 流 ₍ ップ₎

実行 ．

以 終了

通知 ．

V_Q : GIM-V^{再計算 対象} V_b : V_Q ^{接 点}

V_u : ^{そ 以外 点}

3.5. ^設計 : ^動作 :V

^計算

Source (M)

Source (G) Master (M)

[UDOP]

Split (G)

Sink (M) Bundle (M)

Worker(W1) [UDOP]

〃_(W2) [UDOP]

〃_(WK) [UDOP] Sink

(W1)

〃 (W2)

〃 (WK)

Split (W1) ^〃(W2) ^〃(WK)

Bundle (W1) ^〃(W2) ^〃(WK)

Master^⇔Worker^間 Worker^{プ 間}

ワ 指示 送 ．

V_Q ^{い 点 ，隣 合う 点} V_Q ^{い 確認 ．}

確認 条件 合う 点 V_b ^{追加 ．}

次 状態 移行．

以 終了

通知 ．

新規 点 _init 実行． 既存 点 _scale 実行．

V_Q : GIM-V^{再計算 対象} V_b : V_Q ^{接 点}

V_u : ^{そ 以外 点}

3.6. ^設計 : ^動作 :GIM-V ^計算

Source (M)

Source (G) Master (M)

[UDOP]

Split (G)

Sink (M) Bundle (M)

Worker(W1) [UDOP]

〃_(W2) [UDOP]

〃_(WK) [UDOP] Sink

(W1)

〃 (W2)

〃 (WK)

Split (W1) ^〃(W2) ^〃(WK)

Bundle (W1) ^〃(W2) ^〃(WK)

Master^⇔Worker^間 Worker^{プ 間}

ワ 指示 送 ．

各_V

b ^,VQ ^{隣接 辺 対}

combine2 ^{実行 ，結果 送 ．} 各_V

Q ^{combine2 計算結果}

，_combineAll 実行 ．

全 点 値 束 ，

あ い 規定回数 ップ 実行

以 終了

通知 ．

各_V

Q ^{そ 結果 assign ，}

点 値 更新 ．

束 定 行う．

V_Q : GIM-V^{再計算 対象} V_b : V_Q ^{接 点}

V_u : ^{そ 以外 点}

3.7. ^設計 : ^動作 : ^結果出力

Source (M)

Source (G) Master (M)

[UDOP]

Split (G)

Sink (M) Bundle (M)

Worker(W1) [UDOP]

〃_(W2) [UDOP]

〃_(WK) [UDOP] Sink

(W1)

〃 (W2)

〃 (WK)

Split (W1) ^〃(W2) ^〃(WK)

Bundle (W1) ^〃(W2) ^〃(WK)

Master^⇔Worker^間 Worker^{プ 間}

ワ 指示 送 ．

各 点 計算結果

( ^{点 値}) ^{出力 ．}

全 点 _V

Q^{, V}b ^{解除 ．}

機状態 戻 ．

映 フ情報

あ 映 ．

以 終了

通知 ．

V_Q : GIM-V^{再計算 対象} V_b : V_Q ^{接 点}

V_u : ^{そ 以外 点}

4. ^評価

1.

^背景

2.

^手法

3.

^設計

4.

^評価

5.

^議論

6.

^関連研究

7.

4.1. ^評価 : ^実験内容



^{実験 プ ン}



^PageRank



^実験内容



^{フ G}

^G

^用意



^{記二通 計算 計算時間 比較}

1.

_G

^対 _PageRank ^{計算結果 利用}

G

PageRank Incremental GIM-V ^計算

2.

_G

_PageRank ^通常 _GIM-V ^計算

4.2. ^評価 : ^実験条件 : ^データ



^{実験 ( 人 )}



^{フ G}

 ^{以 条件 従い ン 生成}

 ^{点数 : 10000}

 ^{辺数 : 各 点 対数正規 布 従う乱数( 均127.1)}

(^合計辺数 : ^約127.1^万)

 Web ^{フ 辺 数 対数正規 布 従う}*



^{フ G}

 ^{以 条件 従う11通 フ ン 生成}

 ^G₁ ^{見 V}_Q ^{属 点 割合(変化率r)}

0%, 10%, …, 100% ^{う G}₁ ^変化

* : G. Malewicz et al, “Pregel: A System for Large-Scale Graph Processing”, ACM 2010.

V_Q : GIM-V^{再計算 対象} V_b : V_Q ^{接 点}

V_u : ^{そ 以外 点}

変化率_r

= V_Q ^{全 点 占 割合} = GIM-V^{計算対象 割合}

4.2. ( ^補足 ) ^{実験データについて}



^{全体 点数 1 万 , 辺 数 約 127 万}



Incremental GIM-V G

PageRank ^{計算 行う際}

GIM-V ^{再計算 範} (= ^変化率 r = V

^割合 )

0% , 10%, …, 90%, 100% ^{変動 実験}

V

V

V

変化 点，辺

4.3. ^評価 : ^実験条件 : ^環境



^実験環境



^{計算機 (5} ) : AMD Phenom X4 2.5GHz

L2 512KB (4 cores), Memory 8GB

 ^{1 (4 ) , ワ 4 (16 )}

 ^{(ワ プ 数:64)}



OS : CentOS 5.22.6



DSMS : InfoSphereStreams 1.2 (System S)



^ン : gcc 4.1.2

4.4. ^評価 : ^実験結果



^{通常 GIM-V}

PageRank ^{計算 ，}

Incremental GIM-V

用い 高

計算 能．

 ^変化率r

: V_Q(GIM-V^{再計算対象})

^{属 点 割合}



(Incremental PageRank

同様 結果 あ ₎

0.0 5.0 10.0 15.0 20.0 25.0 30.0 35.0

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

計算時間(秒)

変 化 率_(r) Incremental GIM-V GIM-V

5.0 ^{6.3 5.9}

4.5 4.7 2.9

4.4

2.5 2.1 2.4

0.0 1.1

1.0 2.0 3.0 4.0 5.0 6.0 7.0

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

Incremental GIM-V度比

目次

1.

^背景

2.

^手法

3.

^設計

4.

^評価

5.

^議論

6.

^関連研究

7.

5. ^議論



^適用範



^今回， PageRank Incremental GIM-V ^適用



^{今後，ほ フ処理 適用 い}

検討 必要 あ



^例 : Random Walk with Restart ^{， ン ，}

最短経路問題

 Incremental GIM-V^{そ ，}

無向辺 フ 処理 高 化 見込 い



^{高 化 計算簡略化}



^{元 手法 ッ 処理 高 化手法 あ}



^{計算 簡略化 高 化 必要}

 ^{計算精度 犠牲}

6. ^関連研究



^Pregel

^{, PEGASUS}



^{既存 大規模 フ処理}



^{ッ 処理}



Incremental PageRank

, Adaptive PageRank



^{PageRank 計算 高 化手法}

*1 : G. Malewicz et al, “Pregel: A System for Large-Scale Graph Processing”, ACM 2010.

*2 : U Kang et al, “PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations”, ICDM 2009.

*3 : P. Desikan et al, “Incremental Page Rank Computation on Evolving Graphs”, ACM 2005.

*4 : S. Kamvar et al, “Adaptive methods for the computation of PageRank”, Linear Algebra and its Applications 386 (2004) 51-65.

7. ^まとめ





^{フ処理 計算}

Incremental GIM-V ^考案



IBM System S ^実装



^{今後 課題}



^{( 高 ) 計算 考案}



^{適用範 広い計算 考案}

 ^{例 : ン ，最短路問題}



^{清聴あ う い ．}

補足 _: 実験時の _GIM-V 計算反復回数

1

29

21

23

15

22

13

18

16

13

7 9

32

9

0

4

8

12

16

20

24

28

32

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

復 回 数 ( 限 3 2回 )

変 化 率 _(r)

Incremental GIM-V

GIM-V