Améliorer le calcul d'une multiplication (32*32)bits ?

Version imprimable

Voir 40 message(s) de cette discussion en une page

13/03/2006, 09h08
progfou

j.p.mignot : Si je reviens à ta première suggestion, je me demande comment tu fais pour savoir quel nombre a sa décomposition bianire la plus courte (le nombre de 1 le plus petit) en peu de cycles (idéalement, un) ?
Car, savoir lequel est le plus petit, déjà, ça peut aider, si l'un des deux est une puissance de deux, c'est encore plus rapide, ou si l'un des deux est nul...
13/03/2006, 09h40
Jean-Marc.Bourguet

Il y a des algo (recherche population count) mais je doute qu'on y arrive en un cycle. En fait, je doute que l'approche soit rentable -- sauf peut-être quand c'est pour des constantes -- considérant que tu as un multiplieur 16x16.

Sinon, ce qui compte ce n'est pas le nombre de 1, c'est le nombre de transitions 1 -> 0 et 0-> 1: Multiplier x par 127, c'est x*128-x.

A+
--
Jean-Marc
13/03/2006, 10h08
progfou

Je vais voir, en insérant des tests, si l'un des deux est nul, ou si l'un des deux est une puissance de deux, je vais renvoyer le résultat (0 ou un décalage), sinon, je le laisse faire la multiplication.
13/03/2006, 10h19
Matthieu Brucher

Ca serait étonnant que la multiplication 32*32 ne soit pas optimale sur ton processeur.
13/03/2006, 17h01
j.p.mignot

J'avais commencé mon 1er mail avec "suggestion sans aucune garantie!"
Et j'abonde dans le sens des précédents mails et doute que de façon générale on gagne du temps surtout si il faut rechercher les 1.
Par contre en cas de nombres connus peut-être est-il plus rapide de faire
une série d'additions et de shifts plutôt que la multiplication comme par exemple
b << 3 + b <<2 plutôt que b*12
SI b >= 0
22/03/2006, 08h54
progfou

Bon, après deux semaines d'essais et autres joyeuseté, j'ai enfin compris ce qu'il se passe !
Un

Code:

objdump -d monfichier.elf | more

m'a donné la solution !
La page 206 (202 sur le PDF) du manuel Sparc V8
donne le code d'une multiplication signée utilisant mulscc, et qui est la macro utilisée par GCC.
Or, ayant l'instruction smul implémentée, il m'a suffit d'inliner ce smul, et j'avais alorsla multiplication en quelques cycles. Regardez le code dans le manuel, il est particulièrement long, dû à l'istruction utilisée.
Au passage, en modifiant cette instruction, j'ai gagné 37% sur le temps d'exécution, et encore, tout n'est pas modifié...
22/03/2006, 11h13
Jean-Marc.Bourguet

Citation:

Envoyé par progman

Bon, après deux semaines d'essais et autres joyeuseté, j'ai enfin compris ce qu'il se passe !
Un

Code:

objdump -d monfichier.elf | more

m'a donné la solution !
La page 206 (202 sur le PDF) du manuel Sparc V8
donne le code d'une multiplication signée utilisant mulscc, et qui est la macro utilisée par GCC.
Or, ayant l'instruction smul implémentée, il m'a suffit d'inliner ce smul, et j'avais alorsla multiplication en quelques cycles. Regardez le code dans le manuel, il est particulièrement long, dû à l'istruction utilisée.
Au passage, en modifiant cette instruction, j'ai gagné 37% sur le temps d'exécution, et encore, tout n'est pas modifié...

Ceci pourrait t'aider:

Citation:

Envoyé par GCC manual

