GPGPUを用いた高速大規模グラフ処理に向けて

概要

論文の詳細を見る
データ量の肥大化,ストレージの省コスト化,オンラインソーシャルネットワークの成功等に伴い大規模グラフ処理の重要性が高まっている.また,GPGPU と呼ばれる,GPU を汎用計算に応用する技術の研究・開発が進んでおり,GPU のスーパーコンピュータやクラウドへの導入が進みつつある.大規模グラフ処理ライブラリの一つに PEGASUS があり,MapReduce の反復処理によって計算することができる.GPU を利用した MapReduce 処理ライブラリの一つに Mars があるが,大規模グラフ処理に対して GPU を使用してどの程度高速化できるのか,またメモリあふれへの対処やマルチ GPU 化した場合のデータの割り振り方法は明らかではない.Mars 上にグラフ処理アプリケーション (PageRank,Random Walk with Restart,Connected Components) を実装し,PEGASUS との比較実験を行った結果,反復 1 回あたり PageRank で 2.17〜9.53 倍,RWR で 2.18〜5.47 倍,Connected Components で 2.41〜8.46 倍の高速化がされることを確認した.
2011-07-20