@inproceedings{53210087ae3f4334a13272157a47d852,
title = "ROME: Maximizing GPU Efficiency for All-Pairs Shortest Path via Taming Fine-Grained Irregularities",
abstract = "All-Pairs Shortest Path (APSP), a fundamental problem in graph analytics, can be solved efficiently by reducing the computational workload through vertex reordering. However, it fails on GPUs due to fine-grained granularity, shape, and dependency irregularities, which cause severe hardware underutilization. We introduce ROME, a system that tames these irregularities by spatially restructuring computation into regularized workloads and temporally overlapping them with an asynchronous pipeline. ROME achieves 14.7-244.5{\texttimes} speedup over the state-of-the-art multicore CPU solution and 11.2-338.0{\texttimes} speedup over the state-of-the-art GPU solution. Notably, our results achieve mostly above 20\% and up to 34.7\% of peak min-plus OPs across all tested graphs.",
keywords = "All-Pairs Shortest Path, GPU Computing, Irregular Workloads",
author = "Weile Luo and Yuhan Chen and Xiangrui Yu and Qiang Wang and Ruibo Fan and Hongyuan Liu and Xiaowen Chu",
note = "Publisher Copyright: {\textcopyright} 2026 Owner/Author.; 31st Annual ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2026 ; Conference date: 31-01-2026 Through 04-02-2026",
year = "2026",
month = jan,
day = "28",
doi = "10.1145/3774934.3786461",
language = "英语",
series = "Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP 2026",
publisher = "Association for Computing Machinery, Inc",
pages = "204--217",
editor = "Tony Hosking and Madan Musuvathi and Kenjiro Taura",
booktitle = "Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP 2026",
}