Zada, Hedron Grinder

Data Level Parallelism

Comment fait Ducobu pour faire plus vite ses punitions ?

Il utilise le fameux « crayon multi-ligne » !

Et bien il fait du SIMD :-)

N.B. : marche aussi avec un pinceau et un mur…

Illustration

X   |  [ x_0 | x_1 | x_2 | x_3 ]
+   |     +     +     +     +
X   |  [ y_0 | y_1 | y_2 | y_3 ]
=   |     =     =     =     =
Z   |  [ z_0 | z_1 | z_2 | z_3 ]

Single Instruction Multiple Data

Les processeurs classiques travaillent sur des scalaires. Les processeurs vectoriels travaillent sur des vecteurs:

Le temps d'exécution d'une opération sur un scalaire ou un vecteur est du même ordre de grandeur.

Il faut pouvoir transférer (charger ou décharger) les données depuis la mémoire vive vers les registres vectoriels.

Historique (dangerous)

le Cray-1 (né en 1975, 1m96...)

exemple d'architecture: les coeurs de XeonPhi

Ce que l'on trouve dans une documentation Intel sur le Xeon Phi

exemple d'architecture: les coeurs de XeonPhi

Et quand on creuse (pas trop profond dans le silicium) encore chez Intel

Les instructions vectorielles ont une latence supérieure à celle des instructions scalaires mais le même débit d'instruction!

Merci le pipeline !

Il y a un accès partagé au cache L1 et L2: attention aux interférences!

Merci le pipeline !

Merci le pipeline !

Merci le pipeline !

La fameuse Vector unit:

Contrat Matériel

Les architectures matérielles offrent de la performance MAIS à condition de respecter des contraintes de bon fonctionnement de ce matériel:

Dans votre ThinkPad / Lenovo / Asus

$ grep flags /proc/cpuinfo
flags    : ... mmx ... sse4_1 sse4_2 ... avx avx2 ...

Dans votre carte de Gamer

Assassin's creed VALHALLA - PC Specs

        Minimum     Recommended     High        Enthusiast      Ultra
GPU     GTX960      GTX1060         GTX1080     RTX2080S        RTX2080

Source: Ubisoft

Dans les centres de calcul

https://www.top500.org/, November 2020

Fujitsu uses 512bit vector lane, with scalable vector extension Volta architecture has 5120 CUDA cores and 640 Tensore cores

Instructions SIMD, Vues du C

Les intrinsèques supportés par la majorités des compilateurs, par famille de jeu d'instruction

#include <immintrin.h>

for(float *iter0 = ptr0, *iter2 = ptr1 ; iter0 < end0; iter0 += 16, iter1 += 16)
{
  __m256 v0 = _mm256_loadu_ps(iter0);
  __m256 v1 = _mm256_loadu_ps(iter1);
  dot0 = _mm256_fmadd_ps(v0, v1, dot0);
  v0 = _mm256_loadu_ps(iter0 + 8);
  v1 = _mm256_loadu_ps(iter1 + 8);
  dot1 = _mm256_fmadd_ps(v0, v1, dot1);
}

Instructions SIMD, Vues du C

Avantages :

Inconvénients :

Bible Intel sur le sujet: https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html

Instructions SIMD, Vues du C++

Bibliothèque de portabilité, basées sur les intrinsèques et la méta-programation

for(size_t i = 0; i < vec_size; i += 2 * simd_size)
{
  auto v0 = xs::load_aligned(&ptr0[i]);
  auto v1 = xs::load_aligned(&ptr1[i]);
  dot0 = xs::fma(v0, v1, dot0)
  v0 = xs::load_aligned(&ptr0[i + simd_size]);
  v1 = xs::load_aligned(&ptr1[i + simd_size]);
  dot1 = xs::fma(v0, v1, dot1)
}

cf. xsimd ou MIPP

Instructions SIMD, Vues du C++

Avantages :

Inconvénients :

Instructions SIMD, Vues de d'OpenMP

Annotation de code pour la vectorisation automatique de boucles

  interface
    real function func(x)
      !$OMP DECLARE SIMD (func)
      real, intent(in) :: x
    end function func
  end interface

  vec_sum = 0.
