:: Enseignements :: ESIPE :: E4INFO :: 2021-2022 :: Collections Concurrentes ::

Single instruction, Multiple Data (SIMD)

Vectorisation, Loop decomposition, Opérations binaires et Masks

Nous allons utiliser l'API jdk.incubator.vector intégrée au JDK 17.
Comme on va faire quelques tests de performance, je vous ai préparé un zip qui contient un projet Maven avec son POM, struct-conc-lab5.zip, et les fichiers de config pour Eclipse et IntelliJ déjà écrits.

Exercice 1 - Vectorized Add / Vectorized Min

Le but de cet exercice est de calculer la somme et le minimum d'un tableau de façon vectorisée (en utilisant des vecteurs de valeurs). Nous allons pour cela créer une classe fr.umlv.structconc.VectorComputation (dans src/main/java) qui contiendra les différentes méthodes statiques.
Les tests unitaires correspondant s'appellent fr.umlv.structconc.VectorComputationTest (dans src/test/java).
De plus, la classe fr.umlv.structconc.VectorComputationBenchMark (dans src/main/java) contient les tests de performance JMH pour vérifier que le code que vous avez écrit est bel et bien plus performant qu'une simple boucle sur les données du tableau.

On cherche à écrire une fonction sum qui calcule la somme des entiers d'un tableau passé en paramètre. Pour cela, nous allons utiliser l'API de vectorisation pour calculer la somme sur des vecteurs.
- Quelle est la classe qui représente des vecteurs d'entiers ?
- Qu'est ce qu'un VectorSpecies et quelle est la valeur de VectorSpecies que nous allons utiliser dans notre cas ?
- Comment créer un vecteur contenant des zéros et ayant un nombre préféré de lanes ?
- Comment calculer la taille de la boucle sur les vecteurs (loopBound) ?
- Comment faire la somme de deux vecteurs d'entiers ?
- Comment faire la somme de toutes les lanes d'un vecteur d'entiers ?
- Si la longueur du tableau n'est pas un multiple du nombre de lanes, on va utiliser une post-loop, quel doit être le code de la post-loop ?
Une fois que vous avez répondu à toutes ces questions, écrire le code de sum et vérifier que le test nommé "testSum" passe. De plus, vérifier avec les tests de performance dans VectorComputationBenchMark (dé-commenter les annotations correspondantes) que votre code est plus efficace qu'une simple boucle.
Rappel : pour lancer les tests JMH, il suffit d'exécuter java -jar target/benchmarks.jar dans un terminal (et arrêter tout les programmes qui tournent !).
On souhaite écrire une méthode sumMask qui évite d'utiliser une post-loop et utilise un mask à la place.
- Comment peut-on faire une addition de deux vecteurs avec un mask ?
- Comment faire pour créer un mask qui allume les bits entre i la variable de boucle et length la longueur du tableau ?
Écrire le code de la méthode sumMask et vérifier que le test "testSumMask" passe.
Que pouvez dire en terme de performance entre sum et sumMask en utilisant les tests de performances JMH ?
On souhaite maintenant écrire une méthode min qui calcule le minimum des valeurs d'un tableau en utilisant des vecteurs et une post-loop.
Contrairement à la somme qui a 0 comme élément nul, le minimum n'a pas d'élément nul... Quelle doit être la valeur utilisée pour initialiser de toute les lanes du vecteur avant la boucle principale ?
Écrire le code de la méthode min, vérifier que le test nommé "testMin" passe et vérifier avec les tests JMH que votre code est plus efficace qu'une simple boucle sur les valeurs du tableau.
On souhaite enfin écrire une méthode minMask qui au lieu d'utiliser une post-loop comme dans le code précédent, utilise un mask à la place.
Attention, le minimum n'a pas d’élément nul (non, toujours pas !), donc on ne peut pas laisser des zéros "traîner" dans les llanes lorsque l'on fait un minimum sur deux vecteurs.
Écrire le code de la méthode minMask et vérifier que le test nommé "testMinMask" passe.
Que pouvez-vous dire en termes de performance entre min et minMask en utilisant les tests de performances JMH ?

Exercice 2 - FizzBuzz

