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

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?

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.

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.

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.

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.

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.

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.

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.

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.

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.