Search NASA⌕ Search

Engineering topics

Chen, Jou-An

Publications and source records attributed to Chen, Jou-An.

BitGNN: Unlocking the Performance Potential of Binary Graph Neural Networks on GPUs

Graph Neural Networks (GNNs) have shown compelling results in many graph-based learning tasks. They are, however, time-consuming. Recent work has shown a promising direction in improving GNN speed and shrinking the size — network binarization, which binarizes network values and operations. Prior work, however, mainly focused on algorithm designs, leaving it open on how to fully materialize the performance potential. This work fills the gap by proposing techniques to best map binary GNNs and their computations to fit the nature of bit manipulations, optimizations and algorithms to maximize BSpMM kernel efficiency, and solutions to other factors influencing the end-to-end time on GPUs. Results on real-world graphs show that the proposed techniques outperform state of-the-art binary GNN implementations by 21-67× with little accuracy loss.

Chen, Jou-An↗

Accelerating matrix-centric graph processing on GPUs through bit-level optimizations

Even though it is well known that binary values are common in graph applications (e.g., adjacency matrix), how to leverage the phenomenon for efficiency has not yet been adequately explored. This paper presents a systematic study on how to unlock the potential of the bit-level optimizations of graph computations that involve binary values. 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 the intrinsics of modern GPUs. It additionally introduces Deep Reinforcement Learning (DRL) as an efficient way to best configure the bit-level optimizations on the fly. Additionally, the DQN-based adaptive tile size selector with dedicated model training can reach 68% prediction accuracy. 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×.

79 ASTRONOMY AND ASTROPHYSICS↗

Bit-GraphBLAS: Bit-Level Optimizations of Matrix-Centric Graph Processing on GPU

In the graph data structure like adjacency matrix, the connectivity of two nodes can be sufficiently represented using only 1 bit, but they are generally treated as 32-bit full-precision in state-of-the-art graph frameworks to adopt common sparse format such as CSR. Meanwhile, bit-level parallelism has recently be explored to have high-performance potential and low storage requirement on GPUs with dense bit-tiles. To fill the gap, our solution is a hierarchical storage format that contains the bit-indexing base and dense bit-tile units. Inherently, the granularity of the bit-tile is an essential factor in achieving both storage compression and GPU parallelism. How to find a sweet spot that trades off between avoiding sparsity and exploiting is comprehensively researched in this work. In the experiment, we evaluate the proposed storage format and algorithms on modern generation GPUs, including Pascal and Volta, to figure out critical software co-designs in conjunction with existing hardware-specific optimization.

Chen, Jou-An↗