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.