Pourquoi l'addition est-elle aussi rapide que les opérations en bits dans les processeurs modernes?

73

Je sais que les opérations binaires sont très rapides sur les processeurs modernes, car ils peuvent fonctionner en parallèle sur 32 ou 64 bits. Les opérations binaires ne prennent donc qu'un cycle d'horloge. Toutefois, l’ajout est une opération complexe qui consiste en au moins une, voire une douzaine d’opérations par bits, de sorte que j’ai naturellement pensé que ce serait 3 à 4 fois plus lent. J'ai été surpris de voir, après un simple repère, que l'addition est exactement aussi rapide que les opérations en bits (XOR, OR, AND, etc.). Quelqu'un peut-il faire la lumière sur cette question?

Anonyme
la source
1
Oui, la multiplication a été assez rapide dans mes tests aussi. C'était seulement environ 2x plus lent que l'addition, alors que la division était environ 30x (!) Fois plus lente.
Anonyme
Présentation compacte des derniers ajouteurs d'
Franki
Plus élaboré: thèse juin thèse de doctorat de Chen "structures préfixe parallèle pour binaire et modulo {2n-1, 2n, 2n + 1} sommateurs" digital.library.okstate.edu/etd/Chen_okstate_0664D_10070.pdf
Franki

Réponses:

104

L'addition est rapide car les concepteurs d'UC ont mis en place les circuits nécessaires pour la rendre rapide. Cela prend beaucoup plus de portes que d'opérations au niveau des bits, mais il est assez fréquent que les concepteurs de CPU aient jugé que cela en valait la peine. Voir https://en.wikipedia.org/wiki/Adder_(electronics) .

Les deux peuvent être assez rapides pour être exécutés dans un seul cycle de la CPU. Ils ne sont pas aussi rapides - un ajout nécessite plus de portes et plus de temps de latence qu'une opération bit par bit - mais il est suffisamment rapide pour qu'un processeur puisse le faire en un seul cycle d'horloge. Il existe une surcharge de temps de latence par instruction pour la logique de décodage et de commande des instructions. Cette latence est nettement supérieure à la latence nécessaire pour effectuer une opération au niveau du bit, de sorte que la différence entre les deux est absorbée par cette surcharge. Les réponses d' Apogrammer et de Paul92 expliquent bien ces effets.

DW
la source
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter .
DW
38

Il y a plusieurs aspects.

  • Le coût relatif d'une opération au niveau des bits et d'un ajout. Un additionneur naïf aura une profondeur de grille qui dépend linéairement de la largeur du mot. Il existe des approches alternatives, plus coûteuses en termes de portes, qui réduisent la profondeur (la profondeur dépend alors de manière logarithmique de la largeur du mot). D'autres ont donné des références pour de telles techniques. Je soulignerai simplement que la différence est également moins importante que ce qui peut sembler juste en considérant le coût de l'opération en raison de la nécessité d'une logique de contrôle qui ajoute des délais.

  • Ensuite, il y a le fait que les processeurs sont généralement cadencés (je suis au courant de recherches ou de conceptions non cadencées spéciales, mais je ne suis même pas sûr que certaines soient disponibles dans le commerce). Cela signifie que quelle que soit la vitesse d'une opération, elle prendra un multiple entier du cycle d'horloge.

  • Enfin, il y a les considérations micro-architecturales: êtes-vous sûr de mesurer ce que vous voulez? De nos jours, les processeurs ont tendance à être en pipeline, multi-scalaires, avec une exécution dans le désordre et ainsi de suite. Cela signifie qu'ils sont capables d'exécuter plusieurs instructions en même temps, à différents stades d'achèvement. Si vous voulez montrer, à l'aide de mesures, qu'une opération prend plus de temps qu'une autre, vous devez prendre cet aspect en considération, car son objectif est de masquer cette différence. Vous pouvez très bien avoir le même débit pour les opérations d’addition et par bits lors de l’utilisation de données indépendantes, mais une mesure de la latence ou l’introduction de dépendances entre les opérations peut indiquer le contraire. Et vous devez également vous assurer que le goulot d'étranglement de votre mesure réside dans l'exécution, et non par exemple dans les accès mémoire.

