マルチコアおよびGPUを用いたグラフ型データベースの性能評価

• Item type: SIG Technical Reports(1)
• 公開日: 2014-01-21
• タイトル: マルチコアおよびGPUを用いたグラフ型データベースの性能評価
• タイトル / 言語: en
• タイトル: Performance Evaluation of Graph Database using Multicore and GPU
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 並列処理
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 慶應義塾大学理工学部
• 著者所属: 慶應義塾大学理工学部／科学技術新興機構さきがけ／国立情報学研究所
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Technology, Keio University
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Technology, Keio University / PRESTO, Japan Science and Technology Agency / National Institute of Informatics
• 著者名: 森島, 信; 松谷, 宏紀
• 著者名(英): Shin, Morishima; Hiroki, Matsutani
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフ型データベースは、データをグラフ形式で蓄積し処理するデータベースである。グラフ型データベースはノード間の関係性を表現するのに向いているため、SNS(Social Networking Service)やソーシャルグラフを基にしたリコメンデーションエンジンヘの応用が期待されている。グラフ型データベースで最も計算量が多い処理は、グラフの探索である。本論文では、グラフ探索処理の並列化とＧＰＵによる高速化を実現し、その性能を評価する。ここではグラフ型データベース Neo4j を対象に、Dijkstra 法や A*法を高速化する。評価では、Facebook の次数分布を基にした 100,000 ノードのグラフに対して探索を行ったときの計算時間を測定した。データ構造を変える際のオーバーヘッドを含めない場合は、オリジナルの Neo4j と比べて、8 ノードで並列化すると、Dijkstra 法において 16.2 倍、A*法において 13.8 倍高速化できた。一方、GPU では、Dijkstra 法において 26.2 倍、A*法において 32.8 倍高速化できた。オーバーヘッドを考慮しても、この性能向上は有意である。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Graph databases use graph structures to store data sets as nodes, edges, and properties. They are used to store and search the relationships between a large number of nodes, such as social networking services and recommendation engines that use customer social graphs. Since graph search queries typically require high computation power, in this paper, we accelerate the graph search functions (Dijkstra and A* algorithms) of a graph database Neo4j using multicore and graphics proceccing units (GPUs). We use 100,000-node graphs generated based on a degree distribution of Facebook social graph for evaluations. Although our initial evaluation results do not include overhead of building extra data structures, the results show that, compared to the original Neo4j, the 8-core parallelized version improves the Dijkstra and A* search performance by 16.2x and 13.8x, respectively. The GPU based implementation improves the Dijkstra and A* search performance by 26.2x and 32.8x, respectively.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 研究報告システムLSI設計技術（SLDM）; 巻 2014-SLDM-164, 号 20, p. 1-6, 発行日 2014-01-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会