DTSpMV: An Adaptive SpMV Framework for Graph Analysis on GPUs
Guoqing Xiao, Tao Zhou, Yuedan Chen, Yikun Hu, Kenli Li · 2022
Sparse Matrix and Vector multiplication (SpMV) is one of the core algorithms in various large-scale scientific computing and real-world applications. With the rapid development of AI and big data, the input vector in SpMV becomes more and more sparse in many application fields. Especially in some graph analysis calculations, the sparsity of the input vector will change with the running of the program. At this time, the optimal SpMV kernel may be different, and a single SpMV kernel can no longer meet the acceleration requirements. In this paper, we propose a decision tree-based adaptive SpMV framework, named DTSpMV, that can automatically select appropriate SpMV kernels based on different input data in iterations of graph computation. Based on the analysis of computational patterns and serial and parallel algorithms, we encapsulate six SpMV cores within the proposed framework. We explore machine learning-based kernel selectors in terms of both accuracy and runtime overhead. Experimental results on NVIDIA Tesla P100 GPU show that our adaptive framework achieves the arithmetic average performance improvement of 60% compared to the state-of-the-art SpMV kernel benchmark, and the average ratio of the runtime prediction overhead of the framework to the total computing overhead is 1.9%.