:: Enseignements :: ESIPE :: E4INFO :: 2019-2020 :: Collections Concurrentes ::

Single instruction, Multiple Data (SIMD)

Calcul Parallele, Vectorisation, Loop decomposition

Nous allons utiliser l'API jdk.incubator.vector qui est en cours de création, elle devrait être intégrée dans le JDK 15 si tout se passe bien, par contre cela demande à utiliser un JDK spécial:

Pas de version pour Windows !
Il va donc falloir configurer votre IDE préféré pour utiliser ce JDK après l'avoir gunzippé quelque part.
Le lien vers la javadoc du package jdk.incubator.vector
Et quand vous aurez un peu de temps, vous pouvez lire la JEP 338 qui explique un peu le pourquoi du comment.

Comme je suis gentil avec vous, je vous ai préparé un zip qui contient un projet Maven avec son POM, struct-conc-lab5.zip, et les fichiers de configs pour Eclipse et IntelliJ déjà écrits.

Exercice 1 - Startup

Faite en sorte de pouvoir builder le projet struct-conc-lab5 dans votre IDE, de pouvoir lancer les tests JUnit et d'exécuter le benchmark JMH.
Rappel: il faut indiquer à Maven où est le JDK en changeant la variable d'environement JAVA_HOME
```
      export JAVA_HOME=/path/to/jdk-15-vector
    
```
Rappel 2: mvn package génère le jar, enfin les jars car il y a le jar avec votre projet et le jar pour le benchmark JMH
Rappel 3: le jar de benchmark s'appel benchmark.jar que l'on lance comme ceci $JAVA_HOME/bin/java -jar target/benchmark.jar.

Exercice 2 - Vectorized Add

Comme vous l'avez surement remarqué, la classe Vectorized possède une méthode sumLoop qui calcul la somme des éléments d'un tableau d'entier en faisant une boucle.
On se propose d'écrire une nouvelle version, normalement plus rapide, en utilisant les opérations sur des vecteurs de données.

Vector API
Un vecteur de donnée est une classe

Spécifique à un type primitive ShortVector, IntVector, FloatVector etc
qui regroupe ensemble de plusieurs valeurs d'un même type, par exemple, 4 ints. Le nombre de valeurs (le nombre de lanes) dépend de votre processeur, sur un Intel (AVX1 = 128bits donc 4 lanes de ints, AVX2 = 256bits donc 8 lanes de ints, AVX3 = 512 donc 16 lanes de ints).
La classe VectorSpecies représente le type de vecteur (vectorSpecies.elementType) ainsi que le nombre de lanes (vectorSpecies.length()).
La constante IntVector.SPECIES_PREFERRED permet d'obtenir la taille préférée (équivalent à la taille max à part si le processeur gère mal sa taille max, car Intel à des problèmes de perfs avec le support 512 bits sur certain processeurs).
qui offre des méthodes
- IntVector.fromArray(SPECIES, array, index) pour extraire des valeurs à l'index d'un tableau et les stocker dans le vecteur renvoyée. vector.intoArray(array, i) pour faire l'opération inverse, prende les valeurs du vecteur et les stocker dans le tableau.
  Attention, ces opération ne marchent passi i + SPECIES.length() dépasse de la taille du tableau
- IntVector.zero() et IntVector.broadcast(value) permettent d'initiliser un vecteur respectivement à zéro ou à la valeur passée en paramètre.
- add,sub, mul, div etc qui applique la même opération sur toutes les valeurs du vecteur. On appel ces opérations lanewise et bien sûr, les vecteurs doivent avoir la même taille, le même nombre de lanes.
- vector.reduceLanes(associative) permet de prendre les valeurs de toutes les lanes et appliquer la même opération. Les opérations sont définies dans la classe VectorOperators (ADD, MUL, etc).

Post-loop
Pour parcourir un tableau array avec la granularité d'une lane d'un vecteur, on peut utiliser la boucle

     for (var i = 0; i < array.length; i += SPECIES.length()) {
        ...
     }

