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 k
sont 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 n
cycles pour terminer la division, alors qu'il n
existe 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.
la source
Réponses:
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:
et ce diviseur qui réduit les opérandes de 8 et 8 bits à un résultat de 8 bits:
(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
diviser
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)
Diviser
( Diviser sur un ICE40 ) (avertissement: image ~ 100 Mpixel)
la source
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.
la source
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.
Une multiplication surtout dans les ordinateurs utilise une variante de la multiplication longue binaire. La multiplication longue binaire implique
Voyons donc comment implémenter ceci dans le matériel.
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".
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.
Ainsi, le nombre d'étages logiques nécessaires pour mettre en œuvre la division est à peu près proportionnel à n carré.
la source
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).
la source
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).
la source
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?
ou
La division prend plus de temps que la multiplication parce que c'est plus difficile à faire .
la source