中南大学学报（英文版）
中南大學學報（英文版）
중남대학학보（영문판）
JOURNAL OF CENTRAL SOUTH UNIVERSITY OF TECHNOLOGY(ENGLISH EDITION)
2015年
6期
2238-2249
,共12页
杨博%卢凯%高颖慧%王小平%徐凯
楊博%盧凱%高穎慧%王小平%徐凱
양박%로개%고영혜%왕소평%서개
parallel graph isomorphism%GPU%backtrack paradigm
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.
