Multi-GPU Programming Model for Subgraph Matching in Large Graphs

Abstract

Subgraph matching is an important method of data mining in complex networks. In recent years, the subgraph matching algorithm based on GPU (graphics processing units) has shown obvious speed advantages.However, due to the large scale of graph data and a large number of intermediate results of subgraph matching, the memory capacity of a single GPU soon becomes the main bottleneck for processing subgraph matching algorithm of large graph. Therefore, this paper proposes a multi-GPU programming model for large graph subgraph matching. Firstly, the framework of subgraph matching algorithm based on multi-GPU is proposed, and the cooperative operation of subgraph matching algorithm on multi-GPU is realized, which solves the problem of graph scale of subgraph matching on GPU. Secondly, a dynamic adjustment technique based on query graph is used to deal with cross-partition subgraph sets, which solves the cross-partition subgraph matching problem caused by graph segmentation. Finally, based on the characteristics of SIMT (single instruction multiple threads) architecture on GPU, a priority scheduling strategy is proposed to ensure the internal load balancing of GPU, and a pipeline mechanism of shared memory is designed to optimize the cache contention of multi-core concurrency. Experiments show that the proposed multi-GPU programming model can get the correct matching results on billions of datasets. Compared with the latest GPU-based solution, the proposed algorithm framework can achieve 1.2 to 2.6 times of acceleration ratio.

Keywords

• graph analysis; multi-gpu; subgraph matching in large graphs; priority scheduling; concurrent programming model