Prédiction de branche

Bonjour à tous,

voila je viens de m’intéresser au systeme de pipepine du processeur et de la prediction de branche. Et j'aimerais savoir dans le cas ou dans mon code j'ai :

Code:

---

1 2 3 4 5 6 7 8

if( a > 10) { ... } else { ... }

---

et que je sais qu'il y aura plus de cas ou la valeur a est inférieur ou égale a 10, dois je plutot mettre le code de la forme :

Code:

---

1 2 3 4 5 6 7 8

if( a <= 10) { ... } else { ... }

---

ou laisser comme avant. Je suppose que l'unité de prediction de branche doit il y allait au début un peu au piff et finalement prendre le premier choix, donc je me demande s'il serait plus favorable d'utiliser le second extrait de code?

Merci d'avance pour vos éclaircissements

Bonjour

Moi je mets toujours en premier le cas le plus probable. Je ne sais pas si ça optimise quoi que ce soit pour le compilo mais ça optimise ma relecture.

On peut aussi se dire que tester "inférieur ou égal" fera deux opérations alors que "supérieur" n'en fera qu'une mais là je peux pas dire si c'est pertinent ou pas.

Citation:

---

Envoyé par Sve@r

Je ne sais pas si ça optimise quoi que ce soit pour le compilo

---

Moi :mrgreen:, je me dis que ni le compilateur ni le processeur ne peuvent savoir les valeurs qui vont être testées ... et souvent c'est également le cas pour le développeur :whistle:

Le compilateur même après une analyse profonde de ton code, il ne peut rien faire.
Ou à moins, que par exemple, en voyant la plage des valeurs du test très réduite (en plus des tests des extrémités comme les avertissement du test négatif pour des nombres positifs), il peut transformer ton test en switch (jump table). Des optimisations qui n'ont rien à voir avec le sujet.

Pour le processeur, je pense qu'il va s'adapter aux valeurs. SI au bout de 2, 3 fois, il voit que le code passe + par le cas else, il va changer son branchement.
Mais cela suppose un test appelé plusieurs fois. À moins, qu'il a remarqué que dans ton code, tous les if passe en premier lieu dans le else.
Quelles statistiques, le processeur fait ? :koi:

Citation:

---

Envoyé par Sve@r

Moi je mets toujours en premier le cas le plus probable [...] mais ça optimise ma relecture.

---

Tout pareil [...] et c'est effectivement un bon point :king:

:salut:

Les compilateurs peuvent quand même prendre en entrée des infos de la part du programmeur sur la probabilité de branchement, par exemple GCC et son __builtin_expect : https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

Bonjour,

En C++, il y a 2 attributs pour gérer cela [[likely]] et [[unlikely]]. Le compilateur va écrire un code tel que ce qui est plus probable sera pré-supposé par le processeur (du moins les premières fois, au delà comme l'a dis Foetus il va s'adapter.)
A ma connaissance, sans information préalable les processeurs considèrent un saut vers l'arrière comme probable et un saut vers l'avant comme non probable lors du premier passage.
On devrait donc plutôt écrire :

Code:

---

1 2 3 4

if ( condition_non_probable ) { } else { }

---

Mais si la fonction est appelée fréquemment, le processeur va toujours utiliser ses algorithmes de prédiction. Et à ma connaissance, il n'existe aucun moyen d'interférer avec cela.
Faire une erreur de prédiction peut amener à perte d'environ 4 à 50 cycles sur un processeur CISC (Intel, ...) ou une perte de 3 ou 4 cycles sur un processeur RISC (ARM, ...) donc perdre un temps "faramineux" d'environ 5ns ce qui peut poser un problème si la fonction est appelée plusieurs millions de fois par seconde.

Comme l'a très bien dit daflab, les attributs unlikely et likely peuvent être utilisés, ils sont notamment assez utilisés dans les sections critiques du noyau Linux. Ils peuvent être utilisés comme suit if (unlikely(ret < 0)){/*Condition improbable*/}. Si tu sais pertinemment qu'une branche va être quasiment systématiquement prise, ça peut être intéressant d'utiliser ce type d'astuce pour aider le prédicteur de branche.

