ビッグデータ分析技術ワークショップ ~ グラフマイニング研究の最新動向と応用事例 ~ 平成 28 年 2 月 28 日 頂点順序の最適化による 高速なグラフ分析 新井淳也 日本電信電話株式会社 ソフトウェアイノベーションセンタ
この発表について 下記論文についての発表です Rabbit Order: Just-in-time Parallel Reordering for Fast Graph Analysis J. Arai, H. Shiokawa, T. Yamamuro, M. Onizuka, S. Iwamura IEEE IPDPS 2016 (to appear) 関連発表 DEIM Forum 2015 頂点順序の最適化によるスケーラブルなグラフ並列処理 NTT コミュニケーション科学基礎研究所 オープンハウス2015 CPUを賢く使ってグラフから素早く知識を発見 データ配置の最適化による高速なグラフ分析 idb Workshop 2015 Rabbit Order: Lightning-fast Reordering for Parallel Graph Processing ビッグデータ基盤研究会 (H27.8.26) 頂点順序の最適化による高速なグラフ処理 今回は コレの内容 新しい実験結果 2
大規模グラフ分析の性能問題 大規模なグラフの分析には時間がかかる 主な原因の一つはメモリアクセス局所性の低さ キャッシュミス増大によるメモリアクセスレイテンシの影響 メモリ帯域の飽和やコア間通信による並列処理性能の低下 コ コ コ コ ア ア ア ア 高いレイテンシ 狭いバンド幅 キャッシュメモリ 3
グラフ分析のメモリアクセス 例 PageRank until convergence do for each vertex do 𝑠 = 𝑢 𝑁 𝑠 𝑢 /degree(𝑢) 𝒔[𝒗]: 頂点 の PageRank スコア 𝑵𝒗 : と接続された頂点の集合 アクセスされる配列 𝒔 の要素 = 0 のとき 𝑠 0, 𝑠 2, 𝑠 4, 𝑠[7] にアクセスが発生 3 6 1 =0 2 4 7 0 1 2 3 4 5 6 7 0 5 4
グラフ分析のメモリアクセス 例 PageRank until convergence do for each vertex do 𝑠 = 𝑢 𝑁 𝑠 𝑢 /degree(𝑢) 𝒔[𝒗]: 頂点 の PageRank スコア 𝑵𝒗 : と接続された頂点の集合 アクセスされる配列 𝒔 の要素 0 1 2 3 4 5 6 7 3 6 1 =0 =1 2 4 7 0 5 5
グラフ分析のメモリアクセス 例 PageRank until convergence do for each vertex do 𝑠 = 𝑢 𝑁 𝑠 𝑢 /degree(𝑢) 𝒔[𝒗]: 頂点 の PageRank スコア 𝑵𝒗 : と接続された頂点の集合 アクセスされる配列 𝒔 の要素 0 1 2 3 4 5 6 7 3 6 1 2 4 7 0 =0 =1 =2 5 6
グラフ分析のメモリアクセス 例 PageRank until convergence do for each vertex do 𝑠 = 𝑢 𝑁 𝑠 𝑢 /degree(𝑢) 𝒔[𝒗]: 頂点 の PageRank スコア 𝑵𝒗 : と接続された頂点の集合 アクセスされる配列 𝒔 の要素 0 1 2 3 4 5 6 7 3 6 1 2 4 7 0 5 =0 =1 =2 =3 =4 =5 =6 =7 7
グラフ分析のメモリアクセス 例 PageRank until convergence do for each vertex do 𝑠 = 𝑢 𝑁 𝑠 𝑢 /degree(𝑢) 𝒔[𝒗]: 頂点 の PageRank スコア 𝑵𝒗 : と接続された頂点の集合 アクセスされる配列 𝒔 の要素 0 1 2 3 4 5 6 7 3 6 1 2 4 7 0 5 =0 =1 =2 =3 =4 =5 =6 =7 低い空間的局所性 低い時間的局所性 8
リオーダリングによる局所性向上 リオーダリング : 頂点順序 ( 頂点 ID) を最適化するテクニック隣接頂点をメモリ内で近傍に配置すると局所性が向上する つまり隣接頂点に数値的に近い ID 番号を与える様々なリオーダリング手法が提案されている :RCM, LLP, SlashBurn, ランダムな頂点順序 局所性の高い頂点順序 6 3 1 4 7 2 5 0 2 1 0 3 6 4 7 5 NTT 新井淳也 9
リオーダリングされたグラフ上のアクセス 例 PageRank until convergence do for each vertex do 𝑠 = 𝑢 𝑁 𝑠 𝑢 /degree(𝑢) アクセスされる配列 𝒔 の要素 局所性の高い頂点順序 1 2 0 4 3 6 5 7 𝒔[𝒗]: 頂点 の PageRank スコア 𝑵𝒗 : と接続された頂点の集合 0 1 2 3 4 5 6 7 =0 =1 =2 =3 =4 =5 =6 =7 10
リオーダリングされたグラフ上のアクセス 例 PageRank until convergence do for each vertex do 𝑠 = 𝑢 𝑁 𝑠 𝑢 /degree(𝑢) アクセスされる配列 𝒔 の要素 局所性の高い頂点順序 1 2 0 4 3 6 5 7 𝒔[𝒗]: 頂点 の PageRank スコア 𝑵𝒗 : と接続された頂点の集合 0 1 2 3 4 5 6 7 =0 =1 =2 =3 =4 =5 =6 =7 高い空間的局所性 高い時間的局所性 11
既存リオーダリング手法の問題点 End-to-end 処理時間の増大 End-to-end: リオーダリング + 分析 リオーダリングなし 分析 ( 例 :PageRank) リオーダリングありリオーダリング分析 時間 遅くなっている!!! NTT 新井淳也 12
提案手法 Rabbit Order アルゴリズムによる end-to-end 処理時間の短縮 リオーダリングなし 分析 ( 例 :PageRank) リオーダリングありリオーダリング分析 Rabbit Order リオーダリング 分析 時間 短いリオーダリング時間 & 高い局所性向上効果 NTT 新井淳也 13
2 つの主なテクニック 1. 階層的コミュニティに基づくオーダリング 高い局所性向上を実現 2. 並列逐次集約 短いリオーダリング時間を実現 NTT 新井淳也 14
2 つの主なテクニック 1. 階層的コミュニティに基づくオーダリング 高い局所性向上を実現 2. 並列逐次集約 短いリオーダリング時間を実現 NTT 新井淳也 15
コミュニティに基づくオーダリング コミュニティ 密に接続された頂点のグループ 各コミュニティに含まれる頂点を互いに近傍に配置する コミュニティに含まれる頂点へ連続した頂点 ID 番号を与える アクセスされる配列 𝒔 の要素 1 2 0 コミュニティ1 頂点ID 0 2 0 1 2 3 4 5 6 7 4 3 6 5 7 コミュニティ2 頂点ID 3 7 =0 =1 =2 =3 =4 =5 =6 =7 コミュニティ 1 コミュニティ 2 16
コミュニティに基づくオーダリング コミュニティ 密に接続された頂点のグループ 各コミュニティに含まれる頂点を互いに近傍に配置する コミュニティに含まれる頂点へ連続した頂点 ID 番号を与える アクセスされる配列 𝒔 の要素 0 1 2 3 =0 =1 =2 Facebook social network http://snap.stanford.edu/data/egonets-facebook.html 17
着眼点 コミュニティの階層構造 コミュニティ内部にはネストしたコミュニティがある 例 生徒のソーシャルネットワーク 学校 学年 クラスの階層 Facebook social network http://snap.stanford.edu/data/egonets-facebook.html 18
階層的コミュニティに基づくオーダリング 階層を捉えることでさらに局所性を向上させる コミュニティ内のコミュニティについても再帰的に頂点を近傍に配置 より密で小さいブロックの生成により局所性が向上 アクセスされる配列 𝒔 の要素 0 1 2 3 =0 =1 =2 密なブロック Facebook social network http://snap.stanford.edu/data/egonets-facebook.html 19
階層的コミュニティに基づくオーダリング 階層を捉えることでさらに局所性を向上させる コミュニティ内のコミュニティについても再帰的に頂点を近傍に配置 より密で小さいブロックの生成により局所性が向上 アクセスされる配列 𝒔 の要素 0 1 2 3 =0 =1 =2 では 密なブロック 階層的コミュニティをどう見つける リオーダリング時間は短くしたい Facebook social network http://snap.stanford.edu/data/egonets-facebook.html 20
2 つの主なテクニック 1. 階層的コミュニティに基づくオーダリング 高い局所性向上を実現 2. 並列逐次集約 短いリオーダリング時間を実現 NTT 新井淳也 21
並列逐次集約 逐次集約 (incremental aggregation) [Shiokawa+ 13]: ボトムアップなコミュニティ抽出を高速に行うためのテクニック Rabbit Order では更なる高速化のため逐次集約を並列化 詳細は割愛 1 3 6 2 4 7 1 0 3 2 4 5 コミュニティ 3 1 6 3 7 4 コミュニティ 0 2 5 7 4 Modularity [Newman+ 04] を最も 改善する隣接頂点へ各頂点をマージ 22
評価 実験環境 : Xeon E5-2697v2 物理 12コア x 2ソケット / RAM 256GB データセット berkstan enwiki ljournal uk-2002 road-usa uk-2005 it-2004 twitter sk-2005 webbase 頂点 0.7M 4.2M 4.8M 18.5M 23.9M 39.5M 41.3M 41.7M 50.6M 118.1M エッジ 7.6M 101.4M 69.0M 298.1M 57.7M 936.4M 1150.7M 1468.4M 1949.4M 1019.9M 比較対象 表記 説明 並列? Slash SlashBurn [Lim+ TKDE 14] No BFS Unordered parallel BFS [Karantasis+ SC 14] Yes RCM Unordered parallel RCM [Karantasis+ SC 14] Yes ND Multithreaded Nested Dissection [LaSalle+ IPDPS 13] Yes LLP Layered Label Propagation [Boldi+ WWW 11] Yes Shingle The shingle ordering [Chierichetti+ KDD 09] Yes Degree 次数昇順 Yes Random ランダム ( ベースライン ) ー NTT 新井淳也 23
性能低下 性能向上 End-to-end PageRank 高速化率 リオーダリングとナイーブに並列化した PageRank を48スレッド (HT使用) で実行 End to end 高速化率 = Random 順序時の PageRank 処理時間 リオーダリング時間 + PageRank 処理時間 Rabbit Order は最大3.5倍, 平均2.2倍の高速化を達成 他の手法は多くのグラフで処理速度を低下させている 平均高速化率2位の RCM でも僅か 1.08 倍の高速化 ND は twitter, sk-2005, webbase のリオーダリングに失敗 メモリ不足 24
PageRank 実行時間の内訳 速い! it-2004 における処理時間 Rabbit Order のみ短いリオーダリング時間と高い高速化率が両立 他の手法は両方またはどちらかが欠けている NTT 新井淳也 25
性能低下性能向上 PageRank 以外での有効性 全 10 グラフ平均の end-to-end 高速化率 Rabbit Order は PageRank 以外の分析アルゴリズムでも有効 ただし分析アルゴリズムが占める時間の長短に影響を受ける 分析時間が長いほどリオーダリングに要した時間の償却が容易 DFS と CC はそれぞれ似たメモリアクセスパターンを示すが 後者のほうが分析時間が長いため高い高速化率を示す (BFS と diameter の関係も同様 ) NTT 新井淳也 26
結論 グラフ分析の局所性を向上させるためにリオーダリング が用いられている しかしリオーダリングのオーバーヘッドは end-to-end の処理時間をむしろ増大させることが多い そこで 高速なリオーダリングアルゴリズムである Rabbit Order を提案する 2つの主なテクニック 1.階層的コミュニティに基づくオーダリング 高い局所性を実現 2.並列逐次集約 短いリオーダリング時間を実現 ランダムな頂点順序比で最大3.5倍の PageRank 性能 PageRank 以外の分析アルゴリズムでも高速化効果を確認 27