分散グラフ処理における グラフ分割の技術評価 D2-4 藤森 俊匡 (大阪大学) 塩川 浩昭 (筑波大学) 鬼塚 真 (大阪大学) 1 研究の背景 • 現実世界における大規模なグラフデータの登場 • ソーシャルグラフ • Webグラフ • グラフデータに対する分析処理はさまざまの分野で有用 • 最短経路探索 • 頂点のランキングアルゴリズム（PageRankなど） • グラフクラスタリング • 大規模なグラフデータに対する分析処理を高速に行うためのあああ 分散グラフ処理の需要が高まる 2 分散グラフ処理の流れ 1. グラフを分割して各計算機に割り当て 分析処理 • 配置後のグラフの再割り当ては行わない 2. 分析処理を並列実行 計算機1 入力グラフデータ 割り当て 分割 計算機2 通信 割り当て 重要 3 分散グラフ処理におけるグラフ分割 • グラフ分割は分析処理時間を大きく左右する重要な要素 通信コスト • 切断されるエッジ（頂点）数が多いほど 増大 計算機0 ロードバランス • 各計算機に割り当てられたエッジ数の 偏りが大きいほど悪化 計算機1 ロードバランスを保ちつつ通信コストを抑えることで 分析処理を高速化 4 既存のグラフ分割手法 高 グラフ構造全体を 利用する手法 グ ラ フ 分 割 の 精 度 METIS[Karypis 1998]など グラフデータを高速に分割し かつ精度の高いグラフ分割が 可能な手法が求められる 読み込んだ頂点やエッジの 割り当て先を逐次決定する手法 近年の分散グラフ処理で多く用いられる 低 長 グラフ分割に要する時間 短 5 本研究の概要 • グラフデータを高速に、かつ精度よく分割できるグラフ分割手法を 提案 • クラスタの逐次集約手法[Shiokawa 2013]を採用することで高速なグラフ分割 が可能 Modularity[Newman 2004]が 高くなるようにグラフデータを 分割することで 切断エッジ数を削減 & 各クラスタの内包エッジ数が 同程度（等粒度）になるように グラフデータを分割することで 高いロードバランスを実現 6 提案手法の概要 • 2ステップを経てグラフを𝑘個（計算機台数）に分割 1. Modularityクラスタリングステップ • 等粒度性を保ちつつ Modularity の値を大きくすることで切断エッジ数を削減 2. 等粒度クラスタリングステップ • 最終的に得られるクラスタの等粒度性が高くなるようにマージ クラスタ数：𝑎 ∗ 𝑘 クラスタ数：|𝑉| Modularity クラスタリング ステップ クラスタ数：𝑘 等粒度 クラスタリング ステップ 7 Modularity クラスタリングステップ • エッジ数の比率とModularityを合成した指標によりクラスタをマージ |E𝑖 | |𝐸𝑗 | Δ𝑄𝑖𝑗 ′ = 𝑚𝑖𝑛 , × Δ𝑄𝑖𝑗 |E𝑗 | |𝐸𝑖 | 通信コスト 等粒度性 𝐸𝑖 ∶ クラスタ 𝑖 が内包するエッジの集合 ∆𝑄𝑖𝑗 : クラスタ𝑖, 𝑗をマージした場合のModularityの変化量 Modularity : クラスタ内が密・クラスタ間が疎 → 大 |𝐸𝑖 |と|𝐸𝑗 |の差が大きい → 小 第1項 :|𝐸 |と|𝐸 |の差が小さい → 大 𝑖 𝑗 Modularity を大きくすることで クラスタ間のエッジ数を削減 エッジ数の比率を考慮することで等粒度性を保持 8 等粒度クラスタリングステップ • 内包エッジ数が多いクラスタ上位 𝑘 個を種クラスタに • 種クラスタと他のクラスタを等粒度性を考慮しつつマージ • 隣接するクラスタの組をマージすることで切断エッジ数を削減 左図のグラフを2つのグラフに分割したいとする 5 50 5 20 10 円内の数字：クラスタの内包エッジ数 円間の数字：クラスタ間エッジ数 内包エッジ数の多いクラスタ上位2個を種クラスタに 内包エッジ数の少ない種クラスタと隣接クラスタをマージ 5 種クラスタと隣接していないクラスタがいた場合 内包エッジ数が少ない種クラスタとマージ 10 5 最終的なクラスタの内包エッジ数 10 10 10 赤クラスタ 青クラスタ 65 65 切断エッジ数：10 9 実験・評価 • 既存のフレームワークであるPowerGraph[Gonzalez 2012]に本手法を 組み込み性能評価を行った 1. 2. 3. 4. グラフ分割指標による評価 Modularityと通信コストとの関係性 分析処理を実行した場合の評価 スケーラビリティの評価 • 比較対象となるグラフ分割手法 • PowerGraphで採用されている逐次割り当て手法3つ • random, oblivious[Gonzalez 2012], HDRF[Petroni 2015] • 提案手法 10 グラフ分割指標による評価 通信コスト レプリケーションファクタ • 頂点が切断されることによって生成される複製の平均数 • 最小値 1 （小さいほど通信コストが小さい） ロードバランス ロードバランスファクタ • 各計算機に割り当てられたエッジ数の最大値 / 平均値 • 最小値 1 （小さいほど負荷の均衡がとれている） 11 グラフ分割指標による評価 • 各計算機台数におけるレプリケーションファクタおよびロードバラン スファクタによる比較 • webbase-2001（およそ1億頂点、10億エッジ）の結果のみ掲載 レプリケーションファクタ ロードバランスファクタ 12 10 8 6 4 2 0 1.15 1.1 1.05 1 0.95 8台 16台 32台 48台 64台 8台 計算機台数 random oblivious HDRF 16台 32台 48台 64台 計算機台数 本手法 random oblivious HDRF 本手法 ロードバランスの悪化を抑えつつ、通信コストを大きく削減できていることが分かる 12 Modularity と 通信コストの関係性 • 提案手法は Modularity の値を大きくして切断エッジを削減すること で通信コストを抑制 グラフデータのModularityの値と通信コスト抑制の効果との 関係性を検証 • 従来手法と比較してレプリケーションファクタをどれぐらい小さくでき たのかによって通信コスト抑制の効果を評価 13 Modularity と 通信コストの関係性 使用データセット 頂点数 エッジ数 1 email-EuAll 265,214 420,045 2 web-Stanford 281,903 2,312,497 3 com-DBLP 317,080 1,049,866 4 web-NotreDame 325,729 1,497,134 5 amazon0505 410,236 3,356,824 6 web-BerkStan 685,230 7,600,595 7 web-Google 875,713 5,105,039 8 soc-Pokec 1,632,803 30,622,564 9 roadNet-CA 1,965,206 2,766,607 10 wiki-Talk 2,394,385 5,021,410 11 soc-LiveJournal1 4,847,571 68,993,773 12 uk-2002 18,520,486 298,113,762 13 webbase-2001 レプリケーションファクタの比 No. データ名 randomとの比（random=1） 0.5 0.45 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05 0 1 10 8 11 9 3 5 0 0.2 0.4 0.6 0.8 4 2 6 7 13 12 1 1.2 Modularityの値 Modularity の値が大きいグラフデータほど 本手法による通信コスト抑制の効果が 大きいことが分かる 118,142,155 1,019,903,190 14 分析処理を実行した場合の評価 • 以下の分析処理を実行し分析処理時間と各計算機の平均送信 バイト量を測定 • PageRank, SSSP（単始点最短経路探索）, CC（連結成分抽出） 平均送信バイト量(random=1) 1.2 1 0.8 0.6 0.4 0.2 0 PageRank SSSP CC 分析処理 random oblivious HDRF 本手法 送信バイト量(random=1) 分析処理時間(random=1) 分析処理時間(random=1) 1.2 1 0.8 0.6 0.4 0.2 0 PageRank SSSP CC 分析処理 random oblivious HDRF 本手法 通信コストが削減されていることにより分析処理が高速化されていることが分かる 15 スケーラビリティの評価 • 計算機台数を変化させた場合の PageRank の分析処理時間、グラフ 分割時間および全体実行時間を比較 分析処理時間(秒) グラフ分割時間(秒) 5000 4000 3000 2000 1000 0 合計実行時間(秒) 2000 5000 4000 3000 2000 1000 0 1500 1000 500 0 8台 16台 32台 48台 64台 8台 計算機台数 random oblivious HDRF 16台 32台 48台 64台 8台 16台 計算機台数 本手法 random oblivious HDRF 32台 48台 64台 計算機台数 本手法 random oblivious HDRF 計算機台数の増加に伴って分析処理時間が 短くなっていることが分かる 16 スケーラビリティの評価 • 計算機台数を変化させた場合の PageRank の分析処理時間、グラフ 分割時間および全体実行時間を比較 分析処理時間(秒) グラフ分割時間(秒) 5000 4000 3000 2000 1000 0 合計実行時間(秒) 2000 5000 4000 3000 2000 1000 0 1500 1000 500 0 8台 16台 32台 48台 64台 8台 計算機台数 random oblivious HDRF 16台 32台 48台 64台 8台 計算機台数 本手法 random oblivious HDRF 16台 32台 48台 64台 計算機台数 本手法 random oblivious HDRF oblivious, HDRFは計算機台数の増加に伴いグラフ分割時間が線形に 増大しているのに対し、本手法はグラフ分割時間が計算機台数に依存しない 17 スケーラビリティの評価 • 計算機台数を変化させた場合の PageRank の分析処理時間、グラフ 分割時間および全体実行時間を比較 分析処理時間(秒) グラフ分割時間(秒) 5000 4000 3000 2000 1000 0 合計実行時間(秒) 2000 5000 4000 3000 2000 1000 0 1500 1000 500 0 8台 16台 32台 48台 64台 8台 計算機台数 random oblivious HDRF 16台 32台 48台 64台 8台 計算機台数 本手法 random oblivious HDRF 16台 32台 48台 64台 計算機台数 本手法 random oblivious HDRF すべての計算機台数において本手法が 最も全体実行時間が短くなっていることが分かる 18 まとめ • 分散グラフ処理を高速化するようなグラフ分割手法を提案 • 提案手法の特徴 • 従来のグラフ構造全体を利用する手法よりも高速にグラフ分割が可能 • Modularityの値が大きくなるようにグラフ分割を行うことで切断エッジ数を削減、通信コ ストを抑制 • 各計算機に割り当てられるエッジ数を等粒度にすることでロードバランスを向上 • 提案手法を既存のフレームワークに組み込み性能を評価 • Modularity の高いグラフデータほど本手法による通信コスト抑制の効果が 大きい • 分析処理中の通信バイト量を削減することで分析処理を高速化できる • 計算機台数を増加させることで分析処理を高速化できる 19
© Copyright 2024 ExpyDoc
