| Item type |
Trans(1) |
| 公開日 |
2016-03-08 |
| タイトル |
|
|
タイトル |
Pregelグラフ処理系におけるメッセージ配送最適化 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Optimized Message Communication Method for Pregel Graph Processing System |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
[アルゴリズム] グラフ処理，分散メモリ，Pregel |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| 著者所属 |
|
|
|
東京工業大学／JST CREST |
| 著者所属 |
|
|
|
トーマス・J・ワトソン研究所／JST CREST |
| 著者所属 |
|
|
|
東京工業大学／JST CREST |
| 著者所属(英) |
|
|
|
en |
|
|
Tokyo Institute of Technology / JST CREST |
| 著者所属(英) |
|
|
|
en |
|
|
IBM T.J. Watson Research Center / JST CREST |
| 著者所属(英) |
|
|
|
en |
|
|
Tokyo Institute of Technology / JST CREST |
| 著者名 |
上野, 晃司
鈴村, 豊太郎
松岡, 聡
|
| 著者名(英) |
Koji, Ueno
Toyotaro, Suzumura
Satoshi, Matsuoka
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
ソーシャルネットワークやWebグラフなど大規模グラフ解析の需要は近年高まっている．Pregelは大規模グラフの並列分散処理系の中でも最も簡単にグラフアルゴリズムを記述できるプログラミングモデルの1つであるが，処理速度の遅さが問題であった．本論文ではSendAllというメッセージ配送最適化手法を提案する．SendAllはすべての隣接頂点に同じメッセージを送る場合にしか適用できないという制約はあるが，計算処理を少し変えるだけで多くのグラフアルゴリズムに適用可能な最適化手法である．TSUBAME2.5を使った性能評価ではSendAllを適用しない場合に比べて，PageRankで1.80倍～4.04倍，幅優先探索で1.76倍～4.76倍に高速化した．また，通信データ量はR-MATグラフに対して32ワーカで動作させた場合Combinerを使った場合と比較してPageRankで45%削減した． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11833852 |
| 書誌情報 |
情報処理学会論文誌コンピューティングシステム（ACS）
巻 9,
号 1,
p. 30-40,
発行日 2016-03-08
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1882-7829 |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-TACS0901005.pdf (2.3 MB)
