Logicielsmoto.com http://www.logicielsmoto.com/phpBB/ |
|
Etude du décalage à droite programmé: d>>n http://www.logicielsmoto.com/phpBB/viewtopic.php?f=3&t=538 |
Page 1 sur 1 |
Auteur: | Samuel Devulder [ 30 Mar 2016, 21:36 ] |
Sujet du message: | Etude du décalage à droite programmé: d>>n |
En travaillant sur des routines mathématiques, je me suis trouvé dans le besoin de coder en assembleur un décalage à droite non signé et de longeur variable: ((unsigned short)data)>>n. J'ai donc été ammené à étudié diverses solutions à ce problème. On va supposer que data et n sont tout deux de 16 bits placé sur la pile avant d'appeller la routine de décalage (nota: pour n va de 0 à 255, donc la partie haute est nulle). Le résultat doit être dans D, et on peut trasher le registre X ainsi que les valeurs sur la pile. La taille du code n'est pas importante si elle reste raisonnable. 1) Approche naïve Ma première approche fut de faire une boucle: Code: * naive Ce code est pas mal (c'est celui que GCC produit), mais je trouve que le surcout du leax/bne est vraiment très gros par rapport au décalage à proprement parler. On passe 2x plus de temps à faire l'administration de la boucle (8 cycles) que de faire ce à quoi elle sert (4 cycles). Tout ca tourne moralement 3x trop lentement. Un décalage de 16 donne 0 en 212cycles. C'est énorme, il faut vraiment amméliorer ca.s0 ldd 2,s ; 6 ldx 4,s ; 6 beq s0_2 ; 3 s0_1 lsra ; 2 rorb ; 2 leax -1,x ; 5 bne s0_1 ; 3 s0_2 rts ; 5 => 20+n*12 2) Dichotomie 1 J'ai donc cherché un code où l'on déroule la boucle le plus possible, de sorte à minimiser le cout de l'administration. En fait si on décompose n en binaire, si son bit 0 est à 1 il fait faire un décalage de 1 bit, si son bit 1 est à 1 il faut faire un décalage de 2 bits (donc 2x lsra rorb), si le bit 2 est à 1 il faut 4x lsra rorb. Si le bit 3 est à 1 on peut faire 8x lsra rorb d'un coup. Si les bits 4 à 7 sont à 1, c'est que n>=16 et il faut donc retourner 0. Code: (pseudo-code c) if n&1 then data>>=1 if n&2 then data>>=2 if n&4 then data>>=4 if n&8 then data>>=8 if n&0xF0 then data=0 Ah oui! Il semble tout à fait possible de procéder ainsi. Et on peut même faire mieux, car 8x lsra rorb d'un coup (24 cycles) est équivalent à un "tfr a,b ; clra" (8 cycles). Ah oui c'est carrément bien ce truc! Cela donne l'algorithme suivant: Code: s1 ldd 2,s ; 5 Quelle est la complexité de cet algo ? On fait 4 tests sur les bits (7+3=10 cycles), et un nombre de décalages proportionnel à n pour n de 0 à 7, au delà de 8, on fait un nombre de décalage proportionnel à (n-8). J'obtiens le tableau suivantlsr 5,s ; 7 bcc s1_1 ; 3 lsra ; 2 bit0=1 rorb ; 2 s1_1 lsr 5,s ; 7 bcc s1_2 ; 3 lsra ; 2 bit1=1 => 2 décalages rorb ; 2 lsra ; 2 rorb ; 2 s1_2 lsr 5,s ; 7 bcc s1_3 ; 3 lsra ; 2 bit2=1 => 4 déclages rorb lsra rorb lsra rorb lsra rorb s1_3 lsr 5,s ; 7 bne s1_5 ; 3 bcc s1_4 ; 3 tfr a,b ; 6 bit3=1 => 8 décalages (optimisé) clra ; 2 s1_4 rts ; 5 s1_5 ldd #0 ; 3 l'un des bits 4...7 à 1 => zero rts ; 5
3) Dichotomie 2 On pourrait donc voir à charger dans A la valeur de n, et faire un décalage en mémoire uniquement pour le MSB de la donnée. Comme on ne décale pas forcément la donnée pour chaque bit de n, on devrait avoir un gain sur la moyenne. Ca donne le code suivant Code: t1 ldb 3,s ; 5 qui coute quelque chose comme lda 5,s ; 5 lsra ; 2 bcc t1_1 ; 3 lsr 2,s ; 7 rorb ; 2 t1_1 lsra ; 2 bcc t1_2 ; 3 lsr 2,s rorb ; 2 lsr 2,s ; 7 rorb t1_2 lsra ; 2 bcc t1_3 ; 3 lsr 2,s rorb lsr 2,s rorb lsr 2,s rorb t1_3 lsra ; 2 bne t1_5 ; 3 bcc t1_4 ; 3 ldb 2,s ; 5 clra ; 2 rts ; 5 t1_4 lda 2,s ; 5 rts ; 5 t1_5 ldd #0 ; 3 rts ; 5
|
Auteur: | Samuel Devulder [ 30 Mar 2016, 22:02 ] |
Sujet du message: | Re: Etude du décalage à droite programmé: d>>n |
4) Saut 1 Comme on a pas vraiment de contrainte sur la taille du code, pourquoi n'écrirait-on pas en mémoire une suite de lsra rorb consécutifs, et qu'on ferait un saut le (15-n) ème couple. C'est le principe du "Duff Device". Code: s3 ldb 5,s ; 5 La complexité est assez simple à calculer:bitb #$F0 ; 2 bne s3_16 ; 3 s3_1 ldx #s3_00 ; 3 lslb ; 2 negb ; 2 leax b,x ; 5 ldd 2,s ; 6 jmp ,x ; 3 s3_16 ldd #0 ; 3 rts ; 5 s3_15 lsra rorb s3_14 lsra rorb s3_13 lsra rorb s3_12 lsra rorb s3_11 lsra rorb s3_10 lsra rorb s3_09 lsra rorb s3_08 lsra rorb s3_07 lsra rorb s3_06 lsra rorb s3_05 lsra rorb s3_04 lsra rorb s3_03 lsra rorb s3_02 lsra rorb s3_01 lsra rorb s3_00 rts ; 5
5) Saut 2 Surtout que... attendez.. décaler à droite de 15 revient à récupérer le MSBit, lequel peut être obtenu avec un décage à gauche du MSByte. De même avec n=8, on a quand même 32cycles de décalages alors qu'un "tfr a,b; clra" de 8 cycles fait le même résultat. Et en plus, pour les décalages à plus de 8, on se fiche de décaler B, il sera écrasé à un moment donné. On pourrait donc se contenter d'un simple décalage 8 bits. Hum... oui oui... en fait il y a en fait pleins de façon d'obtenir le résultat du décalage à droite 16 bits plus rapidement qu'avec des... décalages à droite 16 bits. Par contre les operations ne sont plus de taille fixe. On ne peut plus faire un saut aussi simplement que dans "saut 1", mais on peut s'en sortir en utilisant une table de pointeur sur les routines de longeur variable: Code: s2 ldb 5,s ; 5 Quelle est la vitesse de cet algo? J'obtiens les formules suivantesbitb #$F0 ; 2 bne s2_16 ; 3 ldx #s2_t ; 3 lslb ; 2 abx ; 3 ldd 2,s ; 6 jmp [,x] ; 6 s2_t fdb s2_00 fdb s2_01 fdb s2_02 fdb s2_03 fdb s2_04 fdb s2_05 fdb s2_06 fdb s2_07 fdb s2_08 fdb s2_09 fdb s2_10 fdb s2_11 fdb s2_12 fdb s2_13 fdb s2_14 fdb s2_15 s2_16 ldd #0 ; 3 rts ; 5 s2_15 lsla ; 7 ldd #0 rolb rts ; 5 s2_14 lsla ; 12 rolb lsla rolb clra andb #3 rts s2_13 lsla ; 16 rolb lsla rolb lsla rolb clra andb #7 rts s2_12 lsra ; 16 s2_11 lsra ; 14 s2_10 lsra ; 12 s2_09 lsra ; 10 s2_08 tfr a,b ; 8 clra rts s2_07 lslb ; 2 tfr a,b ; 6 rolb ; 2 rola ; 2 anda #1 ; 2 rts s2_06 lslb rola rolb rola rolb exg a,b anda #3 ; 20 rts s2_05 lsra ; 20 rorb s2_04 lsra ; 16 rorb s2_03 lsra ; 12 rorb s2_02 lsra ; 8 rorb s2_01 lsra ; 4 rorb s2_00 rts
|
Auteur: | Samuel Devulder [ 30 Mar 2016, 22:21 ] |
Sujet du message: | Re: Etude du décalage à droite programmé: d>>n |
6) Bilan Résumons les temps de ces algos dans un tableau Code: n | naïf dicho1 dicho2 saut1 saut2 ----+-------------------------------------- 0 | 20* 53 43 33 35 1 | 32* 57 52 37 39 2 | 44 61 61 41* 43 3 | 56 65 70 45* 47 4 | 68 69 79 49* 51 5 | 80 73 88 53* 55! 6 | 92 77 97 57 55!* 7 | 104 81 106 61 49* 8 | 116 61 45 65 43* 9 | 128 65 54 69 45* 10 | 140 69 63 73 47* 11 | 152 73 72 77 49* 12 | 164 77 81 81 51* 13 | 176 81 90 85 51* 14 | 188 85 99 89 47* 15 | 200! 89! 108! 93! 47* ----+------------------------------------ 16 | 212 64 38 18* 18* 17 | 224 68 47 18* 18* 18 | 236 72 56 18* 18* 19 | 248 76 65 18* 18* 20 | 250 80 74 18* 18* 21 | 262 84 83 18* 18* 22 | 274 88 92 18* 18* 23 | 286 92 101 18* 18* ----+------------------------------------ 24 | 298 64 38 18* 18* Légende: "!" temps maxi pour les valeurs normales de n "*" routine optimale à n donné On voit que en moyenne les algos de type "saut" sont les plus performants. Ils sont très voisins pour les petites valeurs de n, mais sur le long terme avec les grosses valeurs de n, "saut 2" l'emporte. C'est lui qui a la moyene la plus basse pour la plage 0<=n<=16. 7) Amméliorations? Ce qu'il serait bien serait de pouvoir gagner 2 cycles dans le prologue de "saut 2" pour l'ammener au niveau de "saut 1". Ca ne me semble pas évident, mais peut-être que je loupe un gros truc. Quelqu'un aurait-il une idée? "Saut 2" est le plus lent avec n=5 ou n=6. Le cas n=6 est déjà une optimisation qui me semble optimale. Le cas n=5 n'est en revanche pas optimisé du tout. J'ai beau eu chercher, mais je ne vois pas comment optimiser un décalage à droite de 5 avec un décalage à gauche ou mieux. Quelqu'un aurait-il une idée géniale pour optimiser "data>>5", et réduire encore mieux le temps passé dans le décalage variable sur 6809 ? |
Auteur: | PulkoMandy [ 31 Mar 2016, 07:53 ] |
Sujet du message: | Re: Etude du décalage à droite programmé: d>>n |
Moi j'aurais pensé à utiliser des tables de lookup. On veut décaler un nombre sur 8 bits (256 possibilités) de 0 à 8 bits (8 possibilités) soit une table de 256*8=2K. On peut couper en deux, on fait une table pour les 4 bits de poids fort, et une pour les 4 bits de poids faible. Pour le poids faible on ne peut shifter que de 4 bits, et il y a 16 possibilités de valeur, donc 16*4=64 octets. Pour le poids fort on peut shifter jusqu'à 8 bits, donc 16*8=128 octets de table. On fait les 2 lookups pour chaque moitié puis un OR entre les 2. Est-ce que c'est intéressant en nombre de cycles? Je sais pas, ça fait peut-être trop d'accès mémoire? Une autre solution est de faire une multiplication par 2^(8-N) et de récupérer le résultat dans B. Mais la conversion de N en 2^(8-N) reste à faire. N=0: MUL 256 N=1: MUL 128 N=2: MUL 64 N=3: MUL 32 etc. |
Auteur: | Samuel Devulder [ 31 Mar 2016, 14:08 ] |
Sujet du message: | Re: Etude du décalage à droite programmé: d>>n |
PulkoMandy a écrit: Moi j'aurais pensé à utiliser des tables de lookup. On veut décaler un nombre sur 8 bits (256 possibilités) de 0 à 8 bits (8 possibilités) soit une table de 256*8=2K. Heu, le nombre à shifter est sur 16 bits avec 16 décalages possibles soit 65536*16*2 (car 2 octets) = 2Mo Par contre avec le découpage, il y a de l'idée. Une table de 256*16(*2) contient les 16 décalages possibles pour la partie basse, et une autre contient les 256*16(*2) de la partie haute. Code: d>>n == table1[((n&15)<<8) + ((d&0xFF00)>>8)] | table2[((n&15)<<8) + ((d&0x00FF)>>0)] Ca fait quand même 8Ko par table. On peut être effectivement tenter de découper plus par bouts de 4bits, ce qui ferait juste 4 tables de 512octets soit 2ko. La clef (256 valeurs) est constituée des 4 bits de la donnée en poids fort, et des 4 bits du décalage en poids faible: Code: d>>n == table1[((d&0xF000)>>8) + (n&15)] | table2[((d&0x0F00)>>4) + (n&15)] | table3[((d&0x00F0)>>0) + (n&15)] | table4[((d&0x000F)<<4) + (n&15)] En C ca a l'air fort sympathique, mais en ASM ca fait finalement beaucoup de décalages par 4. C'est pas évident de savoir si on descend en dessous des 55 cycles de la méthode "saut 2". Par contre, on peut imaginer une table qui contient ce qu'il faut pour le décalage avec n=5. Le passage de n=5 à n=6, ne coute que 4 cycles de plus (lsra/rorb). Bonne idée: je vais creuser ca. |
Auteur: | PulkoMandy [ 31 Mar 2016, 14:15 ] |
Sujet du message: | Re: Etude du décalage à droite programmé: d>>n |
Pour la partie basse, il n'y a que 8 décalages, les 8 autres donnant tous 0 (tous les bits sont sortis). ça gagne encore un peu de place mais il faut tester n>8. Et le résultat est forcément sur 8 bits aussi (car on ne décale que vers la droite). |
Page 1 sur 1 | Heures au format UTC + 1 heure |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |