PGMiner: A Load-Aware Dynamic Graph Pattern Matching Approach on GPUs

Abstract

Dynamic graph pattern matching is a crucial task in graph processing. However, with the exponential growth of graph size and the increasing demand for real-time updates, CPU-based graph pattern matching methods face serious performance problem. When the existing dynamic graph pattern matching model based on incremental computing is transplanted to GPUs, it still faces problems such as redundant computing, load imbalance and low resource utilization. To address the problems, we propose a dynamic graph pattern matching approach based on GPUs namely PGMiner. First, we propose a GPU-based dynamic graph pattern matching model. It generates shared execution plans for the edges of isomorphic pattern graphs by analyzing the topological structure of the pattern graph, thereby reducing redundant computations and symmetry checks. Second, a load-aware GPU-based dynamic graph pattern matching scheme is proposed to make full use of GPU computing resources. Specifically, a task overhead prediction model is proposed to guide task allocation to alleviate the load imbalance between multiple GPU devices. In the GPU, we propose a load-aware balancing strategy. The adaptive task splitting strategy is proposed to perceive and split high-load tasks, and the dynamic work stealing strategy is proposed to perceive high-load warps and steal their tasks, in order to alleviate the load imbalance between different warps in the GPU. Within the warp, by perceiving the load of the vertices in the candidate set, a dynamic loop unrolling mechanism of load fusion is performed, and multiple intersection calculations are performed in parallel, thereby improving thread utilization. Experimental results show that compared with state-of-the-art dynamic graph pattern matching systems GraphSet-P and G <inline-formula><tex-math notation="LaTeX">$^{2}$</tex-math><alternatives><mml:math><mml:msup><mml:mrow/><mml:mn>2</mml:mn></mml:msup></mml:math><inline-graphic xlink:href="mao-ieq1-3718204.gif"/></alternatives></inline-formula> Miner-P, PGMiner has achieved performance acceleration of 2.18<inline-formula><tex-math notation="LaTeX">$\sim 7.81\times$</tex-math><alternatives><mml:math><mml:mrow><mml:mo>∼</mml:mo><mml:mn>7</mml:mn><mml:mo>.</mml:mo><mml:mn>81</mml:mn><mml:mo>×</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="mao-ieq2-3718204.gif"/></alternatives></inline-formula> and 3.85<inline-formula><tex-math notation="LaTeX">$\sim 9.21\times$</tex-math><alternatives><mml:math><mml:mrow><mml:mo>∼</mml:mo><mml:mn>9</mml:mn><mml:mo>.</mml:mo><mml:mn>21</mml:mn><mml:mo>×</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="mao-ieq3-3718204.gif"/></alternatives></inline-formula>, respectively.