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

• Item type: SIG Technical Reports(1)
• 公開日: 2011-07-20
• タイトル: GPGPUを用いた高速大規模グラフ処理に向けて
• タイトル / 言語: en
• タイトル: Towards GPGPU-Based Large-Scale Fast Graph Processing
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: GPU
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京工業大学
• 著者所属: 東京工業大学
• 著者所属: 東京工業大学／IBM東京基礎研究所
• 著者所属: 東京工業大学／科学技術振興機構／国立情報学研究所
• 著者名: 白幡, 晃一; 佐藤, 仁; 鈴村, 豊太郎; 松岡, 聡
• 著者名(英): Koichi, Shirahata; Hitoshi, Sato; Toyotaro, Suzumura; Satoshi, Matsuoka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: データ量の肥大化，ストレージの省コスト化，オンラインソーシャルネットワークの成功等に伴い大規模グラフ処理の重要性が高まっている．また，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 倍の高速化がされることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Large-scale graph processing is becoming more important due to the large volume of available data, the low cost of storage and the stunning success of online social networks. Besides, recent large-scale computing systems tend to employ GPUs to gain good peak performance and high memory bandwidth. Mars is one of the MapReduce library accelerated with GPUs;however, the problems on GPGPU-based large-scale graph processing, such as the performance improvement by using GPUs, the memory management in GPUs, and the data distribution between multiple GPUs, are not investigated. In order to clarify the problems, we implemented several graph processing applications such as PageRank, Random Walk with Restart(RWR) and Connected Components on top of Mars and compared the results with PEGASUS, one of the large-scale graph processing library. Our experimental results show that the mean time of one iteration in Mars is 2.17-9.53 times faster on PageRank, 2.18-5.47 times on RWR, and 2.51-8.46 times on Connected Components respectively compared with PEGASUS.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 2011-HPC-130, 号 14, p. 1-8, 発行日 2011-07-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会