TY - GEN
T1 - ROME
T2 - 31st Annual ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2026
AU - Luo, Weile
AU - Chen, Yuhan
AU - Yu, Xiangrui
AU - Wang, Qiang
AU - Fan, Ruibo
AU - Liu, Hongyuan
AU - Chu, Xiaowen
N1 - Publisher Copyright:
© 2026 Owner/Author.
PY - 2026/1/28
Y1 - 2026/1/28
N2 - 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× speedup over the state-of-the-art multicore CPU solution and 11.2-338.0× 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.
AB - 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× speedup over the state-of-the-art multicore CPU solution and 11.2-338.0× 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.
KW - All-Pairs Shortest Path
KW - GPU Computing
KW - Irregular Workloads
UR - https://www.scopus.com/pages/publications/105029759380
UR - https://www.scopus.com/pages/publications/105029759380#tab=citedBy
U2 - 10.1145/3774934.3786461
DO - 10.1145/3774934.3786461
M3 - Conference contribution
AN - SCOPUS:105029759380
T3 - Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP 2026
SP - 204
EP - 217
BT - Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP 2026
A2 - Hosking, Tony
A2 - Musuvathi, Madan
A2 - Taura, Kenjiro
Y2 - 31 January 2026 through 4 February 2026
ER -