So erhalten Sie eine SIMD-Optimierung für HotSpot JavaVM

HotSpot JavaVM-Vektorisierungskonvertierung

Das aktuelle HotSpot JavaVM wurde optimiert, um die iterative Verarbeitung von Skalaroperationen zu vektorisieren und in [SIMD] -Anweisungen (https://ja.wikipedia.org/wiki/SIMD) umzuwandeln (was ist SIMD? Siehe die zweite Hälfte). Als ich es mit dem Code ausprobierte, der tatsächlich für die Optimierung funktioniert, wurde eine 1,5- bis 2,8-fache Geschwindigkeitsverbesserung ** festgestellt, sodass es gut mit Java-Bibliotheken verwendet werden kann, die viel arithmetische Verarbeitung ausführen (nicht auf GPGPU angewiesen). Dies kann eine effektive Optimierungsmethode sein.

Die SIMD-Optimierung von HotSpot basiert auf Parallelität auf Superword-Ebene (SLP) (im Folgenden ist diese Optimierung SLP genannt). Ursprünglich sollte dieses Dokument die Zeit widerspiegeln und nicht SIMD-kompatible Bild- / Audioverarbeitung in Anweisungen konvertieren, die SIMD auf Compiler- und Laufzeitebene verwenden. Dies ist jedoch Java-Bytecode ohne SIMD-Anweisungen. Es ist auch effektiv für die Verwendung von SIMD.

HotSpot JavaVM-Vektorisierungskonvertierung

SLP-Konvertierungsprozess

Nehmen Sie die folgende einfache Schleifenverarbeitung an.

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

[Abrollen der Schleife](https://ja.wikipedia.org/wiki/%E3%83%AB%E3%83%BC%E3%83%97%E5%B1%95%E9%96] % 8B) (Schleifenexpansion) wird durchgeführt.

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];
}

Dies allein reduziert die Anzahl der Interaktionen, die Anzahl der Bedingungsbeurteilungen und die Strafe für die Verzweigungsvorhersage, sodass eine Beschleunigung zu erwarten ist (es gibt einige solcher Schleifenerweiterungen, die von einem Compiler oder einer virtuellen Maschine durchgeführt werden können).

Nun kann die Verarbeitung innerhalb der Schleife als die folgende Vektoroperation angesehen werden.

\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}

Diese Vektoroperation wird tatsächlich durch eine Vektoroperationsanweisung ersetzt.

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]
}

Mit dieser Konvertierung ist es möglich, die Wiederholung der einfachen arithmetischen Verarbeitung in eine Vektorarithmetik umzuwandeln. Da alle modernen CPUs SIMD-Anweisungen verwenden können, ist es effektiv, SIMD zu verwenden, ohne den Quell- oder Bytecode zu ändern.

Verhalten in Java 8

Aktivieren / deaktivieren Sie SLP mithilfe der folgenden Quellen und vergleichen Sie die Ausführungszeiten. Messungen sind angemessen. Wenn Sie also genaue Nachweise benötigen, tun Sie dies selbst.

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);
  }
}

Das Ausführen der obigen Quelle auf einem Core i7-6600U (MMX, SSE, SSE2, SSSE3, SSE4, AVX-kompatibel) macht einen signifikanten Unterschied (obwohl ich die Schleife einfach entrollt habe, weil ich nicht sicher bin, ob ich den SIMD-Befehl verwendet habe). Es gibt keine Möglichkeit, nur einen Unterschied zu machen: rollende_Augen :).

Ich habe hier "float" verwendet, aber sowohl "int" als auch "double" machen einen signifikanten Unterschied, also probieren Sie es aus. Aufgrund der Datenbreite unterscheidet sich "double" jedoch nicht so stark von "int" und "float".

SLP ist standardmäßig ab Java7u40 aktiviert. Wenn Sie es deaktivieren möchten, verwenden Sie die 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)

Die Ausführungszeit (Millisekunden) jeder Operation ist wie folgt.

