Tri Fusion avec vecteur SSE

1.1. Introduction

Le but de ce projet est de comparer deux implantations du tri fusion (merge sort) sur les entiers 32 bits :

• la première est une implantation classique
• la seconde utilise un tri de quatre entiers adjacents dans un registre vectoriel SSE

• Le premier tient au fait que le réordonnancement des quatre entiers sera réalisé par l'instruction PSHUFD qui n'admet qu'un paramètre constant.

  PSHUFD xmm0, xmm1/m128, imm8

  On fait le choix ici de modifier ce paramètre à la volée dans le code.
• Le second concerne la modification de l'instruction qui n'est pas possible directement dans le segment de code car celui-ci est protégé en écriture. On peut alors, soit mettre le code dans la section de données ou alors utiliser mprotect pour rendre le segment de code inscriptible. Nous testerons les deux possibilités.
• Enfin, afin de déterminer la valeur imm8 qui indique comment seront réordonnées les valeurs, il est nécessaire de trouver un moyen qui permet de manière unique de savoir comment faire. Nous calculerons donc une valeur servant d'identifiant, mais pour obtenir cette valeur de manière efficace il faut utiliser l'instruction PEXT qui fait partie du jeu d'instructions BMI (Bit Manipulation). Il y a deux jeux d'instructions (BMI1 et BMI2) introduits à partir de l'architecture Haswell (2013). Certains ordinateurs anciens ne comportent donc pas ce jeu d'instruction, il est donc nécessaire de remplacer PEXT par une série de AND/OR/SHR qui potentiellement ralentissent le traitement. Nous verrons si cela est confirmé.

1.2. Rappels sur le tri fusion (Merge Sort)

L'algorithme du tri-fusion est composé de deux phases :

• une phase de séparation (split) qui consiste à diviser le tableau à trier de $N$ éléments en deux sous tableaux de $N/2$ éléments de manière récursive
• une phase de fusion (merge) qui intervient quand on a atteint une taille de 1 (ou 2 éléments suivant les implantations) et qui consiste à réordonner les valeurs de deux sous tableaux triés pour n'en faire qu'un seul.

Voir le principe sur Wikipedia

Le principal avantage du tri fusion est qu'il possède une complexité en $N × log(N)$ mais l'étape de fusion nécessite la création d'un tableau temporaire comme le montre le code suivant :

Voici un ordre de grandeur sous Ryzen 1700X des temps d'éxécution de l'implantation pour différentes tailles de tableaux :

1.3. Tri Fusion modifié

1.3.1. Modification de l'algorithme

La modification de l'algorithme consiste

• à arrêter l'étape de split quand la taille du tableau est égale à 4. Le tri ne fonctionnera alors correctement que si la taille du tableau est multiple de 4.

  /**
   * Recursively split initial array t of size sz into two smaller arrays
   * until array size is equal to 4
   */
  void split_vec(int *t, int sz) {
  	if (sz == 4) {
  		asm_sse_sort(t);
  		return ;
  	}
  	// divide array t in its middle
  	int m = (sz / 2);
  	// split into two sub arrays
  	split_vec(t, m);
  	split_vec(t + m, sz - m);
  	// merge sub arrays
  	merge(t, sz, m);
  }

• à trier quatre entiers adjacents dans un vecteur SSE grâce à la fonction asm_sse_sort

Il faut donc trouver un moyen pour savoir comment les ordonner.

1.3.2. Comment ordonner les valeurs

Pour ordonner les valeurs on dispose de l'instruction PSHUFD mais celle-ci n'admet qu'un argument de type constante qui indique comment sélectionner les valeurs.

Comme indiqué préalablement on modifiera la constante de l'instruction à la volée.

		0x66, 0x0f, 0x70, 0xc0, 0xe0 ; pshufd xmm0,xmm0,0xe0

Pour trouver un identifiant unique lié à la réorganisation des valeurs, on va comparer 4 entiers adjacents à des réordonnancements de ces 4 valeurs comme sur l'exemple suivant, on compare le vecteur V1 à V2 et V3

• V1 est le vecteur initial (ici, il est déjà trié)
• V2 est un décalage à droite de V1 de 32 bits
• V3 est un décalage à droite de V2 de 32 bits

V1 (xmm0) =	1	2	3	4
V2 (xmm1) =	4	1	2	3
V3 (xmm2) =	3	4	1	2

Pour réaliser la comparaison, on s'appuiera sur l'instruction PCMPGTD (Compare Packed Signed Integers for Greater Than) qui permet de comparer deux registres SSE.

Dans l'exemple précédent, si on compare V1 à V2, puis V1 à V3, on obtient les résultats suivants mais on voudrait obtenir des valeurs comme dans la colonne de droite :

