| 孟轲,林志恒,谭光明.基于GPU的子图匹配优化技术[J].高技术通讯(中文),2022,32(1):1~12 |
| 基于GPU的子图匹配优化技术 |
| Optimizing GPU-based subgraph matching algorithm |
| |
| DOI：10.3772/j.issn.1002-0470.2022.01.001 |
| 中文关键词: 子图匹配； 图挖掘； 图形处理单元（GPU）； 高性能； 图处理 |
| 英文关键词: subgraph matching, graph mining, graphic processing unit (GPU), high performance, graph processing |
| 基金项目: |
|
| 摘要点击次数: 1524 |
| 全文下载次数: 1013 |
| 中文摘要: |
| 为了解决图挖掘应用中子图匹配任务的性能问题，本文提出了一种基于图形处理单元（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 vertex-pruning subgraph matching (GVSM) system is proposed. GVSM adopts a blacklist pruning algorithm and an order-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 proposed 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. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
