12729

Performance Evaluations of Graph Database using CUDA and OpenMP-Compatible Libraries

S. Morishima, H. Matsutani
Keio University, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama, Japan; National Institute of Informatics; Japan Science and Technology Agency PRESTO

@article{morishimaperformance,

   title={Performance Evaluations of Graph Database using CUDA and OpenMP-Compatible Libraries},

   author={Morishima, Shin and Matsutani, Hiroki}

}

Download Download (PDF)   View View   Source Source   

1298

views

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 computation cost for graph search queries increases as the graph becomes large, in this paper we accelerate the graph search functions (Dijkstra and A* algorithms) of a graph database Neo4j using two ways: multithreaded library and CUDA library for graphics processing units (GPUs). We use 100,000-node graphs generated based on a degree distribution of Facebook social graph for evaluations. Our multi-threaded and GPU-based implementations require an auxiliary adjacency matrix for a target graph. The results show that, when we do not take into account additional overhead to generate the auxiliary adjacency matrix, multi-threaded version improves the Dijkstra and A* search performance by 16.2x and 13.8x compared to the original implementation. The GPU-based implementation improves the Dijkstra and A* search performance by 26.2x and 32.8x. When we take into account the overhead, although the speed-ups by our implementations are reduced, by reusing the auxiliary adjacency matrix for multiple graph search queries we can significantly improve the graph search performance.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: