« Fonctionnement d'un ordinateur/Exécution dans le désordre » : différence entre les versions

Contenu supprimé Contenu ajouté
Ligne 40 :
==Un problème de latence…==
 
Idéalement, on voudrait démarrer une nouvelle instruction sur l'unité de calcul dès qu'elle est libre. Cependant, une unité d'émission naïve attend que les opérandes soient disponibles avant de démarrer une nouvelle instruction dans cette ALU. MaisEt entre le moment où cette nouvelleune instruction quitte la fenêtre d'instruction et le moment où elle arrive dans l'unité de calcul, plusieurs cycles se sont écoulés. Pour donner un exemple, sur le Pentium 4, on trouve 6 étages entre la fenêtre d’instruction et l'entrée de l'ALU. Les instructions ne démarrent donc pas aussi vite qu'elles le pourraient, du moins si elles attendent la disponibilité de leurs opérandes.
 
===ÉmissionL'émission en avance===
 
La solution consiste à démarrer des instructions en avance, quelques cycles avant que les opérandes soient tous disponibles. Le nombre de cycles d'avance est facile à connaitre : c'est le nombre d'étages entre l'unité de calcul et la fenêtre d'instruction. Le cas le plus simple est celui des instructions qui ont une durée fixe : on gère la situation en ajoutant quelque circuits dans l'unité d'émission, ou en se basant sur un ''scoreboard''. Sur certains processeurs on mémorise le temps d'exécution de l'instruction dans la fenêtre d'instruction : chaque entrée se voit ajouter un champ de latence d'instruction qui est mis à jour à chaque cycle d’horloge (un simple compteur suffit). Malheureusement, cette méthode ne fonctionne que pour les instructions de durée fixe.
 
===PrédictionLa prédiction de latence===
 
Pour gérer le cas des instructions à durée variable, le processeur peut tenter de prédire combien de temps va durer l'instruction, et agir en conséquence. : ilIl suffit de vider le pipeline si la prédiction se révèle être fausse ! Certains processeurs utilisent ainsi une unité de prédiction de latence mémoire, qui va prédireprédit si la donnée est dans le cache ou la mémoire, et éventuellement dans quel cache elle est : (cache L1, L2, etcautre). Cette prédiction se base sur des techniques directement inspirées des techniques de prédiction de branchement, comme des compteurs à saturation, une prédiction statique, etc. La latence prédite de l'instruction est stockée dans le fameux champ de latence d'instruction mentionné plus haut, quelques bits associés permettant de faire la différence entre durée prédite et connue avec certitude.
 
===PipelineLes pipelines à répétition===
 
Certains processeurs sont beaucoup plus agressifs dans leurs prédictions, au point de postuler qu'aucune instruction ne fait de défaut de cache. Évidemment, ces processeurs devraient en théorie vider leurs pipelines assez souvent, mais ils utilisent une technique élégante pour gérer ces ratés de prédiction : ils utilisent ce qu'on appelle des '''pipelines à répétition''' (''replay pipeline''). Sur ces pipelines, on lance une instruction sans savoir quelle est la latence et on réexécute celle-ci en boucle tant que son résultat n'est pas valide. Pour réexécuter une instruction en boucle, le pipeline se voit ajouter une sorte de boucle, en plus du pipeline normal. Les instructions vont se propager à la fois dans la boucle et dans le pipeline normal. Les étages de la boucle servent juste à propager les signaux de commande de l'instruction, sans rien faire de spécial. Dans le pipeline qui exécute l'instruction, ces signaux de commande sont consommés au fur et à mesure, ce qui fait qu'à la fin du pipeline, il ne reste plus rien de l'instruction originale. D'où la présence de la boucle, qui sert à conserver les signaux de commande. L'étage final de la boucle vérifie que l'instruction n'a pas été émise trop tôt avec un ''scoreboard'', et il regarde si l'instruction a donné lieu à un défaut de cache ou non. Si l'instruction a donné un bon résultat, une nouvelle instruction est envoyée dans le pipeline. Dans le cas contraire, l'instruction refera encore un tour dans le pipeline. Dans ce cas, l'unité de vérification va devoir envoyer un signal à l'unité d'émission pour lui dire « réserve un cycle pour l'instruction que je vais faire boucler ».
 
