Introduction

Java 16 viens d'être annoncé par Oracle avec un certain nombre de nouveautés intéressantes à voir en détail ici. L'une d'entre elles est la possibilité d'écrire des opérations qui utilisent la pleine puissance des processeurs vectoriels.

On va regarder ensemble rapidement ce qu'il en est et comment utiliser cette API.

Intérêt et cas d'usage

Quand on parle de vectorisation, on parle effectivement de parallélisme, mais pas n'importe lequel. En effet, on pourrait paralléliser un calcul sur plusieurs machines. On parlerait alors d'une architecture en cluster. On pourrait paralléliser un calcul sur plusieurs cœurs d'un même processeur. On parlerait alors de parallélisation inter-coeur.

Dans notre cas, on va chercher à effectuer une parallélisation intra-coeur, c'est-à-dire qu'on va paralléliser un calcul au sein d'un seul cœur à l'aide d'instructions particulières.

On est alors en mesure de se poser la question suivante : "Pourquoi diable voudrait-on s'infliger ça" ?

Les unités de calcul vectoriel sont très présentes dans les GPU, mais on en trouve aussi dans la plupart des processeurs grand public. Avant ça, son usage était réservé aux supercalculateurs (ie. la grande époque des Cray).

L’intérêt du calcul vectoriel est qu'il permet de réduire le nombre de chargements d'instructions. En effet, avec une approche traditionnelle, l'augmentation du nombre de cycles par instruction accélère l'horloge du CPU. Utiliser une approche vectorielle garantie des performances intéressantes comme nous le verrons plus tard dans cet article.

L'optimisation vectorielle permet alors aux processeurs de consommer mois d’électricité et par effet, de prendre plus soin de la planète💡🌎.

Cas d'usage

Typiquement, on peut utiliser la vectorisation pour toutes les opérations faites sur un tableau d’élément.

Prenons l'exemple du calcul de la distance euclidienne entre deux points.

On pourrait modéliser ce problème sous forme de calcul vectoriel comme suit :

Pensons deux vecteurs A et B avec :

$$\vec{A} = Xa,Ya,Za\newline
\vec{B} = Xb,Yb,Zb$$

Capture_decran_2021-06-04_a_10.45.04.png

On remarque que si le nombre de dimensions de notre vecteur augmente - dans une certaine mesure - le nombre d'operations de notre calcul ne change pas.

Prérequis

IDE

Pour pouvoir utiliser un IDE avec Java 16, il vous faudra certainement le mettre à jour :

  • IntelliJ:

Il vous faudra une version supérieure ou égale à 2021.1.1

  • Eclipse:

Il vous faudra une version supérieure ou égale à 4.20M1

Installer Java 16

Le JDK 16 est disponible sur le site officiel d'oracle vous pouvez le trouver ici

  • Distributions linux :
sudo dnf install java-latest-openjdk.x86_64
  • OSX :

Installation manuelle :

## extract your JDK here
cd /Library/Java/JavaVirtualMachines/
## Change your JAVA_HOME to /Library/Java/JavaVirtualMachines/jdk-16.jdk/Contents/Home
  • Si vous n'utilisez pas déjà Jenv :
## installez jenv : https://www.jenv.be/
jenv add /System/Library/Java/JavaVirtualMachines/jdk-16.jdk/Contents/Home
jenv global 16

Configuration d'IntelliJ

  • Pour les flemmards :

Je vous ai préparé un projet maven out of the box à lancer dans votre IDE ici

Au passage voici un petit tips de productivité : vous pouvez lancer vos projets dans IntelliJ directement depuis le terminal en ajoutant un petit alias a votre .zshrc comme ceci

