Est la multiplication entière vraiment la même vitesse que l'addition sur le CPU moderne

non, ils n'ont pas la même vitesse. Qui vous a dit cela?

Agner le Brouillard de l'instruction tables montrent que lors de l'utilisation d'entier de 32 bits des registres, Haswell est ADD/SUB prendre de 0,25–1 cycles (selon comment bien pipeline des instructions), tandis que MUL prend 2-4 cycles. Le point flottant est l'inverse: les ADDSS / SUBSS prennent de 1 à 3 cycles, tandis que les MULSS prennent de 0,5 à 5 cycles.

il s'agit d'une réponse encore plus complexe que la simple multiplication par opposition à l'addition. En réalité, la réponse ne sera probablement jamais oui. La Multiplication, par voie électronique, est un circuit beaucoup plus compliqué. La plupart des raisons pour lesquelles, est que la multiplication est l'acte d'une étape de multiplication suivie d'une étape d'addition, rappelez-vous ce que c'était que de multiplier des nombres décimaux avant d'utiliser une calculatrice.

l'autre chose à se rappeler est que la multiplication prenez plus ou moins de temps selon l'architecture du processeur sur lequel vous l'exécutez. Cela peut ou peut ne pas être simplement une société particulière. Alors qu'un AMD sera très probablement différent d'un Intel, même un Intel i7 peut être différent d'un core 2 (au sein de la même génération), et certainement différent d'une génération à l'autre (en particulier plus on remonte en arrière).

