Vectorizing Sparse Matrix Computations with Partially-Strided Codelets

The compact data structures and irregular computation patterns in sparse matrix computations introduce challenges to vectorizing these codes. Available approaches primarily vectorize strided regions of computation in a sparse code. They also reorganize data and computations, at a cost, to increase the number of strided regions. In this work, we propose a locality-based codelet mining (LCM) algorithm that efficiently searches for strided and partially strided regions in sparse matrix computations for vectorization. We also present a classification of partially strided codelets along with a differentiation-based approach to generate codelets from memory accesses in the sparse computation. LCM is implemented as an inspector-executor framework called LCM I/E. It generates vectorized code for the sparse matrix-vector multiplication (SpMV) and sparse matrix times dense matrix (SpMM), kernels with parallel outermost loops, and kernels with loop-carried dependence, specifically the sparse triangular solver (SpTRSV). We demonstrate the performance of the LCM I/E-generated code for SpMV/SpMM on a set of 789 real matrices (0.1-330M nonzeros) and SpTRSV on a set of 132 symmetric positive definite matrices. LCM I/E outperforms the highly specialized library MKL with an average speedup of 1.67×, 4.1×, 1.75× for SpMV, SpTRSV, and SpMM, respectively. For the same matrices, LCM I/E outperforms the state-of-the-art inspector-executor framework Sympiler [1] for the SpTRSV kernel with an average speedup of 1.9×.