Warning: Undefined array key "category" in /var/www/02search_html/bin/summary.php on line 35

Warning: Undefined variable $STR_top_url in /var/www/02search_html/bin/__base_html.php on line 883
IEICE Trans - 効率的なグラフ分析のための実行時並列リオーダリング

効率的なグラフ分析のための実行時並列リオーダリング

新井　淳也
塩川　浩昭
山室　健
鬼塚　真
岩村　相哲

誌名
電子情報通信学会論文誌 D   Vol.J102-D    No.4    pp.302-312
発行日: 2019/04/01
早期公開日: 2019/01/11
Online ISSN: 1881-0225
DOI: 10.14923/transinfj.2018DEP0010
論文種別: 特集論文 (データ工学と情報マネジメント論文特集)
専門分野: グラフ処理
キーワード: 
グラフ処理,  並列処理,  キャッシュ,  リオーダリング,  疎行列,  

本文: PDF(2.7MB)>>
論文を購入


あらまし: 
グラフ分析におけるメモリアクセスの局所性を向上させるため，頂点リオーダリングによってデータ配置を事前に最適化するアプローチが広く用いられている．しかしながら既存のアルゴリズムは効果的なオーダリングの生成に長い時間を要するため，リオーダリングと後続のグラフ分析を合計した全体の処理時間をむしろ増加させてしまうという問題がある．本論文において我々は全体の処理時間を短縮するための並列リオーダリングアルゴリズムであるRabbit Orderを提案する．Rabbit Orderは高い局所性と高速なリオーダリングを同時に達成するとともに，効率的な並列処理により高いスケーラビリティを示す．実験の結果，全体処理時間の観点でRabbit Orderは平均2.2倍グラフ分析を高速化することが確認された．