Pourquoi la division est-elle tellement plus complexe que les autres opérations arithmétiques?

39

J'ai récemment rencontré un cas où j'avais besoin d'une opération de division entière sur une puce qui en manquait une (ARM Cortex-A8). En essayant de rechercher pourquoi cela doit être, j'ai découvert qu'en général, la division nécessite beaucoup plus de cycles que l'addition, la soustraction ou la multiplication sur à peu près n'importe quelle architecture entière (ou à virgule fixe). pourquoi est-ce le cas? N'est-il pas représentable avec une logique AND à deux couches comme tout le reste?

Phonon
la source

Réponses:

34

La division est un algorithme itératif dans lequel le résultat du quotient doit être décalé vers le reste à l'aide d'une mesure euclidienne, voir 2 ; alors que la multiplication peut être réduite à une série (fixe) d’astuces de manipulation de bits.

aterrel
la source
2
Auparavant, la multiplication et la division étaient des opérations lentes. De nos jours, la multiplication est un peu plus rapide (mais légèrement plus lente que l'addition / soustraction), mais la division est toujours plus lente que les autres. Je crois que Newton-Raphson est encore utilisé en interne par la plupart des gens pour faire alterner un nombre.
JM
12
(Hors sujet: "Les opérations inverses sont généralement difficiles. Il suffit de regarder l'intégration par rapport à la différenciation." facile.)
JM
1
D'accord, je vais laisser tomber en disant que la cubature est une boîte de Pandore différente; mais au moins dans le cas unidimensionnel, la quadrature est plus facile que la différenciation.
JM
1
Dans tous les cas, les inverses viennent toujours par paires. Pourquoi voudriez-vous appeler l'un le "opération" et l'autre le "inverse"?
David Ketcheson
2
Ni itération ni inverse ne le rend plus difficile. La dureté de la division provient du fait que vous devez déplacer le résultat du quotient au reste en utilisant une mesure euclidienne. Voir le théorème de l'algorithme de division .
20

Bien que tous les processeurs actuels semblent utiliser une approche itérative, comme le suggère aterrel , des travaux ont été réalisés sur les approches non itératives. La division à virgule flottante et la racine carrée à précision variable parlent d’une implémentation non itérative de la division et de la racine carrée à virgule flottante dans un FPGA , à l’aide de tables de recherche et d’agrandissement de la série Taylor.

Je pense que les mêmes techniques peuvent permettre de réduire ces opérations à un seul cycle (débit, sinon latence), mais vous aurez probablement besoin de tables de recherche énormes , et donc de trop grandes zones de silicium pour le faire. .

Pourquoi ne serait-ce pas faisable?

Lors de la conception de processeurs, de nombreux compromis sont nécessaires. La fonctionnalité, la complexité (nombre de transistors), la vitesse et la consommation d'énergie sont toutes liées et les décisions prises lors de la conception peuvent avoir un impact considérable sur les performances.

Un processeur moderne pourrait probablement avoir une unité principale à virgule flottante qui dédie suffisamment de transistors sur le silicium pour effectuer une division en virgule flottante en un seul cycle , mais il ne serait probablement pas une utilisation efficace de ces transistors.

La multiplication des virgules flottantes a fait cette transition d'itératif à non itératif il y a une décennie. De nos jours, la multiplication , voire l'accumulation , d'un cycle est courante, même dans les processeurs mobiles.

Avant que cela devienne une utilisation efficace du budget des transistors, la multiplication, comme la division, était souvent effectuée par une méthode itérative. À l’époque, les processeurs DSP dédiés pouvaient dédier la majeure partie de leur silicium à une seule unité d’ accumulation rapide (MAC) . Un processeur Core2duo a une latence multipliée à virgule flottante de 3 (la valeur sort du pipeline 3 cycles après son entrée dans le pipeline), mais peut avoir 3 multiplications en même temps, générant ainsi un débit en un seul cycle, tandis que l'unité SSE2 peut pomper plusieurs multiplications FP en un seul cycle.

Au lieu de dédier de grandes surfaces de silicium à une unité de division à un cycle, les CPU modernes disposent de plusieurs unités, chacune pouvant effectuer des opérations en parallèle, mais optimisées pour leurs propres situations. En fait, une fois que vous prenez en compte SIMD instructions telles que SSE ou la CPU graphique intégrée du Sandy Bridge ou CPU plus tard ce, il peut y avoir beaucoup de ces unités de division à virgule flottante sur votre CPU.

Si la division générique en virgule flottante était plus importante pour les processeurs modernes, il serait peut-être logique de dédier suffisamment de surface de silicium pour en faire un cycle, mais la plupart des fabricants de puces ont évidemment décidé de pouvoir mieux utiliser ce silicium en utilisant ces portes à d'autres fins. . Ainsi, une opération est plus lente, mais dans l’ensemble (pour les scénarios d’utilisation typiques), le processeur est plus rapide et / ou consomme moins d’énergie.

Mark Booth
la source
À ma connaissance, aucun composant n’a de latence de division à cycle unique pour virgule flottante. Par exemple, les tableaux d'instructions d'Agner Fog pour les processeurs Intel, AMD et VIA répertorient DIVPS (division à virgule flottante emballée SSE) selon 10-14 cycles. Je ne trouve aucun matériel avec des instructions de division à cycle unique, mais je serais prêt à me tromper. Ce n'est pas commun pour autant que je puisse dire.
Bill Barth
@ Bill - Merci, vous avez raison. Je suis sûr que j'ai déjà vu des opérations de division à cycle unique dans des puces DSP, alors je suppose que cela aurait été transféré au bureau, comme le faisait la multiplication à cycle unique, mais je ne trouve aucune référence pour le moment. J'ai mis à jour ma réponse et ajouté quelques informations pertinentes sur les méthodes non itératives qui pourraient le permettre à l'avenir. Il est étonnant de penser que la division n’est pas plus efficace par cycle maintenant que lorsque j’utilisais des transputeurs.
Mark Booth
1
Je pense que les DSP font cela en limitant la plage dans laquelle ils sont précis. C'est la même stratégie que celle utilisée pour la recherche + interpolation pour la racine carrée.
Matt Knepley
1
Je ne suis cependant pas sûr de la latence d'une telle division. À 4 GHz, effectuer un aller-retour vers la table de consultation en moins de N cycles limite fortement la taille potentielle de cette table (par exemple, les caches L1 stagnent à 32K chacun). Le fait de passer à la 3D aiderait à augmenter ce taux (mais pose un défi au refroidissement). Avez-vous une idée de la latence qui pourrait être atteinte avec les processeurs modernes 4GHz / 5GHz?
Matthieu M.
1
Pour les nombres de divps / divpd vs latence mulps / mulpd et débit, voir Division multiplication à virgule flottante vs multiplication à virgule flottante . J'ai pris des données dans les tableaux d'instructions d'Agner Fog et les ai mises en forme de manière à résumer le débit et la latence div et mul, pour une largeur simple ou double et pour différentes largeurs de vecteur SIMD. (Les puces Intel ont généralement un diviseur SIMD qui ne représente que la moitié de la largeur des autres ALU vectorielles.)
Peter Cordes