Authors: Chen Chen, Junsheng Chang, Xin Yang, Ruochun Jin, Li Shen, and Kai Lu (National University of Defense Technology (NUDT))
Abstract: Subgraph matching on massive graphs is hindered by GPU memory oversubscription, where frequent CPU-GPU data transfers create severe performance bottlenecks. Existing unified memory solutions suffer from bandwidth waste due to coarse-grained page transfers, while BFS-based approaches often fail due to intermediate result explosion. To address these challenges, we present PUMatch, a bandwidth-efficient, DFS-based CPU-GPU collaborative framework. PUMatch introduces four key innovations: (1) dual-scale packaging that reorganizes missing neighborhoods into compact CSR units to maximize bandwidth efficiency; (2) a synchronization-free asynchronous coordination protocol for DFS execution; (3) orthogonal warp scheduling with trie-based resumption that operates independently of the SM’s built-in scheduler; and (4) an adaptive hybrid data access scheme that dynamically optimizes data movement via a lightweight learning controller. Extensive experiments on real-world graphs with billions of edges demonstrate that PUMatch achieves up to 10.49× speedup over state-of-the-art BFS baselines and 3.45× over DFS baselines, while reducing PCIe traffic by 73%.
Presentation: file