Site de Jean-Michel RICHER

Maître de Conférences en Informatique à l'Université d'Angers

Ce site est en cours de reconstruction certains liens peuvent ne pas fonctionner ou certaines images peuvent ne pas s'afficher.


6. TP 6
Produit Scalaire, suite et fin



6.1. Programme de test

Pour faire suite au TP 5, on désire écrire un programme bash (perf.sh) qui permet de tester le temps de calcul de chaque méthode et d'afficher un tableau de résultats :

# method; method name; checksum; mean time; stddev; minimum time; maximum time
01;        dp_ref; 31457277952.000; 11.7070; 0.135; 11.6451; 11.9481
02;        dp_fpu; 31457277952.000; 11.6475; 0.001; 11.6467; 11.6485
03;    dp_sse_low; 31457277952.000;  5.8734; 0.077;  5.8365;  6.0107
04;        dp_sse; 31457277952.000;  1.5640; 0.063;  1.5096;  1.6440
05; dp_sse_intrin; 31457277952.000;  1.0440; 0.041;  1.0221;  1.117
...

On affiche les colonnes suivantes pour un test exécuté 20_000 fois sur des vecteurs de 524_289 floats :

  • le numéro de la méthode sur 2 caractères
  • le nom de la méthode sur 13 caractères
  • une valeur de checksum qui correpond à la variable total du programme
  • le temps total d'exécution du programme (avec 4 chiffres après la virgule)
  • l'écart type (standard deviation en anglais)
  • le temps minimum obtenu pour 5 exécutions
  • le temps maximum obtenu pour 5 exécutions

Les paramètres des tests sont les suivants :

  • nombre de répétitions : -z 20000
  • longueur des vecteurs : -s 524289

On utilisera Hyperfine pour réaliser les tests.

hyperfine -r 5 --export-json tmp.json "taskset -c 0 \$binary -s 524289 -z 20000 -m \$method >tmp.txt" 2>/dev/null
  • on réalise 5 exécution du programme ou la variable binary contient l'exécutable
  • on exporte les résultats au format JSON dans le fichier tmp.json
  • on exécute le programme sur le coeur 0 du microprocesseur

Ce package peut être installé sous Ubunu par la commande :

richer@zentopia:\$sudo apt install hyperfine

6.2. Méthode utilisant les unités vectorielles SSE et dépliage par 2

Il est possible de continuer d'améliorer les fonctions grâce à du dépliage.

Ecrire la méthode dp_sse_ur2 qui réalise le calcul du produit scalaire en utilisant $4 × 32$ bits d'un vecteur SSE et en dépliant la boucle de calcul par 2.

Afficher le code    assembly/programs/dp_sse_vec_ur2.cpp
  1. /**
  2.  * Use of SSE vector units
  3.  * unroll loop by a factor of 2
  4.  */
  5. f32 dp_sse_vec(f32 *x, f32 *y, u32 size) {
  6.   // we use only one vector but twice
  7.     f32 v_sum[4];
  8.     v_sum[0] = v_sum[1] = v_sum[2] = v_sum[3] = 0.0;
  9.    
  10.    
  11.     u32 i;
  12.        
  13.     // loop unrolling by a factor of 2x4
  14.     for (i = 0; i < (size & ~7); i += 8) {
  15.         v_sum[0] += x[i + 0] * y[i + 0];
  16.         v_sum[1] += x[i + 1] * y[i + 1];
  17.         v_sum[2] += x[i + 2] * y[i + 2];
  18.         v_sum[3] += x[i + 3] * y[i + 3];
  19.        
  20.         v_sum[0] += x[i + 4] * y[i + 4];
  21.         v_sum[1] += x[i + 5] * y[i + 5];
  22.         v_sum[2] += x[i + 6] * y[i + 6];
  23.         v_sum[3] += x[i + 7] * y[i + 7];
  24.        
  25.     }
  26.    
  27.     // sum of partial sums
  28.     float sum = v_sum[0] + v_sum[1] + v_sum[2] + v_sum[3];
  29.    
  30.     // last iterations
  31.     while (i < size) {
  32.       sum += x[i] * y[i];
  33.       ++i;
  34.     }
  35.    
  36.     return sum;
  37. }
  38.  

6.3. Méthode utilisant les unités vectorielles SSE et dépliage par 2 sans dépendance