Programmateur
la source
6
+1 Oui, la plupart des processeurs sont cadencés, mais quelques processeurs sans horloge sont disponibles dans le commerce.
David Cary
2
Une autre possibilité est qu’un processeur stocke un registre de 64 bits sous la forme d’un bloc de 16 bits et de trois blocs de 17 bits, les bits supplémentaires de chaque bloc contenant un report différé de la base. Un ajout suivi d'une opération au niveau du bit ou d'un magasin peut nécessiter 1 à 2 cycles supplémentaires pour propager le report, mais pas un ajout suivi d'un autre. En outre, dans le cas "magasin", le temps de propagation supplémentaire peut retarder les performances du magasin, mais il ne serait pas nécessaire que le code "l'attende".
Supercat
3
@supercat Le Pentium 4 a fait quelque chose comme cela, avec une ALU à double vitesse (par rapport au reste du processeur) qui aurait les 16 ou 32 bits les plus bas prêts pour une opération ultérieure un demi-cycle avant les bits de la moitié supérieure.
Jeffrey Bosboom
2
êtes-vous sûr de mesurer ce que vous voulez? Dans ce cas, la conclusion du PO à partir des mesures s'avère correcte pour la grande majorité des processeurs. L'addition est si courante que les processeurs superscalaires ont des unités ajoutées sur tous les ports d'exécution et les booléens sont si peu coûteux à implémenter (en nombre de transistors) qu'ils sont également présents sur tous les ports. Donc, add et booleans ont presque toujours le même débit (par exemple, 4 par horloge dans Intel Haswell).
Peter Cordes
2
Le nombre entier ajouté par SIMD est souvent inférieur à celui de SIMD booléen, même s’ils ont généralement la même latence. Les processeurs Intel de Pentium II à Broadwell ne peuvent exécuter des ajouts vector-int (par exemple paddw) à 2 par horloge, mais des booléens (comme pand) à 3 par horloge. (Skylake met un additionneur de vecteur sur les trois ports d'exécution de vecteur.)
Peter Cordes
24

Les processeurs fonctionnent par cycles. À chaque cycle, il se passe quelque chose. Généralement, une instruction nécessite plus de cycles à exécuter, mais plusieurs instructions sont exécutées simultanément, dans des états différents.

Par exemple, un processeur simple peut avoir 3 étapes pour chaque instruction: extraire, exécuter et stocker. A tout moment, 3 instructions sont en cours de traitement: une en cours d’extraction, une autre en cours d’exécution et une autre stockant ses résultats. Ceci s'appelle un pipeline et a dans cet exemple 3 étapes. Les processeurs modernes ont des pipelines avec plus de 15 étapes. Toutefois, l'addition, ainsi que la plupart des opérations arithmétiques, sont généralement exécutées en une étape (je parle de l'opération d'ajout de 2 nombres par l'ALU, et non de l'instruction elle-même. En fonction de l'architecture du processeur, l'instruction peut nécessiter plus de cycles pour récupérer les arguments de la mémoire, effectuer des conditions, stocker les résultats dans la mémoire).

La durée d'un cycle est déterminée par le chemin critique le plus long. Fondamentalement, il s’agit du temps le plus long nécessaire à une étape de la ligne de tir. Si vous souhaitez rendre le processeur plus rapide, vous devez optimiser le chemin critique. S'il n'est pas possible de réduire le chemin critique en tant que tel, vous pouvez le scinder en deux étapes du pipeline. Vous pouvez désormais cadencer votre processeur presque deux fois plus souvent (en supposant qu'aucun autre chemin critique ne vous en empêche ). Mais cela vient avec une surcharge: vous devez insérer un registre entre les étapes du pipeline. Ce qui signifie que vous ne gagnez pas vraiment la vitesse 2x (le registre a besoin de temps pour stocker les données), et vous avez compliqué la conception.

