DGSM: A GPU-Based Subgraph Isomorphism framework with DFS exploration
DGSM: A GPU-Based Subgraph Isomorphism framework with DFS exploration
复制标题
DOI：
10.1109/rsdha56811.2022.00006
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
W. Han;Connor Holmes;Bo Wu
中科院分区：
文献类型：
--
作者：
W. Han;Connor Holmes;Bo Wu
亚图同构是图分析中的一个基本问题，并且已应用于许多领域。众所周知，亚图同构是一个NP完整问题。因此，它通常成为应用程序应用的应用的瓶颈。在过去的二十年中，已经有很多致力于这个问题的努力。但是，基于GPU的子图同构系统相对较少，因为GPU存储器不足以在匹配过程中保存所有实例。当前的大多数GPU子图同构框架均具有有限的GPU主内存和冗余计算。这些问题将它们限制在较小的模式和图形上，并限制其性能。为了克服这些问题，我们设计了一个名为DGSM的新的基于GPU的子图同构系统。我们的系统还有效地利用特殊的体系结构功能来改善数据并行性和内存带宽以进行匹配。我们通过与两个基于CPU的DAF和基于GPU的GSI进行比较来验证我们的技术。我们的实验结果表明，我们的系统在标记和未标记的图上均比DAF和GSI快2个数量级。
Subgraph Isomorphism is a fundamental problem in graph analytics and it has been applied to many domains. It is well known that subgraph isomorphism is an NP-complete problem. Thus, it generally becomes bottle-neck of the applications to which it is applied. There has been a lot of efforts devoted to this problem in the past two decades. However, GPU-based subgraph isomorphism systems are relatively rare since the GPU memory is not big enough to hold all the instances during the matching process. Most current GPU subgraph isomorphism frameworks suffer from the limited GPU main memory and redundant computation. These issues restrict them on smaller patterns and graphs and limit their performance. To overcome these issues, we design a new GPU-based sub-graph isomorphism system named DGSM. Our system also efficiently utilize special architecture features to improve data parallelism and memory bandwidth for matching. We validate our techniques by comparing with two state-of-the-art systems, CPU-based DAF and GPU-based GSI. Our experimental results show that our system achieve 2 orders of magnitude faster than DAF and GSI on both labeled and unlabeled graph.