Discussion :

[Kannagi]

Pardon, sur x86, on dirait que la division peut approcher les 100 cycles! Probablement parce que l'ALU est taillé pour travailler en 64 bits, donc plus de bits à traiter...

Sauf que c'est pour le Intel P4 , P6 et AMD K7 , en gros c'est obsolètes
Si ces procs fait autant de cycles ,c'est surtout que ce genre de processeur avait une pipeline extrêmement grande (pour atteindre des fréquence élevé notamment) ,du coup a chaque pipeline stall tu te bouffer une trentaines de cycles (même pour une simple addition).
D'ailleurs je prendrais des pincettes sur les chiffres mis sur ce pdf , ça me semble assez fantaisiste.

De nos jours les divisions peuvent atteindre que quelque cycle (voir 1 cycle sur les flottants en utilisant les instructions SSE), la solution d'intel et amd est de multiplier énormément d'ALU (facilement plus de 6) donc la pipeline peut continuer sans se bloquer.
Il faut savoir que théoriquement de nos jours tout peux s’exécuter sur un cycle , voir même plusieurs instruction par cycle.
J'ai fait des test sur des proco modernes (années 2010 et plus) , sur les dernier procs Intel/ryzen ça tourne à 4 IPC , et ça même pour des calculs lourd (comme la multiplications de matrice ou la transformation perspective donc multiplication+division).

Par contre ce que je trouve stupide sur la doc c'est qu'il est bel et bien impossible de prédire la vitesse d'une instruction , cela dépend de l'état de la pipeline et pas des instructions en elle même (le proc ne bloque jamais la pipeline sauf en cas de besoin ).

[wistiti1234]

Sauf que c'est pour le Intel P4 , P6 et AMD K7 , en gros c'est obsolètes
Si ces procs fait autant de cycles ,c'est surtout que ce genre de processeur avait une pipeline extrêmement grande (pour atteindre des fréquence élevé notamment) ,du coup a chaque pipeline stall tu te bouffer une trentaines de cycles (même pour une simple addition).
D'ailleurs je prendrais des pincettes sur les chiffres mis sur ce pdf , ça me semble assez fantaisiste.

Regarde un petit peu mieux, il s'agit de toutes les architectures core (Haswell, Broadwell, Skylake, etc...). Ca ne me paraît pas particulièrement vieux
P4 dépasse allègrement les 100 cycles (~150), mais c'est bien les dernières génération Intel (à ~90) que j'avais dans le viseur.
Et de toute façon, on ne peut pas présumé sur quelle plateforme tournera un soft, donc il vaut mieux évoquer les chiffres les plus pessimistes, plutôt que de mettre en avant les beaux scores ZEN...
Par contre je te rejoins pour la qualité de ce pdf. J'ai depuis trouvé d'autres sources qui me paraissent un petit peu plus digne de confiance et où il ne serait plus question que de 30 à 40 cycles, en gros pour toutes les plateformes (sauf rares extrêmes).

De nos jours les divisions peuvent atteindre que quelque cycle (voir 1 cycle sur les flottants en utilisant les instructions SSE), la solution d'intel et amd est de multiplier énormément d'ALU (facilement plus de 6) donc la pipeline peut continuer sans se bloquer.
Il faut savoir que théoriquement de nos jours tout peux s’exécuter sur un cycle , voir même plusieurs instruction par cycle.
J'ai fait des test sur des proco modernes (années 2010 et plus) , sur les dernier procs Intel/ryzen ça tourne à 4 IPC , et ça même pour des calculs lourd (comme la multiplications de matrice ou la transformation perspective donc multiplication+division).

Par contre ce que je trouve stupide sur la doc c'est qu'il est bel et bien impossible de prédire la vitesse d'une instruction , cela dépend de l'état de la pipeline et pas des instructions en elle même (le proc ne bloque jamais la pipeline sauf en cas de besoin ).

Alors là tu m'intéresses. Tu as des sources solides pour appuyer tous ça?

