Chapitre 74 : Assembleur ARM 64 : tri d’octets avec les instructions SIMD

J’ai donc persisté pour écrire des routines avec les instructions SIMD pour tenter de voir toutes les possibilités. En regardant sur internet, j’ai vu qu’il y avait possibilité d’écrire un tri fusion en utilisant des instructions de ce type.

Alors allons y et commençons par écrire une routine qui trie 4 octets contenus dans un registre. Dans le programme rechtri4SIMD.s la routine tri4octets prend en entrée dans le registre x0, les 4 valeurs à trier.

Le principe de ce tri est de partir de 2 octets triés puis de les fusionner pour arriver à 4 octets triés.

Appelons ces 4 octets a,b,c,d et nous allons les découper en 2 parties a,b et c,d que nous allons comparer.

Pour cela nous mettons la valeur de x0 dans le registre vecteur s0 que nous découpons par tranche de 2 octets avec les instructions mov v1.h[0],v0.h[1] et mov v2.h[0],v0.h[0]. Nous nous retrouvons avec les valeurs a,b dans le registre v1 et c,d dans le registre v2.

La comparaison des 2 registres s’effectue par cmgt v3.8b,v1.8b,v2.8b (gt pour greather : plus grand) et le registre v3 contiendra pour chaque octet comparé la valeur FF si plus grand et 00 si plus petit.

Suivant le résultat, il faut inverser les 2 valeurs des 2 registres pour avoir les valeurs les plus petites dans un registre et les plus grandes dans l’autre. C’est le rôle des instructions :

    mov v4.8b, v1.8b

    mov v5.8b, v2.8b

    bit v4.8b,v2.8b,v3.8b     // échange en fonction du résultat

    bit v5.8b,v1.8b,v3.8b 

qui échangent dans les registres v4 et v5 les valeurs de v1 et v2 en fonction du résultat contenus dans v3.

Donc maintenant nous avons a<c et b<d, et nous allons fusionner ces 2 petites listes triées en comparant a,c et b,d (pour la théorie voir les livres ou article des algorithmes de tri-fusion parallèles). Nous devons mettre les bons octets de v4 et V5 à la bonne place dans v1 et v2. Nous recomposons d’abord la séquence complète a c b d dans le registre v0 avec l’instruction zip et nous le redécoupons comme précédemment dans v1 et v2. Nous effectuons à nouveau la comparaison et inversons les valeurs comme précédemment.

Il faut effectuer une dernière comparaison pour comparer b et c et donc il nous faut mettre les valeurs a et b dans le registre v1 et d et c dans le registre v2. Pour cela nous utilisons les instructions de déplacement d’un octet    mov v2.b[0],v5.b[1] et mov v2.b[1],v5.b[0].

Après cette comparaison, nous remettons les 4 octets triés dans le bon ordre dans le registre v0  puis dans le registre x0 pour le retour vers le programme appelant.

Ce tri fonctionne donc avec 3 comparaison seulement mais il faut quand même beaucoup d’instructions de déplacement.

Dans le programme suivant rechtri4SIMD1.s, nous allons voir quelques points d’amélioration puis nous adapterons la routine pour trier 4 octets se trouvant dans la mémoire.

Nous pouvons améliorer les inversions après comparaisons en utilisant l’instruction bsl (bits select) mais je n’ai rien trouvé de mieux pour la découpe.

Pour la recomposition finale, j’utilise l’instruction tbl qui à partir d’un vecteur guide permet de reconstituer les données en combinant celles de 2 vecteurs. Attention, je me suis fait piéger et j’ai cherché un moment la cause d’un dysfonctionnement. En effet l’accès aux octets du deuxième registre se fait avec des index supérieurs à 15 et la valeur doit être en hexa si la définition des données est en hexa. Ne pas mettre 16 et 17 par exemple pour accéder aux 2 premiers octets du 2 ième registre mais 10 et 11 !!! Attention il faut aussi que les 2 registres origines se suivent (v3 puis v4).

La routine tri4OctetsMem attend en entrée dans x0 l’adresse mémoire de 4 octets à trier et dans X1 l’adresse en mémoire de stockage du résultat. La routine de tri est identique à celle précédente mais il a fallu modifier l’ordre de recomposition finale pour avoir en mémoire l’ordre correct. Le registre x0 retourne aussi les octets triés.

Cette routine est-elle plus performante qu’un tri classique ? Je n’ai pas fait de tests pour l’instant car son application pratique est nulle !!!

Maintenant, que nous vu les principes sur 4 octets, nous allons voir le tri de 8 octets puis celui de 16 octets.

Pour le tri de 8 octets, il faut effectuer 6 comparaisons dans le programme rechtri8SIMD.s : tout d’abord nous coupons les 8 valeurs en 2 vecteurs de 4 octets que nous comparons pour obtenir 4 listes de 2 valeurs triées. Puis nous les fusionnons pour obtenir 2 listes de 4 valeurs triées et que nous fusionnons pour obtenir 1 liste des 8 octets triés.  Pour les inversions, j’ai repris la première méthode vue pour les 4 octets et pour les éclatements, j’ai laissé les instructions de déplacement octet par octet. Il est donc possible de gagner quelques instructions avec les méthodes vues dans le 2^ième programme de tri de 4 octets.

Pour le tri de 16 octets, il faut effectuer 10 comparaisons dans le programme rechtri16SIMD.s . Nous reprenons la même logique que les autres programmes en utilisant au maximum l’instruction tbl pour réorganiser les données après chaque inversion.

Comme exercice, je vous laisse le soin de trier des données en mémoire en passant à la routine les adresses à lire et à écrire. Je vous laisse aussi réfléchir à la façon de trier des listes de dizaines d’octets avec cette routine !!!!

Moi je m’arreterai là car ces routines ont peu d’intérêt pratique. En effet on ne peut trier que des clés de 8 bits et il faut ajouter des instructions pour mouvementer les articles associés aux clés car un tri ne concerne pas que des clés !!!

Pour aller au delà des clés de 8 bits, on peut utiliser des instructions concernant 16 bits (v0 .4h) mais les comparaisons vont s’effectuer sur 4 clés au lieu de 8 et donc un gain plus limité.