Predicting Vectorization Profitability Using Binary Classification

Antoine TROUVÉ  Arnaldo J. CRUZ  Dhouha BEN BRAHIM  Hiroki FUKUYAMA  Kazuaki J. MURAKAMI  Hadrien CLARKE  Masaki ARAI  Tadashi NAKAHIRA  Eiji YAMANAKA  

IEICE TRANSACTIONS on Information and Systems   Vol.E97-D   No.12   pp.3124-3132
Publication Date: 2014/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014EDP7190
Type of Manuscript: PAPER
Category: Software System
machine learning,  support vector machine,  automatic vectorization,  software characteristics,  

Full Text: PDF(867KB)>>
Buy this Article

Basic block vectorization consists in realizing instruction-level parallelism inside basic blocks in order to generate SIMD instructions and thus speedup data processing. It is however problematic, because the vectorized program may actually be slower than the original one. Therefore, it would be useful to predict beforehand whether or not vectorization will actually produce any speedup. This paper proposes to do so by expressing vectorization profitability as a classification problem, and by predicting it using a machine learning technique called support vector machine (SVM). It considers three compilers (icc, gcc and llvm), and a benchmark suite made of 151 loops, unrolled with factors ranging from 1 to 20. The paper further proposes a technique that combines the results of two SVMs to reach 99% of accuracy for all three compilers. Moreover, by correctly predicting unprofitable vectorizations, the technique presented in this paper provides speedups of up to 2.16 times, 2.47 times and 3.83 times for icc, gcc and LLVM, respectively (9%, 18% and 56% on average). It also lowers to less than 1% the probability of the compiler generating a slower program with vectorization turned on (from more than 25% for the compilers alone).