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
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
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.

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! :D Cela donne l'algorithme suivant:
Code:
s1      ldd     2,s     ; 5
        lsr     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
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 suivant
  • 0<=n<=7 ---> 53+4*n
  • 8<=n<=15 ---> 61+4*(n-8)
  • 16<=n ---> 64+4*(n&7)
Hum..53 cycles minimaux, même quandd on ne fait rien à la donnée (n=0). C'est pas génial. Le cout du test sur les bits prend à lui seul 4*10=40cycles. C'est énorme. Ce qui grève les perfs c'est le LSR en mémoire systématique même s'il n'est pas suivi d'un décalage. Un LSR sur un registre serait nettement moins couteux.

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
        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
qui coute quelque chose comme
  • 0<=n<=7 ---> 43+(n&7)*9
  • 8<=n<=15 ---> 45+(n&7)*9
  • 16<=n ---> 38+(n&7)*9
Alors oui avec n=0, on tombe à 43 cycles, c'est mieux que les 61 de "dichotomie 1". La constante fixe est plus faible qu'avant. Par contre le cout de chaque bit à 1 dans n est plus gros (9), mais quand même plus petit que le cout de la boucle de l'algo naïf (12). Le pire cas se produit donc lorsque n=15 (tous les bits à 1) avec 108cycles. Hum... 108 c'est beaucoup quand même :(

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
        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
La complexité est assez simple à calculer:
  • 0<=n<=15 ---> 33+4*n
  • 16<= n ---> 18
Ah oui seulement 33 cycles quand on ne fait rien. C'est bien :) mais avec n=15, on fait 93 cycles. C'est mieux que les 108 au dessus, mais a peine. :L

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
        bitb    #$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
Quelle est la vitesse de cet algo? J'obtiens les formules suivantes
  • * 0<=n<=5 ---> 35+4*n
  • n=6 ---> 30+(23) = 53
  • n=7 ---> 30+(19) = 49
  • n=8 ---> 30+(13) = 43
  • n=9 ---> 30+(15) = 45
  • n=10 ---> 30+(17) = 47
  • n=11 ---> 30+(19) = 49
  • n=12 ---> 30+(21) = 51
  • n=13 ---> 30+(21) = 51
  • n=14 ---> 30+(17) = 47
  • n=15 ---> 30+(17) = 47
  • 16<=n ---> 18
Hum... ca a l'air pas mal du tout, on est facilement 3x plus rapide que la routine native pour les grosses valeurs de n. Ca veut dire qu'on a +/- gommé les calculs inutiles (gestion de boucle) de l'algo naïf. :D

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 ? :voyons:

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 :evil:

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. :L

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/