Fonctionnement d'un ordinateur/Interruptions et pipeline

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

Sur un processeur purement séquentiel, ces interruptions et exceptions ne posent aucun problème. Mais si on rajoute un pipeline, les choses changent : cela pose des soucis si une instruction génère une exception ou interruption dans le pipeline. Avant que l'exception n'ait été détectée, le processeur a chargé des instructions dans le pipeline alors qu'elles n'auraient pas dû l'être. En effet, ces instructions sont placées après l'instruction à l'origine de l'exception dans l'ordre du programme. Logiquement, elles n'auraient pas dû être exécutées, vu que l'exception est censée avoir fait brancher notre processeur autre part.

Exception et pipeline

Une solution consiste à placer des instructions inutiles après une instruction susceptible de générer une exception matérielle ou une interruption. Dans l'exemple, l'exception est prise en compte avec deux cycles d’horloge de retard. Il suffit donc de placer deux instructions inutiles juste après celle pouvant causer une exception. Le seul problème, c'est que le nombre d'instructions inutiles à ajouter dépend du pipeline du processeur, ce qui peut poser des problèmes de compatibilité. Au lieu d'insérer ces instructions directement dans le programme, les concepteurs de processeur ont décidé de faire en sorte que le processeur se charge lui-même de gérer exceptions et interruptions correctement : le processeur annule les instruction chargées à tort et remet le pipeline en ordre.

Achèvement dans l’ordre[modifier | modifier le wikicode]

Ces techniques de gestion des exceptions sont spéculatives : le processeur va spéculer que les instructions qu'il vient de charger ne lèvent aucune exception. Le processeur continuera à exécuter ses instructions, ce qui évite des bulles de pipeline inutiles si la spéculation tombe juste. Mais si jamais cette prédiction se révèle fausse, il va devoir annuler les instructions exécutées suite à cette erreur de spéculation. Au final, ce pari est souvent gagnant : les exceptions et interruptions sont très rares, même si beaucoup d'instructions peuvent en lever.

Ordre des écritures[modifier | modifier le wikicode]

Pour implémenter cette technique, le processeur garantit que les instructions chargées ne feront aucun mal si jamais la spéculation est fausse : leurs écritures en RAM, dans les registres, ou dans le program counter doivent pouvoir être empêchées et annulées. Pour régler ce problème, on doit garantir que ces écritures se fassent dans l'ordre du programme. Avec un pipeline de longueur fixe, il n'y a rien à faire, contrairement à ceux de longueur variable. Prenons cet exemple : je charge deux instructions l'une à la suite de l'autre dans mon pipeline, la première prend 8 cycles pour s’exécuter, tandis que la seconde en prend 4. On a beau avoir démarré les instructions dans l'ordre, la première enregistre son résultat avant la seconde : si la première instruction lève une exception, les résultats de la seconde auront déjà été enregistrés dans les registres. La solution consiste à ajouter des bulles de pipeline pour retarder certaines instructions. Si une instruction est trop rapide et risque d'écrire son résultat avant ses prédécesseurs, il suffit simplement de la retarder avec le bon nombre de cycles.

Pipeline bubble

Pour ce faire, on utilise un circuit spécial : le registre de décalage de résultat (result shift register), un registre à décalage qui contient autant de bits qu'il y a d'étages dans notre pipeline. Chaque bit est attribué à un étage et signifie que l'étage en question est utilisé par une instruction. À chaque cycle d'horloge, ce registre est décalé d'un cran vers la droite, pour simuler la progression des instructions dans le pipeline. Lorsque l'unité de décodage démarre une instruction, elle vérifie le nombre de cycles que va prendre l'instruction pour s’exécuter. Pour une instruction de n cycles, elle va vérifier le n-ième bit de ce registre. S'il est à 1, une autre instruction est déjà en cours pour cet étage, et l'instruction est mise en attente. Si ce bit est à 0, l’unité va le placer à 1, ainsi que tous les bits précédents : l'instruction s’exécutera.

Récupération après spéculation[modifier | modifier le wikicode]