`-mcpu=CPU_TYPE'
Set the instruction set, register set, and instruction scheduling
parameters for machine type CPU_TYPE. Supported values for
CPU_TYPE are `v7', `cypress', `v8', `supersparc', `sparclite',
`f930', `f934', `hypersparc', `sparclite86x', `sparclet',
`tsc701', `v9', `ultrasparc', and `ultrasparc3'.

Default instruction scheduling parameters are used for values that
select an architecture and not an implementation. These are `v7',
`v8', `sparclite', `sparclet', `v9'.

Here is a list of each supported architecture and their supported
implementations.

v7: cypress
v8: supersparc, hypersparc
sparclite: f930, f934, sparclite86x
sparclet: tsc701
v9: ultrasparc, ultrasparc3

By default (unless configured otherwise), GCC generates code for
the V7 variant of the SPARC architecture.
22/03/2006, 11h28
progfou

C'est un gcc modifié, il compile pour Sparc V8, et le code présent dans la doc pour la multiplication signée est celui que j'ai retrouvé en désassemblant mon exécutable.
22/03/2006, 22h19
Rafy

Re: Améliorer le calcul d'une multiplication (32*32)bits ?

Citation:

Envoyé par progman

1 cycle pour du 16*16, 2 cycles pour du 32*8, 5 pour du 32*16 et 35 ! pour du 32*32

hum désolé de te décevoir mes tout ça dépent des processeurs.....
un athlon XP 2600+ pour faire une multiplication 32bits prend 11 passes....
Donc je crois que tu devrais plutôt t'intéresser à un truc dans le genre cosinus ou sinus où la il faut pas moins de 200 passes....
Ou même optimiser la division, car elle prend en générale plus de temps qu'une racine carré par exemple....
Et dans tous ces cas, si tu arrives à optimiser un truc, pas dans le genre gagner 1 cycle sur une journée de calculs, alors tu pourras, je pense demander à Intel ou AMD, s'il veulent bien te prendre pour participer à la création d'archi de processeurs....
Les processeurs des cartes graphiques sont même plus étudié par des hommes, ce sont des salles géantes, rempli de gros serveurs qui étudient des archi de proc.... Des machines qui étudient des machines.....
A mon avis s'il était possible d'améliorer un algorithme de multiplication de 2 nombre de 32 bits, alors ces PC surpuissant l'aurait trouvé !!!!!
Vous ne pensez pas ??? :furieux:
Il est préférable je pense d'améliorer un algo, plutôt que de se pign**** avec des détails de multiplication...
22/03/2006, 22h58
progfou

Tu as tout lu ?
Car je l'ai optimisée, et j'ai un gain de 37%...
C'est sur mon algo que je voulais l'optimiser. Si tu relis tout, et en particulier la doc technique, tu verras que ce n'est pas sur un processeur du type x86, que par conséquent j'ai bien seulement 5 cycles pour effectuer ma multiplication, contre presque 40 en laissant GCC faire.
Edit: je ne sais pas si tu as déjà fait de la conception de processeur, mais il est possible, moyennant astcues en tout genre, de concevoir des processeurs effectuant, en 1 cycle (en moyenne dans le flot d'instructions modulo une architecture Harvard modifiée) 8 Multiplication avec accumulation. Cf. les DSP :wink:
22/03/2006, 23h15
Rafy

Citation:

Envoyé par progman

Tu as tout lu ?

Oui j'ai tout lu.

Citation:

Envoyé par progman

Car je l'ai optimisée, et j'ai un gain de 37%...

En théorique ou tu as fais un bench, pour voir que tu avais gagné 37% de temps...
Par exemple tu fais une boucle qui va faire 100000 multiplications sans ton 'optimisation', tu regardes le temps, puis tu recommence avec ton 'optimisation'...
Alors la tu gagnais 37% de temps ? C'est ça que tu as fait ?

Citation:

Envoyé par progman

C'est sur mon algo que je voulais l'optimiser.

Une multiplication c'est une multiplication. C'est une instruction assembleur que tu donnes au proc, que tu codes d'une certaine manière, ou d'une autre ça sera toujours de l'assembleur... Donc que ce soit dans ton algo ou ailleur c'est toujours des opérations élémentaires de ton processeur qui sont apellées...

Citation:

Envoyé par progman

Si tu relis tout, et en particulier la doc technique, tu verras que ce n'est pas sur un processeur du type x86, que par conséquent j'ai bien seulement 5 cycles pour effectuer ma multiplication, contre presque 40 en laissant GCC faire.

Pour mettre une valeur dans le registre processeur tu prends des cycles, c'est pas gratuit, pour faire des mov tu prends des cycles, c'est pas gratuit... C'est bien de voir qu'en faisant certaines opérations tu gagnes du temps, mais transmettre les valeurs d'opérations en opérations tu prends aussi des cycles...
Tu as désassemblé ton code pour voir s'il faisait bien que des instructions qui en tout ne prennaientt que 5 cycles ???
Tu es sur qu'il n'y a pas de mov, de comparaison, etc que tu n'a pas compté ?
Je suis toujours septique.....
Je voudrai bien voir la différence de mes yeux.
Fais un exe, ou l'on peut constater qu'effectivement ta multiplication prend 37% de temps en moins...
22/03/2006, 23h18
Rafy

Citation:

Envoyé par Miles

Ca serait étonnant que la multiplication 32*32 ne soit pas optimale sur ton processeur.

Ben ouais...

Voici le code implémentant une multiplication 32*32 dans le processeur SparcV8, utilisé par GCC.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
/*Procedure to perform a 32-bit by 32-bit multiply.
* Pass the multiplicand in %o0, and the multiplier in %o1.
* The least significant 32 bits of the result are returned in %o0,
* and the most significant in %o1.
*/
mov %o0, %y ! multiplier to Y register
andncc %o0, 0xfff, %g0! mask out lower 12 bits
be mul_shortway ! can do it the short way
andcc %g0, %g0, %o4 ! zero the partial product and clear N and V conditions
!
! long multiply
!
mulscc %o4, %o1, %o4 ! first iteration of 33
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4
mulscc %o4, %o1, %o4 ! 32nd iteration
mulscc %o4, %g0, %o4 ! last iteration only shifts
!
! If %o0 (multiplier) was negative, the result is:
! (%o0 * %o1) + %o1 * (2**32)
! We fix that here.
!
tst %o0
rd %y, %o0
bge 1f
tst %o0 !
 
etc.

Ayant l'instruction smul, il m'a suffit de faire :

Code:

1
2
3
4
5
 
__asm__ __volatile__ ("smul %2,%1,%0\n\t"
                                  :"=r" (res)
                                  :"r" (a)
                                  :"r" (b));

Je zappe un mov supplémentaire, mais c'est le principe qui compte.
Profiling effectué sur 67000 multiplications plus toutes les autres instructions, gain de 37%.

Je n'ai rien inventé, juste utilisé une instruction implémentée...

23/03/2006, 09h14
Matthieu Brucher

Donc en fait, tu viens de dire que ton premier message est à bazarder et que tu as pu en fait enfin utiliser l'instruction du processeur.
Tu n'as pas décomposée l'instruction, c'est GCC qui le faisait et maintenant tu utilises l'instruction dont tu parlais au début et que tu voulais à priori optimiser sans savoir ce que GCC faisait.
Donc on est tous d'accord entre nous, vaut mieux utiliser les instructions du proc plutôt que leurs versions émulées ;)
23/03/2006, 09h23
progfou

Exact ;)

Citation:

Envoyé par Miles

Tu n'as pas décomposée l'instruction, c'est GCC qui le faisait et maintenant tu utilises l'instruction dont tu parlais au début et que tu voulais à priori optimiser sans savoir ce que GCC faisait.

gcc ne fait que ce qu'on lui demande:

Citation:

Envoyé par Doc gcc

By default (unless configured otherwise), GCC generates code for the V7 variant of the SPARC architecture.

With `-mcpu=v8', GCC generates code for the V8 variant of the SPARC architecture. The only difference from V7 code is that the compiler emits the integer multiply and integer divide instructions which exist in SPARC-V8 but not in SPARC-V7.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 ~/src 33>$ cat mult.c int m(int a, int b) { return a*b; } $ gcc-4.1.0 -S mult.c $ cat mult.s .file "mult.c" .global .umul .section ".text" .align 4 .global m .type m, #function .proc 04 m: save %sp, -112, %sp st %i0, [%fp+68] st %i1, [%fp+72] ld [%fp+68], %o0 ld [%fp+72], %o1 call .umul, 0 nop mov %o0, %g1 mov %g1, %i0 restore jmp %o7+8 nop .size m, .-m .ident "GCC: (GNU) 4.1.0" $ gcc-4.1.0 -mcpu=v8 -S mult.c $ cat mult.s .file "mult.c" .section ".text" .align 4 .global m .type m, #function .proc 04 m: save %sp, -112, %sp st %i0, [%fp+68] st %i1, [%fp+72] ld [%fp+68], %g2 ld [%fp+72], %g1 smul %g2, %g1, %g1 mov %g1, %i0 restore jmp %o7+8 nop .size m, .-m .ident "GCC: (GNU) 4.1.0"
et j'ai un comportement semblable avec toutes les versions de gcc que j'ai essaye (la plus vieille etant 2.95.3). Meme en devant utiliser une version fournie par quelqu'un d'autre et patchee specifiquement pour un processeur, j'ai des difficultes a croire que ces patchs auraient enleve la possibilite d'utiliser les instructions du processeur pour lequel elle a ete patchee...

23/03/2006, 11h34
progfou

Je te garantis pourtant que c'est le cas, je ne l'ai pas, je crois qu'elle est avec un mtune=v8, mais je tâcherais de vérifier, je ne l'ai pas sous la main à l'instant...
Ceci dit, je sais que le Leon (puisqu'il s'agit de lui) n'a pas l'instruction de division, en tout cas, pas dans l'implémentation que nous utilisons. Peut-être que du coup, ils ont laissé v7...

Voir 40 message(s) de cette discussion en une page