Chapitre 91: assembleur ARM 64 bits : tests de différents tris fusion

 

J’avais besoin d’un tri stable et qui reste assez rapide car le tri par insertion est stable mais pas très performant. J’ai donc recherché d’autres tris stables et j’ai donc testé plusieurs exemples de tri fusion.

Le premier algorithme est issu du site rosetta code et je l’ai intégré dans un programme qui génère une table de nombres aléatoires, qui effectue les mesures de performance comme vues au chapitre 87, ce qui permet la comparaison de plusieurs tris.

Dans le programme testMergeTri64.s, nous trouvons la génération de la table, sa copie, l’appel aux mesures et l’appel à chaque tri. Le premier tri est un tri shell qui servira de comparaison. Le deuxième est le tri de rosetta code.

Voici les résultats pour trier 1000 valeurs numériques :

Tri shell

instructions: 178676 Cycles: 195663 temps en µs: 365573 temps1: 358906

tri merge

instructions: 2074928 Cycles: 2150297 temps en µs: 3740209 temps1: 3738177

Ce dernier tri n’est donc pas du tout performant. Je recherche donc d’autres algorithme dont celui de Robert Sedgewick en langage C que j’adapte à l’assembleur :

Nouveau tri merge :

instructions: 257280 Cycles: 313895 temps en µs: 612135 temps1: 609896

ce qui est mieux !! mais attention ce tri utilise une table annexe ce qui peut poser un problème de place.

J’améliore ce tri en effectuant les opérations de manière itérative :

instructions: 214244 Cycles: 253779 temps en µs: 456458 temps1: 451771

Puis il me vient l’idée d’effectuer le premier passage qui compare 2 valeurs successives sans utiliser le stockage dans la table intermédiaire puisque dans ce cas il suffit de stocker les 2 valeurs à intervertir dans seulement 2 registres :

instructions: 179335 Cycles: 230524 temps en µs: 405052 temps1: 401042

Voyons pour 100000 valeurs

tri shell :

instructions: 37658720 Cycles: 42019684 temps en µs: 73245522 temps1: 73231616

tri merge 1

instructions: 20051919690 Cycles: 20112824889 temps en µs: 30899260563 temps1: 30899177076

C’est énorme

tri merge

instructions: 40135342 Cycles: 46668064 temps en µs: 83594376 temps1: 83597240

tri merge itératif :

instructions: 35420192 Cycles: 44364228 temps en µs: 77672919 temps1: 77622968

autre tri merge itératif :

instructions: 31226666 Cycles: 41760383 temps en µs: 72490157 temps1: 72477969

La différence est nette pour ce dernier tri.

Avec ces derniers tests itératifs, il est possible d’utiliser la pile pour stocker la table intermédiaire.

Maintenant il faut vérifier la stabilité de ces tris (sauf le shell qui n’est pas stable). Pour cela dans le programme testMergeTri64Multi.s je crée une structure avec 2 zones dont une est alphanumérique pour tester le tri sur zone alpha.

J’adapte les tris pour effectuer les comparaisons suivant le choix alpha ou numérique.

L’affichage du début de la table triée pour chaque tri montre la même séquence pour les 3 tris fusion et un écart pour le tri shell. Ce qui semble être bon.

J’ai refait un test sur un programme légèrement modifié : au lieu de générer des valeurs numériques aléatoires, je stocke directement le compteur. Ensuite en triant sur les chaînes, il suffit de vérifier que l’ordre des valeurs numériques est croissant pour les chaînes identiques.

Évidemment les temps sont supérieurs à ceux du premier programme ce qui est normal puisque la comparaison s’effectue sur des chaînes de plusieurs caractères.

Chapitre 90 : assembleur ARM 32 bits : affichage des nombres en virgule flottante : algorithme grisu et grisu 2

 

