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 2023

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, *iter1 = 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);
  _mm256_storeu_ps(iter0, dot0);
  v0 = _mm256_loadu_ps(iter0 + 8);
  v1 = _mm256_loadu_ps(iter1 + 8);
  dot1 = _mm256_fmadd_ps(v0, v1, dot1);
  _mm256_storeu_ps(iter1, 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

🎮 Jeu !

Corrigez le code suivant en utilisant les bons intrinsèques:

https://godbolt.org/z/M7xcs4xK3

#include <immintrin.h>
#include <cstdint>
void toy(uint16_t *ptr0, uint16_t *ptr1, uint16_t *end0) {
  for(uint16_t *iter0 = ptr0, *iter1 = ptr1;
      iter0 < end0;
      iter0 += 30, iter1 += 30)
  {
    __m256i v0 = _mm256_loadu_si256((__m256i*)iter0);
    __m256i v1 = _mm256_loadu_si256((__m256i*)iter1);
    __m256i adds = _mm256_add_epi16(v0, v1);
    _mm256_store_si256((__m256i*)iter0, adds);
  }
}

Commentez la sortie de l'outil llvm-mca sur cet exemple

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)
  dot0.store_aligned(&ptr0[i]);
  v0 = xs::load_aligned(&ptr0[i + simd_size]);
  v1 = xs::load_aligned(&ptr1[i + simd_size]);
  dot1 = xs::fma(v0, v1, dot1)
  dot1.store_aligned(&ptr0[i + simd_size]);
}

cf. xsimd ou MIPP

Instructions SIMD, Vues du C++

Avantages :

Inconvénients :

🎮 Jeu !

Comparez avec la sortie du code suivant :

https://godbolt.org/z/nWPd1nxM6

#include <xsimd/xsimd.hpp>
void toy(uint16_t *ptr0, uint16_t *ptr1, uint16_t *end0) {
  using b16_t = xsimd::batch<uint16_t>;
  for(uint16_t *iter0 = ptr0, *iter1 = ptr1;
      iter0 < end0;
      iter0 += b16_t::size, iter1 += b16_t::size)
  {
    auto v0 = b16_t::load_unaligned(iter0);
    auto v1 = b16_t::load_unaligned(iter1);
    auto adds = xsimd::sadd(v0, v1);
    adds.store_unaligned(iter0);
  }
}

Changez l'architecture cible et observez le résultat en terme de performance et de portabilité.

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

Instructions SIMD, Vues du Compilateur

Avantages :

Inconvénients :

🎮 Jeu !

Comparez la sortie de gcc et clang sur le code suivant :

https://godbolt.org/z/9eGbaGabv

#include <limits>
#include <cstdint>
void toy(uint16_t *ptr0, uint16_t *ptr1, uint16_t *end0) {
  for(uint16_t *iter0 = ptr0, *iter1 = ptr1 ;
      iter0 < end0;
      iter0 += 1, iter1 += 1)
  {
    uint32_t tmp = *iter0 + *iter1;
    if(tmp > std::numeric_limits<uint16_t>::max())
      tmp = std::numeric_limits<uint16_t>::max();
    *iter0 = tmp;
  }
}

Changez le niveau d'optimisation, l'architecture cible... et comparez la sortie de llvm-mca sur ces différents cas.

Classification des opérations (1)

D'après le manuel ARM /Neon

(...)

Classification des opérations (2)

(...)

🎮 Jeu !

Faites mieux que GCC sur le code suivant

https://godbolt.org/z/s8zP79K3T

#include <complex>
void toy(std::complex<float> *ptr0, std::complex<float> *ptr1) {
  ptr0[0] *= ptr1[0] + 2.f;
  ptr0[1] *= ptr1[1] + 2.f;
  ptr0[2] *= ptr1[2] + 2.f;
  ptr0[3] *= ptr1[3] + 2.f;
}

Astuces: -ffast-math, -O3, intrinsics, xsimd, lecture ... ?

Instructions SIMD : point-à-point

if-conversion perte de précision macro instructions permutations

Instructions SIMD, contraintes algorithmiques

On aime :

On aime moins :

🎮 Jeu !

Vectoriser le code dotprod.cpp en utilisant intrinsèques ou xsimd.

> clang -O2 dotprod.cpp -o dotprod -mavx2 -mfma
> ./dotprod 10000

🎮 Jeu !

Vectoriser le code vmprod.cpp en utilisant intrinsèques ou xsimd.

> clang -O2 vmprod.cpp -o vmprod -mavx2 -mfma
> ./vmprod 10000

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!!!
1