Pourquoi la division du matériel prend beaucoup plus de temps que la multiplication?

37

Pourquoi la division du matériel prend-elle tellement plus de temps que la multiplication sur un microcontrôleur? Par exemple, sur un DSPIC, une division prend 19 cycles, alors que la multiplication ne prend qu'un cycle d'horloge.

J'ai suivi quelques tutoriels, y compris l' algorithme de division et l' algorithme de multiplication sur Wikipedia. Voici mon raisonnement.

Un algorithme de division, comme une méthode de division lente avec restauration sur Wikipedia, est un algorithme récursif. Cela signifie que les résultats (intermédiaires) de l'étape ksont utilisés comme entrées pour l'étape k+1, ce qui signifie que ces algorithmes ne peuvent pas être parallélisés. Par conséquent, il faut au moins des ncycles pour terminer la division, alors qu'il nexiste un nombre de bits dans un dividende. Pour les dividendes sur 16 bits, cela correspond à au moins 16 cycles.

Un algorithme de multiplication n'a pas besoin d'être récursif, ce qui signifie qu'il est possible de le paralléliser. Cependant, il existe de nombreux algorithmes de multiplication différents et je n'ai aucune idée de celui qui peut être utilisé par les microcontrôleurs. Comment fonctionne la multiplication sur un matériel / microcontrôleur?

J'ai trouvé un algorithme multiplicateur Dadda , censé ne prendre qu'un cycle d'horloge pour terminer. Cependant, ce que je ne comprends pas, c'est que l'algorithme de Dadda se déroule en trois étapes, alors que les résultats de l'étape 1 sont utilisés à l'étape 2, etc. Selon cela, il faudrait au moins trois cycles d'horloge pour terminer.

Marko Gulin
la source
2
L'algorithme ne définit pas vraiment le nombre de cycles d'horloge. Votre CPU spécifique peut avoir un multiplicateur / diviseur matériel fonctionnant sur un cycle ou 20 cycles, indépendamment de la mise en œuvre interne.
Eugene Sh.
1
OP, pouvez-vous fournir un lien donnant plus d’informations sur les 19 cycles contre 1 dont vous parlez? Quelque chose de spécifique à propos de votre DSP.
Vladimir Cravero
1
Merci pour les réponses. Voici une fiche technique pour mon microcontrôleur: ww1.microchip.com/downloads/fr/DeviceDoc/70005127c.pdf . Voir Vue d'ensemble du jeu d'instructions à partir de la page 292. Il est indiqué que toutes les instructions DIV prennent 18 cycles, tandis que toutes les instructions MUL ne prennent qu'un cycle. Mais ce n'est pas commun que pour ce MCU, j'ai vu cela dans de nombreux autres MCU.
Marko Gulin le
2
@ Curd, eh bien, ils sont à peu près les mêmes, n'est-ce pas. Sont pour moi. Je ne pense pas que cela illustre aussi bien que vous pouvez l'imaginer.
TonyM
1
L'autre facteur est l'économie et les modèles d'utilisation. La plupart des usages invoquent se multiplient beaucoup plus souvent que diviser. Déduire une grande surface de silicium pour une fonction de division matérielle plus rapide qui sera utilisée relativement peu fréquemment est une solution peu rentable. Mieux vaut créer une puce plus petite et moins chère, ou utiliser la logique supplémentaire de manière plus productive. BTW quand j'ai commencé avec les mini-ordinateurs, diviser n'était pas toujours une instruction. Sur certaines machines, il s’agissait d’un appel de bibliothèque de logiciels, comme la racine carrée.
nigel222

Réponses:

34

Un séparateur correspond beaucoup moins élégamment à un matériel typique. Prenons les exemples de FPGA LCE ICE40.

Comparons deux cas: ce multiplicateur de 8x8 bits à 16 bits:

module multiply (clk, a, b, result);
   input clk;
   input [7:0]a;
   input [7:0]b;
   output [15:0]result;
   always @(posedge clk)
     result = a * b;
endmodule // multiply

et ce diviseur qui réduit les opérandes de 8 et 8 bits à un résultat de 8 bits:

module divide(clk, a, b, result);
   input clk;
   input [7:0] a;
   input [7:0] b;
   output [7:0] result;
   always @(posedge clk)
     result = a / b;
