PGMiner：一种基于GPU的、考虑负载的动态图模式匹配方法

《IEEE Transactions on Knowledge and Data Engineering》：PGMiner: A Load-Aware Dynamic Graph Pattern Matching Approach on GPUs

　　

摘要：

动态图模式匹配是图处理中的关键任务。然而，随着图规模的指数级增长以及对实时更新需求的增加，基于CPU的图模式匹配方法面临着严重的性能问题。当将现有的基于增量计算的动态图模式匹配模型移植到GPU上时，仍然存在计算冗余、负载不平衡以及资源利用率低等问题。为了解决这些问题，我们提出了一种基于GPU的动态图模式匹配方法——PGMiner。首先，我们设计了一种基于GPU的动态图模式匹配模型，该模型通过分析模式图的拓扑结构，为同构模式图的边生成共享的执行计划，从而减少计算冗余和对称性检查。其次，我们提出了一种考虑负载的基于GPU的动态图模式匹配方案，以充分利用GPU的计算资源。具体而言，我们提出了一个任务开销预测模型，用于指导任务分配，从而缓解多个GPU设备之间的负载不平衡。在GPU内部，我们提出了一种考虑负载的平衡策略。此外，还提出了自适应任务分割策略，用于识别并分割高负载任务，以及动态工作窃取策略，用于识别高负载线程并窃取其任务，以此来缓解GPU中不同线程之间的负载不平衡。在单个线程内，通过识别候选集中各顶点的负载，实现负载融合的动态循环展开机制，同时并行执行多个交集计算，从而提高线程的利用率。实验结果表明，与现有的最先进的动态图模式匹配系统GraphSet-P和G2 Miner-P相比，PGMiner实现了2.18～7.81×和3.85～9.21×的性能加速效果。