## open current dir in intelliJ
 alias intellijize="open -na 'IntelliJ IDEA CE.app' --args './'"
  • Config manuelle
    • pom.xml:

      • dependencies :
      <dependencies>
      <!--Unit testing-->
          <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-api</artifactId>
            <version>5.7.1</version>
            <scope>test</scope>
          </dependency>
          <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-params</artifactId>
            <version>5.7.1</version>
            <scope>test</scope>
          </dependency>
          <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-engine</artifactId>
            <version>5.7.1</version>
            <scope>test</scope>
          </dependency>
      <!--Benchmarking tools for perf review-->
          <dependency>
            <groupId>org.openjdk.jmh</groupId>
            <artifactId>jmh-core</artifactId>
            <version>1.28</version>
          </dependency>
          <dependency>
            <groupId>org.openjdk.jmh</groupId>
            <artifactId>jmh-generator-annprocess</artifactId>
            <version>1.28</version>
            <scope>provided</scope>
          </dependency>
        </dependencies>
      
      • Build:
      <build>
              <plugins>
                  <plugin>
                      <groupId>org.apache.maven.plugins</groupId>
                      <artifactId>maven-compiler-plugin</artifactId>
                      <version>3.8.1</version>
                      <configuration>
                          <release>16</release>
                          <compilerArgs>
                              <compilerArg>--add-modules</compilerArg>
                              <compilerArg>jdk.incubator.vector</compilerArg>
                          </compilerArgs>
                          <annotationProcessorPaths>
                              <path>
                                  <groupId>org.openjdk.jmh</groupId>
                                  <artifactId>jmh-generator-annprocess</artifactId>
                                  <version>1.27</version>
                              </path>
                          </annotationProcessorPaths>
                      </configuration>
                  </plugin>
      
                  <plugin>
                      <groupId>org.apache.maven.plugins</groupId>
                      <artifactId>maven-surefire-plugin</artifactId>
                      <version>3.0.0-M5</version>
                      <configuration>
                          <argLine>--add-modules jdk.incubator.vector</argLine>
                      </configuration>
                  </plugin>
      
                  <plugin>
                      <groupId>org.apache.maven.plugins</groupId>
                      <artifactId>maven-shade-plugin</artifactId>
                      <version>3.2.4</version>
                      <executions>
                          <execution>
                              <phase>package</phase>
                              <goals>
                                  <goal>shade</goal>
                              </goals>
                              <configuration>
                                  <finalName>benchmarks</finalName>
                                  <transformers>
                                      <transformer
                                              implementation="org.apache.maven.plugins.shade.resource.ManifestResourceTransformer">
                                          <mainClass>org.openjdk.jmh.Main</mainClass>
                                      </transformer>
                                  </transformers>
                                  <filters>
                                      <filter>
                                          <artifact>*:*</artifact>
                                          <excludes>
                                              <exclude>**/module-info.class</exclude>
                                              <exclude>META-INF/MANIFEST.MF</exclude>
                                          </excludes>
                                      </filter>
                                  </filters>
                              </configuration>
                          </execution>
                      </executions>
                  </plugin>
              </plugins>
          </build>
      
    • config intellij:

Capture_decran_2021-05-31_a_11.09.14.png

Capture_decran_2021-05-31_a_11.09.41.png

Capture_decran_2021-05-31_a_11.10.31.png

Vérifiez que les dépendences de Modules sont bien en java 16

Capture_decran_2021-05-31_a_11.09.54.png

Un coup d’œil aux CPU "modernes"

L'apparition d'instructions SIMD (lire : Single instruction, Multiple Data) sur les processeurs grand public date des années 90 avec l’extension MMX sur Intel Pentium. On parle plus généralement de processeurs vectoriels.

La page Wikipédia des processeurs vectoriels est très exhaustive. Je vous suggère de la consulter. Pour aller plus loin vous pouvez aussi consulter ce lien et celui ci

  • Registres & Lanes