Si rien n'est précisé, c'est prédicteur de branche qui va tenter d'inférer la branche la plus probable pour la pipeliner et ne pas perdre de cycle de calcul. Cette solution n'est pas parfaite puisque faillible mais le taux de réussite du prédicteur de branche est généralement supérieur à 90% donc quand même très acceptable. (Après, c'est dur de rentrer très en détail du comportement du prédicteur de branche, celui-ci étant très opaque et souvent imparfait (cf. Spectre, Meltdown, ...))

Ceci dit, je ne sais pas quelles sont les contraintes de ton code, mais sauf si tu as des contraintes de performances très fortes, ce genre d'optimisation te donnera des gains assez faibles, de l'ordre de quelques cycles pour chaque mauvaises prédiction évitée. Donc comme toujours, attention à l'optimisation prématurée. Ça à tendance à complexifier ton code alors que les gains restent généralement très marginaux.

Bonne journée.

Citation:

---

Envoyé par dalfab

A ma connaissance, sans information préalable les processeurs considèrent un saut vers l'arrière comme probable et un saut vers l'avant comme non probable lors du premier passage.
On devrait donc plutôt écrire :

Code:

---

1 2 3 4

if ( condition_non_probable ) { } else { }

---

---

je n'ai pas compris ce que tu entendais par un saut en arriere. tu veux dire en assembleur un jmp qui retournerai vers les instructions passées, donc une boucle en C ?

Citation:

---

Envoyé par cosmoff

voila je viens de m’intéresser au système de pipepine du processeur et de la prediction de branche. Et j'aimerais savoir dans le cas ou dans mon code j'ai :

---

Techniquement ta question n'a rien n'a voir avec le C !
Secundu pour la pipeline du processeur , la pipeline du processeur à était faite pour atteinte la sacro-sainte x instruction/cycles (x est un chiffre variant entre 1 et plus).

La prédiction de branche se fait dans le cas le plus courant.
Maintenant si tu veux mon avis , c'est une question un peu "stupide" , parce que tu optimisera rien comme cela , la prédiction de branche est une boite noire , et les failles Meltdown et Spectre ne sont qu'un aperçu.

Et si je dis que cela est stupide , cela dépend aussi de l'état de la pipeline !
Je m'explique pourquoi avoir créer une prédiction de branche ?
Parce que dans certain cas , le proc doit attendre la condition (donc comme on ne veut pas attendre , on exécute la suivante) , mais il se peut aussi qu'il y''en a pas besoin , si la pipeline n'est pas "bloqué".
Si tu compare A et B et que ces valeurs sont connu pendant la condition , alors il est probable qu'il faudra pas trop attendre alors la prediction de branche se fera quasiment pas.
Mais bon la prédiction peut se tromper (d'où les failles processeurs) , et comme tu le code pas en assembleur , tu ne peux pas garantir ce que fera le proc (même en assembleur c'est pas un truc fiable à 100% de tromper une prédiction de branchement ou inversement de garantir qu'il lira ta condition à 100%).
Bref ce n'est pas sur un code C qu'on peut jouer avec la prédiction de branchement , et la plupart des optimisation qu'on peut faire se trouve ailleurs (principalement sur l'algo choisis).

Maintenant comme on parle du C , ta question s'oriente vers un certain CPU et le C se veut portable.
Certain proc ARM par exemple (comme le RasPI) n'ont pas de prédiction de branche pour la simple raison que ce sont des processeurs dit "in order" donc qui laisse au programmeur (ou au compilateur) de faire lui même l'optimisation de la pipeline manuellement.

Bonsoir,

Attention, il faut dissocier les choses. Les prédictions de branchement n’ont absolument rien à voir avec les conditions écrites en langage C et les optimisations faites par le compilateur surtout qu'ici, on est dans le cas de la prédiction de branche dynamique; sans oublier que le programme en lui-même peut très bien avoir des prédictions de branchement sans les conditions écrites dans le code source de départ. Entre ce que fait le compilateur et ce que fait le pipeline lors d’exécutions d’un programme (tout aussi bien des optimisations du compilateur avant exécution du programme que les optimisations utilisées/méthode utilisée par le processeur lors d’exécutions des instructions d’un programme) n’ont rien à voir.

Le pipeline/ technique de pipeline est le parallélisme d’instruction qui permet d’augmenter la vitesse d’exécution d’instruction dans le CPU où une instruction se voit être décomposée en plusieurs phases / étapes qui s’exécutent indépendamment sous réserve d’avoir l’unité fonctionnelle permettant de réaliser ce parallélisme et s’ajoute à cela la façon dont le CPU va exécuter les instructions :

Soit : Une exécution dans le désordre peut être utilisée par le processeur et donc, au lieu d’attendre que toutes les instructions ou leurs données (voire ressources) soient disponible, le CPU va exécuter celles qui sont disponibles immédiatement. Ce fait renonce à suivre l’ordre logique d’exécution du programme et opter pour une exécution immédiate dès que possible dont à l'issue, il doit réorganiser le tout pour retrouver l’ordre original du programme.

Soit : Le CPU exécute le programme en mode spéculatif dans lequel le processeur va précharger les instructions dans l’ordre du programme et c’est là où les branchements (plus particulièrement les branchements conditionnels) deviennent un peu compliqués car tant que l'instruction du branchement n’est pas exécutée, le CPU ne peut absolument pas savoir si le saut va être effectif (pris en compte) ou pas et donc où se trouve la prochaine instruction. Au lieu d’arrêter le pipeline de façon temporaire, il va faire des suppositions sur le saut et poursuivre l’exécution de manière spéculative et si cette spéculation s’est avérée correcte, il n’y a absolument pas d’interruption d’exécution du programme. Dans le cas contraire, le travail de prédiction est alors ignoré pour repartir sur la/les prédictions correctes. A titre informatif, le taux actuel de réussite des prédictions (sur les processeurs récents) dépasse les 98 % et non 90 % ce qui veut également dire qu’il y a toujours des instructions que le CPU exécute. Pour comprendre et répondre à la question initialement posée partant d’un exemple simple et classique ci-dessous.

Code:

---

1 2 3 4 5 6 7 8 9

for( size_t i = 0x0; i < 20; i++ ){ if( i > 10 ) /* instruction if */ else /* instruction sinon */   /* Autre instruction */ }

---

Ici, le processeur va croiser à plusieurs reprises dans son cycle la condition if, il va alors soit opter pour une exécution dans l’ordre et dans ce cas, il ne prend pas le branchement ou alors ne prend uniquement que le saut de la condition. Et comme le pipeline détecte de lui-même les dépendances nécessaires. Il va introduire des bulbes, à la résolution des aléas : en clair, il va introduire des temps d’attente (en assembleur des nop), car dans les pipelines, les instructions de branchement génèrent des retard. Pour ne pas attendre, des caches associatifs du processeur (branch target buffer) vont être utilisés dans les pipelines pour mémoriser les adresses des instructions de branchement déjà exécutées et s’en servir pour deviner la prochaine rencontre de la condition en prenant en compte les règles de mécanisme/algorithme de prédiction, à savoir : que tout branchement non conditionnel est toujours pris ; tout branchement qui consiste à revenir en arrière (et donc à une instruction précédente dans le code tel que les retours de boucle) est toujours pris et tout branchement conditionnel n’est jamais pris ce qui donne alors le schémas suivant pour le cas des if/else

Code:

---

1 2 3 4 5

if( i > 10 ) executer le branchement sur BRAN1 sinon le banchement sur BRAN2 BRAN1: Exécuter l'instruction BRAN2: Sortie immédiate

---

Et donc, si une spéculation est correcte, on continue l’exécution des instructions. En revanche, dans le cas contraire, tout changement en mémoire est ignoré, et le processeur revient en arrière pour prendre la bonne branche. Dans l’exemple actuel, si i atteint la valeur 20-1, le processeur est dans le cas ou il est probable qu'il se trompe.

Citation:

---

Envoyé par emixam16

Si rien n'est précisé, c'est prédicteur de branche qui va tenter d'inférer la branche la plus probable pour la pipeliner et ne pas perdre de cycle de calcul. Cette solution n'est pas parfaite puisque faillible mais le taux de réussite du prédicteur de branche est généralement supérieur à 90% donc quand même très acceptable. (Après, c'est dur de rentrer très en détail du comportement du prédicteur de branche, celui-ci étant très opaque et souvent imparfait (cf. Spectre, Meltdown, ...))....

---

On sort un peu de la discussion mais pour le cas de Meltdown, ce n’est pas une question que ça soit imparfait ou autre, la faille Meltdown en elle-même n’est pas basée à proprement parler sur l’exécution spéculative, c’est juste un vecteur qui permet par la suite d’exploiter le cache. Pour moi, la véritable attaque est faite sur le cache par canaux auxiliaires en mode itération pour lire l’ensemble de la mémoire virtuelle. Bref, si on veut parler réellement, c’est plus « spectre », car qui on se base sur l’optimisation de la prédiction spéculative en forçant le processeur, c’est un autre débat et qui n’a pas lieu ici le fait d’en parler est déjà limite hors sujet.

Ceci dit @cosmoff avant de se pencher sur les mécanismes des architectures machine avez-vous compris/résolue vos erreurs en assembleur 64 bits dans la section assembleur avant de vous attaquer à plus grand.

à bientôt

Citation:

---

Envoyé par sambia39

la faille Meltdown en elle-même n’est pas basée à proprement parler sur l’exécution spéculative

---

De ce que j'ai compris :mrgreen:, c'est le processeur lorsqu'il a un if, s'il doit prendre une décision, va donc prendre soit le if soit le else.
Mais dans le cas où le processeur se trompe dans sa prédiction, on s'est aperçu qu'au lieu d’arrêter le code qui ne doit pas être exécuté, il le laisse finir normalement (sauf que le résultat n'est jamais pris en compte) : et donc ce code peut faire des appels mémoire normalement.

Citation:

---

Envoyé par foetus

De ce que j'ai compris :mrgreen:, c'est le processeur lorsqu'il a un if, s'il doit prendre une décision, va donc prendre soit le if soit le else.
Mais dans le cas où le processeur se trompe dans sa prédiction, on s'est aperçu qu'au lieu d’arrêter le code qui ne doit pas être exécuté, il le laisse finir normalement (sauf que le résultat n'est jamais pris en compte) : et donc ce code peut faire des appels mémoire normalement.

---

Oui et pas tout à fait..

En plus simple lorsque le processeur exécute des instructions, il va exécuter la première instruction puis fait de la spéculation sur la prochaine instruction afin de deviner quelles seront là où les prochaines instructions à traiter et pour traiter ses différentes instructions et ceux peu importe l'ordre, il va falloir de la mémoire et cette mémoire va être prise dans la mémoire vive ; puis à l'aide du cache, le processeur va d'abord enregistrer les adresses virtuelles qu'il a rencontrées dans sa propre mémoire cache ; pour information ; les caches du CPU sont utilisées pour masquer les latences d'accès à la mémoire en mettant en mémoire dite tampon les données fréquemment utilisées dans une mémoire interne plus petite et plus rapide. Les processeurs actuels ont plusieurs niveaux de caches qui sont soit privés par cœur, soit partagés entre eux. Les tables de conversion de l'espace d'adressage sont également stockées en mémoire et, par conséquent, également mises en cache cela est donc nécessaire au processeur pour qu'ils puissent y accéder rapidement et directement.

Après avoir mis en cache les adresses virtuelles, le processeur effectue ensuite d’autres traitements et sauvegarde le résultat dans un registre de sa mémoire interne. Suite à tous ses traitements, le processeur va déterminer si oui ou non ça prédiction a été la bonne (correcte) et si c’est le cas (prédiction réussie) il va transmettre le résultat à l’espace utilisateur pour ensuite passer au traitement de la prochaine instruction ; cas contraire il ignore en supprimant de son registre interne le résultat des erreurs pour recommencer son traitement. Sauf qu’entre-temps, la mémoire cache interne du processeur n’est pas vide puisqu’il y a toujours les fameuses adresses virtuelles que le processeur avait sauvegardées et c’est là où réside le vecteur qu’exploite Meltdown, car involontairement, les erreurs commissent par les instructions dites out of order génèrent des fuites mémoire et l’on comprend également que ces mêmes instructions permettent involontairement (si je peux le dire) des accès à l’espace noyau sachant que cela est interdit. Ce n’est pas donc pas tout à fait des appels mémoire.

D’ailleurs, pour exploiter ce vecteur va falloir dans un premier temps avoir accès à la mémoire noyau puis extraire les informations (donc au début mis en place d’un « probe array » ensuite on s’assure que notre « probe array » n’est pas mise en cache en utilisant des instructions propres au CPU pour effacer un emplacement mémoire du cache. Puis lecture des data dans l'espace d'adressage du noyau, piéger l'instruction d'erreur pour pouvoir poursuivre l'exécution, des instruct etc..).

à bientôt

Citation:

---

Envoyé par sambia39

Oui et pas tout à fait..

En plus simple lorsque le processeur exécute des instructions, il va exécuter la première instruction puis fait de la spéculation sur la prochaine instruction afin de deviner quelles seront là où les prochaines instructions à traiter et pour traiter ses différentes instructions et ceux peu importe l'ordre,

---

Si on veut être exact il faudrait dire que le processeur va exécuter x instructions en même temps (la plupart des processeurs actuel sont superscalaires) , le proc Intel est capable exécuter 5 instructions en même temps ! (dans les faits c'est un cas particulier les 5).

Tu es sûr qu'il fait de la spéculation pour les prochaines instructions ? (sauf si tu parles d'un branchement conditionnel) , techniquement vu comment Intel présente le truc , j'ai l'impression qu'il exécute seulement les instructions qui n'ont pas de pipeline stall, ce qui me semble le plus logique et le plus simple à faire.
Il y'a pas de raison de faire du spéculative dedans, tant que la pipeline est libre, on peut continuer à exécuter les prochaines instructions, j'ai pas forcément fait une étude sérieuse dessus mais on programme sur des proc in-order, 90% du temps qui bloque la pipeline c'est les dépendances de données.
Et il y a un truc pour ça le Renommage de registres ;)
Apres il y a ensuite les dépendances entre deux instructions (genre A = B+C et ensuite A = A*D), et là on revient en arrière dans la discussion pas besoin de spéculation, le proc peut exécuter un bout du deuxième (A = A*D ) le IF /ID par exemple, faire A = B+C en complet et d'autre instructions et ensuite revenir sur le deuxième :)


NT: J'ai l'impression d’être un peu HS, vu que ce genre de discussion aurait plus sa place dans la section assembleur que dans la section C :aie:

Citation:

---

Envoyé par Kannagi

.... Tu es sûr qu'il fait de la spéculation pour les prochaines instructions ? (sauf si tu parles d'un branchement conditionnel) , techniquement vu comment Intel présente le truc , j'ai l'impression qu'il exécute seulement les instructions qui n'ont pas de pipeline stall, ce qui me semble le plus logique et le plus simple à faire.

---

Oui, puisque le principe de l’exécution spéculative est que les instructions sont exécutées avant de savoir qu’elles sont effectives/correctes. Sans exécution spéculative, le processeur doit attendre que les instructions précédentes soient terminées avant d'exécuter les suivantes. Cependant, en exécutant les instructions de manière spéculative, les performances peuvent donc être améliorées en minimisant la latence/temporisation en question et en tirant une plus grande partie du parallélisme.

De plus, là où les formes d'exécution spéculative sont le plus utilisé implique le/les flux de contrôle du programme ; exemple : au lieu d'attendre que toutes les instructions de branche soient résolues pour déterminer les diverses opérations/instruction à réalisé, le processeur va prédire le flux de contrôle ce qui permet d’un autre côté avoir des performances élevées en masquant les latences des opérations et donc même pour les branchements conditionnels tant que l’instruction de celle-ci n'est pas exécutée en soit le processeur ne peut absolument pas savoir si son saut a été effectif. Plutôt, que de bloquer de façon temporaire le pipeline, il fait des suppositions et poursuit sont exécution de manière spéculative et ce n’est qu’après que le saut soit véritablement effectif que le CPU va savoir si le branchement est correct et comme bénéfice de toute cette spéculation « pas d’interruption » cas contraire et comme je l’ai mentionné précédemment les instructions exécutées de manière spéculative sont ignorées et le processeur sera redirigé pour exécuter la prédiction de l’instruction qui est correcte.

Citation:

---

Envoyé par Kannagi

.NT: J'ai l'impression d’être un peu HS, vu que ce genre de discussion aurait plus sa place dans la section assembleur que dans la section C :aie:

---

Oui, je suis d'avis avec vous que ce genre de question trouverait bien ça place non pas forcément en assembleur, mais en architecture machine, mais bon ça été initié ici donc...

Voilà ce que dit une partie wikipedia :

Citation:

---

Les microprocesseurs modernes utilisant un pipeline se servent de l'exécution spéculative pour réduire le coût des instructions de branchement conditionnel. Quand une instruction de branchement conditionnel est rencontrée, le processeur devine quelle voie du branchement le programme est susceptible de suivre (c'est ce que l'on appelle la prédiction de branchement), et commence à exécuter les instructions correspondantes.

---

Donc on parle bien pour un branchement conditionnel ?

Parce que comme dit avant (avec mon addition et ma multiplication) tu n'as besoin d'aucune spéculation pour résoudre le problème de pipeline , juste de réorganise les instruction dans le désordre ! :p
(Donc d'exécuter la pipeline le plus loin possible , et sans forcément attendre que toutes les instructions soit résolu)

Je rajouterai que je ne dirai pas que cela augmente les performances , c'est une optimisation , tu peux faire cette optimisation manuellement sur certain proc , certain proc plus exotique te permet même d'avoir un contrôle totale sur les instructions exécuter en doubles + un contrôle fin de la mémoire cache (pour éviter tout les caches miss).

Citation:

---

Envoyé par Kannagi

Donc on parle bien pour un branchement conditionnel ?.

---

Oui, avec un pipeline en exécution spéculative.

Citation:

---

Envoyé par Kannagi

Parce que comme dit avant (avec mon addition et ma multiplication) tu n'as besoin d'aucune spéculation pour résoudre le problème de pipeline , juste de réorganise les instruction dans le désordre ! :p
(Donc d'exécuter la pipeline le plus loin possible , et sans forcément attendre que toutes les instructions soit résolu)
.

---

J'ai du mal à comprendre, ici, il n'est pas question de résoudre les problèmes liés au pipeline, c'est plus comment le pipeline traite les instructions, type branchement conditionnel ; et comme je l'ai souligné, les formes d'exécution spéculative le plus utilisé impliquent des flux de contrôle du programme et même-si, les instructions sont de type addition multiplication, qu'est-ce qui empêche le CPU de pré-charger les instructions dans l’ordre du programme ? Et ceux même ci le processeur utilise l'exécution spéculative ; c'est d'ailleurs un point que je n'ai pas avancée quant à la question sur Meltdown d'où j'ai écrit que la faille Meltdown en elle-même n’est pas basée à proprement parler sur l’exécution spéculative.

Pour faire simple, Meltdown ne marche pas à tous les coups parce qu'on a une architecture qui utilise de l'exécution spéculative ; exemple sur les machines ARM, quand bien même il a une exécution spéculative dans le désordre l'attaque, Meltdown n'aboutira pas; car l'architecture en question ne prend pas en charge certaines exécutions spéculatives / out of order (car celles-ci sont limitées).

Citation:

---

Envoyé par Kannagi

Je rajouterai que je ne dirai pas que cela augmente les performances , c'est une optimisation , tu peux faire cette optimisation manuellement sur certain proc , certain proc plus exotique te permet même d'avoir un contrôle totale sur les instructions exécuter en doubles + un contrôle fin de la mémoire cache (pour éviter tout les caches miss).

---

Si cela augmente tout de même les performances; quant à l'optimisation que vous présentez elle est basé sur le fait que votre pipeline possède des étapes supplémentaires vous permettant ainsi de procéder au renommage de vos registres en sollicitent des étapes supplémentaires et qui dit étage supplémentaire veut dire soit le pipeline est un pipeline double/pipeline dit long (donc plusieurs étages). Par déduction sans être indiscret, soit vous travaillez sur des architectures disposant de pipeline double ce qui vous permet d'exécuter des instructeurs simultanément chacune dans leurs pipelines respectifs ou sur l'architecture superscalaire, mais la seconde un peu moins à mon avis..

à bientôt