Suite à l’écriture de la routine d’affichage pour l’assembleur 64 bits, je me suis penché à nouveau sur la routine pour le 32 bits que j’avais écrit au chapitre 11 au tout début de ma découverte de l’assembleur ARM. Bon c’est pas très joli joli : la routine est fausse et les résultats ne sont pas très bons. Je suis donc repartit du document pdf de Florian Loitsch (voir : https://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf ) et de la transposition en 64 bits que j’ai faite au chapitre 88 pour essayer de réécrire ces algorithmes pour le 32 bits.

Dans le programme convertFloat32.s, j’ai donc transposé l’algorithme grisu. Cela pose quelques difficultés car les nombres en virgule flottante traités sont en double précision et donc nécessitent une zone de 64 bits pour stocker la mantisse et les opérations doivent donc s’effectuer avec 2 registres . L’exposant lui peut être stocké sur 32 bits. De plus en 32 bits, le nombre de registres est limité (13) et donc il faut jongler avec pour arriver à tout calculer.

Dans ce premier programme, je reprends la trame de l’algorithme : conversion du nombre contenu dans le registre d0, normalisation, calcul du coefficient K pour accéder à la table des puissances de 10.

A ce propos, en découvrant sur github, cette méthode écrite pour d’autres langages (C,c++, java), j’ai constaté une différence entre les valeurs de ma table et celles publiées pour les mêmes puissance de 10. Je pense que mes valeurs sont calculées avec une moindre précision que les valeurs publiées.

La multiplication de 2 nombres codés suivant la structure proposée m’a posé quelques difficultés surtout dans le report des retenues.

J’ai gardé le découpage du résultat en 3 zones comme proposé mais l’affichage n’est pas satisfaisant : en utilisant la routine de conversion habituelle y a affichage de caractères blancs avant les chiffres du résultat.

Le résultat affiché est juste jusqu’à 17 chiffres et les valeurs suivantes sont fausses.

Dans le deuxième programme convertFloat32G2V2.s, je programme l’algorithme grisu 2 avec une table réduite par pas de 8 et une table reconstituée à partir d’une trouvée sur Internet.

Les principales difficultés sont de bien gérer les déplacements gauche et droite de bits sur 2 registres 32 bits. Dans la sous routine genererChiffres, pour pouvoir effectuer les calculs sans avoir à sauvegarder des valeurs en mémoire, je stocke certains registres dans les registres s0,s1,s2,et s3 . On gagne pas grand-chose car pour une routine utilisable par d’autres programmes et pour éviter tout problème, il faut sauvegarder quand même ces registres en début de routine et les restaurer en fin.

Pour le formatage, du résultat final, j’ai fait assez simple soit l’exposant est à zéro et j’affiche tous les chiffres disponibles et si l’exposant est différent de zéro, j’affiche le résultat sous la forme nombreEexposant. Il est donc possible d’améliorer cet affichage pour produire d’autres formats.

La routine donne des résultats satisfaisant avec toujours au maximum 17 chiffres significatifs. Reste à savoir si elle est toujours exacte !!!!

Chapitre 89 : Assembleur ARM 64 : routine calcul inverse racine carrée rapide pour des nombres en virgule flottante

 

En recherchant des algorithmes pour le chapitre précédent, je suis tombé sur une routine pour calculer la racine carrée inverse d’un nombre.Elle va nous permettre de tester la conversion de la routine grisu2 précédente en module.

Pour cela j’ai supprimé tout ce qui était inutile dans le programme grisu2NV2_64.s et je l’ai renommé routConvFloat64.s. J’ai ensuite compilé ce programme pour créer un objet.

Ensuite dans le programme calculinvRac, j’ai écrit la routine de calcul telle qu’elle est exposée dans Wikipedia et je l’ai compilé puis linké avec l’objet précédent.

Voici le résultat pour le nombre donnée en exemple dans Wikipedia :

2.529810967007374 (la valeur exacte est 2,52982)

et pour 4 :

0.4999978544248724 (la valeur exacte est 0,5

Il n’est donc plus nécessaire de faire appel à l’instruction printf du C pour afficher les nombres en virgule flottante.

C’est tout pour aujourd’hui !!!

Chapitre 88 : Assembleur ARM 64 bits : affichage des nombres en virgule flottante : algorithme grisu

 

Dans plusieurs chapitres précédents, lors de manipulations de nombres en virgule flottante, j’ai du faire appel à l’instruction printf du langage C pour afficher les résultats.

Cet été j’ai recherché sur internet des algorithmes pour effectuer la conversion directement en langage assembleur mais uniquement en 64 bits. J’ai commencé par trouver un algorithme dragon4 (voir ) mais son adaptation me semblait complexe. Mais ce site aussi renvoyait sur un document pdf (https://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf ) qui proposait 3 algorithmes pour convertir les floats.

J’ai donc épluché ce document et commencé par écrire un premier programme pour étudier en détail le premier algorithme proposé : grisu.

Cet algorithme fait appel à une table des puissances de 10 converties en une structure utilisable par l’algorithme. Donc j’ai du écrire un premier programme (genTableDeTableORI64.s) qui convertit toutes les puissances de 10 entre 10E-309 et 10E307 dans le format décrit dans le document ci dessus.

Curieusement, bien que la norme IEEE754 suppose des puissances de 10 au delà de cette plage, le compilateur as refuse les floats avec des puissances inférieure à -309 et supérieure à +307. Ici, j’ai fait un programme simple qui affiche les résultats que j’ai ensuite recopiés dans un fichier à insérer dans le programme grisu64.s.

Dans ce programme, j’ai repris les idées développées par Florian Loitsch : structure des données, calcul du coefficient pour accéder à la puissance 10 de la table, multiplication, et éclatement du résultats en 3 zones pour l’affichage.

Cela m’a permis d’éclaircir certains points, et d’effectuer les tests pour arriver à un résultat satisfaisant. Bon d’accord l’affichage est plutôt brut mais les résultats trouvés sont corrects (mais avec une perte de précision).

Exemple :

Affichage de 0f12345E-10 :

123450000000000005536E-26

Affichage de Pi : 0f314159265358979323E-17 :

31415926535897931160E-19

Affichage de -0.3 :

-29999999999999993976E-20

Pour ce programme, la table des puissance de 10 contient 309 + 307 = 616 postes, ce qui est beaucoup. Mais le document en référence propose un deuxième algorithme grisu2 qui utilise une table avec des puissance de 10 avec un pas de 8, ce qui réduit le nombre de poste à 78 postes.

D’autres part, en 64 bits la multiplication proposée peut être réduite à une seule instruction umulh. Puis l’analyse de l’algorithme fait apparaître qu’il n’ait nécessaire que d’avoir 4 valeurs avec la structure proposée. Donc il est possible de n’utiliser que des registres 64 bits pour gérer ces valeurs sans avoir à les stocker en mémoire.

Le programme grisu2NV2_64.s met en pratique ces idées. De l’entrée de la valeur à convertir contenue dans le registre d0 à l’extraction des chiffres du résultat, il n’y a aucun appel à une sous routine !! tous les calculs sont effectués dans la même routine. Ensuite les affichages en nombre entiers, nombres décimaux et nombre en notation scientifique (xEexposant) sont effectués par une seule sous-routine. Cela allège le programme mais complique la lisibilité !!

Bien sûr la table des puissances de 10 utilisée est différente et elle est plus petite.

Les résultats sont corrects mais je ne garantie pas leur exactitude pour tous les cas. 

Pi :

3.141592653589793
 

affichage décimal :

-0.3

 

Notation scientifique

-1.234e+306

 

Ce programme doit pouvoir être amélioré (par exemple en améliorant l’affichage de certains nombres comme 1E23 ou 1E53 )et encore optimisé !!

Chapitre 87 : assembleur ARM 64 bits : mesure des performances d'une routine

Il y a quelque temps j’avais essayé de porter le programme 32 bits qui indiquait le nombre d’instructions et de cycles d’une routine en assembleur 64 bits. Je n’y étais pas arrivé car l’appel système PERF_EVENT_OPEN n’était pas disponible en 64 bits. J’avais donc essayé de lire les valeurs directement du registre compteur de cycles proposé par le processeur Cortex A53 mais hélas les instructions de type msr ou mrs sont refusées lors de l’exécution d’un programme exécuté avec la version raspbian buster. Je n’ai pas trouvé pourquoi !!

Mais je me suis repenché sur le problème et maintenant le fonctionnement de PERF_EVENT_OPEN est correct en 64 bits. Est-ce la nouvelle version de Buster ? la mise à jour du package linux-perf ? ou la mise en place des packages suivants nécessaires pour la création de modules du kernel :

sudo apt install build-essential fakeroot dpkg-dev perl libssl-dev bc gnupg dirmngr libncurses5-dev libelf-dev flex bison

je l’ignore mais maintenant il est possible d’extraire le nombre d’instructions, le nombre de cycles et le temps pris par des instructions ou une routine.

Je vous conseille de vous plonger dans la documentation (en anglais) de l’appel système linux PERF_EVENT_OPEN car les possibilités sont nombreuses.

Ici je vais utiliser la possibilité de regrouper les 3 mesures dans le même buffer en créant un process leader et 2 process fils. Cette solution permet de lancer en une seule commande la mesure et d’arrêter la mesure grâce à l’identifiant du leader seul. Les commandes utilisent l’appel système IOCTL puis l’appel READ pour lire les résultats.

Les tests du programme mesurePerf1.s  montrent que les résultats sont surprenants. Le comptage des instructions doit tenir compte de toutes les instructions comprises entre les 2 svc de lancement et d’arrêt de la mesure.

Pour les cycles, les résultats sont très variables si on se contente d’une seule mesure. J’ai donc mis une boucle de mille mesures ce qui permet d’avoir une meilleure estimation du nombre de cycles.

Par exemple pour le simple test du mov x0,1, le nombre d’instruction est de 3012, ce qui correspond à 1001 fois les 3 instructions mov, subs et cbnz et les 9 autres instructions comprises entre les 2 svc (et en les comptant).

Pour le nombre de cycles , celui est variable autour de 2080 ce qui semble indiquer que les 3003 instructions de la boucle correspondent à 2000 cycles.

Or je m’attendais à avoir un nombre de cycles supérieur au nombre d’instructions !! Ce n’est pas le cas et la recherche du fonctionnement de ce type de processeur me fait penser que l’on voit là le gain des architectures pipe line de traitement des instructions.

Si on ajoute une instruction mul, le nombre de cycles augmente seulement de mille alors que cette instruction est donnée pour utiliser au minimum 2 cycles.

En ce qui concerne les temps, ils sont très très variables !!! Donc la recherche d’optimisation ne va être très facile sauf à faire tourner les routines des millions de fois pour voir l’évolution d’une modification.

Mais ce n’est que le début et je vais poursuivre des tests en particulier sur la routine de division de nombres de 128 bits utilisée dans le chapitre précédent.

 

Chapitre 86 : assembleur ARM 64 bits factorisation d'un nombre et threads

Voici un programme facteurthread64.s  écrit pendant la période de confinement et qui marie calculs  pour trouver un facteur d’un grand nombre  et utilisation de threads.

En effet c’est souvent un challenge qui est proposé pour découvrir les problèmes liés à la recherche d’un facteur d’un grand nombre  cad ici à un maximum de 2 puissance 64 – 1.

Pour cela, nous allons d’abord vérifier que le nombre n’est pas premier puis lancer un thread qui va chercher un petit facteur, lancer un thread qui va chercher un facteur proche de la racine carrée et enfin un thread qui va rechercher un facteur quelconque.

Dès qu’un thread aura trouvé un facteur, il sera affiché et on terminera les 2 autres threads.

Pour déterminer si un nombre est premier, j’ai utilisé le test de Fermat (voir wikipedia) qui vérifie si le calcul de x puissance (nombre-1) modulo nombre est divisible par nombre. Ici j’ai pris des valeurs de x égales à 2, 3, 5, 7, 11, 13 et 17 ce qui devrait être suffisant pour la plage des nombres de 64 bits.

Pour le calcul modulo, j’au du écrire une fonction de division d’un nombre de 128 bits par un nombre de 64 bits qui doit être améliorée.

Les 2 premières recherches d’un petit facteur ou d’un facteur proche de la racine carrée ne posent pas de problème (peut être le calcul de la racine carrée d’un nombre !!).

La 3^ième recherche d’un facteur quelconque est faite à l’aide de l’algorithme Rho de Pollard (voir wikipedia ou autres sites d’algorithmique). Là aussi il faut utiliser une division d’un nombre de 128 bits par un nombre de 64 bits si l’on veut décomposer des nombres proche de 2 puissance 63.

Après la vérification de la primalité du nombre, le programme effectue le lancement des 3 threads fils à l’aide de l’appel système Linux CLONE puis se contente d’attendre la fin d’un des threads fils. Pour cela j’utilise l’appel système WAIT4 auquel je passe les pid de chaque fils. J’ai essayé d’utiliser l’appel WAITID mais je ne suis pas arrivé à l’utiliser correctement.

Dès qu’un thread se termine, le programme maitre arrête les 2 fils restant en utilisant l’appel système TKILL et en passant leur N° de pid.

Pour de petits nombres, ce programme fonctionnait correctement après les corrections des petites erreurs habituelles. Pour de plus grands nombres ce programme ne marchait plus car certains tests s’effectuaient sur des valeurs signées (codes lt ou gt par exemples) alors qu’il faut effectuer des tests en valeurs non signées (codes lo ou hi).

Après correction, il restait une erreur résiduelle pour des nombres  dont la division 128 devait s’effectuer avec un diviseur de 64 chiffres significatifs. J’ai mis du temps à trouver où était mon erreur.

En effet l’algorithme que j’utilise compare 2 nombres de 64 bits pour voir si on peut soustraire l’un de l’autre puis décale le reste d’un bit sur la gauche. Et dans la première version, je perdais ce bit !!. Dans la nouvelle version, le décalage du reste de 64 bits nécessite l’utilisation du registre x8 pour conserver le bit le plus à gauche.

Et c’est pourquoi aux lignes 848 et 849, vous trouvez une soustraction et non pas une comparaison. La soustraction permet de gérer la retenue et de pouvoir la déduire du registre x8.

Jusqu’à maintenant, je n’ai pas trouvé de nouvelles erreurs dans ce programme qui trouve le bon résultat en quelques secondes.

Chapitre 85 : assembleur ARM 32 et 64 bits : affichage des variables d'environnement

Dans ce chapitre nous verrons dans 2 petits programmes comment récupérer les variables d’environnement qui peuvent être utiles dans un programme (par exemple la variable USER ou le répertoire courant comme PWD).

En fait la récupération est très simple puisque l’adresse de ces variables sont stockées sur la pile par LINUX avant l’appel à notre programme.

Dans le programme 32 bits varEnv.s  nous commençons par stocker dans le registre fp (frame register) la pile puis nous stockons plusieurs adresses de la pile dans les registres pour examiner leur contenu après l’affichage par la macro vidregtit.

Comme déjà vu, l’adresse 0 contient le nombre de paramètres passés à notre programme dans la ligne de commande. Ici nous avons un seul paramètre (le nom du programme) dont l’adresse est passée à +4. En +8, nous trouvons l’adresse de retour qui est ici à zéro puisque nous revenons au système d’exploitation.

En +12, nous trouvons l’adresse de la première variable d’environnement. Et il nous suffit donc de remonter toutes les adresses jusqu’à en trouver une à zéro pour afficher une à une les variables.

Dans la deuxième partie du programme, je place les différentes adresses des sections dans des registres pour regarder leur emplacement.

Et enfin, nous effectuons une recherche d’une variable pour afficher son contenu. Sur mon raspberry, la variable USER contient pi. Pour démarrer la recherche à la bonne adresse quelque soit le nombre de paramètres passés dans la ligne de commande, l’indice de recherche est initialisé avec le nombre de paramètre + 2.

Le programme varEnv64.s effectue la même chose en 64 bits, sauf que les adresses sont sur 8 octets et non plus sur 4 octets.

Peut être vous posez vous la question du pourquoi du save du registre x1 et lr en début de la routine de recherche alors que ces 2 registres ne sont pas modifiés dans la routine. Et bien c’est pour les avoir toujours en exemple et pour éviter une anomalie si je suis obligé d’ajouter une routine d’affichage en cas de problème. Vous remarquerez que dans cette routine j’utilise les registres r12 etc donc il n’est pas nécessaire de les sauver (cf norme d’appel des routines).