ROME: Maximizing GPU Efficiency for All-Pairs Shortest Path via Taming Fine-Grained Irregularities
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$\times$ speedup over the state-of-the-art multicore CPU solution and 11.2-338.0$\times$ 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.
Mon 2 FebDisplayed time zone: Hobart change
15:50 - 17:10 | GPU and Heterogeneous ComputingMain Conference at Pyrmont Chair(s): Frank Mueller North Carolina State University, USA | ||
15:50 20mTalk | PRISM: An Efficient GPU-Based Lossy Compression Framework for Progressive Data Retrieval with Multi-Level InterpolationBest Paper Nominee Main Conference Bing Lu Institute of Computing Technology of Chinese Academy of Sciences, Zedong Liu University of Chinese Academy of Sciences, Hairui Zhao Jilin University, Dejun Luo University of Chinese Academy of Sciences, Wenjing Huang University of Chinese Academy of Sciences, Yida Gu University of Chinese Academy of Sciences, Jinyang Liu University of Houston, Guangming Tan University of Chinese Academy of Sciences, Dingwen Tao Institute of Computing Technology, Chinese Academy of Sciences DOI | ||
16:10 20mTalk | Dynamic Detection of Inefficient Data Mapping Patterns in Heterogeneous OpenMP Applications Main Conference Luke Marzen Iowa State University, Junhyung Shim Iowa State University, Ali Jannesari Iowa State University DOI | ||
16:30 20mTalk | Root-Down Exposure for Maximal Clique Enumeration on GPUs Main Conference DOI | ||
16:50 20mTalk | ROME: Maximizing GPU Efficiency for All-Pairs Shortest Path via Taming Fine-Grained Irregularities Main Conference Weile Luo The Hong Kong University of Science and Technology, Guangzhou, Yuhan Chen The Hong Kong University of Science and Technology, Guangzhou, Xiangrui Yu The Hong Kong University of Science and Technology, Guangzhou, Qiang Wang Harbin Institute of Technology, Shenzhen, Ruibo Fan The Hong Kong University of Science and Technology, Guangzhou, Hongyuan Liu Stevens Institute of Technology, Xiaowen Chu The Hong Kong University of Science and Technology, Guangzhou DOI | ||