XBFS: eXploring Runtime Optimizations for Breadth-First Search on GPUs
Published in HPDC19: Proceedings of the 28th International Symposium on High-Performance Parallel and Distributed Computing, 2019
Recommended citation: Gaihre, Anil, et al. "Xbfs: exploring runtime optimizations for breadth-first search on gpus." Proceedings of the 28th International Symposium on High-Performance Parallel and Distributed Computing. 2019. https://anil-gaihre.github.io/files/XBFS.pdf
XBFS introduces dynamic optimizations to BFS on GPUs. It adaptively uses four either novel or optimized scan approaches to rapidly generate frontier queue. Further, inspired by the observation that bottom-up BFS experiences unpredictable amounts of workload, the paper proposes the novel dynamic workload balancing method. Third, the work designs and implements the first truly asynchronous BFS traversal..
Recommended citation: Gaihre, Anil, et al. “Xbfs: exploring runtime optimizations for breadth-first search on gpus.” Proceedings of the 28th International Symposium on High-Performance Parallel and Distributed Computing. 2019.