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

Optimizing GPU-based subgraph matching algorithm

为了解决图挖掘应用中子图匹配任务的性能问题,本文提出了一种基于图形处理单元(GPU)的顶点预剪枝子图匹配系统(GVSM)。GVSM采用黑名单剪枝算法和调度排序来减少冗余搜索。利用前缀树数据结构,GVSM可以对中间结果进行压缩,以便快速索引并降低内存消耗。GVSM将子图匹配的搜索部分卸载到GPU上执行,通过设计软件流水线进行重叠计算和数据移动,在PCI-E接口传输数据图拓扑数据的同时激活中央处理器(CPU)与GPU上的计算,并用动态负载均衡的方法减少计算资源的浪费。实验结果表明,本文方法能够有效提升子图匹配算法的性能,GVSM在性能上相比国际同类算法有显著提升,并且能处理更大规模的数据。

In order to solve the performance problem of subgraph matching,a graphic processing unit(GPU)-based ver-tex-pruning subgraph matching(GVSM)system is proposed.GVSM adopts a blacklist pruning algorithm and an or-der-selection to reduce redundant searching.By using a prefix tree,GVSM can compress the intermediate results,which reduces the memory footprint.Meanwhile,GVSM processes graphs using GPU cores while streaming topology data of graphs via PCI-E interfaces with a fully pipelined algorithm is designed to overlap the computing and data movement.A dynamic load-balance method is used to keep balanced workloads in GPU and center processing unit(CPU)in each iteration to reduce the waste of computing resources.The experimental results show that the pro-posed method can solve the subgraph matching task effectively and efficiently.GVSM has significantly outperformed the state-of-the-art work and has the ability to process larger dataset.