en toute technicité, si les multiples étaient la seule chose que vous faisiez (sans bouclage, comptage, etc...), les multiplications seraient 2 à (comme on l'a vu sur les architectures PPC) 35 fois plus lentes. C'est plus un exercice de compréhension de l'architecture et de l'électronique.

En Outre: Il est à noter qu'un processeur peut être construit pour lequel toutes les opérations, y compris une horloge à prises multiples, peuvent être effectuées. Ce que ce processeur devrait faire est, se débarrasser de tous les pipelinages, et ralentir l'horloge de sorte que la latence HW de tout circuit OPs est inférieure ou égale à la latence fournie par le chronomètre.

pour ce faire se débarrasserait des gains de performance inhérents que nous sommes en mesure d'obtenir en ajoutant pipelinage dans un processeur. Le pipelinage est l'idée de prendre une tâche et de la décomposer en de plus petites sous-tâches qui peuvent être effectuées beaucoup plus rapidement. En stockant et en transmettant les résultats de chaque sous-tâche entre les sous-tâches, nous pouvons maintenant exécuter un rythme d'horloge plus rapide qui ne doit tenir compte que de la latence la plus longue des sous-tâches, et non de la tâche globale dans son ensemble.

image du temps à travers un multiplicateur:

|--------------------------------------------------| Non Pipelining

|--Étape 1--|--L'Étape 2--|--Étape 3--|--Étape 4--|--Étape 5--| Pipeline

dans le schéma ci-dessus, le circuit non pipelé prend 50 unités de temps. Dans la version à pipelinette, nous avons divisé les 50 unités en 5 étapes chacune en prenant 10 unités de temps, avec une étape de stockage dans entre. Il est extrêmement important de noter que dans l'exemple à la pipeline, chacune des étapes peut fonctionner complètement seule et en parallèle. Pour qu'une opération soit terminée, elle doit passer par les 5 étapes dans l'ordre, mais une autre de la même opération avec les opérandes peut être à l'étape 2 comme une est à l'étape 1, 3, 4, et 5.

avec tout cela étant dit, cette approche pipelinée nous permet de remplir en continu l'opérateur chaque cycle d'horloge, et obtenir un résultat sur chaque cycle d'horloge si nous sommes en mesure de commander nos opérations de sorte que nous pouvons effectuer toutes les opérations avant de passer à une autre opération, et tout ce que nous prenons comme un coup de synchronisation est la quantité originale d'horloges nécessaires pour obtenir la première opération hors du pipeline.

Mystical soulève un autre bon point. Il est également important d'examiner l'architecture d'un point de vue plus systémique. Il est vrai que les nouvelles architectures Haswell ont été construites pour améliorer la multiplier les performances à l'intérieur du processeur. Pour cette raison, au niveau du système, il a été conçu pour permettre à plusieurs multiplications de se produire en simultanéité versus un add qui ne peut se produire qu'une seule fois par horloge système.

tout cela peut se résumer comme suit:

1. chaque architecture est différente d'un point de vue HW de niveau inférieur ainsi que d'un point de vue système
2. fonctionnellement, un multiplier prendra toujours plus de temps qu'un complément, car il combine un vrai multiplier avec une vraie outre l'étape.
3. comprenez l'architecture sur laquelle vous essayez d'exécuter votre code, et trouvez le juste équilibre entre la lisibilité et obtenir la meilleure performance de cette architecture.

Cela dépend vraiment de votre machine. Bien sûr, la multiplication entière est assez complexe par rapport à l'addition, mais pas mal D'AMD CPU peuvent exécuter une multiplication en un seul cycle . C'est tout aussi rapide que l'addition.

D'autres CPU prennent trois ou quatre cycles pour faire une multiplication, qui est un peu plus lente que l'addition. Mais il est loin de la pénalité de performance que vous avez dû subir Il ya dix ans (à l'époque une multiplication de 32 bits pourrait prendre une trentaine de cycles sur certains CPU).

donc, oui, la multiplication est dans la même classe de vitesse de nos jours, mais non, ce n'est toujours pas aussi rapide que l'addition sur tous les CPU.

une multiplication nécessite une étape finale d'une addition de, au minimum, la même taille du nombre; il faudra donc plus de temps qu'une addition. En décimal:

    123
    112
   ----
   +246  ----
   123      | matrix generation  
  123    ----
  -----
  13776 <---------------- Addition

même chose en binaire, avec une réduction plus élaborée de la matrice.

cela dit, les raisons pour lesquelles ils peuvent prendre la même quantité de temps:

1. pour simplifier l'architecture pipelinière, toutes les instructions régulières peuvent être conçues pour prenez la même quantité de cycles (les exceptions sont les mouvements de mémoire par exemple, qui dépendent du temps qu'il faut pour parler à la mémoire externe).
2. Depuis l'additionneur pour l'étape finale du multiplicateur est juste comme l'additionneur pour un complément d'instruction... pourquoi ne pas utiliser le même adder en sautant la génération de matrice et la réduction? S'ils utilisent la même adder, alors évidemment ils prendront la même quantité de temps.

bien sûr, il ya plus complexe architectures où ce n'est pas le cas, et vous pourriez obtenir des valeurs complètement différentes. Vous avez aussi des architectures qui prennent plusieurs instructions en parallèle quand elles ne dépendent pas l'une de l'autre, et alors vous êtes un peu à la merci de votre compilateur... et du système d'exploitation.

la seule façon d'exécuter ce test de façon rigoureuse, vous auriez à exécuter dans l'assemblage et sans un système d'exploitation - sinon, il ya trop de variables.

même si c'était le cas, cela nous dit principalement quelle restriction l'horloge met sur notre matériel. Nous ne pouvons pas pointer plus haut à cause de la chaleur(?), mais le nombre de portes D'instruction ADD un signal peut passer pendant une horloge peut être très grand mais une seule instruction ADD n'en utilise qu'une seule. Ainsi, bien qu'il puisse, à un moment donné, prendre autant de cycles d'horloge, le temps de propagation des signaux n'est pas entièrement utilisé.

si on pouvait pointer plus haut, on pourrait Déf. faire AJOUTER plus rapide, probablement par plusieurs ordres de grandeur.

non, ce n'est pas le cas, et en fait c'est nettement plus lent (ce qui s'est traduit par un succès de performance de 15% pour le programme réel particulier que j'exécutais).

Je m'en suis rendu compte en posant cette question il y a quelques jours seulement ici .

comme les autres réponses traitent de dispositifs réels et actuels -- qui sont appelés à changer et à s'améliorer au fil du temps -- j'ai pensé que nous pourrions examiner la question du point de vue théorique.

Proposition: lorsqu'il est implémenté dans des portes logiques, en utilisant les algorithmes habituels, un circuit de multiplication entier est O(log N) fois plus lent qu'un circuit d'addition, où N est le nombre de bits dans un mot.

preuve: le temps pour un circuit combinatoire pour stabiliser est proportionnelle à la profondeur de la plus longue séquence de portes logiques à partir de n'importe quelle entrée vers n'importe quelle sortie. Nous devons donc montrer qu'un circuit multiplie gradueschool est O(log N) fois plus profond qu'un circuit d'addition.

Plus est normalement mis en œuvre que d'un demi-additionneur suivi de N-1 additionneurs complets, avec le report de bits enchaînés à partir d'un additionneur à la prochaine. Ce circuit a clairement la profondeur O (N). (Ce circuit peut être optimisé de nombreuses façons, mais la pire performance sera toujours être O (N) à moins que des tables de recherche absurdement grands sont utilisés.)

pour multiplier A par B, il faut d'abord multiplier chaque bit De A avec chaque bit DE B. Chaque multiplication par bit est simplement un et porte. Il y a n^2 multiplications bitwise à effectuer, donc N^2 et gates -- mais toutes peuvent exécuter en parallèle, pour une profondeur de circuit de 1. Cela résout la phase de multiplication de l'algorithme gradeschool, ne laissant que la phase d'addition.

dans l'addition phase, nous pouvons combiner les produits partiels en utilisant un circuit binaire inversé en forme d'arbre pour faire plusieurs des additions en parallèle. L'arbre sera(log N) des noeuds profonds, et à chaque noeud, nous additionnerons deux nombres avec O (N) bits. Cela signifie que chaque noeud peut être implémenté avec un adder de profondeur O(N), donnant une profondeur totale de circuit de O(N log n). QED.