GPU acceleration of subgraph isomorphism search in large scale graph  

作　　者：杨博 卢凯 高颖慧 王小平 徐凯 

机构地区：[1]Science and Technology on Parallel and Distributed Processing Laboratory, National University of Defense Technology [2]College of Computer, National University of Defense Technology [3]Department of Electronic Science and Engineering, National University of Defense Technology

出　　处：《Journal of Central South University》2015年第6期2238-2249,共12页中南大学学报（英文版）

基　　金：Projects(61272142,61103082,61003075,61170261,61103193)supported by the National Natural Science Foundation of China;Project supported by Funds for New Century Excellent Talents in University of China;Projects(2012AA01A301,2012AA010901)supported by the National High Technology Research and Development Program of China

摘　　要：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.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.

关 键 词：parallel graph isomorphism GPU backtrack paradigm 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] TP334.7[自动化与计算机技术—计算机科学与技术]