For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2014/12/01
Online ISSN: 1745-1361
Type of Manuscript: PAPER
Category: Software System
machine learning, support vector machine, automatic vectorization, software characteristics,
Full Text: PDF(867KB)>>
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).