Comment accélérer un pipeline ? Qu'est-ce qu'un prédicteur de branchement ? Introduction Comme on a vu dans le dernier cours sur les systèmes embarqués, le pipeline permet de lancer une instruction par cycle. Néanmoins l’utilisation d’un pipeline peut avoir différents aléas : aléa de données : donnée non disponible à cause de la latence du pipelinealéa de contrôle : délai lors de l’exécution d’une instruction de branchement/sautaléa de structure : conflit pour l’accès à une ressource matérielle Sommaire masquer 1 Comment accélérer un pipeline ? Qu'est-ce qu'un prédicteur de branchement ? 1.1 Introduction 1.2 Les aléas de données 1.3 Les dépendances 1.4 Interruption sur les pipelines 1.4.1 Exécution « spéculative » des instructions 1.5 Augmentation profondeur du pipeline 1.6 Aléa de branchement 1.6.1 La prédiction de branchement 1.6.2 Le cache de branchement Les aléas de données Les aléas de données arrivent quand la valeur que l’on souhaite récupérer n’est pas disponible ou que l’on obtient une ancienne valeur de la variable que l’on souhaite récupérer et non la nouvelle valeure calculé.Donnée non disponibleMais quand la donnée n’est pas disponible dans le processeur, les aléas de données ne peuvent être résolus par des court-circuits.— Lecture mémoire— opérations en plusieurs cycles (flottant) On opére alors une suspension du pipeline (bubble ou pipeline stall)En pratique, pour une suspension :— on fige le pipeline pour les étages LI et DI (pas d’écriture des registrespipeline)— on injecte un nop dans le registre LR/EX Latence de donnéeEn décomposant les instructions dans chaque étage, il se peut que les données dont on a besoin ne soit pas encore disponible du fait qu’elle est traité dans le cycle suivant par exemple. Ceci s’appelle une latence de cycle ou délai de chargement de cycle.Voici un exemple de latence : li di ex mm rr li di ex mm rr li di ex mm rr Ici on peut voir que si « mm » de la première ligne souhaite avoir la nouvelle valeur de « ex », alors il va devoir attendre deux cycles.Les opérations entières complexes (multiplication/division) et les opérations flottantes ont souvent une latence de plusieurs cycles.Les aléas de données entraînent alors un délai d’attente et donc on perds l’intérêt d’un pipeline.C’est pour cela que certaine opérations ne sont pas pipeliné, notamment les divisions. Les dépendances La dépendance est la contrainte de séquentialité entre instructions qui lisent ou écrivent une donnée dans un même registre.Il y a différent type de dépendances :Dépendance de données (read-after-write) : L’instruction i écrit le registre r et l’instruction i + n lit rDépendance de nom (write-after-read) : L’instruction i lit la donnée dans r et l’instruction i+ n génère une nouvelle valeur dans rDépendance de sortie (write-after-write) : Les instructions i et i + n génèrent une information dans le même registre r.On va donner un exemple de dépendance entre plusieurs registres : add r1,r2,r3add r4, r1, r5add r1, r6, r7add r1, r8, r9add r10,r1,r11 dépendance de donnée : L’information dans r1 est utilisée par l’instruction 2 . C’est une vraie dépendance de donnée qui doit être respectée.dépendance de nom : Le registre r1 est écrit par l’instruction 3 et l’instruction 2 doit lire son contenu avant. Par contre, il suffit d’utiliser un autre registre que r1 pour que le problème disparaisse.dépendance de sortie : Les instructions 3 et 4 écrivent successivement le registre r1. L’ordre des écritures doit être respecté. Interruption sur les pipelines Comme sur les fonctions, il existe aussi des interruptions sur les pipelines. On va voir comment les gérer.L’exécution d’un programme peut être interrompue par :un événement extérieur (interruption)un problème interne au processeur (exception) (erreur arithmétique (÷0), problème d’accès mémoire (erreur du bus))…Pour une exception propre :toutes les instructions avant celle qui a provoqué l’exception doivent se termineraucune instruction suivant celle qui a provoqué l’exception ne doit se terminerIl y a plusieurs façon de traiter les interruptions dans un pipeline :Terminaison dans l’ordre des instructions : Une instruction multi-cycles oblige toutes les instructions suivantes à attendre pour se terminer, même s’il n’y pas de dépendances de données ou si elles ne provoquent pas d’exceptions.Terminaison non ordonnées des instructions : Sans dépendance de données, si on autorise les instructions suivantes à se terminer, elles vont modifier les registres et donc la mémoire. Des exceptions « propres » sont alors impossibles (les instructions suivant l’exception ne doivent pas terminer). Exécution « spéculative » des instructions La dernière façon de traiter les interruptions dans un pipeline est l’exécution spéculative des instructions. Les instructions peuvent s’exécuter, mais on attend pour modifier l’état du processeur ou de la mémoire.Pour cela on range temporairement les résultats des instructions et on ne modifie les registres et la mémoire que lorsque l’on est sûr qu’il n’y aura pas d’exception.Le renommage des registresLe renommage des registres est aussi utile pour l’exécution spéculative.Pour cela il y a deux possibilités : Duplication du banc de registres : Une instruction écrit dans un registre futur et on recopie dans un registre présent quand l’instruction est garantie. Au lancement de l’instruction, on associe un registre physique à un registre logique avec une table de correspondance (renommage). La recopie du registre physique vers le registre logique se fait quand l’instruction est achevée et garantie. Augmentation profondeur du pipeline En ajoutant des étages d’un pipeline, on peut augmenter la fréquence d’horloge (superpipeline). Ceci corresponds à la duplication des étages critiques et l’accroissement de la profondeur du pipeline.Néanmoins ceci a un coût : Le superpipeline augmente les délais de chargement et de branchement (en cycles) mais permet de réduire le temps de cycle.Le nombre d’étages de pipeline dépend beaucoup du processeur utilisé : Architecture Pentium Pipeline Architecture Arm Pipeline Pentium 5 ARM 1-7 3 Pentium Pro 14 ARM 11 8 Intel Core 14 Cortex A8 13 Aléa de branchement Une rupture de séquence dans un programme provoque un délai de branchement. Pour supprimer ce temps de branchement, on fait de la prédiction de branchement matériel et de l’ordonnancement des instructions.Nous allons maintenant voir comment faire de la prédiction de branchement. Pour cela on doit introduireIl y a différente manière de supprimer le temps prit par le changement de branchement : — La prédiction de branchement— L’instructions de transfert conditionnel— L’ ordonnancement des instructions La prédiction de branchement Si on attend d’avoir décodé l’instruction de branchement, on va avoir une pénalité de temps. On va donc supposer dans la prédiction de branchement qu’une instruction de branchement a un comportement souvent répétitif.De plus on va mémoriser dans une petite mémoire le comportement des instructions de branchement (pris/non pris + adresse cible).Il y a deux grand types de prédiction :Prédiction statique (à la compilation)Prédictions dynamiques (à l’exécution) Prédiction statiqueLa prédiction statique est l’information connues à la compilation (boucles, par exemple) grâce au profilage des programmes. Dans la prédiction statique on suppose le même comportement pour un branchement dans un programme.Il peut être défini par le matériel ou prédit par le compilateur : toujours pristoujours non-prisbranchement arrière pris (avec une boucle while ou boucle for)branchement avant non pris (avec if then else) Prédiction dynamique Les prédictions dynamiques sont faite durant l’exécution du programme.Il y a deux type prédicteurs dynamique :Prédicteurs locaux (1 et 2 bits)Prédicteurs globaux (historique de branchements)Le Prédicteur 1 bitPour ce prédicteur on mémorise l’état pris/non pris pour chaque branchement. Avec ce prédicteur 1 bit on suppose le comportement d’un branchement suffisamment répétitif. On va maintenant voir un exemple de prédicteur 1 bits. Dans cet exemple on va alterner les branchements pris puis non pris (P = pris et N = Non pris.). Ceci se trouve sur la première ligne.La deuxième ligne corresponds aux valeurs du prédicteur. On va maintenant expliquer la deuxième ligne du prédicteur. Pour le premier branchement, on n’a pas d’historique donc on met un point d’interrogation. Comme le premier branchement était pris, alors le deuxième branchement prédit est aussi pris ce qui n’était pas le bon banchement . (Il faut regarder colonne par colonne)On peut voir dans les colonnes suivante que le prédicteur se trompe à chaque fois (quand c’est pris le prédicteur prédit non pris et inversement). A chaque mauvaise prédiction on entoure la mauvaise valeur du prédicteur. On peut donc voir qu’avec un changement de branchement de pris à non pris le prédicteur ne peut pas s’adapter et se trompe à chaque fois. Conclusion : En changeant de branchement à chaque fois on n’obtient aucune prédiction de bonne avec un prédicteur 1 bit. On va maintenant voir un autre exemple avec un changement de branchement moins rapide afin de voir si le prédicteur 1 bit est plus performant. Dans cet exemple on va alterner les branchements pris puis non pris (P = pris et N = Non pris.). Ceci se trouve sur la première ligne.La deuxième ligne corresponds aux valeurs du prédicteur. Ceci va être mise en place avec le cache de branchement. Le cache de branchement Pour pouvoir faire de la prédiciton de branchement, on va s’intéresser au cache d’adresse de branchement.Celui est constitué d’une table :l’adresse du branchement (étiquette)les bits utilisés pour déterminer la prédiction pris/non pris du branchementl’adresse cible quand le branchement est pris