Les registres vectorisés ont une taille supérieur aux registres normaux. Sur les CPU Intel on trouve des registres spécialisés (xmm0, ymm0, zmm0.. cf : https://fr.wikipedia.org/wiki/Advanced_Vector_Extensions) qui effectuent une même opération sur plusieurs lanes

Capture_decran_2021-05-31_a_14.20.28.png

Une opération SIMD indique l'opération, la taille d'une lane et la taille des registres.

Pour l'exemple précédent on a : PADDW xmm0, xmm2, xmm3

avec

  • Préfixe

P pour 128 bits

VEX VP pour 256 bits

EVEX VP pour 512 bits

  • Opération

ADD pour l’opération

  • Taille d’une ligne

B (byte) = 8 bits

W (word) = 32bits

D (double) = 64bits

Q (quad) = 128bits

Les éléments principaux de l'API

Pour lancer une classe avec les bons modules :

java --add-modules jdk.incubator.vector fr.guihardbastien.boilerplate.Main

Premiers pas

Pour étudier les éléments important de l'API prenons des exemples simple:

package com.univalence.boilerplate;

import jdk.incubator.vector.IntVector;
import jdk.incubator.vector.VectorSpecies;

public class Main {
    public static void main(String[] args) {
        VectorSpecies<Integer> species = IntVector.SPECIES_PREFERRED;
        IntVector v1 = IntVector.broadcast(species, 20);
        IntVector v2 = IntVector.broadcast(species, 22);
        IntVector v3 = v1.add(v2);
        for (var i = 0; i < v3.length(); i++) {
            System.out.println(v3.lane(i));
        }
    }
}

VectorSpecies

Un VectorSpecies indique un type (en l’occurrence Integer) et une shape (taille en bits).

On peut faire référence à IntVector.SPECIES_[64|128|256|512] pour obtenir la shape.

Ici on fait référence a SPECIES_PREFERRED pour - d'après la doc - :

make the code dynamically adapt to optimal shape for the platform on which it runs

IntVector v1 = IntVector.broadcast(species, 20);

C'est ici qu'on "rempli" nos lanes décrites par le VectorSpecies avec la valeur 20.

Opération

On effectue une addition des deux registres vectorisés : IntVector v3 = v1.add(v2);

Sortie

Sur ma machine on peut voir la sortie suivante :

WARNING: Using incubator modules: jdk.incubator.vector
42
42
42
42
42
42
42
42

Les huit affichages nous indiquent que mes registres vectorisés mesurent 256 bits (on additionne 8 int encodés sur 32 bits simultanément)

Deuxième exemple

public class Main {
    public static void main(String[] args) {
        VectorSpecies<Integer> species = IntVector.SPECIES_PREFERRED;
        var arr = new int[]{0, 1, 2, 3, 4, 5, 6, 7};
        var b = new int[8];

        IntVector vectorizedArray = IntVector.fromArray(species, arr, 0);
        IntVector conditionVector = IntVector.broadcast(species, 6);
        IntVector addTermVector = IntVector.broadcast(species, 10);
        VectorMask<Integer> mask =  vectorizedArray.lt(conditionVector); // lt -> lower than

        // on ajoute 10 respectivement au mask
	IntVector vb = vectorizedArray.add(addTermVector, mask);
        vb.intoArray(b, 0);
        System.out.println(Arrays.toString(b));

    }
}

/* output

WARNING: Using incubator modules: jdk.incubator.vector
[10, 11, 12, 13, 14, 15, 6, 7]

*/

Concrètement ici, on effectue une condition relative a un vecteur en créant un masque. En gros, on fait un if vectorisé. Dans notre exemple le masque ressemble à ça : TTTTTTFF.

Pour toutes les lanes qui sont true sur le masque, on leur ajoute 10.

Post-loop & Mask

Pour l'exemple suivant, l'idée est de manipuler un array de manière vectorisée et du finir avec un reduce directement sur les vecteurs.

L'explication du code est faite directement en commentaire.

private static final VectorSpecies<Integer> SPECIES = IntVector.SPECIES_PREFERRED;

    public static int sum(int[] array) {
        var length = array.length;

	// loopBound permet de savoir jusqu'ou on peut vectoriser l'array
	// On se servira plus tard d'une "post-loop" pour finir le travail
        var loopBound = length - length % SPECIES.length();

	// la methode .zero est equivalente à 
	// IntVector.broadcast(species, 0);
        var v0 = IntVector.zero(SPECIES);
        var i = 0;
        for (; i < loopBound; i += SPECIES.length()) {
	    // chunk vector of array
            var v = IntVector.fromArray(SPECIES, array, i);
	    // on additionne le contenu des lanes entre eux
            v0 = v0.add(v);
        }
	// ici on on additionne les lanes entres elles
        int sum = v0.reduceLanes(VectorOperators.ADD);

	// La post-loop qui nous permet de finir le traitement complet de l'array
        for (; i < length; i++) {
            sum += array[i];
        }
        return sum;
    }

Voici un équivalent avec un masque :

public static int sumMask(int[] array) {
        var length = array.length;
        var loopBound = length - length % SPECIES.length();
        var v0 = IntVector.zero(SPECIES);
        var i = 0;
        for (; i < loopBound; i += SPECIES.length()) {
            var v = IntVector.fromArray(SPECIES, array, i);
            v0 = v0.add(v);
        }
        int sum = v0.reduceLanes(VectorOperators.ADD);

        var mask = SPECIES.indexInRange(i, length);
        var vMask = IntVector.fromArray(SPECIES, array, i, mask);
        int sumMask = vMask.reduceLanes(VectorOperators.ADD);

        return sum + sumMask;
    }

Test avec benchmark

Classe VectorComputation

import jdk.incubator.vector.IntVector;
import jdk.incubator.vector.VectorOperators;
import jdk.incubator.vector.VectorSpecies;

public class VectorComputation {
    private static final VectorSpecies<Integer> SPECIES = IntVector.SPECIES_PREFERRED;

    public static int sum(int[] array) {
        var length = array.length;
        var loopBound = length - length % SPECIES.length();
        var v0 = IntVector.zero(SPECIES);
        var i = 0;
        for (; i < loopBound; i += SPECIES.length()) {
            var v = IntVector.fromArray(SPECIES, array, i);
            v0 = v0.add(v);
        }
        int sum = v0.reduceLanes(VectorOperators.ADD);
        for (; i < length; i++) {
            sum += array[i];
        }
        return sum;
    }

    public static int sumMask(int[] array) {
        var length = array.length;
        var loopBound = length - length % SPECIES.length();
        var v0 = IntVector.zero(SPECIES);
        var i = 0;
        for (; i < loopBound; i += SPECIES.length()) {
            var v = IntVector.fromArray(SPECIES, array, i);
            v0 = v0.add(v);
        }
        int sum = v0.reduceLanes(VectorOperators.ADD);

        var mask = SPECIES.indexInRange(i, length);
        var vMask = IntVector.fromArray(SPECIES, array, i, mask);
        int sumMask = vMask.reduceLanes(VectorOperators.ADD);

        return sum + sumMask;
    }
}

VectorComputationBenchmark

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.infra.Blackhole;

import java.util.Random;
import java.util.concurrent.TimeUnit;

@Warmup(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@Fork(value = 1, jvmArgs = {"--add-modules", "jdk.incubator.vector"})
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Benchmark)
@SuppressWarnings("static-method")
public class VectorComputationBenchMark {
    private final int[] array = new Random(0).ints(100_000, 0, 1_000).toArray();

    @Benchmark
    public int sum_loop_array(Blackhole blackhole) {
        var sum = 0;
        for (var value : array) {
            sum += value;
        }
        return sum;
    }

    @Benchmark
    public int sum_vector_array(Blackhole blackhole) {
        return VectorComputation.sum(array);
    }

}

Benchmark

Lancer le benchmark

Branchez votre machine sur secteur puis :

cd ./maven-loom-intellij-boilerplate
mvn clean install
cd ./lab1/target
java -jar ./benchmarks.jar

Conclusions

REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on
why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial
experiments, perform baseline and negative tests that provide experimental control, make sure
the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts.
Do not assume the numbers tell you what you want them to tell.

Benchmark                                    Mode  Cnt   Score   Error  Units
VectorComputationBenchMark.sum_loop_array    avgt    5  23,589 ± 2,136  us/op
VectorComputationBenchMark.sum_vector_array  avgt    5   5,612 ± 0,284  us/op

Ressources