Fonctionnement d'un ordinateur/Interruptions et pipeline

Un livre de Wikilivres.

Sur un processeur sans pipeline, les branchements ne posent aucun problème. Mais si on rajoute un pipeline, les branchements sont une source de problèmes. Pour comprendre pourquoi, prenons l'exemple de l’exécution d'un branchement. Lorsqu'on charge un branchement dans le pipeline, l'adresse à laquelle brancher ne sera connue qu'après quelques cycles et des instructions seront chargées durant ce temps. Et ces instructions chargées à tord s’exécuteront à tord. Pour éviter tout problème, on doit faire en sorte que ces instructions ne modifient pas les registres du processeur ou qu'elles ne lancent pas d'écritures en mémoire.

En plus des instructions de branchements, il faut aussi tenir compte des interruptions et exceptions matérielles, qui sont des branchements cachés. Rappelons qu'une interruption ou une exception matérielle stoppent l’exécution du programme en cours et effectuent un branchement vers une routine d'interruption. Imaginons que le processeur exécute un programme et qu'une exception survienne. L'exception est le plus souvent détectée loin dans le pipeline, généralement dans les étages finaux. 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, instructions qui 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. La même chose survient avec les branchements et les interruptions.

Exception et pipeline

La solution la plus simple consiste à inclure des instructions qui ne font rien, des NOP (No OPeration), à la suite du branchement : c'est ce qu'on appelle un délai de branchement. Le processeur chargera ces instructions, jusqu’à ce que l'adresse à laquelle brancher soit connue. Par exemple, si l'adresse à laquelle brancher est connue avec deux cycles d’horloge de retard, il suffit de placer deux NOP juste après le branchement. Mais le nombre de NOP à ajouter dépend du pipeline du processeur, ce qui peut poser des problèmes de compatibilité, sans compter que la perte de performance est notable. De plus, cette solution ne marche que pour les branchements, pas pour les exceptions et interruptions.

Pour éliminer les délais de branchements et régler les problèmes liés aux interruptions/exceptions, les concepteurs de processeur ont fait en sorte que le processeur gère lui-même exceptions et interruptions correctement. Avec ces techniques, le processeur spécule que les instructions qu'il vient de charger ne lèvent aucune exception, qu'il n'y a pas d'interruptions, qu'il n'y a pas de branchements. Le processeur continue à exécuter ses instructions, ce qui évite des bulles de pipeline inutiles si la spéculation tombe juste. Mais si jamais la prédiction se révèle fausse, il annule les instructions exécutées à tord suite à cette erreur de spéculation. L'idée est que les écritures en RAM, dans les registres, ou dans le program counter doivent pouvoir être empêchées et annulées en cas de mauvaises prédictions. Au final, ce pari est souvent gagnant : les exceptions et interruptions sont très rares, même si beaucoup d'instructions peuvent en lever.

L'achèvement dans l’ordre[modifier | modifier le wikicode]

Avec l’achèvement dans l'ordre, le processeur garantit que les écritures se fassent dans l'ordre du programme, que ce soit pour les écritures dans les registres ou la RAM. Avec un pipeline de longueur fixe, il n'y a rien à faire, contrairement à ceux de longueur variable. Prenons cet exemple : je charge deux instructions consécutives dans le 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.

L'ajout de bulles de pipeline[modifier | modifier le wikicode]

La solution consiste à retarder certaines instructions de quelques cycles d'horloges. 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. On dit alors qu'on ajoute une bulle de pipeline, terme qui n'est pas très évident au premier abord...

Bulle de pipeline.

Pour ce faire, on utilise un circuit spécial : le registre de décalage de résultat , 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.

La 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'à l'étage final du pipeline, qui est chargé d'enregistrer les données dans les registres et/ou la RAM. 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.

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

L'achèvement dans le désordre[modifier | modifier le wikicode]

Il existe d'autres solutions pour maintenir l'ordre des écritures, où les instructions peuvent se terminer dans un ordre différent du programme. L'idée est que les instructions peuvent enregistrer leurs résultat le plus tôt possible, sans recourir à des bulles de pipeline. Les instructions démarrent dans l'ordre du programme, mais les plus rapides peuvent écrire leur résultat avant les autres. Toutes ces techniques 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 :

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

Le tampon de réordonnancement[modifier | modifier le wikicode]

Une première solution consiste à exécuter les instructions sans se préoccuper de l'ordre des écritures, avant de les remettre dans le bon ordre. Pour remettre en ordre ces écritures, les résultats des instructions sont mis en attente dans une FIFO, avant d'ê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). Avec le tampon de réordonnancement, les résultats ne sont pas écrits directement dans les registres ou la RAM, mais dans une mémoire séparée, afin que les résultats soient ensuite envoyés aux registres dans le bon ordre.

Tampon de réordonnancement.

Lorsqu'une instruction vient d'être décodée, elle 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 fait automatiquement dans l'ordre du programme. Un résultat est enregistré dans un registre lorsque les instructions précédentes (dans l'ordre du programme) ont toutes elles-mêmes enregistré leurs résultats. Dit autrement, seule l'instruction la plus ancienne peut quitter le ROB et enregistrer son résultat, les autres instructions doivent attendre. 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.

Le ROB est composé de plusieurs entrées, des blocs qui stockent des informations sur les résultats à écrire dans les registres ou la mémoire. Chaque entrée contient les informations suivantes :

  • 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.
  • Le résultat de l'instruction, à écrire dans les registres.
  • 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é.
  • Le nom du registre de destination du résultat, histoire de savoir où l'enregistrer.
  • Un bit Exception qui précise si l'instruction a levé une exception ou non.
  • D'autres informations, suivant le processeur.

Lorsqu'un résultat quitte le ROB, pour être enregistré dans les registres, le bit Exception est vérifié pour savoir s'il faut ou non vider le ROB.

Pour rappel, 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.

Quand le ROB est plein, le processeur bloque les étages de chargement, décodage, etc. Cela évite de charger des instructions dans le ROB alors qu'il est plein. Notons que 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.

Le 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 modifie un registre, le HB sauvegarde une copie de l'ancienne valeur, pour la restaurer en cas d'exception. Pour annuler les modifications faites par des instructions exécutées à tort, on utilise le contenu de l'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 les registres tels qu'ils étaient avant l’exécution de l'exception.

Tampon d’historique.

Le banc de registres futurs[modifier | modifier le wikicode]

Avec un HB, 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.