Les processeurs modernes sont superscalaires, c'est-à-dire qu'ils sont capables d'exécuter plusieurs instructions simultanément. Par exemple, certains processeurs peuvent traiter de quatre à six instructions par cycle. De plus, de nombreux processeurs de ce type sont capables de lancer des instructions dans le désordre: ils peuvent commencer à travailler avec des commandes situées dans le code beaucoup plus tard.
Dans le même temps, le code contient souvent des branches (
if–then ). Ces branches sont souvent implémentées comme des "transitions", dans lesquelles le processeur procède soit à l'exécution d'instructions sous le code, soit continue le chemin en cours.
Avec l'exécution superscalaire de commandes dans le désordre, la ramification est difficile. Pour cela, les processeurs ont des blocs de prédiction de branche sophistiqués. Autrement dit, le processeur essaie de prédire l'avenir. Lorsqu'il voit une branche, et donc une transition, il essaie de deviner dans quelle direction ira le programme.
Très souvent, cela fonctionne assez bien. Par exemple, la plupart des boucles sont implémentées en tant que branches. À la fin de chaque itération de la boucle, le processeur doit prédire si la prochaine itération sera effectuée. Il est souvent plus sûr pour le processeur de prédire que le cycle se poursuivra (pour toujours). Dans ce cas, le processeur ne prédit par erreur qu'une seule branche par cycle.
Il existe d'autres exemples courants. Si vous accédez au contenu d'un tableau, de nombreux langages de programmation ajoutent une «vérification liée» - une vérification cachée de l'exactitude de l'index avant d'accéder à la valeur du tableau. Si l'index est incorrect, une erreur est générée, sinon le code continue de s'exécuter de la manière habituelle. Les contrôles aux frontières sont prévisibles, car dans une situation normale, toutes les opérations d'accès doivent être correctes. Par conséquent, la plupart des processeurs devraient prédire presque parfaitement le résultat.
Que se passe-t-il si la ramification est difficile à prévoir?
À l'intérieur du processeur, toutes les instructions qui ont été exécutées mais qui se trouvent sur la branche incorrectement prédite doivent être annulées et les calculs doivent être recommencés. Il est à prévoir que pour chaque erreur de prédiction de branche, nous payons plus de 10 cycles. De ce fait, le temps d'exécution du programme peut augmenter considérablement.
Regardons un code simple dans lequel nous écrivons des entiers aléatoires dans un tableau de sortie:
while (howmany != 0) { out[index] = random(); index += 1; howmany--; }
Nous pouvons générer un nombre aléatoire approprié en moyenne pour 3 cycles. C'est-à-dire que le retard total du générateur de nombres aléatoires peut être égal à 10 cycles. Mais notre processeur est superscalaire, c'est-à-dire que nous pouvons effectuer plusieurs calculs de nombres aléatoires simultanément. Par conséquent, nous pourrons générer un nouveau nombre aléatoire environ tous les 3 cycles.
Modifions un peu la fonction pour que seuls les nombres impairs soient écrits dans le tableau:
while (howmany != 0) { val = random(); if( val is an odd integer ) { out[index] = val; index += 1; } howmany--; }
Vous pourriez naïvement penser que cette nouvelle fonctionnalité pourrait être plus rapide. Et en fait, parce que nous devons enregistrer en moyenne un seul des deux entiers. Il y a une branche dans le code, mais pour vérifier la parité d'un entier, vérifiez simplement un bit.
J'ai comparé ces deux fonctions en C ++ sur un processeur Skylake:
La deuxième fonction fonctionne environ cinq fois plus longtemps!
Peut-on réparer quelque chose ici? Oui, nous pouvons simplement éliminer la ramification. Un entier impair peut être caractérisé de telle sorte qu'il s'agit d'un ET logique au niveau du bit avec une valeur de 1 égale à un. L'astuce consiste à incrémenter l'index du tableau de un uniquement si la valeur aléatoire est impaire.
while (howmany != 0) { val = random(); out[index] = val; index += (val bitand 1); howmany--; }
Dans cette nouvelle version, nous écrivons toujours une valeur aléatoire dans le tableau de sortie, même si elle n'est pas requise. À première vue, c'est un gaspillage de ressources. Cependant, cela nous sauve des branches prédites par erreur. En pratique, les performances sont quasiment les mêmes que le code d'origine, et bien meilleures que la version avec branches:
Le compilateur pourrait-il résoudre ce problème seul? En général, la réponse est non. Parfois, les compilateurs ont des options pour éliminer complètement les branchements, même s'il y a une
if-then dans le code source. Par exemple, la ramification peut parfois être remplacée par un «mouvement conditionnel» ou d'autres astuces arithmétiques. Cependant, ces astuces ne sont pas sûres pour une utilisation dans les compilateurs.
Une conclusion importante: la ramification erronée n'est pas un problème insignifiant, elle a une grande influence.
Mon code source est sur Github .
La création de repères est une tâche difficile: les processeurs apprennent à prédire les branchements
[Remarque trad.: cette partie était un
article distinct de l'auteur, mais je l'ai combiné avec le précédent, car ils ont un thème commun.]
Dans la partie précédente, j'ai montré que la plupart du temps d'exécution d'un programme peut être causé par une prédiction de branche incorrecte. Mon point de repère était d'écrire 64 millions de valeurs entières aléatoires dans un tableau. Lorsque j'ai essayé d'enregistrer uniquement des nombres aléatoires impairs, les performances dues à des prédictions erronées ont considérablement diminué.
Pourquoi ai-je utilisé 64 millions d'entiers plutôt que, disons, 2000? Si vous exécutez un seul test, cela n'aura pas d'importance. Cependant, que se passera-t-il si nous faisons de nombreuses tentatives? Le nombre de branches incorrectement prédites tombera rapidement à zéro. Les performances du processeur Intel Skylake parlent d’elles-mêmes:
Comme le montrent les graphiques ci-dessous, la "formation" se poursuit. Progressivement, la proportion de branches incorrectement prédites chute à environ 2%.
Autrement dit, si nous continuons à mesurer le temps pris par la même tâche, cela devient de moins en moins, car le processeur apprend à mieux prédire le résultat. La qualité de la «formation» dépend du modèle de processeur spécifique, mais les nouveaux processeurs devraient mieux apprendre.
Les derniers processeurs de serveur AMD apprennent à prédire presque parfaitement les branchements (à 0,1% près) en moins de 10 tentatives.
Cette prédiction idéale sur AMD Rome disparaît lorsque le nombre de valeurs du problème augmente de 2000 à 10 000: la meilleure prédiction passe d'une fraction d'erreurs de 0,1% à 33%.
Vous devriez probablement éviter de comparer le code avec le branchement pour les petites tâches.
Mon code github .
Remerciements : valeurs AMD Rome fournies par Vel Erwan.
Lecture supplémentaire :
Un cas pour (partiellement) la prédiction de la longueur de l'histoire géométrique TAggée (Seznec et al.)