Ecrire la méthode dp_sse_ur2_nodep qui réalise le calcul du produit scalaire en utilisant $4 × 32$ bits d'un vecteur SSE et en dépliant la boucle de calcul par 2 et en utilisant des registres vectoriels différents (indépendants) pour chaque partie du dépliage.

Afficher le code    assembly/programs/dp_sse_vec_ur2_nodep.cpp
  1. /**
  2.  * Use of SSE vector units
  3.  * unroll by a factor of 2
  4.  * perform independant calculations
  5.  */
  6. f32 dp_sse_vec(f32 *x, f32 *y, u32 size) {
  7.     u32 i;
  8.    
  9.     // for independant calculcations we use two vectors
  10.     // for example xmm0 for v_sum and xmm2 for w_sum
  11.     f32 v_sum[4], w_w_sum[4];
  12.    
  13.     v_sum[0] = v_sum[1] = v_sum[2] = v_sum[3] = 0.0;
  14.     w_sum[0] = w_sum[1] = w_sum[2] = w_sum[3] = 0.0;
  15.    
  16.     // loop unrolling by a factor of 2x4
  17.     // for example
  18.     // we load x[i:i+3] in xmm1 and x[i+4:i+7] in xmm3
  19.     for (i = 0; i < (size & ~7); i += 8) {
  20.         v_sum[0] += x[i + 0] * y[i + 0];
  21.         v_sum[1] += x[i + 1] * y[i + 1];
  22.         v_sum[2] += x[i + 2] * y[i + 2];
  23.         v_sum[3] += x[i + 3] * y[i + 3];
  24.        
  25.         w_sum[0] += x[i + 4] * y[i + 4];
  26.         w_sum[1] += x[i + 5] * y[i + 5];
  27.         w_sum[2] += x[i + 6] * y[i + 6];
  28.         w_sum[3] += x[i + 7] * y[i + 7];
  29.        
  30.     }
  31.    
  32.     // partial sums of both vectors
  33.     float v_sum_total = v_sum[0] + v_sum[1] + v_sum[2] + v_sum[3];
  34.     float w_sum_total = w_sum[0] + w_sum[1] + w_sum[2] + w_sum[3];
  35.    
  36.     float sum = v_sum_total + w_sum_total;
  37.    
  38.     // last iterations
  39.     while (i < size) {
  40.       sum += x[i] * y[i];
  41.       ++i;
  42.     }
  43.    
  44.     return sum;
  45. }
  46.  

6.4. Méthode utilisant les unités vectorielles AVX et dépliage par 2 sans dépendance

Ecrire la méthode dp_avx_ur2_nodep qui réalise le calcul du produit scalaire en utilisant $8 × 32$ bits d'un vecteur AVX et en dépliant la boucle de calcul par 2 et en utilisant des registres vectoriels différents (indépendants) pour chaque partie du dépliage.

Afficher le code    assembly/programs/dp_avx_vec_ur2_nodep.cpp
  1. /**
  2.  * Use of AVX vector units
  3.  * unroll by a factor of 2
  4.  * perform independant calculations
  5.  */
  6. f32 dp_avx_vec(f32 *x, f32 *y, u32 size) {
  7.    // use ymm0 to store v_sum and ymm2 for w_sum
  8.    f32 v_sum[8], w_sum[8];
  9.     u32 i;
  10.    
  11.     // use xorps ymm0, ymm0
  12.     v_sum[0] = v_sum[1] = v_sum[2] = v_sum[3] = 0.0;
  13.     v_sum[4] = v_sum[5] = v_sum[6] = v_sum[7] = 0.0;
  14.    
  15.     // use xorps ymm2, ymm2
  16.     w_sum[0] = w_sum[1] = w_sum[2] = w_sum[3] = 0.0;
  17.     w_sum[4] = w_sum[5] = w_sum[6] = w_sum[7] = 0.0;
  18.    
  19.    
  20.     // loop unrolling by a factor of 16
  21.     // use ymm1 to store x[i:i+7] and ymm3 to store y[i+8:i+15]
  22.     for (i = 0; i < (size & ~15); i += 16) {
  23.         v_sum[0] += x[i + 0] * y[i + 0];
  24.         v_sum[1] += x[i + 1] * y[i + 1];
  25.         v_sum[2] += x[i + 2] * y[i + 2];
  26.         v_sum[3] += x[i + 3] * y[i + 3];
  27.         v_sum[4] += x[i + 4] * y[i + 4];
  28.         v_sum[5] += x[i + 5] * y[i + 5];
  29.         v_sum[6] += x[i + 6] * y[i + 6];
  30.         v_sum[7] += x[i + 7] * y[i + 7];
  31.        
  32.         w_sum[0] += x[i + 8]  * y[i + 8];
  33.         w_sum[1] += x[i + 9]  * y[i + 9];
  34.         w_sum[2] += x[i + 10] * y[i + 10];
  35.         w_sum[3] += x[i + 11] * y[i + 11];
  36.         w_sum[4] += x[i + 12] * y[i + 12];
  37.         w_sum[5] += x[i + 13] * y[i + 13];
  38.         w_sum[6] += x[i + 14] * y[i + 14];
  39.         w_sum[7] += x[i + 15] * y[i + 15];
  40.        
  41.     }
  42.    
  43.     // sum of partial sums
  44.     float v_sum_total = v_sum[0] + v_sum[1] + v_sum[2] + v_sum[3] +;
  45.       v_sum[4] + v_sum[5] + v_sum[6] + v_sum[7];
  46.     float w_sum_total = w_sum[0] + w_sum[1] + w_sum[2] + w_sum[3] +;
  47.       w_sum[4] + w_sum[5] + w_sum[6] + w_sum[7];
  48.      
  49.     float sum = v_sum_total + w_sum_total; 
  50.    
  51.     // last iterations 
  52.     while (i < size) {
  53.       sum += x[i] * y[i];
  54.       ++i;
  55.     }
  56.    
  57.     return sum;
  58. }
  59.  

