Multi-GPU Programming Model for Subgraph Matching in Large Graphs

doi:10.3778/j.issn.1673-9418.2111062

Abstract

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.

Key words: graph analysis, multi-GPU, subgraph matching in large graphs, priority scheduling, concurrent programming model

摘要： 子图匹配是复杂网络中进行数据挖掘的重要手段。近年来，基于图形处理器（GPU）的子图匹配算法已展现明显的速度优势。然而，由于大图数据的规模宏大以及子图匹配的大量中间结果，单块GPU的内存容量很快成为了处理大图子图匹配算法的主要瓶颈。因此，提出了一种面向大图子图匹配的多GPU编程模型。首先，提出了基于多GPU的子图匹配算法框架，实现了子图匹配算法在多GPU上的协同操作，解决了GPU大图子图匹配的图规模问题。其次，采用了一种基于查询图的动态调节技术来处理跨分区子图集，解决了图划分导致的跨分区子图匹配难题。最后，结合GPU单指令多线程（SIMT）架构特性，提出一种优先级调度策略保证GPU的内部负载均衡，并设计了共享内存的流水线机制优化多核并发的缓存争用。实验表明，多GPU编程模型能够在数十亿级别的数据集上得到正确的匹配结果，与最新的基于GPU的解决方案相比，该算法框架能够获得1.2~2.6倍的加速比。

关键词: 图分析, 多GPU, 大图子图匹配, 优先级调度, 并行编程模型

