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

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?

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.

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.