マルチコアおよびGPUを用いたグラフ型データベースの性能評価(並列処理,FPGA応用及び一般)

概要

論文の詳細を見る
グラフ型データベースは、データをグラブ形式で蓄積し処理するデータベースである。グラフ型データベースはノード間の関係性を表現するのに向いているため、SNS(Social Networking Service)やソーシャルグラフを基にしたリコメンデーションエンジンへの応用が期待されている。グラフ型データベースで最も計算量が多い処理は、グラフの探索である。本論文では、グラフ探索処理の並列化とGPUによる高速化を実現し、その性能を評価する。ここではグラフ型データベースNeo4jを対象に、Dijkstra法やA^*法を高速化する。評価では、Facebookの次数分布を基にした100,000ノードのグラフに対して探索を行ったときの計算時間を測定した。データ構造を変える際のオーバーヘッドを含めない場合は、オリジナルのNeo4jと比べて、8ノードで並列化すると、Dijkstra法において16.2倍、A^*法において13.8倍高速化できた。一方、GPUでは、Dijkstra法において26.2倍、A^*法において32.8倍高速化できた。オーバーヘッドを考慮しても、この性能向上は有意である。
一般社団法人電子情報通信学会の論文
2014-01-21