Bit-GraphBLAS: Bit-Level Optimizations of Matrix-Centric Graph Processing on GPU
Pacific Northwest National Laboratory, Richland, WA, USA
arXiv:2201.08560 [cs.DC], (21 Jan 2022)
@misc{chen2022bitgraphblas,
title={Bit-GraphBLAS: Bit-Level Optimizations of Matrix-Centric Graph Processing on GPU},
author={Jou-An Chen and Hsin-Hsuan Sung and Nathan Tallent and Kevin Barker and Xipeng Shen and Ang Li},
year={2022},
eprint={2201.08560},
archivePrefix={arXiv},
primaryClass={cs.DC}
}
In a general graph data structure like an adjacency matrix, when edges are homogeneous, the connectivity of two nodes can be sufficiently represented using a single bit. This insight has, however, not yet been adequately exploited by the existing matrix-centric graph processing frameworks. This work fills the void by systematically exploring the bit-level representation of graphs and the corresponding optimizations to the graph operations. It proposes a two-level representation named Bit-Block Compressed Sparse Row (B2SR) and presents a series of optimizations to the graph operations on B2SR by leveraging the intrinsics of modern GPUs. Evaluations on NVIDIA Pascal and Volta GPUs show that the optimizations bring up to 40x and 6555x for essential GraphBLAS kernels SpMV and SpGEMM, respectively, making GraphBLAS-based BFS accelerate up to 433x, SSSP, PR, and CC up to 35x, and TC up to 52x.
January 30, 2022 by hgpu