6.5. Méthode utilisant les unités vectorielles AVX, le dépliage par 2 sans dépendance et le FMA

Ecrire la méthode dp_avx_fma_ur2_nodep qui réalise le calcul du produit scalaire en utilisant $8 × 32$ bits d'un vecteur AVX, en dépliant la boucle de calcul par 2 et en utilisant des registres vectoriels différents (indépendants) pour chaque partie du dépliage. Le calcul utilisera l'instruction suivante FMA (Fuse Multiply Add):

  • vfmadd231ps ymm0, ymm1, ymm2 qui additionne au registre ymm0 le produit de ymm1 par ymm2

6.6. Résultats

Voici quelques résultats obtenus sur différentes architectures en utilisant g++-10 et les drapeaux de compilation -O3 -mavx2 -ftree-vectorize -funroll-loops -march=native :

Attention sur AMD si vous utilisez l'option -std=c++11, il faut rajouter l'option -ffast-math.

 Méthode   i5-7400
3.00/3.50 GHz 		  i3-6100   Ryzen 7 1700X   Ryzen 5 3600
3.60 GHz 		  Ryzen 5 5600g 
 dp_ref   4.54   4.51   6.80   6.26   7.69 
 dp_fpu   6.08   5.96   6.82   6.25   7.86 
 dp_sse_low   6.08   5.94   4.08   3.75   3.56 
 dp_sse   1.56   1.76   1.03   0.94   0.90 
 dp_avx   0.87   1.28   0.57   0.49   0.45 
 dp_avx_ur2_no_dep   0.80   1.33   0.51   0.41   0.40 
 dp_avx_fma_ur2_no_dep   0.81   1.21   0.50   0.42   0.37 
 dp_intrin_avx   0.83   1.16   0.87    0.49   0.46 
 ratio sse_low / sse   3.89   3.37   3.96    3.98   3.95 
 ratio sse / avx   1.79   1.37   1.80   1.91   2.00 
Résultats pour 10.000 répétitions de la boucle sur des vecteurs de 524.288 floats

Note : on obtient parfois un problème d'affichage du temps d'exécution, notamment des décimales sur certaines configurations. Cela est dû à la localisation et le fait que les francophones utilisent la virgule pour introduire la partie décimale d'un nombre réel alors que les anglosaxons utilisent le point. Il est alors nécessaire d'utiliser la commande :

LANG=en_US ./perf.sh

6.6.1. Analyse des résultats

On note que pour les processeurs Intel, utiliser la FPU ou la partie basse des registres SSE donne les mêmes résultats. Il se pourrait donc que les mêmes circuits soient utilisés dans les deux cas ou qu'ils aient été conçus de la même manière.

Au contraire, pour AMD, les circuits FPU sont beaucoup plus lents que les registres SSE.

Pour certains processeurs, l'utilisation de l'AVX apporte un gain de presque deux (on va deux fois plus vite) par rapport au SSE. Sauf pour l'Intel i3-6100.