Il existe déjà des méthodes assez efficaces pour effectuer une addition (par exemple, des additionneurs à anticipation) et l'addition n'est pas un chemin critique pour la vitesse du processeur, il est donc inutile de la diviser en plusieurs cycles.

Notez également que même si cela peut sembler compliqué pour vous, les opérations matérielles peuvent être effectuées en parallèle très rapidement.

Paul92
la source
3
Les gros frais généraux liés aux pipelines plus longs impliquent davantage de cycles pour récupérer d'une mauvaise prédiction de la branche! Les dépenses en transistors pour la mise en mémoire tampon des données entre les étapes sont mineures ces jours-ci. Même un simple processeur en pipeline doit aller chercher / décoder avant les instructions qui sont en train de s'exécuter. Si le processeur découvre que le système frontal fonctionne sur le mauvais code, car une branche n'a pas suivi le résultat prévu (ou une autre spéculation erronée), il doit abandonner ce travail et partir de la bonne instruction. Les choses ne font qu'empirer avec les CPU superscalar hors service qui peuvent avoir plusieurs insns en vol.
Peter Cordes
12

Les processeurs sont cadencés. Ainsi, même si certaines instructions peuvent clairement être exécutées plus rapidement que d’autres, elles peuvent prendre le même nombre de cycles.

Vous constaterez probablement que le circuit nécessaire au transport des données entre les registres et les unités d'exécution est beaucoup plus compliqué que les additionneurs.

Notez que la simple instruction MOV (register to register) effectue encore moins de calculs que la logique au niveau du bit, mais que les méthodes MOV et ADD prennent généralement un cycle. Si MOV pouvait être créé deux fois plus vite, les processeurs seraient cadencés deux fois plus vite et les ADD seraient de deux cycles.

James Hollis
la source
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter .
Gilles, arrête de faire le mal
1
Résumé de la discussion: certains CPU hors service gèrent MOV spécialement avec le changement de nom de registre, avec une latence nulle. Voir Le MOV de x86 peut-il vraiment être «gratuit»? Pourquoi ne puis-je pas reproduire cela du tout? pour plus de détails sur ce que coûte vraiment le MOV.
Peter Cordes
12

L’addition est suffisamment importante pour ne pas attendre qu’un bit de retenue soit répercuté sur un accumulateur 64 bits: le terme qui le désigne est un additionneur porteur d’observation qui fait essentiellement partie des processeurs à 8 bits (et de leurs ALU) et plus. En effet, les processeurs modernes n'ont généralement pas besoin de beaucoup plus de temps d'exécution pour une multiplication complète: carry-lookahead est en réalité un outil très ancien (et relativement abordable) dans la boîte à outils d'un concepteur de processeur.

