2024-03-29T13:52:44Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001580522020-10-27T05:03:34Z00934:01119:08503:08504
Pregelグラフ処理系におけるメッセージ配送最適化Optimized Message Communication Method for Pregel Graph Processing Systemjpn[アルゴリズム] グラフ処理,分散メモリ,Pregelhttp://id.nii.ac.jp/1001/00158018/Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=158052&item_no=1&attribute_id=1&file_no=1Copyright (c) 2016 by the Information Processing Society of Japan東京工業大学/JST CRESTトーマス・J・ワトソン研究所/JST CREST東京工業大学/JST CREST上野, 晃司鈴村, 豊太郎松岡, 聡ソーシャルネットワークやWebグラフなど大規模グラフ解析の需要は近年高まっている.Pregelは大規模グラフの並列分散処理系の中でも最も簡単にグラフアルゴリズムを記述できるプログラミングモデルの1つであるが,処理速度の遅さが問題であった.本論文ではSendAllというメッセージ配送最適化手法を提案する.SendAllはすべての隣接頂点に同じメッセージを送る場合にしか適用できないという制約はあるが,計算処理を少し変えるだけで多くのグラフアルゴリズムに適用可能な最適化手法である.TSUBAME2.5を使った性能評価ではSendAllを適用しない場合に比べて,PageRankで1.80倍~4.04倍,幅優先探索で1.76倍~4.76倍に高速化した.また,通信データ量はR-MATグラフに対して32ワーカで動作させた場合Combinerを使った場合と比較してPageRankで45%削減した.In this several years, demand of large scale graph analysis has been bigger than before. Pregel is one of the most simple and straightforward programming model for distributed parallel graph processing. However, the problem of Pregel is low performance. We propose a new efficient message handling technique, called SendAll. Although SendAll can be applied only when a vertex sends the same message to all neighbor vertices, SendAll can be applied to many graph algorithms with a little change in the program. The result of our performance evaluation on TSUBAME2.5 shows that PageRank gets 1.80-4.04 times faster and Breadth-first search gets 1.76-4.76 times faster with SendAll. SendAll can also reduce the communication data volume. When we compute PageRank for R-MAT graph with 32 workers, the amount of data transferred between workers is reduced by 45 percent.AA11833852情報処理学会論文誌コンピューティングシステム(ACS)9130402016-03-081882-78292016-03-03