GPU acceleration of subgraph isomorphism search in large scale graph

YANG Bo(杨博)^{1, 2}, LU Kai(卢凯)^{1, 2}, GAO Ying-hui(高颖慧)³, WANG Xiao-ping(王小平)^{1, 2}, XU Kai(徐凯)^{1, 2}

(1. Science and Technology on Parallel and Distributed Processing Laboratory,
National University of Defense Technology, Changsha 410073, China;
2. College of Computer, National University of Defense Technology, Changsha 410073, China;
3. Department of Electronic Science and Engineering, National University of Defense Technology,
Changsha 410073, China)

Abstract:A novel framework for parallel subgraph isomorphism on GPUs is proposed, named GPUSI, which consists of GPU region exploration and GPU subgraph matching. The GPUSI iteratively enumerates subgraph instances and solves the subgraph isomorphism in a divide-and-conquer fashion. The framework completely relies on the graph traversal, and avoids the explicit join operation. Moreover, in order to improve its performance, a task-queue based method and the virtual-CSR graph structure are used to balance the workload among warps, and warp-centric programming model is used to balance the workload among threads in a warp. The prototype of GPUSI is implemented, and comprehensive experiments of various graph isomorphism operations are carried on diverse large graphs. The experiments clearly demonstrate that GPUSI has good scalability and can achieve speed-up of 1.4–2.6 compared to the state-of-the-art solutions.

Key words:parallel graph isomorphism; GPU; backtrack paradigm