Les exceptions sont détectées dans le pipeline, quand elles sont levées par un circuit. Mais elles ne sont prises en compte qu'au moment d'enregistrer les données en mémoire, dans l'étage d’enregistrement. Pour comprendre pourquoi, imaginez que dans l'exemple du dessus, les deux instructions lèvent une exception à des étages différents. Quelle exception traiter en premier ? Il va de soi qu'on doit traiter ces exceptions dans l'ordre du programme, donc c'est celle de la première instruction qui doit être traitée. Traiter les exceptions à la fin du pipeline permet de traiter les exceptions dans leur ordre d’occurrence dans le programme.

Annulation des écritures fautives[modifier | modifier le wikicode]

Pour interdire les modifications des registres et de la mémoire en cas d'exception, on doit rajouter un étage dans le pipeline, qui sera chargé d'enregistrer les données dans les registres et la mémoire : si une exception a lieu, il suffit de ne pas enregistrer les résultats des instructions suivantes dans les registres, jusqu’à ce que toutes les instructions fautives aient quitté le pipeline.

Prise en compte des exceptions[modifier | modifier le wikicode]

Tout étage fournit à chaque cycle un indicateur d'exception, un groupe de quelques bits qui indiquent si une exception a eu lieu et laquelle le cas échéant. Ces bits sont propagés dans le pipeline, et passent à l'étage suivant à chaque cycle. Une fois arrivé à l'étage d’enregistrement, un circuit combinatoire vérifie ces bits (pour voir si une exception a été levée), et autorise ou interdit l'écriture dans les registres ou la mémoire en cas d'exception.

Propagation de l'indicateur d'exception.

Achèvement dans le désordre[modifier | modifier le wikicode]

Il existe d'autres solutions pour maintenir l'ordre des écritures, sans avoir besoin de registre à décalage. Toutes ces techniques, hormis la sauvegarde de registres, demandent d'ajouter un étage de pipeline pour remettre les écritures dans l'ordre du programme. Celui-ci est inséré entre l'étage d’exécution et celui d'enregistrement. Voici la liste de ces techniques :

  • la sauvegarde de registres ;
  • un tampon de réordonnancement ;
  • un tampon d’historique ;
  • un banc de registres futurs ;
  • autre chose.

Sauvegarde de registres[modifier | modifier le wikicode]

La sauvegarde de registres (register checkpointing) consiste à faire des sauvegardes régulières des registres, et récupérer cette sauvegarde lors d'une exception. Mais sauvegarder les registres du processeur prend du temps, ce qui fait que cette solution n'est que rarement utilisée.

Tampon de réordonnancement[modifier | modifier le wikicode]

Une autre solution consiste à exécuter nos instructions sans se préoccuper de l'ordre des écritures, avant de remettre celles-ci dans le bon ordre. Pour remettre en ordre ces écritures, les résultats des instructions seront mis en attente dans une FIFO, avant d'être autorisés à être enregistrés dans les registres une fois que cela ne pose pas de problèmes. Cette mémoire tampon s'appelle le tampon de réordonnancement (re-order buffer ou ROB). Un résultat est enregistré dans un registre lorsque les instructions précédentes (dans l'ordre du programme) ont toutes écrit leurs résultats dans les registres. Seule l'instruction la plus ancienne peut quitter le ROB et enregistrer son résultat : les autres instructions doivent attendre. Lorsqu'une instruction vient d'être décodée, celle-ci est ajoutée dans le ROB à la suite des autres : les instructions étant décodées dans l'ordre du programme, l'ajout des instructions dans le ROB se fera dans l'ordre du programme, automatiquement. Si une exception a lieu, le ROB se débarrasse des instructions qui suivent l'instruction fautive (celle qui a déclenché l'interruption ou la mauvaise prédiction de branchement) : ces résultats ne seront pas enregistrés dans les registres architecturaux. Quand le ROB est plein, le processeur va bloquer les étages de chargement, décodage, etc. Cela évite de charger des instructions dans celui-ci alors qu'il est plein. Sur les processeurs utilisant un séquenceur microcodé, la fusion de plusieurs instructions machines en une seule micro-opération diminue le nombre d'instructions à stocker dans le ROB, qui stocke les micro-opérations.