Moi j'ai plutôt l'habitude de travailler sur de petits micros. Et initialement, j'imaginais effectivement que nos gros CPU modernes devaient être capable de calculer une simple division en un battement de cil.
Mais ce n'est absolument pas ce que j'ai trouvé jusqu'à présent. Bien au contraire.
Non seulement la division semble toujours s'exécuter entre 20 à 40 cycles suivant la plateforme, que ce soit en entier ou en flottant (et de toute façon peu importe, ce n'est pas parce que la div float serait plus rapide à calculer qu'une div int, que le compilo réorientera la div int vers le FPU!!),
mais en plus, comme tu l'as évoqué, si plusieurs instructions simples (comme l'addition) peuvent être calculé en parallèle, simultanément sur le même cœur, ce n'est pas le cas de la division, qui bénéficie de la double peine (très longue à calculé, et un par un à la queue leu-leu).

De tout ce que j'ai trouvé jusqu'à présent, il semblerait qu'il n'y ait eut encore aucun génie qui n'ait réussis à nous pondre la formule magique pour calculer une division en un seul cycle d'horloge.
J'ai été étonné et déçu de le découvrir, mais au fond, ça peut se comprendre.
C'est comme les divisions qu'on réalise à la main: il faut un cycle par bit.

[wistiti1234]

Pardon je rectifie:
Zen subit la double peine: 46 cycles en 64 bits, et une division après l'autre.
Core par contre a effectivement multiplié les unités de calcul (4 visiblement, pour 35 à 88 cycles en 64bits).
Mais comme il en est de même pour l'addition, le rapport addition / division restera toujours aussi important.

C'est une info intéressante à garder à l'esprit. Surtout quant on écrit une boucle.

[Kannagi]

Je me répète , mais tes chiffres sont faux (en plus complètement absurde de donner des chiffres précis) , tu ne peux pas donner de chiffre précis sur un processeur moderne , comme je te l'ai dit , toutes les instructions peuvent s’exécuter sur 1 cycle (division comprise) pour être exact depuis plus de 20 ans les instructions s’exécute en double (de nos jours un proc actuel peut théoriquement gérer 6 instructions/cycles)
De plus c'est impossible de donner un chiffre précis , le out of order ,superscalaire , le renommage des registres etc etc , donne un coté très peu précis sur la vitesse des instructions , cela dépend de l'optimisation interne des proco et il est quasi impossible de savoir précisément ce qu'il fait !
(et elle dépend de l'état de la pipeline si rien ne bloque ta division , ton addition , ta multiplication etc etc, elle ne te coûtera rien ).
donc la vitesse réel d'une instruction dépend plus de son contexte.

Alors là tu m'intéresses. Tu as des sources solides pour appuyer tous ça?

La doc officiel Intel , AMD , autre et l'architecture des ordis depuis les années 2000

Les sources pour les calculs, mes test perso (enfin de plusieurs cobayes pour être précis):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
Matrix x Matrix PS 1 : 27 3.704
Matrix x Matrix PS 2 : 21 4.762
Matrix x Matrix SS :  43 4.186
Matrix x Matrix int :  40 5.000
Transform Perspective SS :  27 1.852
Raster :  2777 3.961
Matrix x Matrix SS flush :  398 0.452
Matrix x Matrix PS 1 flush :  423 0.236
Matrix x Matrix PS 2 flush :  418 0.239
Mov cache :  0 inf /31.701
Mov flush :  137 0.080 /1.393
time 0.801371 s
frq 1799.699219 MHz
 
Thinkad 580, Ubuntu 18.04,  Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
 
AMD Ryzen 7 2700X
Matrix x Matrix PS 1 : 43 2.326
Matrix x Matrix PS 2 : 20 5.000
Matrix x Matrix SS :  42 4.286
Matrix x Matrix int :  55 3.636
Transform Perspective SS :  34 1.471
Raster :  6237 1.764
Matrix x Matrix SS flush :  941 0.191
Matrix x Matrix PS 1 flush :  845 0.118
Matrix x Matrix PS 2 flush :  786 0.127
Mov cache :  0 inf /27.721
Mov flush :  306 0.036 /0.627
time 0.775116 s
frq 3694.184082 MHz

Je dois avoir une cinquantaine de test comme ça, par contre le raster qui possède plusieurs division , tu remarque que l'IPC est de plus de 1 !
Et donc on bien a moins d'un cycle de division (la transformation perspective à un IPC de 1,4 / 1,8 donc c'est un mul + div)
Et je viens de test c'est quasi pareil pour la transformation perspective avec des int (donc on est loin de 20 , 40 ou autre chiffre fantaisiste pour la division )

