Fonctionnement d'un ordinateur/Dépendances de données

Une limite à une utilisation efficiente du pipeline tient dans l'existence de dépendances entre instructions. Deux instructions ont une dépendance quand elles manipulent la même ressource : le même registre, la même unité de calcul, la même adresse mémoire. Il existe divers types de dépendances, appelées dépendances structurales, de contrôle et de données. Dans ce chapitre, nous allons nous concentrer sur les dépendances de données. Deux instructions ont une dépendance de données quand elles accèdent (en lecture ou écriture) au même registre ou à la même adresse mémoire. Différents cas se présentent alors :

  • Read after read : Deux instructions lisent la même donnée, mais pas en même temps.
  • Read after write : La première instruction va écrire son résultat dans un registre ou dans la RAM, et un peu plus tard, la seconde va lire ce résultat et effectuer une opération dessus. La seconde instruction va donc manipuler le résultat de la première.
  • Write after read : La première instruction va lire un registre ou le contenu d'une adresse en RAM, et la seconde va écrire son résultat au même endroit un peu plus tard.
  • Write after write : Nos deux instructions effectuent des écritures au même endroit : registre ou adresse mémoire.

Pour les dépendances Read after read, on peut mettre les deux instructions dans n'importe quel ordre, cela ne pose aucun problème. Ce ne sont pas de vraies dépendances et je les présente par pur souci d'exhaustivité. Par contre, ce n'est pas le cas avec les trois autres types de dépendances, qui imposent d’exécuter la première instruction avant la seconde. Cela fait que le processeur ou le compilateur doit conserver l'ordre des instructions et ne pas réordonnancer. De plus, la première instruction doit avoir terminé son accès mémoire avant que l'autre ne commence le sien. Et cette contrainte n'est pas forcément respectée avec un pipeline, dont le principe même est de démarrer l’exécution d'une instruction sans attendre que la précédente soit terminée. Dans ces conditions, l'ordre de démarrage des instructions est respecté, mais pas l'ordre des accès mémoire. Reste que les dépendances ne posent problèmes en termes d'accès mémoires que dans certains cas bien précis.

  • Les dépendances Read after write apparaissent quand une instruction a besoin du résultat de la précédente alors que celui-ci n'est disponible qu'après avoir été enregistré dans un registre, soit après l'étape d’enregistrement. Si on ne fait rien, la seconde instruction ne lira pas le résultat de la première, mais l'ancienne valeur, encore présente dans le registre.
  • Les dépendances WAR n'apparaissent que sur les pipelines où l'écriture des résultats a lieu assez tôt (vers le début du pipeline), et les lectures assez tard (vers la fin du pipeline).
  • Les dépendances WAW n'apparaissent que si le pipeline autorise les instructions sur plusieurs cycles d’horloge ou les écritures qui prennent plusieurs étages.

Les bulles de pipeline modifier

Pour éviter tout problème avec ces dépendances, on est obligé d'insérer des instructions qui ne font rien entre les deux instructions dépendantes. Mais insérer ces instructions nécessite de connaitre le fonctionnement du pipeline en détail : niveau portabilité, c'est pas la joie !

Il est possible de déléguer cet ajout de NOP au processeur, à ses unités de décodage. Si une dépendance de données est détectée, l'unité de décodage d'instruction met l'instruction en attente tant que la dépendance n'est pas résolue. Durant ce temps d'attente, on insère des vides dans le pipeline : certains étages seront inoccupés et n'auront rien à faire. Ces vides sont appelés des calages (stall), ou bulles de pipeline (pipeline bubble). Lors de cette attente, les étages qui précédent l'unité de décodage sont bloqués en empêchant l'horloge d'arriver aux étages antérieurs au décodage.

 
Pipeline bubble

C'est un nouvel étage, l'étage d'émission (issue), qui détecte les dépendances et rajoute des calages si besoin. Pour détecter les dépendances, il compare les registres utilisés par l'instruction à émettre et ceux utilisés par les instructions dans le pipeline. Il n'y a pas de dépendance si ces registres sont différents, alors qu'il y a dépendance dans le cas contraire. L'unité d'émission est donc un paquet de comparateurs reliés par des portes OU. En sortie, elle fournit un signal STALL, qui indique s'il faut caler ou non.

L'unité d'émission doit connaitre les registres de destination des instructions dans le pipeline, ainsi que les registres utilisés par l'instruction à émettre. Obtenir les registres de destination des instructions dans le pipeline peut se faire de deux manières. La première méthode utilise le fait que les noms de registres sont propagés dans le pipeline, comme tous les signaux de commande. Dans ces conditions, rien n’empêche de relier les registres tampons chargés de la propagation à l'unité d'émission.

 
Détection des dépendances dans un pipeline, sans scoreboard.

Avec la seconde possibilité, l'unité d'émission mémorise ces registres dans une petite mémoire : le scoreboard. C'est une mémoire dont les mots mémoire font un bit : chaque adresse correspond à un nom de registre, et le bit correspondant à cet adresse indique si le registre est réservé par une instruction en cours d'exécution dans le pipeline. Lors de l'émission, le scoreboard est adressé avec les noms des registres source et destination utilisés dans l’instruction, pour vérifier les bits associés. Le scoreboard est mis à jour lorsqu'une instruction écrit son résultat dans un registre, à l'étape d’enregistrement : le scoreboard met le bit correspondant à zéro.

Le contournement et le réacheminement modifier

Pour diminuer l'effet des dépendances RAW, on peut faire en sorte que le résultat d'une instruction soit disponible rapidement. Avec la technique du contournement (bypass), le résultat est utilisable en sortie de l'unité de calcul, avant d'être enregistré dans les registres.

 
Pipeline Bypass

Implémenter la technique du contournement demande de relier la sortie de l'unité de calcul sur son entrée en cas de dépendances, et à la déconnecter sinon : cela se fait avec des multiplexeurs.

 
Contournement avec des multiplexeurs.

Pour détecter les dépendances, il faut comparer le registre destination avec le registre source en entrée : si ce registre est identique, on devra faire commuter le multiplexeur pour relier la sortie de l'unité de calcul.

 
Implémentation complète du contournement

Pour améliorer un peu les performances du système de contournement, certains processeurs ajoutent un petit cache en sortie des unités de calcul : le cache de contournement (bypass cache). Celui-ci mémorise les n derniers résultats produits par l’unité de calcul. Le tag de chaque ligne de ce cache est le nom du registre du résultat.