GPU向けの反復型グラフ処理フレームワークにおけるトポロジ変更の実現

• Item type: SIG Technical Reports(1)
• 公開日: 2014-07-21
• タイトル: GPU向けの反復型グラフ処理フレームワークにおけるトポロジ変更の実現
• タイトル / 言語: en
• タイトル: Realizing Topology Mutation for an Iterative Graph Processing Framework on a GPU
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: GPU
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学大学院情報科学研究科コンピュータサイエンス専攻
• 著者所属: 大阪大学大学院情報科学研究科コンピュータサイエンス専攻
• 著者所属: 大阪大学大学院情報科学研究科コンピュータサイエンス専攻
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Information Science and Technology, Osaka University
• 著者名: 三谷, 康晃; 伊野, 文彦; 萩原, 兼一
• 著者名(英): Yasuaki, Mitani; Fumihiko, Ino; Kenichi, Hagihara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，GPU（Graphics Processing Unit） 向けの反復型グラフ処理フレームワークにおける高速なトポロジ変更を実現するために，辺を効率よく追加および削除するためのメッセージ管理手法を提案する．提案手法は，各頂点がメッセージ受信用のリストを保持し，リストにメッセージを挿入することにより送信を実現する．このデータ構造はグラフの頂点間の接続関係に依存しないため，辺の追加および削除時にメッセージバッファの再構築は不要である．また，ダブルバッファリング技術を応用し，送信時のメッセージ複製を回避し高速化する．さらに，メッセージ挿入時に発生する，スレッド間の衝突を削減するために，挿入位置を動的に分散する．評価実験では，トポロジ変更を前提としない反復型グラフ処理フレームワーク Medusa と提案手法を性能に関して比較した．Bellman-Ford アルゴリズムに対して最大で 1.3 倍の高速化を達成したが，PageRank アルゴリズムの性能は約 50～90%低下した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose a message management method for efficient addition and deletion of edges, aiming at realizing fast topology mutation for an iterative graph processing framework on a graphics processing unit (GPU). Our method allows vertices to have own lists for receiving messages, which are sent by insertion into the lists. This data structure is independent from the connectivity of vertices of the graph, so that edge addition and deletion does not require reconstruction of message buffer. We also achieve acceleration by using a double buffering technique that avoids duplication of messages to be sent. Furthermore, our method dynamically distributes insertion positions to reduce the number of thread conflicts that can occur at insertion of a message. In experiments, we compare the performance of our method with that of Medusa, a GPU-accelerated framework that does not assume topology mutation. Our method achieves the best speedup of 1.3x for the Bellman-Ford algorithm, but decreases performance for the PageRank algorithm by 50%-90%.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 2014-HPC-145, 号 41, p. 1-7, 発行日 2014-07-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会