[[File:Pipeline à répétition.png|centre|vignette|upright=2|Pipeline à répétition.]]
 
Toutefois, ce pipeline est loin d'être optimal avec des hiérarchies de cache. Prenons un exemple : un succès de cache dans le cache L1 dure 3 cycles d'horloge, un succès de cache dans le L2 dure 8 cycles, et un défaut de cache 12 cycles. Regardons ce qui se passe avec une instruction qui fait un défaut de cache dans le L1, et un succès de cache dans le L2. La boucle de 3 cycles utilisée pour le L1 ne permettra pas de gérer efficacement la latence de 8 cycles du L2 : l'instruction devra faire trois tours, soit 9 cycles d'attente, contre 8 idéalement. La solution consiste à retarder le second tour de boucle de quelques cycles, en rajoutant des étages vides dans la boucle. Dans notre exemple, il faut retarder de deux cycles : 8 cycles, dont trois en moins pour le premier tour, et trois en moins pour le trajet fenêtre d'instruction → unité de calcul.
 
[[File:Pipeline à répétition avec une latence de 3 cycles pour le L1, et 8 cycles pour le L2.png|centre|vignette|upright=2|Pipeline à répétition avec une latence de 3 cycles pour le L1, et 8 cycles pour le L2.]]
 
Le même principe peut s'appliquer pour gérer les latences avec des niveaux de cache supérieurs : il faut alors utiliser plusieurs boucles de tailles différentes. Ce principe peut aussi s'appliquer dans d'autres cas assez spécifiques, dans lesquels l'instruction a été émise trop tôt, sans que cela fasse intervenir les mémoires caches. Les étages situés avant l'étage de vérification seront partagés, mais un multiplexeur se chargera de choisir vers quelle boucle envoyer l’instruction, suivant le cache dans lequel on fait défaut. Dans ces conditions, il arrive que plusieurs boucles veuillent faire rentrer une instruction dans le pipeline en même temps. Pour cela, une seule boucle pourra réémettre son instruction, les autres étant mises en attente. Divers mécanismes d'arbitrage, de choix de la boucle sélectionnée pour l'émission, sont possible : privilégier la boucle dont l'instruction est la plus ancienne (et donc la boucle la plus longue) est la technique la plus fréquente. Mais dans certains cas, mettre une boucle en attente peut bloquer tous les étages précédents, ce qui peut bloquer l'émission de la nouvelle instruction : le processeur se retrouve définitivement bloqué. Dans ce cas, le processeur doit disposer d'un système de détection de ces blocages, ainsi que d'un moyen pour s'en sortir et revenir à la normale (en vidant le pipeline, par exemple).
 
[[File:Pipeline à répétition avec hiérarchie de cache multiples et exceptions.png|centre|vignette|upright=2|Pipeline à répétition pour une hiérarchie de cache.]]
 
Pour gérer au mieux les accès à la mémoire RAM, on remplace la boucle dédiée à la latence mémoire par une FIFO, dans laquelle les instructions sont accumulées en attendant le retour de la donnée en mémoire. Quand la donnée est disponible, lue ou écrite en mémoire, un signal est envoyé à cette mémoire, et l'instruction est envoyée directement dans le pipeline. Là encore, il faut gérer les conflits d'accès à l'émission entre les différentes boucles et la file d’attente de répétition, qui peuvent vouloir émettre une instruction en même temps.
 
[[File:Gestion des accès RAM sur un pipeline à répétition.png|centre|vignette|upright=2|Gestion des accès RAM sur un pipeline à répétition.]]
 
On peut aussi adapter le pipeline à répétition pour qu'il gère certaines exceptions : certaines exceptions sont en effet récupérables, et disparaissent si on réexécute l'instruction. Ces exceptions peuvent provenir d'une erreur de prédiction de dépendance entre instructions (on a émis une instruction sans savoir si ses opérandes étaient prêts), ou d'autres problèmes dans le genre. Si jamais une exception récupérable a eu lieu, l'instruction doit être réexécutée, et donc réémise. Elle doit refaire une boucle dans le pipeline. Seul problème : ces exceptions se détectent à des étages très différents dans le pipeline. Dans ce cas, on peut adapter le pipeline pour que chaque exception soit vérifiée et éventuellement réémise dès que possible. On doit donc ajouter plusieurs étages de vérification, ainsi que de nombreuses boucles de réémission.