Fonctionnement d'un ordinateur/Exécution dans le désordre

On peut diminuer l'influence des bulles de pipeline en changeant l'ordre des instructions du programme. On profite du fait que l'ordre induit par les dépendances de données est moins strict que l'ordre imposé par le program counter, même si ces deux ordres donnent le même résultat. L'idée est de remplir les bulles de pipeline avec des instructions indépendantes. Si on exclu l'intervention du compilateur, les moyens pour combler les vides sont au nombre de deux.

• Avec les architectures dataflow, le compilateur ajoute des informations sur les dépendances de données dans chaque instruction, à côté de l'opcode. Le processeur ne détecte pas les dépendances à l'exécution, c'est le compilateur qui s'en charge. Les informations sur les dépendances sont mémorisées dans le programme lui-même, le plus souvent à l'intérieur des instructions. Le processeur utilise alors les informations fournies par le compilateur pour répartir les calculs sur les unités de calcul de manière optimale.
• Avec l'exécution dans le désordre, si une instruction attend que ses opérandes soient disponibles, on peut remplir le temps d'attente par une instruction indépendante. Le processeur peut virer certaines dépendances qui apparaissent à l’exécution (branchements), ce qui est impossible pour le compilateur. Cette technique utilise plusieurs avals, voire plusieurs unités de calcul.

Il existe différents types d'exécution dans le désordre : le scoreboarding, l'algorithme de Tomasulo et diverses autres techniques. Ces deux techniques ont une caractéristique commune : les instructions sont décodées dans l'ordre du programme, mais exécutées dans un ordre différent. Qui plus est, on ne décode qu'une instruction à la fois. On verra plus tard que certains processeurs arrivent à passer outre ces limitations, mais nous n'en sommes pas encore là !

Le scoreboarding

Avec le scoreboarding, la gestion et la détection des dépendances sont effectuées par un scoreboard, un circuit qui commande le circuit d'émission. Les instructions dont les opérandes ne sont pas disponibles sont mises en attente dans une mémoire tampon, située entre l'étage d'émission et les unités de calcul. Une fois ses opérandes prêts, l'instruction est envoyée à une unité de calcul et est exécutée, sans se soucier de l'ordre des instructions dans le programme. Quand le résultat d'une instruction est calculé, le scoreboard est prévenu par l'unité de calcul, ce qui lui permet de détecter la disponibilité des opérandes. Pour gérer les dépendances WAR, il faut mettre l'instruction en attente tant que les lectures dans le registre de destination ne sont pas terminées. Pour cela, les résultats ne sont pas enregistrés dans les registres immédiatement, mais s'enregistrent dans le banc de registres quand c'est possible. C'est le scoreboard qui autorise ou non cette écriture, en commandant l'étage d'enregistrement en fin de pipeline.

Pipeline d'un processeur utilisant le scoreboarding.

Les fenêtres d’instruction

Le scoreboard est capable de fournir des gains proches de 10 à 30 % suivant les programmes. Mais celui-ci a un défaut : si deux instructions consécutives ont une dépendance structurelle ou WAW, l'instruction attend dans l'étage d'émission et bloque tout le pipeline. Mais au lieu de bloquer le pipeline, pourquoi ne pas utiliser des instructions indépendantes dans la suite du programme ? Pour que cela fonctionne, il faut que l'étage d'émission mette en attente les instructions, sans bloquer le pipeline (chose que fait le scoreboard). Généralement, cette mise en attente se fait en utilisant une ou plusieurs mémoires spécialisées, appelées des fenêtres d'instruction (instruction windows).

Exécution dans le désordre avec une fenêtre d'instruction

La fenêtre d'instruction

Le cas le plus simple n'utilise qu'une seule mémoire tampon : la fenêtre d'instruction. Avec elle, l'unité d'émission :

• détecte les dépendances ;
• met en attente les instructions qui doivent l'être ;
• répartit les instructions sur les unités de calcul.

Fenêtre d'instruction.

Sur certains processeurs, la répartition des instructions sur les unités de calcul est prise en charge par un circuit séparé de l'étage d'émission, les deux étant séparés par une mémoire tampon. On doit ainsi utiliser plusieurs fenêtres d'instruction, souvent une par aval. L'émission se contente de répartir les instructions sur les unités de calcul, la détection des dépendances étant prise en charge par les fenêtres d'instruction. Ces fenêtres d'instruction spécialisées sont parfois appelées des stations de réservation. Le premier avantage des stations de réservation est qu'elles sont plus petites qu'une grosse fenêtre d'instruction. L'autre avantage, c'est qu'il est possible de démarrer l'exécution de plusieurs instructions simultanément : une instruction par station de réservation, contre une par fenêtre d'instruction. Mais les stations de réservation sont souvent sous-utilisées, partiellement remplies, contrairement aux fenêtres d'instruction. Dans ce qui va suivre, j'utiliserai le terme « fenêtre d'instruction » pour parler des stations de réservation, ainsi que de la fenêtre d'instruction.

Processeur avec plusieurs fenêtres d'instruction.