endmodule // divide

(Oui, je sais, l'horloge ne fait rien)

Une vue d' ensemble du schéma généré lors du mappage du multiplicateur à un ICE40 FPGA peuvent être trouvées ici et le diviseur ici .

Les statistiques de synthèse de Yosys sont:

multiplier

  • Nombre de fils: 155
  • Nombre de bits de fil: 214
  • Nombre de fils publics: 4
  • Nombre de bits de fil publics: 33
  • Nombre de mémoires: 0
  • Nombre de bits de mémoire: 0
  • Nombre de processus: 0
  • Nombre d'alvéoles: 191
    • SB_CARRY 10
    • SB_DFF 16
    • SB_LUT4 165

diviser

  • Nombre de fils: 145
  • Nombre de bits de fil: 320
  • Nombre de fils publics: 4
  • Nombre de bits de fil publics: 25
  • Nombre de mémoires: 0
  • Nombre de bits de mémoire: 0
  • Nombre de processus: 0
  • Nombre d'alvéoles: 219
    • SB_CARRY 85
    • SB_DFF 8
    • SB_LUT4 126

Il est à noter que la taille du verilog généré pour un multiplicateur de largeur et un diviseur divisant au maximum ne sont pas si extrêmes. Cependant, si vous regardez les images ci-dessous, vous remarquerez que le multiplicateur a peut-être une profondeur de 15, alors que le diviseur ressemble davantage à une cinquantaine; le chemin critique (c.-à-d. le plus long chemin pouvant se produire en cours de fonctionnement) est ce qui définit la vitesse!


De toute façon, vous ne pourrez pas lire ceci pour avoir une impression visuelle. Je pense que les différences de complexité sont possibles à repérer. Ce sont des multiplicateurs / diviseurs à cycle unique!

Multiplier

Multiplier sur un ICE40 (avertissement: image ~ 100 Mpixel)

Image à l'échelle du multiplicateur

Diviser

( Diviser sur un ICE40 ) (avertissement: image ~ 100 Mpixel)

Image à l'échelle du diviseur

Marcus Müller
la source
4
non, vous pouvez les implémenter de manière non itérative. Mais cela prendra simplement un certain temps avant que le résultat valide "se répande" dans la logique. Les implémentations ci-dessus ne sont pas itératives.
Marcus Müller
9
Je veux une affiche murale du diviseur.
Ian Howson
5
Il y a un PDF maintenant dans la multiplication GIST. C'est 3378 × 3177 mm, donc s'il vous plaît discuter avec votre autre significatif avant de mettre cela sur le plafond de la chambre.
Marcus Müller
2
Vos images de 100 mégapixels sont impressionnantes, mais dépassent vos objectifs et posent de gros problèmes à quiconque tente d'afficher cette page sur un appareil disposant d'une mémoire limitée, telle qu'un téléphone ou une tablette. Si vous souhaitez afficher les images en ligne, veuillez trouver un moyen de produire un aperçu de résolution inférieure.
Dave Tweed
4
Yo, ces graphiques graphviz sont hors de propos, yo!
Spencer Williams le
8

La division lente est intrinsèquement itérative, elle a donc tendance à prendre plus de temps. Il existe des algorithmes de division lente un peu plus rapides que les simples, utilisant des tables de consultation. L'algorithme SRT produit deux bits par cycle. Une erreur dans un tel tableau était la cause du fameux bogue Pentium FDIV (environ 1994). Il existe ensuite des algorithmes dits de division rapide.

Bien sûr, en principe, vous pouvez simplement utiliser une table de recherche volumineuse pour calculer le produit ou le quotient de deux nombres, et obtenir ainsi des résultats en un seul cycle, mais cela tend à devenir rapidement peu pratique lorsque le nombre de bits par nombre augmente.

Spehro Pefhany
la source
Mais au final, les algorithmes de division ne peuvent être parallélisés, contrairement aux algorithmes de multiplication, et c’est pourquoi ils sont tellement plus lents?
Marko Gulin le
2
@ MarkoGulin "ne peut pas" est une affirmation très forte. Ce n'est certainement pas simple.
Spehro Pefhany
2
Je pense que vous pourriez l'affaiblir: "les algorithmes de division ne peuvent pas être parallélisés" et "les moyens que nous avons trouvés de paralléliser la division sont plus contraignants pour le matériel mettant en œuvre la division que la multiplication parallélisée". Sphero donne un exemple de la division en un cycle en utilisant des portes O (2 ^ n) pour multiplier des nombres à n bits ... mais ce n'est tout simplement pas pratique.
Cort Ammon - Réintégrer Monica le
1
Une division longue peut exploiter le parallélisme à tout degré souhaité en calculant une réciproque approximative qui, multipliée par le diviseur, donne un résultat de la forme 1000 ... xxxx, il est facile de travailler avec un diviseur sous une forme de ce type avec N calculer N bits du résultat à chaque étape.
Supercat
8

Nous pouvons avoir plusieurs couches de logique par cycle d'horloge, mais il existe une limite. Le nombre de couches de logique pouvant être complexes dépend de notre vitesse d'horloge et de notre processus de semi-conducteur.

Cependant, il existe de nombreux algorithmes de multiplication différents, et je ne sais pas lequel des microcontrôleurs peut être utilisé.

Une multiplication surtout dans les ordinateurs utilise une variante de la multiplication longue binaire. La multiplication longue binaire implique

  • Déplacement d'un opérande de différents montages
  • Masquer les numéros décalés en fonction du deuxième opérande
  • Additionner les résultats du masquage ensemble.

Voyons donc comment implémenter ceci dans le matériel.

  • Changer de poste dépend simplement de la façon dont nous câblons les choses, alors tout est gratuit.
  • Le masquage nécessite ET les portes. Cela signifie une couche de logique, donc d'un point de vue temporel, c'est bon marché.
  • L'addition est relativement coûteuse en raison de la nécessité d'une chaîne de portage. Heureusement, il existe un truc que nous pouvons utiliser. Pour la plupart des étapes d'addition plutôt que d'ajouter deux nombres pour en produire un, nous pouvons en ajouter trois pour en produire deux.

Voyons donc combien d’étapes logiques nous avons besoin pour un multiplicateur 8x8 avec des résultats 16 bits. Par souci de simplicité, supposons que nous n'essayons pas d'optimiser le fait que tous les résultats intermédiaires ne comportent pas de bits dans toutes les positions.

Supposons qu'un additionneur complet soit implémenté en deux "étapes de porte".

  • 1 pour masquer pour produire 8 résultats intermédiaires.
  • 2 pour ajouter des groupes de trois nombres afin de réduire les 8 résultats intermédiaires à 6
  • 2 pour ajouter des groupes de trois nombres afin de réduire les 6 résultats intermédiaires à 4
  • 2 pour ajouter un groupe de trois nombres afin de réduire les 4 résultats intermédiaires à 3
  • 2 pour ajouter un groupe de trois nombres afin de réduire les 3 résultats intermédiaires à 2
  • 32 pour additionner les deux résultats finaux.

Donc, environ 46 étapes logiques au total. La plupart sont dépensés pour additionner les deux derniers résultats intermédiaires.

Cela pourrait être encore amélioré en exploitant le fait que tous les résultats intermédiaires n’ont pas tous les bits présents (c’est essentiellement ce que fait le multiplicateur dada), en utilisant un additionneur porteur à la lecture pour la dernière étape. En ajoutant 7 nombres pour produire 3 au lieu de trois, deux (réduire le nombre d'étapes au prix de plusieurs portes et de portes plus larges), etc.

Ce n’est que des détails mineurs, mais l’important est que le nombre d’étapes nécessaires pour multiplier deux nombres de n bits et produire un résultat de 2n bits est à peu près proportionnel à n.


D'autre part, si nous examinons les algorithmes de division, nous constatons qu'ils ont tous un processus itératif.

  1. Ce qui est fait lors d'une itération dépend énormément des résultats de l'itération précédente.
  2. le nombre d'étapes logiques nécessaires pour mettre en oeuvre une itération est approximativement proportionnel à n (la soustraction et la comparaison sont très similaires en complexité à l'addition)
  3. le nombre d'itérations est également à peu près proportionnel à n.

Ainsi, le nombre d'étages logiques nécessaires pour mettre en œuvre la division est à peu près proportionnel à n carré.

Peter Green
la source
Merci pour votre réponse. J'ai lu sur Wiki que l'algorithme de Dadda est très efficace en ce qui concerne le nombre requis de portes pour implémenter cet algorithme sur du matériel. Malgré cela, la plupart du matériel utilise "la multiplication longue binaire"?
Marko Gulin le
1
J'ai l'impression que l'algotihm de dada est une version optimisée de la multiplication binaire longue.
Peter Green
Je brûle 8 cycles pour faire une division 1 / x. Je l’utilise ensuite contre une multiplication de 8 cycles pour un coût fixe de 16 cycles.
b degnan
Cela montre bien que la multiplication n’est pas si pire que l’addition, après tout.
Hagen von Eitzen
1
Une itération nécessite une soustraction pouvant être effectuée en étapes O (lgN) en utilisant du matériel O (NlgN) ou en étapes O (sqrt (N)) en utilisant du matériel O (N). Le point essentiel, cependant, est que la multiplication nécessite des étapes O (lgN), tandis que la division nécessite des étapes O (NlgN). Pas O (N * N) mais plus grand que la multiplication par un facteur de O (N) à moins de commencer par prendre une approximation réciproque approximative afin de permettre plus de travail par étape.
Supercat
4

Un algorithme de division (en fait n'importe quel algorithme) peut être créé en un cycle d'horloge. Si vous êtes prêt à payer pour les transistors supplémentaires et la fréquence d'horloge autorisée inférieure.

Supposons que vous ayez un ensemble de portes qui implémente un cycle d'horloge d'un algorithme de division à plusieurs cycles existant. Pour rendre l'algorithme cycle unique, utilisez plusieurs étapes de matériel (similaire à celle utilisée dans une étape de l'algorithme à cycles multiples), la sortie d'une étape alimentant l'étape suivante.

Bien sûr, la raison pour ne pas le faire de cette façon est qu'il utilise beaucoup de transistors. Par exemple, pour une division de 16 bits, il peut utiliser près de 16 transistors supplémentaires. De plus, le fait d'avoir plus d'étages de portes abaisse la fréquence d'horloge maximale autorisée (car il y a plus d'étages de délai de propagation).

utilisateur4574
la source
4

Les algorithmes de division pratiques sont tous basés sur des suites numériques convergeant vers le quotient.

  • Il existe des méthodes additives, telles que la non-restauration ou la SRT, qui consiste à ajouter ou supprimer 2 ^ N au quotient et à ajouter ou supprimer en conséquence le 2 ^ N * diviseur du reste partiel jusqu'à ce qu'il ait convergé vers zéro.

  • Il existe des méthodes multiplicatives, telles que Newton-Raphson ou Goldshmidth, qui sont des méthodes de recherche de racine dans lesquelles la division est calculée comme étant l'inverse de la multiplication.

Les méthodes additives donnent un ou quelques bits par cycle. Les méthodes multiplicatives doublent le nombre de bits pour chaque cycle mais nécessitent une approximation initiale, souvent obtenue avec une table constante.

Les dénominations "lente" et "rapide" sont trompeuses, car la vitesse réelle dépend du nombre de bits, de la quantité de matériel utilisée pour la fonction (et un multiplicateur rapide est très grand) ...

La division est plus lente que la multiplication car il n'y a pas de méthode directe et parallèle pour la calculer: soit il y a une itération, soit le matériel est copié pour implémenter l'itération sous forme de blocs en cascade (ou en pipeline).

TEMLIB
la source
0

Pourquoi la division du matériel prend-elle tellement plus de temps que la multiplication sur un microcontrôleur?

Ce n'est pas une question d'électronique. Au mieux, il s’agit d’une question informatique, mieux adressée à Stack Overflow.

Voir, par exemple, ici: La multiplication est-elle plus rapide que la division float?

En réalité, il s’agit d’une question de la vraie vie: pourquoi la division prend-elle plus de temps que la multiplication?

Que préféreriez-vous calculer sur papier?

51 * 82

ou

4182 / 51

La division prend plus de temps que la multiplication parce que c'est plus difficile à faire .

Nick Gammon
la source