Toward Resource-Efficient Billion-Scale SpGEMM on CPU-GPU Heterogeneous Server

Abstract

Sparse GEneral Matrix Multiplication (SpGEMM) is one of the most vital kernels in massive research domains, including bioinformatics, graph analytics, and machine learning. Moreover, with the prosperity of the Big Data era, nonzero elements in sparse matrices of SpGEMM boost rapidly into the magnitude of billions. Thus, accelerating billion-scale SpGEMMs becomes the new spotlight. To reduce both the monetary and energy costs of resource-intensive billion-scale SpGEMMs while enhancing their efficiency, we propose CESpGEMM, an adaptive resource-efficient library for billion-scale SpGEMMs on CPU-GPU heterogeneous servers. We design an Anchor-based Sparsity-aware Data Compression (ASDC) mechanism of high compression ratio and throughput to resolve the bottleneck of data transfer through PCIe. Moreover, given an arbitrary SpGEMM, we develop a sampling-based auto-tuning model to determine the optimal hyperparameter configuration. CESpGEMM also involves a hierarchical workflow that exploits adaptive CPU-GPU collaboration. We evaluate the performance of CESpGEMM using one T4 GPU with state-of-the-art SpGEMM libraries. The results demonstrate that compared to the cutting-edge implementation with 4 T4 GPUs, CESpGEMM outperforms these in terms of memory and communication efficiency, and can achieve the average acceleration rate of 5.42×.