Le but de cet exercice est de tester les performances des vecteurs 128 bits et 256 bits en prenant comme prétexte le calcul de FizzBuzz.
Pour rappel, FizzBuzz est un programme qui consiste à écrire sur la sortie standard les nombres de 1 à 100 en remplaçant les nombres multiples de 3 par "Fizz", les multiples de 5 par "Buzz", les multiples de 15 par "FizzBuzz", sinon on affiche le nombre.
Pour résoudre le problème avec des vecteurs, on va le décomposer en deux parties. On va résoudre le problème en remplissant un tableau d'entiers avec -1 pour Fizz, -2 pour Buzz, -3 pour FizzBuzz ou le nombre à écrire, puis on utilisera le code suivant pour afficher les chaînes de caractères correspondantes
Arrays.stream(fizzBuzz(19)).mapToObj(i -> switch (i) { case -1 -> "Fizz"; case -2 -> "Buzz"; case -3 -> "FizzBuzz"; default -> "" + i; }).forEach(System.out::println);

On cherche a générer la suite d'entiers correspondants à FizzBuzz ; pour les premières valeurs, cela donne

    -3  1  2  -1  4  -2  -1  7  8  -1  -2  11  -1  13  14  -3  16  17 -1 19 -2 -1 22 23 -1 -2 26  -1 28 29 ...

On peut remarquer qu'une fois passées les 15 premières valeurs, la suite des valeurs négatives se répète (c'est normal avec le module 15).
Les mêmes valeurs, 15 par 15 cela donne

     -3  1  2  -1  4  -2  -1  7  8  -1  -2 11  -1 13 14
     -3 16 17  -1 19  -2  -1 22 23  -1  -2 26  -1 28 29
     -3 31 32  -1 34  -2  -1 37 38  -1  -2 41  -1 43 44 ...
     ...

On peut aussi remarquer que, pour les valeurs non négatives, on ajoute 15 d'une ligne à l'autre.
Avec ces deux informations (les valeurs négatives se répètent toutes les 15 valeurs et on ajoute 15 sur les valeurs positives toutes les 15 valeurs), on peut en déduire un algorithme vectorisé... si on suppose que l'on a des vecteurs de 15 valeurs :

     v =     [-3,  1,  2, -1,  4, -2, -1,  7,  8, -1, -2, 11, -1, 13, 14]
     delta = [ 0, 15, 15,  0, 15,  0,  0, 15, 15,  0,  0, 15,  0, 15, 15]
     boucle toute les 15 valeurs
       on stock v dans le tableau
       v = v + delta

En fait, les vecteurs de 15 valeurs n'existent pas... Dans la vrai vie, soit on a des vecteurs 128 bits, donc 4 int, soit des vecteurs 256 bits, donc 8 int (on peut avoir plus, mais c'est rare sur une machine de dev).
Donc il faut transformer un peu l'algorithme en utilisant plusieurs vecteurs, par exemple pour des vecteurs 128 bits, il faut 4 vecteurs pour stocker les 15 valeurs.
Et il faudra penser à ne pas écrire la dernière valeur dans le tableau des résultats, sinon on va écrire 16 valeurs au lieu de 15.

On souhaite écrire dans la classe FizzBuzz une méthode fizzBuzzVector128 qui prend en paramètre une longueur et renvoie un tableau d'entiers de taille longueur contenant les valeurs de FizzBuzz en utilisant des vecteurs 128 bits d'entiers.
Une fois la méthode écrite, vérifier que celle-ci passe le test.
En exécutant les tests JMH, que pouvez vous conclure en observant les différences de performance entre la version de base et la version utilisant l'API des vecteurs.
On souhaite maintenant écrie une méthode fizzBuzzVector256 qui utilise des vecteurs 256 bits.
Une fois la méthode écrite, vérifier que celle-ci passe le test.
Utiliser les tests JMH pour vérifier la performance de votre implantation. Que pouvez vous en conclure en comparaison de la version utilisant des vecteurs 128 bits.
Il existe une autre façon d'implanter algorithme, on peut ajouter 15 avec un mask ; en pseudo code, cela donne :
```
     v =     [-3,  1,  2, -1,  4, -2, -1,  7,  8, -1, -2, 11, -1, 13, 14]
     mask =  [F,   T,  T,  F,  T,  F,  F,  T,  T,  F,  F,  T,  F,  T,  T]
     boucle toute les 15 valeurs
       on stock v dans le tableau
       v = v + 15 with mask
    
```
, Écrire la méthode fizzBuzzVector128AddMask qui utilise des vecteurs 128 bits et l'addition avec un mask, puis vérifier avec le test que votre code fonctionne correctement.
Comparer les performances de ce nouvel algorithme par rapport votre autre implantation à base de vecteur 128 bits. Que pouvez-vous en conclure ?
Note : n'essayez pas de calculer le mask avec un Stream, les BooleanStream, ça n'existe pas !