Comment obtenir l'optimisation SIMD pour HotSpot JavaVM

Conversion de vectorisation HotSpot JavaVM

HotSpot JavaVM récent est optimisé pour vectoriser le traitement itératif des opérations scalaires et le convertir en instructions SIMD (qu'est-ce que SIMD? Voir la seconde moitié). Lorsque je l'ai essayé avec le code qui fonctionne réellement pour l'optimisation, une amélioration de la vitesse de 1,5 à 2,8 fois ** a été constatée, ce qui permet de bien l'utiliser avec les bibliothèques Java qui effectuent beaucoup de traitement arithmétique (ne comptez pas sur GPGPU). Cela peut être une méthode d'optimisation efficace.

L'optimisation SIMD de HotSpot est basée sur Superword-Level Parallelism (SLP) (ci-après, cette optimisation est Appelé SLP). À l'origine, cet article était destiné à refléter les temps et à convertir le traitement d'image / audio non compatible SIMD en instructions qui utilisent SIMD au niveau du compilateur et des couches d'exécution, mais il s'agit d'un code octet Java sans instructions SIMD. Il est également efficace pour utiliser SIMD.

Conversion de vectorisation HotSpot JavaVM

Processus de conversion SLP

Supposons le traitement de boucle simple suivant.

for(int i=0; i<1024; i++){
  a[i] = b[i] + c[i];
}

[Déroulement de la boucle](https://ja.wikipedia.org/wiki/%E3%83%AB%E3%83%BC%E3%83%97%E5%B1%95%E9%96] % 8B) (extension de boucle) est effectuée.

for(int i=0; i<1024; i+=4){
  a[i] = b[i] + c[i];
  a[i+1] = b[i+1] + c[i+1];
  a[i+2] = b[i+2] + c[i+2];
  a[i+3] = b[i+3] + c[i+3];
}

Cela à lui seul réduit le nombre d'interactions, le nombre de jugements de condition et la pénalité pour la prédiction de branche, donc on peut s'attendre à ce qu'il s'accélère (il existe de nombreuses extensions de boucle de ce type qui peuvent être effectuées par un compilateur ou une machine virtuelle).

Maintenant, le traitement à l'intérieur de la boucle peut être considéré comme l'opération vectorielle suivante.

\begin{pmatrix} a_{i+0} \\ a_{i+1} \\ a_{i+2} \\ a_{i+3} \end{pmatrix} = \begin{pmatrix} b_{i+0} \\ b_{i+1} \\ b_{i+2} \\ b_{i+3} \end{pmatrix} + \begin{pmatrix} c_{i+0} \\ c_{i+1} \\ c_{i+2} \\ c_{i+3} \end{pmatrix}

Cette opération vectorielle est en fait remplacée par une instruction d'opération vectorielle.

for(int i=0; i<1000; i+=4){
  load b[i:i+3] to xmm0
  load c[i:i+3] to xmm1
  add xmm0, xmm1 and store result to xmm0
  load xmm0 to a[i:i+3]
}

Avec cette conversion, il est possible de convertir la répétition d'un traitement arithmétique simple en une arithmétique vectorielle. Étant donné que tous les processeurs modernes peuvent utiliser des instructions SIMD, il est efficace d'utiliser SIMD sans changer la source ou le code d'octet.

Comportement en Java 8

Activez / désactivez en fait SLP en utilisant les sources suivantes et comparez les temps d'exécution. Les mesures sont appropriées, donc si vous avez besoin de preuves précises, faites-le vous-même.

import java.util.Arrays;

public class J8SIMD {
  private static final int SIZE = 1024 * 1024;
  private static final float[] a = new float[SIZE];
  private static final float[] b = new float[SIZE];
  static {
    Arrays.fill(a, 1);
    Arrays.fill(b, 2);
  }
  public static void vectorAdd(){
    for(int i=0; i<a.length; i++){
      a[i] += b[i];
    }
  }
  public static void main(String[] args){
    // warming up
    for(int i=0; i<100; i++) vectorAdd();
    // measure
    long t0 = System.currentTimeMillis();
    for(int i=0; i<10000; i++){
      vectorAdd();
    }
    long t1 = System.currentTimeMillis();
    System.out.printf("vectorAdd: %,d[msec]", t1 - t0);
  }
}

L'exécution de la source ci-dessus sur un Core i7-6600U (compatible MMX, SSE, SSE2, SSSE3, SSE4, AVX) fait une différence significative (même si j'ai simplement déroulé une boucle car je ne suis pas sûr d'avoir utilisé l'instruction SIMD). Il n'y a pas de possibilité de juste une différence: rolling_eyes :).

J'ai utilisé float ici, mais ʻint et double` font une différence significative, alors essayez-le. Cependant, en raison de la largeur des données, «double» n'est pas aussi différent que «int» et «float».

SLP est activé par défaut à partir de Java7u40, et si vous voulez le désactiver, utilisez l'option -XX: -UseSuperWord.

java8simd>java -XX:+UseSuperWord J8SIMD
vectorAdd: 4,624[msec]

java8simd>java -XX:-UseSuperWord J8SIMD
vectorAdd: 6,928[msec]

java8simd>java -version
java version "1.8.0_141"
Java(TM) SE Runtime Environment (build 1.8.0_141-b15)
Java HotSpot(TM) 64-Bit Server VM (build 25.141-b15, mixed mode)

Le temps d'exécution (millisecondes) de chaque opération est le suivant.

J'ai abandonné parce que % = n'a pas fini après avoir attendu quelques minutes (pourquoi est-ce si lent?). L'addition, la soustraction et la multiplication ont montré une accélération de 1,5x. L'accélération de la division est particulièrement remarquable à près de 3 fois, mais y a-t-il un mouvement tel qu'un traitement sur un FPU dédié lorsqu'il est exécuté avec des instructions SIMD?

Ce qui suit est le résultat du passage à la version ʻint` et de l'exécution d'opérations sur les bits. Les opérations Bitshift ne semblent pas être optimisées dans SLP.

Que SLP ait fonctionné efficacement ou non est un nombre remarquable, il semble donc que vous puissiez juger par la présence ou l'absence de l'option -XX: -UseSuperWord.

Conditions d'activation de SLP

Debug Compiled OpenJDK montrera comment les boucles sont perçues en utilisant l'option -XX: + PrintCompilation -XX: + TraceLoopOpts, et -XX: + PrintAssembly affichera l'assembly généré par HotSpot. est.

Java 8 / 9ea répertorié dans: rolling_eyes: Vectorisation dans HotSpot JVM Je vais mettre les conditions de. Je pense que les conditions de déclenchement et les restrictions seront assouplies dans les versions futures, veuillez donc suivre l'actualité.

• Doit être une boucle comptée. En d'autres termes, il s'agit d'une boucle de comptage, et la limite ne change pas pendant la boucle et l'étape est déterminée au moment de la compilation.

for(int i=0; i<100; i++){ } // OK
for(int i=5; i<100; i++){ } // OK
for(int i=t0; i<t1; i++){ } // OK
for(int i=0; i<100; i+=4){ } // OK
for(int i=0; i<100; i+=d){ } // NG
for(int i=0; i<100; i*=2){ } // NG
for(int i=0; i<t1; i++){     // NG
  ...
  if(...) t1 ++;
}

• Les compteurs de boucle sont uniquement ʻint, short, char`.

for(byte i=0; i<100; i++){ }  // NG
for(char i=0; i<100; i++){ }  // OK
for(short i=0; i<100; i++){ } // OK
for(int i=0; i<100; i++){ }   // OK
for(long i=0; i<100; i++){ }  // NG

• Le déroulement de la boucle n'est pas effectué lorsqu'un appel de fonction est inclus.

for(int i=0; i<100; i++){  // NG
  ...
  f();
}

• Les données cibles sont un tableau.

for(int i=0; i<100; i++){  // OK
  a[i] += b[i];
}
for(int i=0; i<100; i++){  // NG
  a.set(i, a.get(i) + b.get(i));
}

• Doit être une simple opération à quatre règles.

a[i] ++;  // OK
a[i] += 2; // OK
a[i] *= b[i]; // OK
a[i] = b[i] + c[i]; // OK

• L'index est continu.

for(int i=0; i<100; i++){  // NG
  a[i] += b[2 * i];
}

• L'agrégation peut être en partie possible à partir de Java 9

int r = 0;
for(int i=0; i<100; i++){
  r += a[i] * b[i];
}

Fonctionnalités comportementales et extensions Java 9

Sans surprise, les opérations API de collecte et Stream en Java (et les langages JavaVM tels que Scala et Kotlin) ne sont pas des opérations qui peuvent être traduites en instructions SIMD. Si le goulot d'étranglement est l'endroit où vous faites beaucoup de maths avec eux, il peut être intéressant d'envisager de le remplacer par un tableau et un nombre de boucles.

Puisque ʻUnsafe est un appel de méthode, vous ne pouvez pas vous attendre à cette optimisation dans le code qui utilise ʻUnsafe pour la prise de risque rapide.

La vectorisation a une contrainte d'alignement de 64 octets, et les fractions en avant du tableau sont effectuées dans une pré-boucle non vectorisée. De plus, les éléments qui ne sont pas des multiples de 4 à la fin du tableau sont post-bouclés sans être vectorisés. Cependant, la post-boucle semble être vectorisée dans Java 9.

Java 8 utilise des registres de 128 bits (xmm), il est donc vectorisé tous les 2 ou 4 éléments, mais en Java 9 AVX2 peut être augmenté à 32 ou quelque chose du genre.

SIMD

SIMD </ b> (Single Instruction Multiple Data) est un mécanisme pour appliquer la même instruction à un grand nombre de données numériques arrangées à la fois.