lundi 7 mai 2018

Chapitre 28 : retour sur les algorithmes de division.


Le processeur arm de mon raspberry n’admet pas la division entière comme instruction de base et il faut donc la programmer. Le chapitre 15 du site Thinckingeek propose plusieurs algorithmes et il s’en trouve d’autres sur Internet et dans les livres sur les algorithmes. Dans ce chapitre je vais m’y intéresser en mesurant le temps nécessaire pour effectuer des milliers de divisions avec chacun d’entre eux.
Dans ce programme, nous décrivons dans la .data, le message nécessaire à l’affichage du temps et dans le .bss 2 tables de 10000 postes de 4 octets : la première contiendra le dividende sous forme de nombres aléatoires et la deuxième le diviseur aussi sous forme de nombres aléatoires. Lors de la création de cette dernière nous nous arrangerons pour que le diviseur soit toujours dans une tranche de nombres mille fois inférieur au dividende. Ces tables permettront d’effectuer des divisions de nombres aléatoires identiques pour tous les algorithmes testés.
Dans le code, nous commençons par générer les 10000 dividendes et les 10000 diviseurs aléatoires que nous stockons dans les 2 tables. Ensuite nous créons 2 sous routines pour enregistrer l’heure de départ d’un test (debutChrono) et l’heure de fin du test (stopChrono) pour calculer par différence le temps écoulé. Pour cela nous nous servons de l’appel system Linux gettimeofday (code 0x4E) pour enregistrer l’heure. La sous routine stopChrono affichera le temps en secondes et microsecondes.
Ensuite nous créons toutes les sous routines de division que nous voulons tester : celles du chapitre 15, une qui fait appel à la division en virgule flottante double précision du processeur, une tirée d’un livre sur l’assembleur ARM et 2 programmée par moi et issus de différents idées d’algorithmes trouvées sur Internet. Chaque routine commence par un test du diviseur pour vérifier qu’il soit différent de zéro. Dans ce cas, la routine retourne la valeur -1 dans le registre r0 car il est peu probable en division non signée d’avoir ce résultat. Mais il serait peut être préferable de positionner le carry à 1 dans ce cas (et penser à le mettre à 0 si la division est OK) ce qui coute quelques instructions de plus.
Pour chacune d’entres elles, nous effectuons les mêmes divisions de nombres aléatoires et nous affichons le temps mis.
Le premier algorithme est identique à la première division du chapitre 15 de http://thinkingeek.com/arm-assembler-raspberry-pi/. Après plusieurs séries de tests, il s’avère le plus lent de tous avec en moyenne 4 ms pour 10000 divisions.
Le second fait appel aux instructions en virgule flottante puisque la division est disponible !! Celle solution s’avère efficace puisque l’on tombe à 2ms. Remarque : j’avais fait des tests sur de grands dividendes et j’avais trouvé des écarts sur des résultats que je n’arrivais pas à expliquer. Et enfin j’ai trouvé une erreur dans l’instruction vcvt.f64.u32 d1, s1  car j’avais mis vcvt.f64.s32 d1, s1 car au début je pensais que le s de S32 voulait dire single pour simple précision alors qu’il veut dire signed. Donc il faut faire très attention lors du codage de ces instructions  et sans cesse tester et vérifier !!!
Le troisième reprend tel quel l’algorithme better_unsigned_division de thinkingeek Le résultat est le meilleur
 de tous car on descend à 1,4 ms. Reste à comprendre comment il fonctionne !!!
Le suivant donne aussi de bons résultats avec 1,8ms et les 2 autres sont moins efficaces mais restent dans la moyenne. 
Ces 2 derniers essaient de diminuer le nombre de boucles internes en évitant les zéros inutiles en début des nombres
 grâce à l’instruction clz. Dans ces programmes j’utilise l’instruction rsb bien utile . En effet avant pour enlever
 la valeur d’un registre d’une constante, je mettais la constante dans un premier registre puis je l’enlevais 
par l’instruction sub. Mais c’est plus simple avec rsb r1,r1,#32 soit r1 =  32 –r1.
 
Nous voyons donc ici différents manières de programmer la même routine et les incidences sur le temps d’exécution. 
Ces algorithmes sont à étudier de très près car ils montrent des utilisations diverses des instructions assembleurs.
Exercice :  essayer d’améliorer ces routines (piste : diminuer le nombre de boucles, ou diminuer le nombre
 d’instructions des boucles) 
                Vérifier que ces algorithmes sont exacts pour une large valeur de dividende et diviseur en stockant les résultats de chacun puis en les comparant pour détecter un éventuel écart.
                Adapter le programme pour effectuer des divisions signées.

2 commentaires:

  1. Et si l'on fait les mêmes divisions dans un langage de plus haut niveau, quel niveau de performance obtient-on?

    RépondreSupprimer
  2. Je n'ai pas fait de tests avec d'autres langages. Pour le langage C, le site Think in Geek indique un résultat dans la moyenne.

    RépondreSupprimer