Vectorizing SpMV by Exploiting Dynamic Regular Patterns

Modern optimizing compilers can exploit memory access and computation patterns to generate vectorized codes. However, such patterns in irregular programs such as SpMV are unknown until runtime due to the input dependence. Thus, either compiler's static optimization or profile-guided optimization cannot represent the patterns for any common input, which leads to suboptimal vectorization. To address the above drawback, we propose DynVec, a framework to automatically exploit regular patterns buried deeply inside SpMV programs and apply corresponding optimizations for better vectorization. Due to the ability to represent instruction features and identify regular patterns with effective feature extraction and data re-arranging methods, DynVec can generate highly efficient vectorized codes by replacing gather/scatter/reduction operations with optimized operation groups. We evaluate DynVec on optimizing SpMV with representative sparse matrix datasets. The experiment results show that DynVec achieves significant speedup compared to the state-of-the-art SpMV implementations across a range of platforms.