Le compactage des fenêtres d’instruction

À chaque cycle, les instructions décodées sont ajoutées dans la fenêtre d'instruction, dans des entrées vides. Vu que les instructions quittent celle-ci dans le désordre, ces vides sont dispersés dans la fenêtre d'instruction, ce qui pose problème pour déterminer où placer les nouvelles instructions. La solution la plus triviale consiste à conserver une liste des vides, mise à jour à chaque insertion ou émission d'instruction. Une autre solution consiste à éliminer les vides en compactant la fenêtre d'instruction à chaque cycle d'horloge. Des circuits se chargent de détecter les vides et de regrouper les instructions en un unique bloc. Il faut signaler que certaines processeurs arrivent à se passer de cette étape de compactage, mais au prix de fenêtres d'instruction nettement plus complexes.

Autre problème : quand il faut choisir quelle instruction émettre, il y a toujours plusieurs candidats. Si on choisit mal, des instructions restent en attente trop longtemps parce que d'autres instructions plus jeunes leur passent devant. Pour éviter cela, les instructions les plus vielles, les plus anciennes, sont prioritaires. Pour cela, on peut utiliser une FIFO un peu spéciale pour la fenêtre d'instruction. Si les ajouts d'instruction se font dans l'ordre, les instructions ne quittent pas forcément la fenêtre d'instruction dans l'ordre imposé par une FIFO : les instructions restent triées dans leur ordre d'ajout, même s'il y a des vides entre elles. Dans ces condition, il est préférable que le compactage conserve l'ordre FIFO des instructions. Dans ces conditions, l'instruction la plus ancienne est celle qui est située à l'adresse la plus faible : le circuit de sélection peut donc être fabriqué avec des encodeurs, et est relativement simple.

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. Et entre le moment où une 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.

L'é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.

La 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. Il 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 prédit si la donnée est dans le cache ou la mémoire et éventuellement dans quel cache elle est (cache L1, L2, autre). 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.

Les 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 : les 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 cela, le pipeline se voit ajouter une sorte de boucle, en plus du pipeline normal. Les instructions se propagent à 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 ».

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.

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).

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.

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.

Les éclaireurs matériels

Il existe d'autres techniques d’exécution dans le désordre, qui exécutent des instructions en parallèle d'une lecture. Les instructions indépendantes d'une lecture s’exécutent pendant que celle-ci attend la mémoire ou le cache. Mais ces architectures sont moins efficaces que les architectures à exécution dans le désordre, vu qu'elles ne peuvent que diminuer l'impact des accès mémoire, pas plus. Parmi ces techniques, les architectures découplées seront vues dans un chapitre à part, tandis que les éclaireurs matériels (hardware scouts) vont être abordés maintenant.

La file d’attente différée

Lors d'une lecture, le processeur met en attente les instructions dépendantes de la donnée lue, mais continue d’exécuter les instructions indépendantes de celle-ci. Les instructions sont mises en attente dans une mémoire tampon, qui s'appelle la file d’attente différée (deferred queue). Celle-ci est souvent une simple mémoire FIFO, mais peut être plus complexe et former une véritable fenêtre d'instruction à retardement. Quand la donnée lue est disponible, écrite dans le registre de destination, les instructions mises en attente sont ré-exécutées.

Le processeur a juste à détecter les instructions dépendantes d'une lecture. Cette détection s'effectue en marquant le registre de destination de la lecture comme « invalide », du moins tant que la lecture n'a pas écrit son résultat dedans. Ensuite, chaque instruction qui a un registre invalide comme opérande est mise en attente. Son registre de destination sera aussi marqué invalide. Pour marquer les registres comme valides ou invalides, on utilise un bit par registre qui indique s'il contient une donnée valide ou non. L'ensemble de ces bits est regroupé dans un registre spécial, invisible pour le programmeur. Pour déterminer le bit de validité d'une instruction, il suffit de deux choses :

• soit il s'agit d'une lecture, et elle est marquée automatiquement comme invalide ;
• soit une instruction écrit une donnée valide dans un registre : le registre en question est automatiquement marqué comme valide ;
• soit on effectue un OU entre les bits des registres d'opérandes : si un seul des registres opérande est invalide, le résultat l'est aussi.

Les points de contrôle

Il arrive qu'une instruction indépendante de la lecture écrase un résultat calculé par les instructions dépendantes. Dans ce cas, l’exécution normale du programme voudrait que le registre contienne la version écrite par l'instruction indépendante, plus récente. Mais le fait de ré-exécuter les instructions dépendantes de la lecture après les instructions indépendante viole totalement ce principe ! Pour éviter tout problème, on est obligé de sauvegarder le contenu des registres à chaque lecture. Le processeur peut ainsi revenir à la normale en cas de problème en remettant les registres à leur état antérieur. Et ces sauvegardes doivent être faites à chaque fois qu'on commence à spéculer, c'est-à-dire pour chaque accès mémoire. Le processeur doit donc être capable de gérer un grand nombre de sauvegardes.