Discussion :

[progfou]

Bonjour à tous !
Je cherche un algorithme qui me permette de calculer une multiplication de deux nombres de 32 bits.
J'ai pensé décomposer chaque terme en deux (ou quatre) termes de 16 bits (ou 8 bits) afin de faire de plus petite multiplications, beaucoup plus rapides sur le processeur qui les implémentera (1 cycle pour du 16*16, 2 cycles pour du 32*8, 5 pour du 32*16 et 35 ! pour du 32*32).
Les instructions de décalage durent également un cycle.

Des idées ?

[j.p.mignot]

suggestion sans aucune garantie!
si on considère 2 entiers a et b, je commencerais par choisir celui qui a sa décomposition en puissance de 2 la plus courte (le moins de 1 dans sa representation binaire ) . supposons que cela soit a

a= somme {k=1..Ko} 2^N(k) N(k) entiers >=0, on peut avoir l'unicité si on fixe N(k) < N(k+1) pour tout k < Ko

puis j'effectuerais

S = Somme {k=1..Ko} ( b << N(k) } ( ici << représente shift left )

[progfou]

Je comprends bien le principe, mais je ne suis pas certain que cela fonctionne . Qu'entends-tu par unicité ?

[j.p.mignot]

Cela fonctionne sans problème si les entiers sont positifs ou nuls. Si non cela est FAUX. Entre autre shl déplacerait le bit de signe.
Unicité car la décomposition en puissance de 2 d'un entier est univoque

[progfou]

Oui, et mon problème, c'est que mes nombres sont signés...
Mais je pense que c'est une voie à creuser !

[j.p.mignot]

Il est toujours possible e multiplier les valeurs absolues par ce moyen puis par -1 en fin de calcul le cas échéant. Reste à savoir si on gagne vraiment du temps!!!
la multiplication par -1 peut se faire facilement comme suit
en complement à 1 : inverser tous les bits (0->1 et 1 -> 0)
en complément à 2, executer le complément à 1 puis ajouter 1 au résultat obtenu.

[progfou]

J'ai trouvé une autre technique, mais je ne l'ai pas testée...
Dans les conditions des temps exposée au début du topic, j'arrive à 10 cycles sans changement de signe (11 ou 12 avec) au lieu de 35 :

Soit a un nombre 32 bits.
Soient al les 16 bits de poids faible, ah le 16 bits de poids fort.
Soit b un nombre 32 bits et bl, bh les mots faible/fort.

a*b = (ah*2^(N/2)+al) * (bh*2^(N/2)+bl)
a*b = al*bl+(ah*2^(N/2)*bl)+(bh*2^(N/2)*al)+(ah*2^(N/2)*bh*2^(N/2))
a*b = al*bl+(ah*bl)<<(N/2)+(bh*al)<<(N/2)+(ah*bh)<<N

Avec << le décalage à gauche.

Je pense que ça se fait, ça me fait 4 multiplications 16*16 (1 cycle chacune), et les décalages et additions en plus j'arrive en gros à 10 cycles.

Mais est-ce correct, aies-je le droit de faire ça ?

[Graffito]

Bonjour,

Compte tenu du nombre de combinaison positif/négatif à envisager (voir post scriptum), je ne pense pas que l'on puisse diminuer le nombre de cycles de façon générale. Par contre, on doit pouvoir améliorer la performance réelle si on considére que dans la majorité des cas on a des multiplications de nombres entre -2**15 et 2**15 .

l'algorithme suivant demande un peu moins de cycles pour les nombres positifs.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
si (a and $FFFF0000) = 0  aller à  Testb // 2 cycles
si (a and $FFFF0000) = -1 aller à Testb // 2 cycles
 
mult3232:
Mult32(a,b) // 35 cycles
aller à fin // 1 cycle
 
Testb:
si (b and $FFFF0000)  = 0  aller à  mult1616 // 2cycles
si (b and $FFFF0000) !=-1  aller à  mult3232 // 2 cycles
 
mult1616:
Mult16(a,b) // 1 cycle
fin :

evaluation du nb de cycles (sans compter les éventuelles sauvegardes de registres nécessaires aux comparaisons):
mult16 : de 1+4 (2 nombres positifs de 16 bits ) à 1+9 (2 nombres négatifs de 16 bits)
mult32 : de 35+3 à 35+9 (autres cas)

PS:
Si l'on prend un exemple de décomposition en morceaux de 8bits (avec signe):
N1=2FF x 2FF n'est pas égal à N2=(2+FF)x(2+FF) étant donné que FF=-1

[j.p.mignot]