LI Cenhao, CUI Pengjie, YUAN Ye, WANG Guoren. Multi-GPU Programming Model for Subgraph Matching in Large Graphs[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(7): 1576-1585.

李岑浩, 崔鹏杰, 袁野, 王国仁. 面向大图子图匹配的多GPU编程模型[J]. 计算机科学与探索, 2023, 17(7): 1576-1585.

References

[1] KAIRAM S R, WANG D J, LESKOVEC J. The life and death of online groups: predicting group growth and longevity[C]//Proceedings of the 5th ACM International Conference on Web Search and Data Mining, Seattle, Feb 8-12, 2012. New York: ACM, 2012: 673-682.
[2] WANG J, CHENG J. Truss decomposition in massive networks[J]. Proceedings of the VLDB Endowment, 2012, 5(9): 812-823.
[3] 张晓琳, 袁昊晨, 李卓麟, 等. 面向子图匹配的社会网络隐私保护方法[J]. 计算机科学与探索, 2019, 13(9): 1504-1515.
ZHANG X L, YUAN H C, LI Z L, et al. Subgraph matching oriented privacy preserving method for social network[J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(9): 1504-1515.
[4] JENA B S, KHAN C, SUNDERRAMAN R. High performance frequent subgraph mining on transaction datasets: a survey and performance comparison[J]. Big Data Mining and Analytics, 2019, 2(3): 159-180.
[5] UGANDER J, BACKSTROM L, KLEINBERG J. Subgraph frequencies: mapping the empirical and extremal geography of large graph collections[C]//Proceedings of the 22nd Inter-national Conference on World Wide Web, Rio de Janeiro, May 13-17, 2013. New York: ACM, 2013: 1307-1318.
[6] LIU H, KESELJ V, BLOUIN C. Biological event extraction using subgraph matching[C]//Proceedings of the 4th Inter-national Symposium for Semantic Mining in Biomedicine, Cambridge, Oct, 2010: 110-115.
[7] LAI L, QIN L, LIN X, et al. Scalable distributed subgraph enumeration[J]. Proceedings of the VLDB Endowment,2016, 10(3): 217-228.
[8] SUN S, LUO Q. In-memory subgraph matching: an in-depth study[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, Portland, Jun 14-19, 2020. New York: ACM, 2020: 1083-1098.
[9] BI F, CHANG L, LIN X, et al. Efficient subgraph matching by postponing Cartesian products[C]//Proceedings of the 2016 International Conference on Management of Data, San Francisco, Jun 26-Jul 1, 2016. New York: ACM, 2016: 1199-1214.
[10] REN X, WANG J. Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs[J]. Proceedings of the VLDB Endowment, 2015, 8(5): 617-628.
[11] 许文, 宋文爱, 富丽贞, 等. 面向大规模图数据的分布式子图匹配算法[J]. 计算机科学, 2019, 46(4): 28-35.
XU W, SONG W A, FU L Z, et al. Distributed subgraph matching algorithm for large scale graph data[J]. Computer Science, 2019, 46(4): 28-35.
[12] LAI L, QIN L, LIN X, et al. Scalable subgraph enumeration in MapReduce[J]//Proceedings of the VLDB Endowment,2015, 8(10): 974-985.
[13] QIAO M, ZHANG H, CHENG H. Subgraph matching: on compression and computation[J]. Proceedings of the VLDB Endowment, 2017, 11(2): 176-188.
[14] WANG X, CHAI L, XU Q, et al. Efficient subgraph matching on large RDF graphs using MapReduce[J]. Data Science and Engineering, 2019, 4: 24-43.
[15] TRAN H N, KIM J, HE B. Fast subgraph matching on large graphs using graphics processors[C]//LNCS 9049: Proceedings of the 20th International Conference on Database Systems for Advanced Applications, Hanoi, Apr 20-23, 2015. Cham: Springer, 2015: 299-315.
[16] ZENG L, ZOU L, ?ZSU M T, et al. GSI: GPU-friendly subgraph isomorphism[C]//Proceedings of the 36th Inter-national Conference on Data Engineering, Dallas, Apr 20-24, 2020. Piscataway: IEEE, 2020: 1249-1260.
[17] GUO W, LI Y, SHA M, et al. GPU-accelerated subgraph enumeration on partitioned graphs[C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, New York, Jun 14-19, 2020. New York: ACM, 2020: 1067-1082.
[18] CUDA parallel computing platform[EB/OL]. [2021-09-04]. http://www.nvidia.com/object/cuda home new.html.
[19] ALAM M, PERUMALLA K S, SANDERS P. Novel parallel algorithms for fast multi-GPU-based generation of massive scale-free networks[J]. Data Science and Engineering, 2019, 4: 61-75.
[20] GALLET B, GOWANLOCK M. Heterogeneous CPU-GPU epsilon grid joins: static and dynamic work partitioning strategies[J]. Data Science and Engineering, 2021, 6: 39-62.
[21] KARYPIS G, KUMAR V. A fast and high quality multilevel scheme for partitioning irregular graphs[J]. SIAM Journal on Scientific Computing, 1998, 20(1): 359-392.
[22] WOOKS H, JINSOO L, JEONGH L. TurboISO: towards ultrafast and robust subgraph isomorphism search in large graph databases[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, New York, Jun 22-27, 2013. New York: ACM, 2013: 337-348.
[23] SUN Z, WANG H, WANG H, et al. Efficient subgraph matching on billion node graphs[J]. Proceedings of the VLDB Endowment, 2012, 5(9): 788-799.
[24] BIBEK B, HANG L, HUANG H H. CECI: compact embed-ding cluster index for scalable subgraph matching[C]//Proceedings of the 2019 International Conference on Management of Data, Amsterdam, Jun 30-Jul 5, 2019. New York: ACM, 2019: 1447-1462.
[25] MYOUNGJI H, HYUNJOON K, GEONMO G, et al. Efficient subgraph matching: harmonizing dynamic programming[C]//Proceedings of the 2019 International Conference on Management of Data, Amsterdam, Jun 30-Jul 5, 2019. New York: ACM, 2019: 1429-1446.
[26] SEUNG W M, VIKRAM S M, ZAID Q, et al. EMOGI: efficient memory-access for out-of-memory graph-traversal in GPUs[J].Proceedings of VLDB Endowment, 2020, 14(2): 114-127.
[27] WANG L, WANG Y, OWENS J D. Fast parallel subgraph matching on the GPU[C]//Proceedings of the 2016 ACM Symposium on High-Performance Parallel and Distributed Computing, Kyoto, May 31-Jun 4, 2016. New York: ACM, 2016.
[28] WebGraph Project Website. Laboratory for web algorithmics[EB/OL]. [2021-09-04]. http://law.di.unimi.it/index.php.
[29] LESKOVEC J, LANG K J, DASGUPTA A, et al. Community structure in large networks: natural cluster sizes and the absence of largewell-defined clusters[J]. Internet Mathematics, 2009, 6(1): 29-123.
[30] DOMENICO M D, LIMA A, MOUGEL P, et al. The anatomy of a scientific rumor[J]. Scientific Reports, 2013, 3(1): 1-9.