Ich habe aufgegeben, weil % = nach ein paar Minuten Wartezeit nicht fertig war (warum ist es so langsam?). Addition, Subtraktion und Multiplikation zeigten eine 1,5-fache Beschleunigung. Die Beschleunigung der Teilung ist bei fast dreimal besonders bemerkenswert. Gibt es jedoch Bewegungen wie die Verarbeitung auf einer dedizierten FPU, wenn diese mit SIMD-Anweisungen ausgeführt werden?

Das Folgende ist das Ergebnis des Wechsels zur "int" -Version und der Ausführung von Bitoperationen. Bitshift-Operationen scheinen in SLP nicht optimiert zu sein.

Ob SLP effektiv funktioniert hat oder nicht, ist eine bemerkenswerte Zahl. Sie können also anscheinend anhand des Vorhandenseins oder Nichtvorhandenseins der Option "-XX: -UseSuperWord" beurteilen.

Bedingungen für die Aktivierung von SLP

Debug Compiled OpenJDK zeigt, wie Schleifen mit der Option -XX: + PrintCompilation -XX: + TraceLoopOpts wahrgenommen werden, und -XX: + PrintAssembly zeigt die von HotSpot generierte Assembly an. ist.

Java 8 / 9ea aufgeführt in: rollende_eyes: Vektorisierung in HotSpot JVM, weil ich es nach einem langen Urlaub einfach nicht tun kann Ich werde die Bedingungen von setzen. Ich denke, dass die auslösenden Bedingungen und Einschränkungen in zukünftigen Versionen gelockert werden, also folgen Sie bitte den aktuellen Angelegenheiten.

• Muss eine Trip-Counted-Schleife sein. Mit anderen Worten, es handelt sich um eine Zählschleife, und die Grenze ändert sich während der Schleife nicht, und der Schritt wird zur Kompilierungszeit bestimmt.

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 ++;
}

• Schleifenzähler sind nur "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

• Das Abrollen der Schleife wird nicht durchgeführt, wenn ein Funktionsaufruf enthalten ist.

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

• Die Zieldaten sind ein Array.

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));
}

• Muss eine einfache Operation mit vier Regeln sein.

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

• Der Index ist fortlaufend.

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

• Eine Aggregation ist möglicherweise teilweise von Java 9 aus möglich

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

Verhaltensfunktionen und Java 9-Erweiterungen

Es überrascht nicht, dass Sammlungs-API- und Stream-Operationen in Java (und JavaVM-Sprachen wie Scala und Kotlin) keine Operationen sind, die in SIMD-Anweisungen übersetzt werden können. Wenn der Engpass darin besteht, dass Sie viel mit ihnen rechnen, ist es möglicherweise sinnvoll, ihn durch eine Array- und Schleifenzahl zu ersetzen.

Da "Unsafe" ein Methodenaufruf ist, können Sie diese Optimierung nicht in Code erwarten, der "Unsafe" für das Eingehen von Risiken verwendet, bei denen die Geschwindigkeit an erster Stelle steht.

Die Vektorisierung unterliegt einer 64-Byte-Ausrichtungsbeschränkung, und die Brüche vor dem Array werden in einer nicht explorierten Vorschleife ausgeführt. Elemente, die am Ende des Arrays keine Vielfachen von 4 sind, werden ebenfalls nachgeschleift, ohne vektorisiert zu werden. Post-Loop scheint jedoch in Java 9 vektorisiert zu sein.

Java 8 verwendet 128-Bit-Register (xmm), daher wird es alle 2 oder 4 Elemente vektorisiert. In Java 9 kann AVX2 jedoch auf 32 oder so erhöht werden.

SIMD

SIMD </ b> (Single Instruction Multiple Data) ist ein Mechanismus, mit dem dieselbe Anweisung auf eine große Anzahl von gleichzeitig angeordneten numerischen Daten angewendet werden kann.