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

doi:10.1587/transinf.2014EDP7190

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

Full Text Views

0

Cite this

Summary :

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).

Publication: IEICE TRANSACTIONS on Information Vol.E97-D No.12 pp.3124-3132

Publication Date: 2014/12/01

Publicized: 2014/08/27

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2014EDP7190

Type of Manuscript: PAPER

Category: Software System

Authors

Antoine TROUVÉ
  Information Technologies and Nanotechnologies
Arnaldo J. CRUZ
  Kyushu University
Dhouha BEN BRAHIM
  ENSEIRB-MATMECA
Hiroki FUKUYAMA
  Kyushu University
Kazuaki J. MURAKAMI
  Kyushu University
Hadrien CLARKE
  Kyushu University
Masaki ARAI
  Fujitsu Laboratories Limited
Tadashi NAKAHIRA
  Fujitsu Laboratories Limited
Eiji YAMANAKA
  Fujitsu Limited

Keyword

machine learning, support vector machine, automatic vectorization, software characteristics

Cite this

Copy

Antoine TROUVÉ, Arnaldo J. CRUZ, Dhouha BEN BRAHIM, Hiroki FUKUYAMA, Kazuaki J. MURAKAMI, Hadrien CLARKE, Masaki ARAI, Tadashi NAKAHIRA, Eiji YAMANAKA, "Predicting Vectorization Profitability Using Binary Classification" in IEICE TRANSACTIONS on Information, vol. E97-D, no. 12, pp. 3124-3132, December 2014, doi: 10.1587/transinf.2014EDP7190.
Abstract: 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).
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2014EDP7190/_p

Copy

@ARTICLE{e97-d_12_3124,
author={Antoine TROUVÉ, Arnaldo J. CRUZ, Dhouha BEN BRAHIM, Hiroki FUKUYAMA, Kazuaki J. MURAKAMI, Hadrien CLARKE, Masaki ARAI, Tadashi NAKAHIRA, Eiji YAMANAKA, },
journal={IEICE TRANSACTIONS on Information},
title={Predicting Vectorization Profitability Using Binary Classification},
year={2014},
volume={E97-D},
number={12},
pages={3124-3132},
abstract={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).},
keywords={},
doi={10.1587/transinf.2014EDP7190},
ISSN={1745-1361},
month={December},}

Copy

TY - JOUR
TI - Predicting Vectorization Profitability Using Binary Classification
T2 - IEICE TRANSACTIONS on Information
SP - 3124
EP - 3132
AU - Antoine TROUVÉ
AU - Arnaldo J. CRUZ
AU - Dhouha BEN BRAHIM
AU - Hiroki FUKUYAMA
AU - Kazuaki J. MURAKAMI
AU - Hadrien CLARKE
AU - Masaki ARAI
AU - Tadashi NAKAHIRA
AU - Eiji YAMANAKA
PY - 2014
DO - 10.1587/transinf.2014EDP7190
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E97-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2014
AB - 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).
ER -