论文标题
GPU上的快速炮弹子图匹配（GSM）
Fast Gunrock Subgraph Matching (GSM) on GPUs
论文作者
论文摘要
在本文中，我们建议使用Gunrock图分析框架GSM（GunRock子图匹配）提出了GPU有效的子图同构算法，以计算GPU上的图形匹配。与基于深度优先遍历的CPU的先前方法相反，GSM基于BFS：在广度优先的策略中同时探讨了可能的匹配。使用基于BFS的遍历的优点是，我们可以利用GPU的大量并行处理能力。缺点是产生更中间的结果。我们提出了几种优化技术来解决问题。我们的实施遵循过滤和验证策略。虽然大多数先前在GPU上的工作都需要一/两步的连接，但我们使用一步验证来决定当前节点前沿中的候选人。与以前的GPU最新实施相比，我们的实施速度高达4倍。
In this paper, we propose a GPU-efficient subgraph isomorphism algorithm using the Gunrock graph analytic framework, GSM (Gunrock Subgraph Matching), to compute graph matching on GPUs. In contrast to previous approaches on the CPU which are based on depth-first traversal, GSM is BFS-based: possible matches are explored simultaneously in a breadth-first strategy. The advantage of using BFS-based traversal is that we can leverage the massively parallel processing capabilities of the GPU. The disadvantage is the generation of more intermediate results. We propose several optimization techniques to cope with the problem. Our implementation follows a filtering-and-verification strategy. While most previous work on GPUs requires one-/two-step joining, we use one-step verification to decide the candidates in current frontier of nodes. Our implementation has a speedup up to 4x over previous GPU state-of-the-art implementation.
