A large-scale sparse matrix multiplication method based on streaming matrix to GPUs

Abstract

Sparse matrices are widely used to analyze a complex system which requires lots of linear algebraic operations such as computer graphics, recommender systems, machine learning, and information retrieval. As the size of real graphs are increasing rapidly, fast and scalable methods for handling such large-scale sparse matrices have become harder than before since the size of matrices increases as well. There have been various studies on implementing GPU-based methods for SpGEMM. However, most of those methods have faced two major challenges. First, the irregularity of matrices causes poor load balancing among threads. Second, many matrices do not fit in the GPU device memory.We propose a scalable and efficient GPU-based sparse-sparse matrices multiplication method called MStream which exploits streaming technology, which could hide memory latency of copy between main memory and device memory. To fully exploit GPU streams technology, we explore the design choice of an efficient data structure called slotted page format which divides a matrix into small fixed-size units instead of performing on Compressed Sparse Row (CSR) or Compressed Sparse Column (CSC) formats which are widely used to represent graphs with a sparse matrix in memory. ⓒ 2017 DGIST