Performance Optimization Of Sparse Matrix Multiplication For High-Performance Computing Platforms

The multi-core CPUs and many-core GPUs have been the mainstream high-performance computing platform for high-performance computing,which boosts the progress of numerous scientific and engineering applications.Sparse GEneral Matrix Multiplication（SpGEMM）is a critical computing component in numerous scientific and engineering applications such as graph computing,linear algbra,and machine learning.Applications such as multi-source breadth-first search,algebraic multigrid solvers,and Markov clustering et al.contains SpGEMM algo-rithm.Improving the performance of the SpGEMM algorithm is important in improving the performance of many scientific and engineering applications.However,due to a large number of irregular memory accesses and computations in performing SpGEMM,and modern high-perforamnce computing platforms mainly consist of multi-coe CPU or many-core GPU,opti-mizing SpGEMM algorithms for these computing platforms faces many challenges.To tackle these challenges,we adopt the research method of combining the hardware architectures and SpGEMM algorithm characteristics?we analyze the problems in existing SpGEMM libraries and propose two optimized SpGEMM algorithms targeting the multi-core CPU and many-core GPU architectures,respectively.In addition,we propose a method to predict the sparse struc-ture of the result matrix,which can be used to improve the performance of SpGEMM and reduce its memory usage.The specific work and innovations of this dissertation are as follows:1)Proposing an optimized SpGEMM algorithm based on binary row merging and ping-pong buffers for multi-core CPU architectures.Combining the CPU architectures and the characteristics of SpGEMM algorithm,we observe that the existing SpGEMM libraries based on CPU architectures suffer inefficient memory access problem.To solve this problem,we propose a novel accumulation method BRMerge based on binary row merging algorithm and ping-pong buffers.Based on BRMerge,we propose two SpGEMM algorithms.BRMerge consecutively stores the intermediate lists to compute each result row into a ping-pong buffer.It then accumulates these intermediate lists two by two in a tree-like hierarchy between the two ping-pong buffers.The architectural benefits of BRMerge on CPU architectures are the streaming access pattern,minimized TLB cache miss rate,and reasonably high L1/L2 cache hit rates.Due to these architectural benefits,BRMerge has relatively high utilization rates of the memory bandwidth and caches.Therefore,BRMerge achieves improved memory access efficiency and improved computing performance.Experimental results show that the proposed SpGEMM algorithms based on BRMerge achieves an average performance speedup of 1.42×compared to the existing best-performing SpGEMM algorithm.2)Proposing a highly optimized SpGEMM computing framework for many-core GPU architectures.Combining the GPU architectures and the characteristics of SpGEMM algorithm,we analyze two state-of-the-art SpGEMM libraries（i.e.,nsparse and sp ECK）and find seven inefficient algorithms and implementations that cannot sufficiently utilize the GPU computing resources.Based on our observations,we propose seven corresponding optimiza-tions?we also integrate these optimizations and design a highly-optimized SpGEMM frame-work Op Sparse.These optimizations include 1)optimizing the binning method by improving the utilization of the shared memory,2)optimizing the hashing method by reducing the accesses to the hash tables,3)improving the trade-off between the hash collision rate and hardware uti-lization in the hashing method by setting appropriate binning ranges,4)reducing the overheads of global memory utilization by minimizing the global memory usage of the metadata and us-ing combined memory allocation instead of multiple separate memory allocations,5)improving the host and device execution parallelism by overlapping global memory allocation with kernel execution,6)improving the load balance of the streaming multiprocessors in the GPU by ma-nipulating the kernel launch orders,and 7)optimizing the kernel configuration to achieve the theoretical full occupancy of GPU cores.Experimental results show that Op Sparse outperforms nsparse and sp ECK by an average of 1.43×and 1.52×,respectively.3)Proposing a method to predict the sparse structure of SpGEMM’s result matrix.The sparse structure of SpGEMM’s result matrix（output structure of SpGEMM）is the number of nonzero elements per result row.This information is critical for improving the performance of SpGEMM and reducing the memory footprint of SpGEMM.However,precisely computing the output structure of SpGEMM takes high costs.Existing prediction method predict the total number of nonzero elements(n_nz)of the result matrix based on the n_nzof a sampled sub-matrix of the result matrix,and predict the output structure based on the additional number of multiplications(n_prod)required for computing each result row.We observe that the n_nzand n_prodof the sampled result matrix have a strong positive correlation.Based on this observation,we propose to utilize both the n_nzand n_prodof the sampled result matrix to predict the output structure of SpGEMM.Moreover,we propose to use the row-wise dataflow to optimize the computing overheads of the proposed method.Experimental results show that the proposed prediction method is far more accurate than the existing prediction method in predicting the output structure of SpGEMM?the execution time of the proposed method only takes 0.72%of the entire execution time of an existing best-performing SpGEMM algorithm on average.