! !$OMP SIMD reduction(+:vec_sum)
  do i = 1,nx
     vec_sum = vec_sum + func(x(i))
  enddo

Compatible C, C++ et Fortran

Instructions SIMD, Vues de d'OpenMP

Avantages :

Inconvénients :

Instructions SIMD, Vues du Compilateur

ICC, Gcc, clang possèdent chacun des passes de vectorisation automatique. Il est alors nécessaire de préciser l'architecture ciblée :

cf. -ftree-vectorize (gcc) -fvectorize clang, activés à -O2 ou -O3 suivant les compilos

Jouons

https://godbolt.org/

double dprod(double const* x, double const* y, unsigned n)
{
  double s = 0;
  for (unsigned i = 0; i < n; ++i)
    s += x[i] * y[i]
  return s;
}

Essayez de vectoriser ça, en jouant avec -O2, -O3, -march=..., -ffast-math ou des optimisations manuelles… Que font ces options ?

Instructions SIMD, Vues du Compilateur

Avantages :

Inconvénients :

Instructions SIMD, contraintes algorithmiques

On aime :

On aime moins :

Instructions SIMD, contraintes matérielles

Pour pleinement tirer parties des instructions SIMD, il est bon de

SIMD vous fait rêver, mais réveillez-vous

Dans la vraie vie d'un code, il y a

Aidons les outils

Mieux vaut

  1. écrire un code bien compréhensible par le compilateur que de finir le code à l'assembleur ou aux intrinsics (AVX-512 = environ 4000 instructions! Bon courage ;) ),
  2. savoir utiliser les bonnes bibiliothèques optimisées et coder des boucles "vectorisables":
    • avec des profondeurs de boucles connues (pas de break, bof bof le while, attention aux tests "if" en cours de boucle),
    • limitant les appels de fonctions (que du basique, passable en inline, issues de librairies "classiques"),
    • avec des itérations indépendantes!!!

Jouons un peu

#include <stdio.h>
#include <math.h>
#define ARRAY_SIZE 1024
#define NUMBER_OF_TRIALS 100000
/* On va declarer des tableaux en statique pour essayer de jouer simplement avec les caches */
static double in1[ARRAY_SIZE], in2[ARRAY_SIZE], in3[ARRAY_SIZE], acc[ARRAY_SIZE], res;
static unsigned int index[ARRAY_SIZE];
void main(int argc, char *argv[]) {
  int i, t;
  double coeff=log(2);
  /* des tableaux de donnees arbitraires */
  for (i=0; i < ARRAY_SIZE; i++) {
    in1[i] = i*1.0e-9; in2[i] = i*0.5e-9;
    index[i] = (2*i+5)%ARRAY_SIZE;
  }
  /* Plein de runs de la boucle a vectoriser */
  for (t=0; t < NUMBER_OF_TRIALS; t++) {
    for (i=0; i < ARRAY_SIZE; i++) {
      acc[i] += coeff*in1[i] + in2[i]; /* MACC de base */
      /* variante de traitement a tester */
      // acc[i] = acc[i-1] + coeff*in1[i] + in2[i];
      /* variante de traitement a tester */
      //acc[i] += coeff*in1[i] + in2[index[i]];
      /* variante de traitement a tester */
      //acc[i%2] += coeff*in1[i%3] + in2[i];
      /* variante de traitement a tester */
      //acc[i%2] += coeff*in1[i] + log(in2[i]);

    }
  }
  /* Une sortie pour eviter la suppression d'operations jugees inutiles par le compilateur */
  for (i=0; i < ARRAY_SIZE; i++) res += acc[i];
  printf("%f\n",res);
}

Compilons - testons - concluons

$ gcc -O2 test.c -o test -lm
$ time ./test
$ gcc -O3 -march=native test.c -o test -fopt-info-vec -fopt-info-vec-missed -lm -fno-tree-vectorize
$ time ./test
$ gcc -O3 -march=native test.c -o test -fopt-info-vec -fopt-info-vec-missed -lm
$ time ./test

Inspectons

$ perf record ./test
$ perf report

$ objdump -S ./test

Comment s'en sort clang ?

1