STMatch: Accelerating Graph Pattern Matching on GPU with Stack-Based Loop Optimizations
STMatch: Accelerating Graph Pattern Matching on GPU with Stack-Based Loop Optimizations
复制标题
DOI：
10.1109/sc41404.2022.00058
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Yi-Hsiu Wei;Peng Jiang
中科院分区：
文献类型：
--
作者：
Yi-Hsiu Wei;Peng Jiang
图模式匹配是许多图分析和图挖掘应用中的基本任务。作为一个NP难问题，它往往是这些应用程序的性能瓶颈。以前的工作提出了使用GPU来加速计算。然而，我们发现，现有的GPU解决方案未能显示出性能优势，由于其子图为中心的设计，比最先进的CPU实现。本文提出了一种基于GPU的基于堆栈的图模式匹配系统，避免了以前以子图为中心的系统的同步和内存消耗问题。我们还提出了一个两级的工作窃取和循环展开技术，以提高我们的系统的线程间和线程内的GPU资源利用率。实验表明，我们的系统显着进步的图形模式匹配的GPU上的最先进的。
Graph pattern matching is a fundamental task in many graph analytics and graph mining applications. As an NP-hard problem, it is often a performance bottleneck in these applications. Previous work has proposed to use GPU to accelerate the computation. However, we find that the existing GPU solutions fail to show a performance advantage over the state-of-the-art CPU implementation due to their subgraph-centric design. This work proposes a novel stack-based graph pattern matching system on GPU that avoids the synchronization and memory consumption issues of the previous subgraph-centric systems. We also propose a two-level work-stealing and a loop-unrolling technique to improve the inter-warp and intra-warp GPU resource utilization of our system. The experiments show that our system significantly advances the state-of-the-art for graph pattern matching on GPU.