utilisateur72735
la source
La multiplication d’entiers représente une latence nettement supérieure et un débit inférieur à ADD sur x86. Mais il est étonnamment rapide compte tenu du nombre d’additionneurs nécessaires pour créer un multiplicateur rapide: par exemple sur Intel depuis Nehalem, et AMD depuis Ryzen, la multiplication d’un nombre entier scalaire de 8/16/32/64 bits correspond à une latence de 3 cycles, avec un débit de un pour 1c. (une unité d'exécution entièrement en pipeline). Cela est nul comparé au débit ADD de 3 ou 4 par horloge, mais est étonnant comparé au temps de latence IMUL à 9 cycles dans Intel Pentium P5. Les choses se ressemblent pour SIMD: la multiplication vectorielle-int correspond à une latence plus élevée et à un débit inférieur à celui de add, mais reste rapide.
Peter Cordes
Donc, oui, multiplier coûtait beaucoup plus cher par rapport aux autres instructions qu'aujourd'hui. Éviter cela avec un coût de plus de 2 instructions ne vaut généralement pas la peine, et parfois même pas un substitut à 2 instructions n'en vaut la peine (par exemple avec un décalage + une leainstruction supplémentaire ).
Peter Cordes
9

Je pense que vous auriez du mal à trouver un processeur dont l'addition nécessitait plus de cycles qu'une opération au niveau des bits. En partie parce que la plupart des processeurs doivent effectuer au moins une addition par cycle d'instructions simplement pour incrémenter le compteur de programme. De simples opérations au niveau des bits ne sont pas si utiles.

(Cycle d'instruction, pas d'horloge - par exemple, le 6502 prend au moins deux cycles d'horloge par instruction car il n'est pas en pipeline et ne contient pas de cache d'instruction.)

Le vrai concept qui vous manque peut-être est celui du chemin critique : dans une puce, l'opération la plus longue pouvant être effectuée en un cycle dicte, au niveau du matériel, la rapidité avec laquelle la puce peut être synchronisée.

L'exception à cette règle est la logique asynchrone (rarement utilisée et à peine commercialisée), qui s'exécute réellement à différentes vitesses en fonction du temps de propagation de la logique, de la température du dispositif, etc.

pjc50
la source
Ce ne sont pas des opérations au niveau des bits contrôlables par l'utilisateur, mais certaines instructions du 8086 (par exemple, effacer l'indicateur d'interruption ) ont nécessité moins de cycles qu'un ajout d'entier. De manière plus abstraite, un système RISC où toutes les instructions ont la taille d’un mot pourrait utiliser un simple compteur binaire pour le PC, ce qui constituerait un circuit beaucoup plus rapide que celui d’un additionneur polyvalent.
Mark
L'addition sur le compteur de programme a tendance à être très simple comparée à une instruction d'arithmétique d'addition, car l'un des opérandes est petit (soit une taille d'instruction, soit un décalage de saut relatif également limité en taille)
Ben Voigt
6502 était en pipeline - il lisait le premier octet de la prochaine instruction au cours du dernier cycle du précédent. Sinon, extraire / décoder / exécuter aurait été d'au moins trois cycles.
gnasher729
8

Au niveau de la porte, vous avez raison de dire qu'il faut plus de travail pour effectuer l'addition, et prend donc plus de temps. Cependant, ce coût est suffisamment insignifiant, peu importe.

Les processeurs modernes sont synchronisés. Vous ne pouvez donner d’instructions qu’à des multiples de cette fréquence. Si les fréquences d'horloge étaient poussées plus haut, pour maximiser la vitesse des opérations au niveau des bits, vous auriez à passer au moins 2 cycles en addition. Une bonne partie de ce temps serait passée à attendre parce que vous n'aviez pas vraiment besoin de 2 cycles complets. Vous avez seulement besoin de 1.1 (ou un chiffre comme celui-là). Maintenant, votre puce ajoute plus lentement que tout le monde sur le marché.

Pire encore, le simple fait d’ajouter ou de faire des opérations sur les bits n’est qu’une partie infime de ce qui se passe au cours d’un cycle. Vous devez être capable d'extraire / décoder des instructions dans un cycle. Vous devez être capable de faire des opérations de cache dans un cycle. Beaucoup d'autres choses se déroulent sur la même échelle de temps que la simple addition ou l'opération au niveau du bit.

Bien entendu, la solution consiste à développer un pipeline extrêmement profond, en décomposant ces tâches en minuscules parties correspondant au temps de cycle défini par une opération au niveau du bit. Le Pentium 4 a montré les limites de la pensée en termes de pipeline profond. Toutes sortes de problèmes se posent. En particulier, il est notoirement difficile de créer des branches, car vous devez vider le pipeline une fois que vous avez les données pour déterminer quelle branche prendre.

Cort Ammon
la source
7

Les processeurs modernes sont synchronisés: chaque opération prend un certain nombre de cycles d'horloge. Les concepteurs du processeur déterminent la durée d'un cycle d'horloge. Il y a deux considérations à prendre en compte: premièrement, la vitesse du matériel, mesurée par exemple en tant que retard d'une seule porte NAND. Cela dépend de la technologie utilisée et des compromis tels que la vitesse par rapport à la consommation d'énergie. Il est indépendant de la conception du processeur. Deuxièmement, les concepteurs décident que la durée d’un cycle d’horloge est égale à n retards d’une porte NAND unique, n pouvant être de 10, 30 ou de toute autre valeur.

Ce choix n limite la complexité des opérations pouvant être traitées en un cycle. Il y aura des opérations qui peuvent être effectuées dans 16 cas, mais pas dans 15 délais NAND. Donc, choisir n = 16 signifie qu'une telle opération peut être effectuée dans un cycle, choisir n = 15 signifie que cela ne peut pas être fait.

Les concepteurs choisiront n pour que de nombreuses opérations importantes puissent être effectuées en un, voire deux ou trois cycles. n sera choisi localement optimal: si vous remplaciez n par n-1, la plupart des opérations seraient un peu plus rapides, mais certaines (celles qui ont vraiment besoin de n délais NAND complets) seraient plus lentes. Si peu d'opérations ralentissaient, de sorte que l'exécution globale du programme est en moyenne plus rapide, vous auriez choisi n-1. Vous auriez aussi pu choisir n + 1. Cela ralentit un peu la plupart des opérations, mais si vous avez beaucoup d'opérations qui ne peuvent pas être effectuées dans n délais mais qui peuvent être effectuées dans des délais n + 1, le processeur sera globalement plus rapide.

Maintenant, votre question: Ajouter et soustraire sont des opérations tellement courantes que vous voulez pouvoir les exécuter en un seul cycle. En conséquence, peu importe que AND, OR etc. puisse s'exécuter plus rapidement: ils ont encore besoin de ce cycle. Bien entendu, l’unité "calculatrice" ET, OU, etc. a beaucoup de temps pour se tordre les pouces, mais cela ne peut être réglé.

Notez que la question de savoir si une opération peut être effectuée dans un délai de l'ordre de n retards NAND est ou non: un ajout, par exemple, peut être effectué plus rapidement en étant un peu intelligent, encore plus rapide en étant très intelligent, toujours un peu plus rapidement en investissant des quantités extraordinaires de matériel Enfin, un processeur peut combiner très rapidement des circuits très coûteux, un peu plus lents et moins chers. Il est donc possible de réaliser une opération assez rapidement en y consacrant plus d'argent.

Vous pouvez maintenant rendre la vitesse d'horloge si élevée / le cycle si court que seules les opérations de bits simples sont exécutées dans un cycle et tout le reste deux ou plus. Cela ralentirait probablement le processeur. Pour les opérations qui prennent deux cycles, il y a généralement une surcharge à déplacer une instruction incomplète d'un cycle à l'autre, donc deux cycles ne signifie pas que vous avez deux fois plus de temps pour l'exécution. Donc, pour faire l'addition en deux cycles, vous ne pouvez pas doubler la vitesse d'horloge.

gnasher729
la source
6

Permettez-moi de corriger quelques points qui ne sont pas mentionnés explicitement dans vos réponses existantes:

Je sais que les opérations au niveau des bits sont tellement rapides sur les processeurs modernes, car ils peuvent fonctionner en parallèle sur 32 ou 64 bits,

C'est vrai. Marquer une CPU comme "XX" bits signifie généralement (et pas toujours) que la plupart de ses structures communes (largeurs de registre, RAM adressable, etc.) ont une taille de XX bits (souvent "+/- 1" ou similaire). Mais en ce qui concerne votre question, vous pouvez sans risque supposer qu’une CPU avec 32 bits ou 64 bits effectuera toute opération de bits de base sur 32 ou 64 bits en temps constant.

donc les opérations au niveau des bits ne prennent qu'un cycle d'horloge.

Cette conclusion n'est pas nécessairement le cas. En particulier, les processeurs dotés de jeux d’instructions riches (google CISC ou RISC) peuvent facilement prendre plus d’un cycle, même pour des commandes simples. Avec l'entrelacement, même des commandes simples peuvent se décomposer en fetch-exec-store à 3 horloges (à titre d'exemple).

Cependant, l'addition est une opération complexe

Non, l'addition d'entiers est une opération simple. soustraction aussi bien. Il est très facile d'implémenter des additionneurs dans un matériel complet, et ils font leur travail aussi instantanément que des opérations de bits élémentaires.

qui consiste en au moins une, voire une douzaine d’opérations au niveau des bits, j’ai donc naturellement pensé que ce serait 3 à 4 fois plus lent.

Cela prendra 3 à 4 fois plus de transistors, mais en comparaison avec la vue d'ensemble qui est négligeable.

J'ai été surpris de voir après un repère simple que l'ajout est exactement aussi rapide que n'importe quelle opération au niveau du bit (XOR, OR, AND, etc.). Quelqu'un peut-il faire la lumière sur cette question?

Oui: l'addition d'entiers est une opération au niveau du bit (avec quelques bits de plus que les autres, mais quand même). Il n'y a pas besoin de faire quoi que ce soit par étapes, pas besoin d'algorithmes compliqués, d'horloges ou quoi que ce soit d'autre.

Si vous souhaitez ajouter plus de bits que votre architecture de processeur, vous serez pénalisé d'avoir à le faire par étapes. Mais cela se situe à un autre niveau de complexité (niveau de langage de programmation, pas de niveau d'assemblage / de code machine). C’était un problème courant dans le passé (ou aujourd’hui sur les petits processeurs embarqués). Pour les PC, etc., leurs 32 ou 64 bits suffisent pour que les types de données les plus courants puissent devenir un point discutable.

AnoE
la source
Il est intéressant de noter que réduire le coût en temps de l'addition de O (N) à O (sqrt (N)) n'augmente pas de manière significative le nombre requis de transistors ou la complexité du routage (chaque étape doit simplement laisser un fil de transport s'introduire par le dessous , et il doit y avoir des étapes de fusion supplémentaires (N). Le coût en temps peut être réduit à O (lgN) au prix de transistors O (lgN), mais dans de nombreux cas, il peut être utile de traiter quelque chose comme un 64- addition de bits comme par exemple huit ajouts de 8 bits (en utilisant le transfert sqrtN) joints à trois couches de logique de fusion, plutôt que 64 ajouts de 1 bit avec six couches de fusion.
Supercat
Ouais, les additionneurs sont assez simples. Ce qui est vraiment impressionnant, ce sont les CPU x86 modernes dotés d’un multiplicateur entier 64 bits à latence 3-pipelings . (par exemple, imul rax, rcxa une latence de 3c et un débit par unité sur la famille Intel Sandybridge et sur AMD Ryzen). Même la multiplication complète 64 bits (produisant le résultat 128 bits dans rdx: rax) a les mêmes temps de latence et de débit, mais est implémentée à 2 uops (qui s'exécutent en parallèle sur des ports différents). (Voir agner.org/optimize pour des tableaux d'instructions et un excellent guide de microarch).
Peter Cordes
[add-with-carry] se situe à un autre niveau de complexité (niveau de langage de programmation, pas de niveau d'assemblage / de code machine . Cela dépend du langage. Le compilateur CA qui cible un processeur 16 bits doit émettre un add / adc pour vous lorsqu'il compile ajout de deux uint32_tvaleurs. Ceci est toujours d'actualité pour int64_t sur les cibles 32 bits. L'AVR étant un microcontrôleur RISC 8 bits, les entiers 32 bits nécessitent donc 4 instructions: godbolt.org/g/wre0fM
Peter Cordes
Oui, @PeterCordes, c'est ce que je voulais dire, j'ai clarifié un peu ma phrase.
AnoE