Non seulement la division semble toujours s'exécuter entre 20 à 40 cycles suivant la plateforme, que ce soit en entier ou en flottant (et de toute façon peu importe, ce n'est pas parce que la div float serait plus rapide à calculer qu'une div int, que le compilo réorientera la div int vers le FPU!!)

Cela existe depuis bien longtemps la PS2 pouvait le faire (techniquement elle ne fait que 7 cycles , mais si tu optimise la pipeline elle ne te coûte que 1 cycle ) , avec le même principe elle pouvait faire même 4 addition et/ou 4 multiplication par cycle , et c'est un proc qui date des années 2000
Donc sur 7 cycles tu pouvait avoir une transformation 3D complète d'un vecteur ! (1 div et 5 x 4mul+4add + convert int to float avec load/store compris)

Pour ma part le souci de l'IPC (sur l'archi x86) sur les proco des années 2010 et plus est largement résolu , par contre une plus grande optimisation actuelle se trouve sur celle de la mémoire cache parce que là c'est un coût de plus d'une centaine de cycles (avec peu d optimisation possible ) alors que la division est largement optimisation niveau pipeline.
Il est plus intéressant d'optimiser la mémoire cache que les instructions vraiment (qui de toute façon n'est pas prédictible en terme de vitesse), on est plus dans les années 80 :p

Les deux seuls proco qui résolu le souci de la mémoire cache est l'Emotion Engine et le processeur CELL , ce sont les deux seuls qui donne des outils au programmeurs pour ne pas en avoir (mais comme ils sont dénué de fonction automatique pour le faire , c'est le programmeur qui doit le faire lui même , en version simple faut y aller en asm ).

Tu as une vision assez faussé du fonctionnement des processeurs moderne (j'ai l'impression que tu me parle d'un processeur des années 80), quand un processeur tombe sur une division , il va continuer l'exécutions des instructions , il se bloquera quand celle ci est pleine (et avec 4 ou plus ALU , AGU , BRU , FPU , SSE etc etc ) , il faut beaucoup beaucoup d'instruction pour qu'elle se bloque (bloque = que les instructions te coûtera plus que 1 cycle).

[wistiti1234]

Je me répète , mais tes chiffres sont faux (en plus complètement absurde de donner des chiffres précis) , tu ne peux pas donner de chiffre précis sur un processeur moderne ...

Pourtant ce Professeur me paraît être quelqu'un de très expérimenté (au regard des autres volumes qu'il a rédigé), et sa méthodologie, plutôt rigoureuse (expliqué en page 4).
Mais si tu crois mieux savoir...

... comme je te l'ai dit , toutes les instructions peuvent s’exécuter sur 1 cycle (division comprise) pour être exact depuis plus de 20 ans les instructions s’exécute en double (de nos jours un proc actuel peut théoriquement gérer 6 instructions/cycles)

Excuses-moi de ne pas te croire ta sainte parole, mais la technique de division en un cycle, ça semble être un secret encore mieux gardé que la recette coca-cola.
J'ai beau cherché encore et encore, je n'est trouvé aucun papier, aucune documentation, aucun brevet, aucune discussion ou sujet de forum qui tendrait à montrer cela réalisable.
Bien au contraire, j'ai trouver de très bon papier montrant toute la complexité de la chose (ici, là, ou encore là, mais je ne vais pas innonder...).

Mais n’hésites surtout pas à reposter, si jamais tu arrives a trouver une source qui confirmerait tes convictions.
Et n'hésites pas à en informer AMD, les pauvres, eux qui en sont toujours réduits à calculer 2 bits par cycles (2.10.2) sur leur petit ZEN (d'où les 14-46 cycles en 64bits, avec les sorties prématurés...), je suis suis sûr qu'ils seraient ravie d'apprendre ta technique (histoire de finir d'enterrer INTEL ).

La doc officiel Intel , AMD , autre et l'architecture des ordis depuis les années 2000

C'est de celle-ci que tu veux parler? (tu pensais peut-être que j'allais pas vérifier?)
Je te laisse vérifier l'appendix C, pour voir de combien s'est planté l'Université du Danemark, moi j'ai pas eu le courage de le faire...

