Résumé #6: Amélioration des performances par la technique du pipeline

À lire: pp. 368 à 405 1/10, 407 1/5 à 407 3/5, 409 3/4 à 410 1/2, 417 1/4 à 418 3/4, 425 4/5 à 426 1/5, 426 2/5 à 426 4/5, 429 à 435 2/3, 440 à 449.

6.1 Introduction

- Analogie pour pipeline = Ligne de montage: Permet l'amélioration des performances via le chevauchement de l'exécution de plusieurs instructions (forme de parallélisme).

- Accélération asymptotique pour une machine avec un pipeline idéal (M+) par rapport à une machine non-pipelinée (M-): M+ est N fois plus rapide que M-, où N = nombre d'étages du pipeline.

- Caractéristique majeure d'un pipeline: Augmente le débit (nombre d'instructions exécutées par unité de temps) mais sans changer le temps de latence (temps total requis pour l'exécution d'une instruction donnée).

6.2 Un chemin de données pipeliné

- Chemin de données pipeliné: Semblable à celui de la mise en oeuvre simple avec un (1) seul cycle par instruction (Section 5.3), mais décomposé en 5 étages et avec des registres temporaires entre les étages (un registre pour chacun des éléments devant être transmis d'un étage à un autre).

- Les 5 étages -- EI, DI, EX, MEM et ER -- du chemin de données pipeliné de la Section 6.2 correspondent aux étapes de la mise en oeuvre du processeur avec un nombre variable de cycles (Section 5.4).

- Chaque registre inter-étage doit être vu comme composé de deux parties: une partie utilisée en lecture (moitié droite) et une autre en écriture (moitié gauche). A chaque cycle d'horloge, les données avancent, à travers le chemin de données, de la partie lecture d'un registre inter-étage à la partie écriture du registre inter-étage suivant.

6.3 Le contrôle pipeliné

- Unité de contrôle: Identique à celle de la mise en oeuvre à un (1) cycle par instruction (Section 5.3), avec les signaux de contrôle transmis (dupliqués) d'un étage à un autre (lorsque nécessaire) via des registres inter-étages.

- Caractéristiques de l'UC avec pipeline idéal (i.e., sans aléas):

• L'exécution d'une nouvelle instruction s'amorce à chaque cycle (donc, asymptotiquement, CPI = 1) mais chaque instruction prend 5 cycles à s'exécuter.
• Le pipeline prend 4 cycles avant de se remplir, i.e., avant de fonctionner à pleine capacité.
• Tous les signaux de contrôle sont déterminés/calculés à l'étape ID puis transmis aux étapes subséquentes via les registres temporaires inter-étages.

6.4 Les aléas de données

- Problème: Il peut exister des dépendances entre les instructions, faisant en sorte que les données requises par une instruction ne sont pas disponibles au moment approprié. Par ex.: une instruction utilise un registre dont le résultat est calculé par l'instruction précédente; comme l'écriture dans le registre ne se fait qu'à la fin du pipeline (ER), le contenu du registre n'est pas disponible à l'étape de lecture des registres (DI).

- Solutions possibles:

• Logiciel: Le compilateur s'assure que de telles dépendances n'existent pas, soit en modifiant l'ordre des instructions du programme (sans toutefois changer son effet), soit en insérant des instructions nop supplémentaires entre les instructions pour lesquelles des dépendances existent, de façon à créer un délai dans l'exécution des instructions subséquentes. Dans ce dernier cas, on a alors des cycles d'horloge durant lesquels aucun travail utile n'est effectué dans certains étages (bulles).
• Suspensions: Le matériel détecte les dépendances et suspend automatiquement le pipeline, i.e., cesse temporairement l'amorce de l'exécution de nouvelles instructions jusqu'à ce que le conflit soit résolu. Cf. Section 6.5.
• Envois: Le résultat approprié est transmis via des registres temporaires additionnels plutôt que via les vrais registres. Cf. Section 6.6.

6.5 Le contrôle pour les aléas de données: les suspensions

- Stratégie: Dès qu'une dépendance entre des instructions est détectée, le pipeline est suspendu, plus précisément, l'insertion de nouvelles instructions dans le pipeline est suspendue (on parle alors de la création de bulles dans le pipeline).

- Méthode de niveau matériel, donc nécessitant l'utilisation de matériel supplémentaire à savoir une unité de détection des aléas. L'unité de détection des aléas, en examinant le contenu des registres inter-étages, peut reconnaître et détecter les dépendances; dans ce cas, l'unité insère une bulle en désactivant (i.e., en mettant à 0) tous les signaux de contrôle.

- Désavantage: Dès qu'une dépendance est détectée, plusieurs bulles sont créées dans le pipeline, dégradant ainsi les performances de la machine (augmentation du CPI moyen) à cause de la présence de cycles supplémentaires inutiles: la machine tourne partiellement à vide pendant un certain nombre de cycles.

6.6 Réduire les aléas de données: l'envoi

- Stratégie: Bien que le résultat final ne soit pas encore écrit dans le véritable registre matériel (i.e., dans le banc de registres), le résultat requis est déjà calculé et disponible dans les registres temporaires inter-étages. La technique de l'envoi consiste donc à transmettre la valeur appropriée sans attendre son écriture dans le banc de registres, en envoyant sa valeur à partir des registres temporaires.

- Méthode de niveau matériel donc nécessitant l'utilisation de matériel supplémentaire à savoir une unité d'envoi. L'unité d'envoi détecte les aléas en examinant le contenu des registres inter-étages et sélectionne, via les multiplexeurs, soit les valeurs normales des registres (obtenues via le banc de registres), soit les valeurs envoyées à partir des registres temporaires.

- Avantage: Nécessite du matériel peu complexe tout en permettant d'obtenir des résultats intéressants: contrairement à la technique des suspensions, aucun cycle inutile (bulle) n'est généré. (Exception: instruction de chargement)

6.7 Les aléas de branchement

- Problème: La décision pour un branchement survient assez tard dans le pipeline (étape MEM), ce qui implique que l'exécution des instructions qui suivent le branchement peut avoir déjà été amorcée ... alors que ces instructions ne devront pas être exécutées si le branchement s'effectue. (On parle alors de nettoyer le pipeline, i.e., de le débarrasser des instructions dont l'exécution a été amorcée mais qui ne doivent pas s'exécuter).

- Nombreuses solutions possibles:

• Suspension: Un branchement entraîne automatiquement une suspension du pipeline jusqu'à ce que la condition soit déterminée. Solution simple (pas de nettoyage) mais non performante (plusieurs bulles générées pour chaque branchement).
• Branchement différé: Les n instructions qui suivent immédiatement l'instruction de branchement s'exécutent toujours, peu importe que le branchement s'effectue ou non. Solution simple au niveau matériel puisque cela ne nécessite jamais de nettoyage du pipeline (parce que la durée du délai de branchement est choisie en fonction du moment où la condition de branchement est certaine d'être déterminée). Par contre, solution plus complexe au niveau du compilateur: ce dernier doit changer l'ordre des instructions du programme ou insérer des nop de façon à s'assurer de remplir correctement les n cases de délai de branchement. (Note: La plupart des machines utilisant des branchements différés ont un délai de branchement de 1 cycle, i.e., seule l'instruction qui suit immédiatement le branchement va toujours s'exécuter, indépendamment de la condition.)
• Prédiction: On tente de prédire si le branchement sera effectué ou non. Si la prédiction est juste, aucun nettoyage du pipeline n'est requis, donc aucune pénalité ou délai. Par contre, si la prédiction est erronée, une pénalité de branchement survient à cause du nettoyage du pipeline, lequel doit être réamorcé avec les instructions provenant de la destination effective.
  • Prédiction statique:

    >> Exemple: On prédit toujours que le branchement ne sera pas effectué, i.e., on continue d'exécuter les instructions qui suivent le branchement. Si le branchement s'effectue, le pipeline doit être nettoyé et les instructions obtenues à partir de l'adresse destination doivent être exécutées; autrement, i.e., branchement non effectué, pas de pénalité.

    >> Exemple (PowerPC 601): Un branchement vers l'avant est prédit non effectué alors qu'un branchement vers l'arrière (boucle) est prédit effectué. Une pénalité survient lorsque la prédiction est erronée.

  • Prédiction dynamique: Le matériel conserve, durant l'exécution du programme, des informations sur le comportement passé des branchements, de façon à prédire leur comportement futur. Nécessite du matériel supplémentaire, donc plus coûteux ... mais permet de meilleures prédictions.

    >> Exemple: Table de prédiction des branchements (branch target buffer). Pour chaque instruction de branchement récemment exécutée, la table indique: i) si le branchement fut effectué ou non; ii) l'adresse destination. Lorsqu'une instruction de branchement est rencontrée, si elle est présente dans la table et que la prédiction indique ``effectué'', alors les instructions à l'adresse destination indiquée dans la table sont obtenues et exécutées. Comme dans la méthode précédente: pénalité si la prédiction est erronée.

6.9 Performances des systèmes pipelinés

- CPI = Nombre moyen de cycles par instruction. Toutefois, peut aussi être vu comme le nombre de cycles requis, en moyenne, entre chaque instruction complétée.

- Machine avec pipeline idéal, i.e., en ignorant les aléas: CPI moyen = 1.

- Machine avec pipeline, en tenant compte des aléas: CPI moyen = 1 + pénalité moyenne dûe aux aléas de données et de contrôle.

- Différences entre les diverses mises en oeuvre vues jusqu'à présent, illustrant divers compromis possibles entre CPI vs.\ vitesse d'horloge:

• Mise en oeuvre simple avec un seul cycle par instruction (Section 5.3): CPI faible (= 1) mais horloge lente.
• Mise en oeuvre avec un nombre variable de cycles par instruction (Section 5.4): Horloge rapide mais avec CPI plus élevé ( 4).
• Mise en oeuvre avec pipeline: CPI faible ( 1) et horloge rapide ... donc la solution la plus performante.