Improving the Accuracy in SpMV Implementation Selection with Machine Learning

Although there are various ways of implementing sparse matrix vector multiplication (SpMV), there is no established way of predicting the best implementation for individual sparse matrices, and thus an SpMV implementation has empirically been selected for each matrix. Cui et al. have proposed a machine learning approach to the prediction. However, their approach focuses only on predicting the best implementation for each matrix, and does not consider the performance differences among candidate implementations. If the performance difference between the best and non-best implementations for a matrix is large, the performance loss by the misprediction is also large. Thus, a machine learning model needs to be trained to preferentially avoid misprediction of such a matrix to achieve a higher expected performance. Therefore, this paper presents a machine learning approach that considers the performance differences at the best SpMV implementation selection problem and quantitatively discusses the performance improvement by the approach. The evaluation results clearly demonstrate that the proposed approach can prevent a machine learning model from selecting significantly low-performance implementations, and thereby improve the expected performance in comparison with the previous approach.