Pour le reste, je n'ai aucun doute que nos CPU doivent bénéficier de tous un tas d'optmisiation pour masquer le plus possible les engorgement dans le pipeline (avec de la prédicion, et d'autres technique que je ne connais pas).
Mais comme toutes ces optimisations bénéficieront tout autant à l'addition qu'à la division, on se retrouve à nouveau à la case départ: la division restera toujours l'instruction de base la plus lente, par rapport à la multiplication et les autres...

[Kannagi]

Pourtant ce Professeur me paraît être quelqu'un de très expérimenté (au regard des autres volumes qu'il a rédigé), et sa méthodologie, plutôt rigoureuse (expliqué en page 4).
Mais si tu crois mieux savoir...

C'est pas une question de croyance , c'est le principe même de la pipeline , mais les processeurs actuel qu'on peut nommer superscalaire out of order rend bien plus complexe et fluctuant une mesure précise.

Excuses-moi de ne pas te croire ta sainte parole, mais la technique de division en un cycle, ça semble être un secret encore mieux gardé que la recette coca-cola.
J'ai beau cherché encore et encore, je n'est trouvé aucun papier, aucune documentation, aucun brevet, aucune discussion ou sujet de forum qui tendrait à montrer cela réalisable.
Bien au contraire, j'ai trouver de très bon papier montrant toute la complexité de la chose (ici, là, ou encore là, mais je ne vais pas innonder...).

Ce n'est pas une question de croyance , j'ai posté quelque calcul que j'ai fait sur un vrai processeur (avec mul et division) donc ça confirme ce qui se dit , je t'ai dit aussi que c'était le cas sur des processeurs que j'ai personnellement programmé (sur PS2 entre autre).

