STMatch: Accelerating Graph Pattern Matching on GPU with Stack-Based Loop Optimizations
SessionGraphs and GPUs
DescriptionGraph 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 GPUs 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. In this work, we propose 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.
Event Type
Paper
TimeWednesday, 16 November 20224pm - 4:30pm CST
LocationC140-142
TP
Numerical Algorithms
Scientific Computing
Recorded
Archive
view