Tampon de réordonnancement.

Ce ROB est composé de plusieurs entrées, des espèces de blocs dans lesquels il va stocker des informations sur les résultats à écrire dans les registres ou la mémoire. Le nombre d'entrées est fixé, câblé une fois pour toutes. Chaque entrée contient l'adresse de l'instruction, obtenue en récupérant le contenu du program counter, pour savoir à quelle instruction reprendre en cas d'erreur de spéculation. Elle contiennent aussi un bit Ecxception pour préciser si l'instruction a levé une exception ou non. Lorsqu'un résultat quitte le ROB, pour être enregistré dans les registres, ce bit est vérifié pour savoir s'il faut ou non vider le ROB. Chaque entrée contient aussi le résultat à écrire dans les registres. Néanmoins, il faut prendre garde à un détail : certaines instructions ne renvoient pas de résultat, comme c'est le cas des branchements. La logique voudrait que ces instructions ne prennent pas d'entrée dans le ROB. Mais n'oubliez pas qu'on détermine à quelle adresse reprendre en se basant sur le program counter de l'instruction qui quitte le ROB : ne pas allouer d'entrées dans le ROB à ces instructions risque de faire reprendre le processeur quelques instruction à côté. Pour éviter cela, on ajoute quand même ces instructions dans le ROB, et on rajoute un champ qui stocke le type de l'instruction, afin que le ROB puisse savoir s'il s'agit d'une instruction qui a un résultat ou pas. On peut aussi utiliser cette indication pour savoir si le résultat doit être stocké dans un registre ou dans la mémoire. De plus chaque entrée du ROB contient le nom du registre de destination du résultat, histoire de savoir où l'enregistrer. Enfin, chaque entrée du ROB contient un bit de présence qui est mis à 1 quand le résultat de l'instruction est écrit dans l'entrée, qui sert à indiquer que le résultat a bien été calculé. Suivant le processeur, le ROB peut contenir d'autres informations.

Tampon d’historique[modifier | modifier le wikicode]

Une autre solution laisse les instructions écrire dans les registres dans l'ordre qu'elles veulent, mais conserve des informations pour remettre les écritures dans l'ordre, pour retrouver les valeurs antérieures. Ces informations sont stockées dans ce qu'on appelle le tampon d’historique (history buffer ou HB). Comme pour le ROB, le HB est une mémoire FIFO dont chaque mot mémoire est une entrée qui mémorise les informations dédiées à une instruction. Lorsqu'une instruction s’exécute, elle va souvent modifier le contenu d'un registre, écrasant l'ancienne valeur. Le HB sauvegarde une copie de cette ancienne valeur, pour la restaurer en cas d'exception. Lorsqu'une instruction située dans l'entrée la plus ancienne a levé une exception, il faut annuler toutes les modifications faites par les instructions suivantes. Pour cela, on utilise les informations stockées dans le HB pour remettre les registres à leur ancienne valeur. Plus précisément, on vide le HB dans l'ordre inverse d'ajout des instructions, en allant de la plus récente à la plus ancienne, jusqu'à vider totalement le HB. Une fois le tout terminé, on retrouve bien nos registres tels qu'ils étaient avant l’exécution de l'exception.

Tampon d’historique.

Banc de registres futurs[modifier | modifier le wikicode]

Le HB possède un défaut : remettre les registres à l'état normal prend du temps. Pour éviter cela, on peut utiliser deux bancs de registres. Le premier est mis à jour comme si les exceptions n’existaient pas, et conserve un état spéculatif : c'est le banc de registres futurs (future file ou FF). L'autre stocke les données valides en cas d'exception : c'est le banc de registres de retrait (retirement register file ou RRF). Le FF est systématiquement utilisé pour les lectures et écritures, sauf en cas d'exception : il laisse alors la main au RRF. Le RRF est couplé à un ROB ou un HB, histoire de conserver un état valide en cas d'exception.

Banc de registres futurs.