Oui si a ET b sont positifs
votre relation est
al*bl+(ah*bl)<<(N/2)+(bh*al)<<(N/2)+(ah*bh)<<N
si on raisonne dur 16bits divisé en 2X 8bits pour raccourcir l'écriture alors
cette relation est
al*bl+(ah*bl)<<8+(bh*al)<<8+(ah*bh)<<16 <1>

par exemple on prend a=b=-70
a=b= 1011 1010 al=bl= 1010= 10 ah=bh = 1011 = 11
<1> donne
10*10 + 10*11*256*2 + 11*11*256*256 = 100+56980+7929856=7986936 =
1111001 1101 1110 1111 1000
ce qui est différent de a*b= 70^2 = 4900= 0001 0011 0010 0100

[progfou]

Alors, j'ai modifié le programme, de telle sorte que le calcul et fait sur les valeurs absolues des nombres, puis ramené en positif ou négatif suivant le signe des nombres de départ.
Ca fonctionne, sauf dans les valeurs proches des limites (2147483648 en l'occurence)

[Jean-Marc.Bourguet]

Bonjour à tous !
Je cherche un algorithme qui me permette de calculer une multiplication de deux nombres de 32 bits.
J'ai pensé décomposer chaque terme en deux (ou quatre) termes de 16 bits (ou 8 bits) afin de faire de plus petite multiplications, beaucoup plus rapides sur le processeur qui les implémentera (1 cycle pour du 16*16, 2 cycles pour du 32*8, 5 pour du 32*16 et 35 ! pour du 32*32).
Les instructions de décalage durent également un cycle.

Des idées ?

Où est-ce que tu as trouvé ces chiffres? (C'est une question sincère: chaque fois que j'ai cherché de la doc précise sur ces sujets sur les sites d'Intel et d'AMD, j'ai abandonné).

j'arrive à 10 cycles

Tu n'oublierais pas de tenir compte des effets tels que:
- les additions ne sont pas sur 32 bits
- il y a des dépendances entre les données qui font que les pipelines ont nécessairement des bulles

Quels sont les résultats des mesures sur ton programme?

[j.p.mignot]

Evidemment!!
2147483648 = 1000’0000’0000’0000’0000’0000’0000’0000 ce qui dans votre codage signé correspond à un nombre négatif ( bit poids fort=1)
en 32 bits signé on ne peut pas dépasser 2147483647.
Par ailleurs j'adhère aussi aux commentaires de j.m. Bourguet.
Les seuls cas où j'ai pu réellement maîtriser le nombre de cycles d'une opération ont été ceux que j'ai programmé en assembleur sur des processeurs - DSP embarqués. Si non …
1- il n’est pas toujours facile de contrôler le compilateur, aussi après compilation d'un source-code C on n'a pas toujours toutes les garanties! de plus certains optimisateurs de code après compilation conduisent à des bugs de fonctionnement.
2- Je n’ai pas eu à me préoccuper de ce type de problème sur PC. Les quelques fois où j'ai eu à implémenter ces opérartions sur des processeurs embarqués , DSP ( TI, … ) j’ai pu trouver en général l’information relative aux nombres de cycles utiles pour les opérations de base.

[progfou]

Bonjour à tous !
Je cherche un algorithme qui me permette de calculer une multiplication de deux nombres de 32 bits.
J'ai pensé décomposer chaque terme en deux (ou quatre) termes de 16 bits (ou 8 bits) afin de faire de plus petite multiplications, beaucoup plus rapides sur le processeur qui les implémentera (1 cycle pour du 16*16, 2 cycles pour du 32*8, 5 pour du 32*16 et 35 ! pour du 32*32).
Les instructions de décalage durent également un cycle.

Des idées ?

Où est-ce que tu as trouvé ces chiffres? (C'est une question sincère: chaque fois que j'ai cherché de la doc précise sur ces sujets sur les sites d'Intel et d'AMD, j'ai abandonné).

j'arrive à 10 cycles

Tu n'oublierais pas de tenir compte des effets tels que:
- les additions ne sont pas sur 32 bits
- il y a des dépendances entre les données qui font que les pipelines ont nécessairement des bulles

Quels sont les résultats des mesures sur ton programme?

L'architecture sur laquelle c'est porté n'est pas x86.
C'est du Leon, donc, pas la même chose au niveau cycles.
Donc, oui, je suis certain des chiffres

[Jean-Marc.Bourguet]

L'architecture sur laquelle c'est porté n'est pas x86.
C'est du Leon, donc, pas la même chose au niveau cycles.
Donc, oui, je suis certain des chiffres

Bizarre... Tu peux me dire de quelle doc tu as extrait tes chiffres? Si je prends le manuel de l'utilisateur sur le site de Gaisler je ne vois pas comment tu peux avoir une configuration avec les caractéristiques que tu donnes.

Pour commencer, quelles instructions as-tu pour sparc V8 qui font du 32*8 et du 32*16? Il y a une instruction "pas de multiplication" qui fait du 32*1, deux instructions de multiplications qui font du 32*32 et une multiplication accumulation faisant du 16*16 avec accumulation dans 40 bits.

Ensuite, pour avoir 35 cycles pour la multiplication 32x32, il faut avoir configuré léon avec un multiplieur itératif, ce qui empèche d'avoir les multiplications accumulations et je ne vois pas comment alors faire du 16x16 en un cycle.

[progfou]

Documentation Gaisler, page 18/92 :

Configurable multiplier (16x16, 32x1, 32x8, 32x16 & 32x32)

Puis, page 19 :

SMUL/UMUL | 1/2/4/5/35*

1 cycle pour 16*16.

[Jean-Marc.Bourguet]

Documentation Gaisler, page 18/92 :

Configurable multiplier (16x16, 32x1, 32x8, 32x16 & 32x32)

Puis, page 19 :

SMUL/UMUL | 1/2/4/5/35*

1 cycle pour 16*16.

A mon avis tu interprètes mal la doc. Elle est peut-être plus claire en page 82.

Pour savoir ce qui est disponible comme instruction, il faut regarder le manuel du Sparc V8. Et dans celui-ci il n'y a que:

• un pas de multiplication
• deux multiplications (signée et non signée) 32x32->64
• deux multiplication accumulation (signée et non signée) 16x16+40->40

La doc de leon indique que ces multiplications sont implémentables avec plusieurs multiplieurs (le choix du circuit utilisé se fait au moment de la synthèse du circuit).

• un multiplieur itératif avec un latence de 35 cycles pour les multiplications 32x32 (le 32x1 de la page 18 );
• un multiplieur 16x16 pipeliné avec un latence de 5 cyles pour les multiplications 32x32;
• un multiplieur 16x16 avec une latence de 4 cycles pour les multiplications 32x32 (mais un débit moins bon que le pipeliné car on ne peut pas enchainer les multiplications);
• un multiplieur 32x8 avec une latence de 4 cycles pour les multiplications (mais pas pipeliné, et ne permet pas les multiplications accumulations mais prend moins de place que le 16x16)
• un multiplieur 32x16 avec une latence de 2 cycles
• un multiplieur 32x32 avec une latence de 1 cycle

La doc complète en disant que les instructions de multiplication-accumulation ne sont disponibles qu'avec le multiplieur 16x16.

[progfou]

Ah...
Ca veut donc dire que mon truc ne fonctionne pas, enfin, qu'il n'améliorera rien...
Ceci dit, l'instruction MAC est implémentée dans le LEON que j'utilise, peut-être que ça me permettrait de résoudre ce problème ?

Ceci dit, ce n'est pas une multiplication 32*32 seule, il y a un décalage vers la droite, à l'issue de la multiplication, et le tout est casté dans un int :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
#define MULT32(a,b,q)    (int)(((__int64)(a)*(__int64)(b))>>(q))

Je précise que le décalage est de 28, 29 ou 30 suivant les cas...

[Jean-Marc.Bourguet]

Ceci dit, l'instruction MAC est implémentée dans le LEON que j'utilise, peut-être que ça me permettrait de résoudre ce problème?

Si MAC est disponible, ça veut dire que le multiplieur hard est 16x16 donc que la multiplication 32*32 se fait en 4 ou 5 cycles. Je doute que tu arrives à améliorer en la faisant toi même, même si tu n'as besoin que des 32 bits les plus significatifs du résultat.

[Rafy]

Je pense que les ingénieurs qui travail sur les processeurs et leur architécture, ont optimisés la multiplication de deux nombre sur 32 bits.
Et que c'est impossible d'optimiser à notre niveau (je veux dire en programmant) cette multiplication...
Des ingénieurs, pour améliorer les calculs de 3D ont optimisés les opérations enchaînées '*' '+'... dans le genre a*b+c.
Il serai plus facile, je pense d'optimiser des choses plus importantes dans l'algorithme, voir même un algorithme entier plutot qu'une multiplication...

[progfou]

Cette opération a été optimisée sur un ARM et le gain, sur l'algo entier, a été de 20%. Cette opération est effectuée des milliers de fois par seconde, donc, même un ou deux cycles gagnés en moyenne, c'est énorme.

De plus, comme je l'ai dit, il y a une multiplication suivie d'un décalage. Optimiser la multiplication en fonction des décalages peut être un résultat !
Mais comme je n'ai pas assez d'expérience dans ces opérations, je cherche auprès de vous .
Les décalages en question sont faits sur le résultat, et vont de 27 à 30 bits vers la droite.
Le résultat est donc calculable en faisant des opérations moins longues, enfin, je pense...