Les types SIMD

L'API JavaScript expérimentale SIMD ajoute des objects vectoriels qui peuvent être manipulés avec des instructions SIMD/SSE sur les processeurs adaptés. SIMD est l'abréviation de Single Instruction/Multiple Data (ce qui correspond à « Unique instruction / Données Multiples ». Les opérations SIMD sont des méthodes qui permettent de traiter des ensembles de données avec une seule instruction. À l'inverse, les opérations scalaires (SISD) ne traitent qu'une seule donnée avec une seule instruction.

Traiter un ensemble de données avec une seule instruction peut apporter des gains de performances conséquents à votre application. Ces gains dépendront, entre autres, de la taille de l'ensemble de données, ou vecteur, qu'on peut manipuler. Pour cette raison, les opérations SIMD sont largement utilisées pour le graphisme en 3D, le traitement audio/vidéo, les simulations physiques, la cryptographie et d'autres domaines.

Un inconvénient de SIMD est que les algorithmes utilisés doivent avoir été conçus pour SIMD. Notamment, un vecteur de données devra être manipulé dans son ensemble alors qu'un algorithme classique pourra parfois avoir besoin de manipuler les composantes des vecteurs de différentes façon. Nous verrons, dans la suite de cet article, comment nous pouvons utiliser les masques et l'aligneemnt de données pour résoudre ce problème.

La mémoire partagée ou le parallélisme à base de threads permettent de paralléliser les traitements et d'appliquer de multiples instructions sur de multiples données (MIMD). La programmation parallèle peut ainsi être rendue plus simple grâce à ces techniques. Toutefois, ces concepts peuvent également être utilisés en combinaison avec SIMD. On peut, par exemple, utiliser une vectorisation SIMD dans chacun des threads du programme. Cette démonstration sur l'ensemble de Mandelbrot, créée par Peter Jensen (Intel), illustre les gains de performances obtenus en utilisant SIMD et les Web Workers.

SIMD et JavaScript

L'API JavaScript SIMD est composée de nouveaux types de donnée et d'opérations qui vous permettent d'utiliser des instructions SIMD en JavaScript. Les navigateurs fournissent des implémentations hautement optimisées de cette API en fonction du matériel présent sur l'ordinateur de l'utilisateur. À l'heure actuelle, l'API JS SIMD est notamment conçue pour les plates-formes ARMv7 avec NEON et x86 avec SSE.

Prenons par exemple le type de donnée SIMD SIMD.Float32x4. Un vecteur SIMD est composé de plusieurs unités de données, appelées « voies » ou « composantes ». Pour l'API actuelle, un registre SIMD est composé de 128 bits. Ainsi, pour un vecteur de 4 composantes (le x4 dans Float32x4), on peut placer une valeur de type Float32 dans chacune des voies, qu'on nommera x, y, z, et w. Avec ce vecteur, au lieu d'avoir à effecteur 4 opérations séparées sur chacune de ces voies, on pourra utiliser SIMD pour appliquer une opération simultanément sur les 4 voies.

Dans le schéma qui suit, on applique une unique instruction (ici une addition), les données peuvent donc être traitées avec SIMD :

 

Schéma 1 et 2 : Comparaison de SISD et SIMD.

Le code scalaire SSID pourrait ressembler à celui-ci (il ne contient pas de boucle et permet juste d'illustrer le concept sous-jacent) :

var a = [1, 2, 3, 4];
var b = [5, 6, 7, 8];
var c = [];

c[0] = a[0] + b[0];
c[1] = a[1] + b[1];
c[2] = a[2] + b[2];
c[3] = a[3] + b[3];
c; // Array[6, 8, 10, 12]

Avec SIMD, on aurait :

var a = SIMD.Float32x4(1, 2, 3, 4);
var b = SIMD.Float32x4(5, 6, 7, 8);
var c = SIMD.Float32x4.add(a,b); // Float32x4[6, 8, 10, 12]

Ce code permettra d'ajouter les valeurs des différentes voies de façon simultanée et produira un nouveau vecteur Float32x4 dont les valeurs des voies sont les résultats des additions.

Comme on peut le voir avec ces trois lignes de code SIMD, on dispose d'un ensemble de fonctions JavaScript qui permettent de créer des vecteurs et d'utiliser des instructions vectorielles (ici l'addition). Au moment où cet article est écrit, il n'existe pas de surcharge des opérateurs (par exemple, pouvoir utiliser le signe « + » à la place de cette méthode), ce qui simplifierait l'écriture de code SIMD et augmenterait sa lisibilité. Cependant, l'API JavaScript SIMD n'est pas encore finalisée et on prévoit d'ajouter la surcharge des opérateurs dans un des prochains brouillons. Le travail de spécification peut être suivi grâce au dépôt GitHub ecmascript_simd.

Réaligner des données pour utiliser des vecteurs SIMD

On aura, la plupart du temps, des tableaux qui serviront pour créer des vecteurs SIMD. Toutefois, la structure de ces tableaux peut ne pas toujours correspondre à une structure adaptée aux opérations SIMD. Prenons l'exemple des données pour représentes les couleurs en RGBA dans une image.

Grâce à la méthode CanvasRenderingContext2D.getImageData() d'un canvas et avec la propriété ImageData.data, on peut obtenir les données concernant chaque pixel dans un tableau unidimensionnel dont les éléments sont des valeurs dans l'ordre RGBA (rouge, vert, bleu, alpha) qui sont chacunes des entiers compris, au sens large, entre 0 et 255 :

[R, G, B, A, R, G, B, A, R, G, B, A, ...]

Si on souhaite traiter cette image, par exemple pour calculer les niveaux de gris avec la formule Y = 0.299r + 0.587g + 0.114b, il faudra réorganiser les données pour les manipuler avec SIMD. L'idée est d'avoir un vecteur pour chacune des composantes r, g, et b, ce qui permettra d'utiliser une instruction SIMD pour chaque couleur. Les vecteurs construits pourront ressembler à cela :

[R, R, R, R, R, R, ...] * 0.299 +
[G, G, G, G, G, G, ...] * 0.587 +
[B, B, B, B, B, B, ...] * 0.114 =
[Y, Y, Y, Y, Y, Y, ...]

Paralléliser des branches conditionnelles

Dans du code scalaires, les branches logiques basées sur des conditions sont utilisées pour contrôler le flux des instructions, par exemple :

var a = [1, 2, 3, 4];
var b = [5, 6, 7, 8];
var c = [];

for (var i = 0; i < 4; i++) {
  if (a[i] < 3) {
    c[i] = a[i] * b[i];
  } else {
    c[i] = b[i] + a[i];
  }
}

console.log(c); // [5, 12, 10, 12]

Or, on ne souhaite pas avoir à fabriquer des vecteurs SIMD pour chaque branche pour exécuter les instructions les unes à la suite des autres. Grâce aux masques de sélection, SIMD permet d'aboutir au même résultat plus efficacement.

Créer des branches, appliquer des masques, sélectionner

La méthode SIMD.%type%.select() sélectionne les voies d'un vecteur à partir d'un masque de sélection. Cela permet de créer des « branches » à partir desquelles on peut manipuler une partie d'un vecteur SIMD. Dans le schéma suivant, un masque de sélection est utilisé pour former un résultat à partir de deux vecteurs SIMD a et b :

Les masques booléen peuvent être créés avec les fonctions de comparaison. Il est également possible d'en créer un de toute pièce grâce aux types SIMD booléens.

En utilisant cette technique, on peut réécrire les branches conditionnelles scalaires de l'exemple précédent en utilisant la fonction select() et en exécutant la multiplication et l'addition en parallèle :

var a = SIMD.Float32x4(1, 2, 3, 4);
var b = SIMD.Float32x4(5, 6, 7, 8);

var mask = SIMD.Float32x4.lessThan(a, SIMD.Float32x4.splat(3));
// Bool32x4[true, true, false, false]

var result = SIMD.Float32x4.select(mask, 
                                   SIMD.Float32x4.mul(a, b),
                                   SIMD.Float32x4.add(a, b));

console.log(result); // Float32x4[5, 12, 10, 12]

Dans cette version SIMD de l'exemple précédent, on effectue les étapes suivantes :

1. On place les données dans des vecteurs SIMD.
2. Ensuite, pour créer une branche conditionnelle, on utilise la fonction SIMD.Float32x4.lessThan().
3. Cela renvoie un masque de sélection dont chaque voie contient des valeurs entières correspondant aux booléens true (-1) et false (0), basées sur le résultat de la comparaison. Le premier élément de comparaison est le vecteur a et le second élément de comparaison est créé grâce à la fonction splat. Cette fonction permet de créer un vecteur dont toutes les composantes sont fixées avec une valeur donnée (ici 3). Cela permet de réaliser une comparaison équivalent à la comparaison scalaire (a[i] < 3).
4. Pour obtenir le résultat, on applique un masque de sélection avec la fonction select. Celle-ci prend trois paramètres : 
   1. Le premier est le masque de sélection
   2. Le deuxième argument est le vecteur dont on prendra les composantes correspondantes aux composantes vraies du masque
   3. Le troisième argument est le vecteur dont on prendra les composantes correspondantes aux composantes fausses du masque.

D'autres algorithmes et cas d'utilisation pertinents pour SIMD

De façon générale, les données qui peuvent être manipulées de façon homogène avec les mêmes instructions tirent un grand bénéfice des opérations SIMD. Les algorithmes et cas d'utilisation suivant sont avantageusement traités avec SIMD :

• Convertir des données en un autre type
• Algorithmes : Somme des différences absolues, transformée en cosinus discrète
• Graphisme : Rastérisation, pixel shading, lancer de rayons.
• Mathématiques : Opérations matricielles, algèbre linéaire.

Statut d'implémentation pour SIMD en JavaScript

L'API SIMD est disponible dans les versions récentes de Firefox Nightly. Elle est disponible sur une version de test pour Microsoft Edge et il y a  « une intention d'implémentation » pour Blink/Chromium.

La spécification SIMD est en cours de développement et est proposée pour être incluse dans ECMAScript 2016 (ES7).

Une implémentation sous forme d'une prothèse d'implémentation (polyfill) basée sur les tableaux typés est disponible dans le dépôt GitHub ecmascript_simd.

Voir aussi

• Les pages de la référence sur SIMD qui listent l'ensemble des types et opérations SIMD.
• La programmation SIMD en JavaScript, une présentation (en anglais) par Peter Jensen, Intel.
• Animation du modèle de Mandelbrot utilisant SIMD, une démonstration (en anglais) par Peter Jensen, Intel.
• État des performances de SIMD.js dans Firefox, un billet de Benjamin Bouvier, Mozilla.