Bit-GraphBLAS: Bit-Level Optimizations of Matrix-Centric Graph Processing on GPU
Bit-GraphBLAS: Bit-Level Optimizations of Matrix-Centric Graph Processing on GPU
复制标题
DOI：
10.1109/ipdps53621.2022.00056
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Jou-An Chen;Hsin-Hsuan Sung;Nathan R. Tallent;K. Barker;Xipeng Shen;Ang Li
中科院分区：
文献类型：
--
作者：
Jou-An Chen;Hsin-Hsuan Sung;Nathan R. Tallent;K. Barker;Xipeng Shen;Ang Li
在像邻接矩阵这样的一般图形数据结构中，当边是齐次的时，两个节点的连通性可以使用单个比特来充分表示。然而，现有的以矩阵为中心的图处理框架还没有充分利用这种洞察力。这项工作填补了空白，系统地探索图的位级表示和相应的优化图操作。提出了一种位块压缩稀疏行（B2SR）的两级表示方法，并利用现代GPU的固有特性对B2SR上的图操作进行了一系列优化。在NVIDIA Pascal和Volta GPU上的评估表明，优化分别为基本的GraphBLAS内核SpMV和SpGEMM带来了40倍和6555倍的加速，使基于GraphBLAS的BFS加速高达433倍，SSSP，PR和CC高达35倍，TC高达52倍。
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 40× and 6555× for essential GraphBLAS kernels SpMV and SpGEMM, respectively, making GraphBLAS-based BFS accelerate up to 433×, SSSP, PR, and CC up to 35×, and TC up to 52×.