一句话：提出 TempGraph，将时序图转为时间依赖链并用 Generate-Activate-Compute 模型在 GPU 上高效并行计算时序路径。
时序图中的时序路径问题对时间敏感应用至关重要，但时间约束要求顶点沿时间依赖链顺序处理，导致并行度低、收敛慢，难以利用 GPU 的大规模并行与高带宽。本文提出链驱动的 GPU 时序图计算框架 TempGraph：先将时序图转化为一组互不相交的时间依赖链，显式暴露顶点间时序依赖并支持沿链快速路径探索；再设计 Generate-Activate-Compute 执行模型，通过为各链维护 shortcut 解耦链间依赖，使大量 GPU 线程可并发处理多条链。在 A100 上，TempGraph 相比先进 GPU 方案加速 3.0–16.2×，相比 128 核 CPU 上的 TeGraph 加速 33.9–368.9×。
Tackling temporal path problems in temporal graphs is essential for time-sensitive applications. Although many solutions have been proposed to handle temporal path problems, due to the intrinsic time constraints, these solutions require the vertices of the temporal graph to be sequentially handled along the time-dependent chains (i.e., the temporal dependencies between these vertices) to form the temporal path. This sequential temporal nature poses the challenges of poor parallelism and slow convergence speed, preventing existing solutions from fully leveraging the massive parallelism and high internal bandwidth of GPU to handle temporal path problems. To overcome these challenges, this paper proposes TempGraph, an efficient chain-driven GPU-based temporal graph computing framework. Specifically, it transforms the temporal graph into a set of disjoint time-dependent chains that can elegantly expose the temporal dependency between the vertices while facilitating the fast path exploration along these chains over GPU. Furthermore, TempGraph employs a novel Generate-Activate-Compute execution model to decouple the temporal dependency between different chains through maintaining a set of shortcuts for them, which enables multiple chains to be concurrently handled by massive GPU threads, achieving fast convergence speed and high parallelism on the GPU. Experiments on an A100 GPU show that TempGraph outperforms the state-of-the-art GPU-based solutions by 3.0-16.2×. Besides, TempGraph on an A100 GPU gains 33.9-368.9× speedups compared to the cutting-edge CPU-based system TeGraph on a 128-core CPU machine.
@inproceedings{0003WH0DHWY0LYL25,
title = {TempGraph: An Efficient Chain-driven Temporal Graph Computing Framework on the GPU},
author = {Jin Zhao and Qian Wang and Ligang He and Yu Zhang and Sheng Di and Bingsheng He and Xinlei Wang and Hui Yu and Hao Qi and Longlong Lin and Linchen Yu and Xiaofei Liao and Hai Jin},
booktitle = {ASPLOS},
year = {2025},
doi = {10.1145/3676642.3736116}
}