GTSM：一种基于GPU的多边形中心化时间子图匹配框架

《ACM Transactions on Architecture and Code Optimization》：GTSM: A multi-edge-centric temporal subgraph matching framework on GPUs

针对时序子图匹配的NP难解问题，现有GPU加速方法存在计算冗余、内存管理低效及扩展性不足等问题。本文提出的GTSM系统通过多边中心范式压缩搜索空间、内存优化提升资源利用率，并采用异构BFS-DFS执行模型实现负载均衡，实验表明其速度提升达5.5倍，支持更多查询。

　　

摘要

时间子图匹配旨在识别时间网络中同时满足结构和时间约束的子图，其应用范围从社交网络分析到欺诈检测。由于这是一个NP难问题，需要对大型图进行大量计算，因此GPU加速变得至关重要。然而，现有的以边为中心的方法存在计算冗余、内存管理效率低下以及在大型图上可扩展性有限的问题，这些因素阻碍了GPU加速的效率。为了解决这些挑战，我们提出了GTSM，这是一个针对GPU优化的时间子图匹配系统，具有三项创新：（1）一种多边为中心的范式，通过多边压缩以及高效的解压缩算法来减少冗余搜索空间；（2）一种基于内存限制的优化方法，以最大化GPU资源利用率；（3）一种异构的BFS-DFS执行模型，其中CPU执行广度优先搜索（BFS），以确保跨GPU的负载均衡。实验表明，与最先进的GPU系统相比，GTSM实现了5.5倍至93.2倍的加速比，并且能够处理多10%至40%的查询量。凭借我们的异构执行模型，我们的系统在多GPU配置下实现了接近线性的扩展性。