Prédiction de branche

La prédiction de branche permet à un processeur pipeliné de deviner le résultat et la cible d'une branche avant qu'elle ne soit résolue, afin qu'il puisse continuer à récupérer et exécuter des instructions le long du chemin probable sans provoquer de blocage.

Definition

La prédiction de branche est une technique microarchitecturale qui prévoit si une branche conditionnelle sera prise et où elle mènera, permettant au processeur de récupérer et d'exécuter spéculativement des instructions le long du chemin prédit et de rejeter ce travail si la prédiction s'avère erronée.

Scope

Ce sujet aborde les techniques de prédiction du flux de contrôle : la prédiction statique, les prédicteurs dynamiques basés sur l'historique des branches (compteurs à un et deux bits, prédicteurs corrélés et tournoi), les tampons de cible de branche, et le coût des erreurs de prédiction. Il traite de la manière dont la prédiction permet des pipelines profonds et la spéculation. Il exclut les mécanismes plus larges d'exécution spéculative et de récupération (exécution dans le désordre) ainsi que l'aléa de contrôle de base lui-même (pipelining et aléas).

Core questions

• Pourquoi les branches bloquent-elles les pipelines profonds, et comment la prédiction aide-t-elle ?
• Comment les prédicteurs dynamiques utilisent-ils l'historique des branches pour améliorer la précision ?
• Qu'est-ce qu'un tampon de cible de branche et que fournit-il ?
• Quelle est la pénalité d'une erreur de prédiction, et comment est-elle récupérée ?

Key concepts

• prédiction statique vs dynamique
• compteurs saturants à un et deux bits
• historique des branches et corrélation
• prédicteurs tournoi
• tampon de cible de branche
• pénalité d'erreur de prédiction
• récupération spéculative

Key theories

Prédiction dynamique basée sur l'historique

Les résultats des branches sont fortement corrélés avec leur propre comportement passé et celui d'autres branches ; les prédicteurs qui enregistrent l'historique dans des compteurs saturants et combinent l'historique local et global (prédicteurs corrélés et tournoi) atteignent une très grande précision.

Mechanisms

Un prédicteur consulte l'historique pour deviner la direction d'une branche et un tampon de cible de branche pour deviner sa cible, permettant au frontal de continuer à récupérer spéculativement. Des compteurs saturants à deux bits suivent les résultats récents par branche ; les prédicteurs corrélés ajoutent un historique global ; les prédicteurs tournoi choisissent dynamiquement entre des schémas locaux et globaux. En cas d'erreur de prédiction, les instructions spéculatives sont annulées et la récupération redémarre à la bonne adresse, entraînant une pénalité proportionnelle à la profondeur du pipeline.

Clinical relevance

Une prédiction de branche précise est essentielle pour les pipelines modernes profonds et larges : les erreurs de prédiction coûtant de nombreux cycles, des prédicteurs dépassant 95 % de précision sont nécessaires pour maintenir des performances élevées. Les structures de prédiction de branche sont également devenues pertinentes pour la sécurité, car leur comportement spéculatif est à la base d'attaques par exécution transitoire telles que Spectre.

History

Les prédicteurs statiques simples et dynamiques à un bit ont cédé la place aux compteurs saturants à deux bits, puis aux prédicteurs corrélés et adaptatifs à deux niveaux au début des années 1990, et aux prédicteurs tournoi et de type neuronal dans les cœurs haute performance. À mesure que les pipelines s'approfondissaient, la sophistication des prédicteurs a augmenté en conséquence pour maintenir les pénalités d'erreur de prédiction tolérables.

Key figures

• James E. Smith
• Yale Patt
• Tse-Yu Yeh
• John L. Hennessy

Seminal works

• hennessy2019
• patterson2020

Frequently asked questions

Que se passe-t-il lorsqu'une branche est mal prédite ?

Le processeur a récupéré et partiellement exécuté spéculativement des instructions sur le mauvais chemin. Lors de la détection de l'erreur de prédiction, il annule (squashes) ce travail spéculatif et redémarre la récupération à partir de la cible correcte, en payant une pénalité à peu près proportionnelle à la profondeur du pipeline.

Quelle est la précision des prédicteurs de branche modernes ?

Les prédicteurs dynamiques modernes dépassent généralement 95 % de précision sur les charges de travail courantes en combinant l'historique des branches local et global. Cette grande précision est ce qui rend les pipelines profonds et larges intéressants, car chaque erreur de prédiction gaspille de nombreux cycles de travail spéculatif.