Et n'hésites pas à en informer AMD, les pauvres, eux qui en sont toujours réduits à calculer 2 bits par cycles (2.10.2) sur leur petit ZEN (d'où les 14-46 cycles en 64bits, avec les sorties prématurés...), je suis suis sûr qu'ils seraient ravie d'apprendre ta technique (histoire de finir d'enterrer INTEL ).

Au mieux cette doc nous dis que la division à une longueur de pipeline de 4-32 cycles pas que la division te coûtera autant (c'est une nuance assez importante).
Dire que la division fait 16 cycles , c'est dire quel le processeur passera 16 cycles à faire ça et rien d'autre .
Avoir une pipeline de 16 cycles, ça veut dire qu'il faut 16 cycles pour qu'elle se termine , mais laissera le soin au processeur d’exécuter d'autre instruction en parallèle , tu la vois la nuance ?
Je vais pousser le raisonnement plus loin si tu as arrive à paralléliser ces 16 cycles , alors ta division aura un coût équivalent de 1 cycle.
Pour ça que je le dis et répète que tu ne peux pas dire combien coûte une division (ou tout autre instruction ) , ça n'a rien n'a voir avec une croyance , c'est le principe même de la pipeline (paralléliser les instructions) , si tu la parallélise suffisamment bien alors tu atteint donc que la fréquence = nombre d'instruction , et si le proc est superscalaire alors tu peux avoir un IPC au delà de un.
Rien de magique ,c'est un principe que tous les processeurs ont acquis depuis plus de 20 ans.

Je ne te cacherai pas que les test que j'ai fait m'ont un peu étonné , je me doutais pas qu'un proc actuel arriverai à paralléliser suffisamment les instructions pour éviter tout les blocage de pipeline et donc avoir une moyenne de 3 instruction par cycle (division et multiplication comprise).
Mais d'un coté cela ne m'étonne pas vraiment la PS2 arrivait a atteindre les 2 instructions/cycles (avec div + instruction SIMD donc pas des petits calculs).
Donc Intel et AMD ont réussi a bien travailler dans ce domaine c'est indéniable (mais pas étonnant dans un sens).

Mais comme toutes ces optimisations bénéficieront tout autant à l'addition qu'à la division, on se retrouve à nouveau à la case départ: la division restera toujours l'instruction de base la plus lente, par rapport à la multiplication et les autres...

Je que je tente de souligner c'est que c'est contre productive de raisonner de cette façon , la vitesse des instructions ne sont pas prédictible à l'avance.
Donc non ce n'est pas vrai , si une addition bloque la pipeline et que la division non , alors l'addition te coûtera plus de cycle que la division , et inversement.
De même que la prédiction de branchement (une condition ou une boucle) si le processeur se loupe sur la prédiction ça te coûtera bien plus que qu'une division
Donc non on est loin de la case de départ , mais dans quelque chose de bien plus complexe.

Mais n’hésites surtout pas à reposter, si jamais tu arrives a trouver une source qui confirmerait tes convictions.

Si mes convictions sont "que tout peux te coûter 1 cycle même la division" alors je reste sans voix fasse a autant de dédains , surtout que je pense que je connais un peu mieux le sujet que toi.

Faisant un peu d'histoire , dans les années 80 les processeurs fonctionnait avec des instructions avec un taux fixe de cycle (l'addition fait 3 cycles la division 80 et j'y passe)
A partir des années 95 est venu sur le marché (pour le PC et pour les consoles) des processeurs avec une pipeline donc pouvoir paralléliser les instructions entre elle et atteindre leur nombre théorique ( fréquence = nombre d'instruction).
Il y'a eu deux voies , une quand nomme in order est une version manuelle de cette optimisation , ce qu'on appelle out of order est une version automatique.
Puis on a voulu exécuter plusieurs instruction en même temps pareil la version automatique est appelé superscalaire et la version manuelle VLIW.

Pour cela que tu ne peux pas savoir combien fait exactement le nombre de cycle d'une instruction sur un proc superscalaire out of order (le x86) parce qu'il fait cette optimisation en interne et que tu ne connais pas précisément la taille exact de cette pipeline , ni même comment il la gère.
Ce n'est pas pour rien que des failles comme spectre et meltdown ont était découvert si tardivement ,c'est bien que ce genre de processeur est une vrai boite noire sur la façon de comment il gère les instructions !

Mais si tu programme sur un proc in order VLIW (comme le CELL) , c'est à toi de gerer la pipeline et les instructions que tu exécute en double ,tu peux en lisant le code source savoir où et quand il y'a un blocage et dire "tiens la division ici me prend 3 cycles et là elle me prend 8 cycles et dans une autre 1 cycle" (ben oui suivant où se trouve les blocages de cette pipeline , cela fluctue beaucoup sur combien de cycle ça te prend).

Donc merci de ne pas me parler de "croyance" ou de "conviction" quand je ne fais qu’énumérer le fonctionnement des processeurs !

[chrtophe]

Pour rejoindre ce que dit Kannagi :

Le nombre d'instructions par seconde d'un processeur peut être déterminé en multipliant l'IPC par la fréquence d'horloge (mesuré en cycles par seconde ou Hertz) du microprocesseur en question. Le nombre d'instructions par seconde est un indicateur approximatif des performances d'un microprocesseur.

Le nombre d'instructions exécutées par cycle n'est pas une constante pour un processeur donné; il dépend de la manière dont le logiciel en cours d'exécution interagit avec le microprocesseur, et évidemment de l'ensemble de la machine, et en particulier de la hiérarchie mémoire. Cependant, certaines fonctions d'un microprocesseur ont pour effet d’accroitre les valeurs d'IPC au-dessus de la moyenne ; la présence de multiples unités arithmétiques et logiques (une ALU est une unité d'un microprocesseur qui peut effectuer des opérations élémentaires d’arithmétique et logique), et un court pipeline.

Un processeur CISC exécute la plupart des instructions élémentaires (addition, multiplication, tests, etc.) en une période d'horloge, tandis qu'il faut généralement quatre périodes d'horloge à un processeur RISC pour obtenir le même résultat. Cependant, le système de pipeline dans les architectures RISC permet d'optimiser l'exécution d'instructions, rendant d'autant plus délicat le lien entre le nombre de MIPS et la performance réelle du processeur.

sources Wikipedia.


Par ailleurs, les CPU Intel intègrent 3 niveaux de cache L1, L2, et L3. Les caches ont une importance primordiale car la mémoire est un goulot d'étranglement pour le CPU. Ton CPU passera probablement autant de temps à charger les deux opérandes et retourner en mémoire le résultat qu'à faire la division.

Et dans le cas d'exemple d'ici, le temps le plus important sera les accès I/O, encore plus "lents" que les accès mémoire.

[Kannagi]

Par ailleurs, les CPU Intel intègrent 3 niveaux de cache L1, L2, et L3. Les caches ont une importance primordiale car la mémoire est un goulot d'étranglement pour le CPU. Ton CPU passera probablement autant de temps à charger les deux opérandes et retourner en mémoire le résultat qu'à faire la division.

Et dans le cas d'exemple d'ici, le temps le plus important sera les accès I/O, encore plus "lents" que les accès mémoire.

Je ne peux que être d'accord à 200% !
Et j'aurais bien voulu expliquer plus cette problématique là (que de la vitesse des instructions).

Sur me mes différents tests (que j'ai du exécuter 1 millions de fois ) pour avoir l'éfficasité du processeurs à traiter un groupe d'instruction (parce qu'on on ne peut pas parler de la vitesse d'une instruction sur un processeur superscalaire) , cela donne un aperçu de la vitesse du proc (je voualit surtout savoir si il arrivait bien a paralléliser correctement les instructions).
Et la réponse est oui , mais d'un coté c'est pas étonnant Intel ou AMD outre qu'ils ont du rajouter beaucoup (beaucoup) d'unité de calcul , ils ont aussi 192 registres interne (pour le renommage de registre qui sert notamment a éviter les dépendance entre les instructions).
Je trouve que c'est une version bazooka de résoudre ce souci , mais bon on va dire qu'elle marche.

Bien sur comme tu le dit , les caches sont bien plus contraignant (3 caches miss sur un ryzen te coûte presque 1000 cycles).
Et c'est pour ma part la différence entre un AMD et un Intel , Intel a un IPC moindre mais gère mieux les cache (les cache miss sont plus rapide) que ceux d'AMD qui ont un avantage sur l'IPC.
D'ailleurs il faut savoir que les compilo tente d’optimiser ce cache vu que les caches miss sont peu parallélisable , et le plus gros gain quand peut avoir sur un proc actuelle se trouve sur ça.
Il faut être conscient que sur un proco moderne cela peut être 50% du temps de calcul perdu , c'est assez énorme.

Le seul truc que je n'ai pas réussi à "mesurer" , c'est la latence du au boucle et aux comparaisons , bref mesurer la vitesse de la prédiction des branchements , mais ça revient à faire les failles meltdown et spectre et de mesurer ensuite le nombre de cycle (et encore meme pas sur que le nombre qu'on aura est fiable), mais bon je pense que avec mes nombreux test , j'ai une vision assez précise de combien prend a peu près chaque partie en terme de cycle.

[chrtophe]

Et c'est pour ma part la différence entre un AMD et un Intel , Intel a un IPC moindre mais gère mieux les cache (les cache miss sont plus rapide) que ceux d'AMD qui ont un avantage sur l'IPC.

Ca je peux pas dire, je n'ai pas testé, et pas étudié vraiment la question.

L'architecture CPU x sera pour un traitement meilleure sur un modèle pour telle chose et moins bonne pour une autre par rapport à l'architecture y à puissance équivalente.
Globalement les processeurs PowerPC G3/G5 avait une puissance équivalente à un Intel de l'époque à fréquence plus faible.

Ce qui est important ici, c'est de savoir que temps de chargement des valeurs à diviser peut dépasser le temps du calcul lui-même (en vulgarisant), dans ce cas précis, il ne sert pas à grand-chose de dire que le calcul prendra x cycles. On est sur un problème C à la base (et dans le forum C, pas assembleur), pas sur un problème assembleur. Savoir qu'une division est couteux en temps CPU suffit.

Le problème est ici en priorité un problème d'algorithme, avant d'être un problème d'optimisation de compilation.