基于GPU的子图匹配优化技术  

Research on subgraph matching optimization based on GPU

作　　者：李安腾 崔鹏杰 袁野 王国仁 LI An-teng;CUI Peng-jie;YUAN Ye;WANG Guo-ren(School of Computer Science and Technology,Beijing Institute of Technology,Beijing 100081,China;School of Computer Science and Engineering,Northeastern University,Shenyang 110169,China)

机构地区：[1]北京理工大学计算机学院,北京100081 [2]东北大学计算机科学与工程学院,辽宁沈阳110169

出　　处：《浙江大学学报（工学版）》2023年第9期1856-1864,共9页Journal of Zhejiang University：Engineering Science

基　　金：国家自然科学基金资助项目(61932004,61732003);中央高校基本科研基金资助项目(N181605012)。

摘　　要：提出高效的基于图形处理器(GPU)的子图匹配算法GpSI,针对主流算法的过滤阶段和连接阶段分别设计优化方案.提出基于复合签名的过滤算法,在过滤阶段利用结点所处局部的数量特征和结构特征提升候选集过滤能力.采用基于候选点的连接策略,在连接阶段以最小邻居数为粒度预分配空间,设计高效的集合运算,避免传统方法重复连接的额外开销.多个数据集测试结果表明GpSI较主流GPU子图匹配算法在候选集过滤能力、执行用时、GPU内存占用和稳定性上均有明显优势.在真实数据集测试中,相比GPU友好子图匹配算法,GpSI的执行用时加速2~10倍.An efficient graphic processing unit(GPU)-based subgraph matching algorithm GpSI was proposed,and the optimization schemes were designed for the filtering phase and the joining phase of the mainstream algorithms.In the filtering phase,a filtering algorithm based on the composite signatures was proposed,and the local quantitative and structural features of the vertices were used to improve the filtering ability of the candidate sets.In the joining phase,a joining strategy based on candidate vertices was adopted.The space was pre-allocated at the granularity of the minimum number of neighbors,an efficient set operations was designed to realize the joining,and the extra overhead caused by the repeated joins in the traditional method was avoided.Experimental results of multiple datasets show that GpSI has obvious advantages in the filtering ability of the candidate set,the execution time,the GPU memory usage and the stability compared with the mainstream GPU subgraph matching algorithms.In a real data set experiment,the execution time of GpSI was 2 to 10 times faster compared to the execution time of GPU-friendly subgraph isomorphism algorithm.

关 键 词：子图同构 数据挖掘 图形处理器(GPU) 并行计算 高性能计算 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]