Le problème est que si la taille du tableau n'est pas une puissance de 2 (supérieur à 2), alors on ne va pas parcourir les derniers éléments. Par exemple, si on parcours un tableau de 19 élements avec un vecteur de taille 2 (2 lanes), on ne peut parcourir que 18 élements (9 x 2), donc il faut ajouter ce que l'on appel une post-loop qui va finir le traitement sur les élements restants.
Donc on écrira un code comme ceci

     var i = 0;
     var limit = array.length - (array.length % SPECIES.length());  // main loop
     for (; i < limit; i += SPECIES.length()) {
       ...
     }
     for (; i < array.length; i++) {                             // post loop
       ...
     }

Vérifier que vous arrivez bien à builder le projet struct-conc-lab5 dans votre IDE et à lancer le benchmark JMH.
Quelle sont les points communs et les différences entre l'API Fork/Join et l'API des Vector ?
Et avec les volatiles/Compare and Set ?
Dans la classe Vectorized, écrire une méthode sumReduceLane qui parcours le tableau, charge chaque partie de tableau dans un vecteur, utilise la méthode vector.reduceLanes(...) pour faire la somme des valeurs du vecteur dans la main loop.
Et vérifier que les tests passent en dupliquant la méthode de test pour tester la méthode sumReduceLane.
PS: n'oublier pas la post-loop
Dans la classe VectorizedBenchMark, dupliquer la méthode de benchmark pour benchmarker la méthode sumReduceLane.
Lancer le benchmark, est-ce que le résultat est satifaisant (la réponse est non), pourquoi ?
Dans la classe Vectorized, écrire une méthode sumLanewise qui initialise un vecteur, parcours le tableau, charge chaque partie du tableau dans un autre vecteur, fait l'addition lanewise entre et les deux vecteur puis une fois la main loop exécutéee utilise la méthode reduceLanes pour faire la somme des valeurs du vecteur.
Ajouter une méthod de test et vérifier que les tests passent sur sumLanewise.
Ajouter une méthode de benchmark qui test la vitesse de sumLanewise et vérifier que la méthode est plus rapide que sumReduceLane. Quelle est le facteur d'amélioration de la vitesse comparé à sumLoop ? Pouvez vous l'expliquer ?

Exercice 3 - Vectorized Sub

On souhaite faire la même chose que l'exercice préceédent, une reduction sur un tableau mais cette fois ci en utilisant la soustraction au lieu de l'addition.
Note: vous allez dire que l'exercice est idiot car le résultat est la négation du résultat de l'exercice précédent 0 - 1 - 2 - 3 >=> - (0 + 1 + 2 + 3). Et vous aurez raison, c'est un exercice pour voir que comme + et - ne se comporte pas pareil mathématiquement, l'API de vectorisation ne propose pas les mêmes opérations.

Toujours dans la classe Vectorized ajouter une méthode differenceLanewise qui fait la soustraction des valeurs du tableau sachant que si le tableau est de taill vide, le résultat doit être 0.
Quelle méthode de l'API de vectorisation n'est pas disponible pour l'opération -, pourquoi ?
Comment corriger le problème ?
Implanter votre solution, vérifier avec un test que les résultats sont corrects puis
Ajouter un test de performance et calculer la différence de vitesse entre une reduction vectorisée avec un + et une reduction vectorisée avec un -.

Exercice 4 - MinMax

On souhaite enfin calculer le minnimum et le maximum des valeurs d'un tableau en un seul parcours de tableau.

Toujours dans la classe Vectorized, écrire la méthode minmax quiprend un tableau d'entier en paramètre et renvoie un tableau à deux élements le premier étant le minimum, le second étant le maximum.
Ajouter des tests unitaires en vérifiant bien que le cacul du minimum et du maximum de valeurs négatives est correcte.
Ajouter un test de performance et comparer avec la vitesse d'exécution de la méthode sumLanewise de l'exercice 1, que pouvez vous en conclure ?