Cmp(V2,V1)	0xFFFFFFFF	0x00000000	0x00000000	0x00000000	= 1000_b = 8
Cmp(V3,V1)	0xFFFFFFFF	0xFFFFFFFF	0x00000000	0x00000000	= 1100_b = 12

Puis en fonction des deux valeurs obtenues sur 4 bits, on génère une valeur sur 8 bits :

C = 16 * Cmp(V2,V1) + Cmp(V3,V1) = 16 * 8 + 12 = 140

Ce qui permet pour chaque cas ( [1,2,3,4], [1,4,3,2], [1,2,2,3], ...) d'obtenir une valeur unique et de calculer la constante à utiliser pour PSHUFD.

Le problème est que pour récupérer le résultat de la comparaison on est contraint de passer par l'instruction PMOVMSKB (Move Byte Mask) :

PMOVMSKB appliqué aux comparaisons de V2 avec V1 et V3 avec V1 donne les résultats suivants et on désire récupérer les bits en rouge :

PMOVMSKB de Cmp(V2,V1)	0xF000	1111_0000_0000_0000_b
PMOVMSKB de Cmp(V3,V1)	0xFF00	1111_1111_0000_0000_b

Pour cela on dispose de l'instruction PEXT (Parallel Bits Extract) qui utilise le masque du troisième opérande afin de sélectionner les bits du second opérande et mettre le résultat dans le premier opérande :

PEXT r32a, r32b, r/m32

Dans notre cas, il suffira d'appliquer le masque 0x1111 sur le résultat de PMOVMSKB.

1.3.3. Modification du code à la volée

1.3.4. Le code principal

On charge le vecteur [4, 3, 2, 1], dans la suite les valeurs contenues dans les registres SSE sont affichées dans l'ordre inverse afin d'afficher la partie haute du registre SSE à gauche et la partie basse à droite :

Au final le réarrangement est 1B_h = 0001_1011_b

1.3.5. Permettre la modification de la section .text

1.3.6. remplacer PEXT par AND/SHR/OR

Comme indiqué dans l'introduction, certains processeurs ne disposent pas de l'instruction PEXT qui est relativement récente et date de 2013. On va donc la remplacer par une série de décalages et sélection de bits.

Ici eax est l'entrée et contient une valeur du type 000X.0000Y.000Z.000T_b et on veut obtenir XYZT_b. Le registre edx contient le masque de sélection 0001.0001.0001.0001_b = 1111_h :

; par exemple 
; eax = 1111.1110.1110.1111_b
; edx = 0001.0001.0001.0001_b
and    eax, edx   ;  eax = 0001.0000.0000.0001_b   application du masque
mov    ebx, eax   ;  ebx = 0001.0000.0000.0001_b   sauvegarde dans ebx de eax
shr    eax, 3     ;  eax =     00010.0000.0000_b   décalage vers la droite  
or     ebx, eax   ;  ebx = 0001.0010.0000.0001_b
shr    eax, 3     ;  eax =        00.0100.0000_b
or     ebx, eax   ;  ebx = 0001.0010.0100.0001_b
shr    eax, 3     ;  eax =           0000.1000_b
or     ebx, eax   ;  ebx = 0001.0010.0100.1001_b
and    ebx, 1111b ;  ebx = 0000.0000.0000.1001_b

On peut écrire la même chose en C :

z = ((z & 0x1000) >> 9) + ((z & 0x0100) >> 6) + ((z & 0x0010) >> 3) + (z & 1);

Par exemple GCC traduira le code précédent sous la forme suivante :

mov     ecx, DWORD [esp+4] ; ecx = z
mov     eax, ecx           ; eax = z
mov     edx, ecx           ; edx = z
shr     eax, 9             ; récupère les deux bits de poids fort
shr     edx, 6
and     eax, 8
and     edx, 4
or      edx, eax
mov     eax, ecx           ; récupère les deux bits de poids faible
and     ecx, 1
shr     eax, 3
and     eax, 2
or      ecx, eax
lea     eax, [edx+ecx]

1.3.7. Switch / Case of

Enfin, on peut se demander si utiliser un switch dégraderait ou améliorerait la performance de l'algorithme. Plutôt que de modifier la constante de PSHUFD, on va se diriger vers du code spécifique :

L'idée est d'utiliser une table avec les adresses du code à exécuter:

1.4. Résultats

Voici un tableau comparatif concernant quelques architectures :

Quelles remarques peut on faire ?

• L'implantation avec vecteur et switch est la plus efficace
• les deux autres implantations avec vecteur sont moins efficaces, cela peut être dû notamment à la modification de l'instruction PSHUFD
• modifier l'instruction PSHUFD dans la section .text semble un peu plus pénalisant que dans la section .data
• l'absence ou la présence de l'instruction PEXT ne semble pas pénaliser le code