Exploiting Dynamic Regular Patterns in Irregular Programs for Efficient Vectorization

Modern optimizing compilers are able to exploit memory access or computation patterns to generate vectorized codes. However, such patterns in irregular programs 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 , 1 a framework to automatically exploit regular patterns buried deeply inside irregular programs and apply corresponding optimizations for better vectorization. Due to the integration of workload distribution and 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 for both serial and parallel irregular programs by replacing gather / scatter / reduction operations with optimized operation groups. We evaluate DynVec on optimizing irregular programs such as SpMV and graph programs with representative sparse matrix datasets. The experiment results show that DynVec achieves significant speedup compared to the state-of-the-art implementations across a range of X86 and ARM platforms.