Le pipeline superscalaire
Une limitation supplémentaire liée au pipeline simple est l’attente inutile que subit une instruction lorsqu’une instruction entrée avant elle dans le pipeline subit elle-même une attente. En effet, si une instruction doit attendre pour s’exécuter, tous les précédents étages du pipeline sont aussi bloqués. Et donc toutes les instructions suivant cette instruction en attente doivent elles aussi subir cette attente. L’organisation superscalaire du pipeline tente de résoudre en partie ce problème en permettant à plusieurs instructions d’être traitées en parallèle à chaque étage. Ainsi, dans cet exemple, chaque étage peut traiter jusqu’à deux instructions chaque cycle. On dit alors que la largeur du pipeline superscalaire est de deux. Un ordonnanceur est nécessaire pour déterminer si les deux instructions qui vont être traitées à l’étage d’exécution sont effectivement indépendantes et peuvent s’exécuter en parallèle. Si ce n’est pas le cas, l’instruction dépendante est mise en attende. Mais cela ne provoque pas nécessairement le blocage du pipeline, cela réduit temporairement la largeur du pipeline au niveau de l’étage d’exécution.
Le gain d’une organisation superscalaire est donc double : plus d’instructions sont traitées chaque cycle et l’e et des dépendances de données est réduit. Le parallélisme d’instructions est donc mieux exploité.
File des loads et des stores et parallélisme mémoire
La file des loads et des stores ou LSQ sert à stocker les informations relatives aux instructions mémoire, en particulier l’adresse mémoire qui sera accédée et la donnée qui sera écrite dans le cas des stores. L’exécution d’une instruction mémoire se fait en deux temps : d’abord le calcul de l’adresse mémoire et ensuite l’accès à la mémoire. Le calcul de l’adresse est traité comme n’importe quelle autre instruction et est soumis aux mêmes problématiques. Le cas de l’accès mémoire est un peu plus complexe à gérer. Pour respecter la sémantique du programme, l’ordre des accès mémoire doit être respecté. Cependant, les loads peuvent être exécutés dans n’importe quel ordre les uns par rapport aux autres. Par contre, les stores doivent être traités dans l’ordre et les loads doivent se faire dans l’ordre par rapport aux stores. Plus précisément, un load doit être lancé obligatoirement après un store si la lecture en mémoire se produit à la même adresse qu’un store précédent. Comme les loads et les stores sont insérés dans la LSQ dans l’ordre, cette structure permet naturellement de vérifier l’ordonnancement mémoire.
Pour conserver l’ordre entre les stores, l’accès mémoire correspondant est uniquement exécuté lorsque le store atteint l’étage de commit et donc dans l’ordre. Lorsque l’accès d’un load est prêt, la LSQ vérifie que les adresses de tous les stores plus anciens que le load sont connues pour s’assurer qu’aucun conflit n’existe avec un des ces stores. Si c’est le cas, le lancement du load est retardé jusqu’à ce que la valeur du store soit prête. À ce moment-là, la valeur du store est directement transmise au load, sans devoir faire appel à la hiérarchie mémoire. On parle du renvoi de l’écriture ou store forwarding. Dans le cas où l’adresse d’un store n’est pas encore connue, le processeur peut adopter deux comportements. Dans le cas où il est conservatif, il part du principe que ce store peut être en con it avec le load et il retarde donc son exécution. Dans le cas où il est optimiste, il estime que le store n’est pas en conflit et que l’accès mémoire du load peut donc s’effectuer. L’accès est donc lancé spéculativement, et sa validité doit être vérifié lorsque l’adresse du store devient disponible. Ce mécanisme de vérification est en fait exécuté lorsque l’accès du store est lancé, au commit. À ce moment-là, le store vérifie l’ensemble des loads plus jeunes que lui dont l’accès a déjà été fait. Si l’un des loads est en conflit, le pipeline doit être vidé et l’exécution doit recommencer à partir de ce load.
Tampon de réordonnancement et validation des instructions
Le tampon de réordonnancement, ou Re-Ordering Bu er (ROB), sert à conserver l’ordre dans lequel les instructions sont entrées dans le pipeline et donc l’ordre dans lequel elles doivent être validées. La validation d’une instruction consiste à valider son résultat. Elle se fait à l’étage de commit. Pour les stores, il s’agit d’envoyer la requête d’écriture à la hiérarchie mémoire. Pour les autres instructions, cela consiste à valider le lien entre le registre destination architectural de l’instruction et le registre physique associé. Ainsi, la valeur courante de ce registre architectural est modifiée du point de vue du programmeur. Une seconde mapping table est donc utilisée au commit pour conserver les liens validés entre les registres architecturaux et les registres physiques. Elle est appelée mapping table non spéculative, car elle représente l’état architectural du processeur au niveau des registres, visible par le programmeur. De son point de vue, l’instruction est considérée comme exécutée une fois cette l’étape de commit accomplie.
Les exceptions liées aux instructions, comme une division par zéro ou un appel système, sont traitées à cet étage. En e et, dans ce cas, l’exécution du programme est souvent stoppée, temporairement ou non, pour traiter l’événement. Le processeur est donc dans un état où l’instruction produisant l’exception est validée et considérée comme exécutée. Avant le traitement de l’exception, l’état de l’exécution du programme est sauvegardé, notamment la valeur courante de tous les registres architecturaux. Ces valeurs sont récupérées en lisant les registres physiques associés aux registres architecturaux dans la mapping table du commit. Une fois l’exception traitée, si besoin est, le processeur peut recommencer à traiter le programme à partir de l’état sauvegardé de l’exécution.
Prédiction de branchements
La prédiction de branchements se base sur une observation simple : le comportement d’un programme est globalement cyclique. Les instructions le composant sont donc exécutées de nombreuses fois lors de l’exécution complète du programme. Et chaque nouvelle instance dynamique de la même instruction statique a un comportement qui est souvent le même. En particulier, les instructions de branchement ont souvent un comportement périodique. De plus, la cible de la plupart des branchements est toujours la même. Un prédicteur de branchements analyse donc le comportement dynamique des branchements et exploite le caractère périodique de ce comportement pour fournir sa prédiction. La précision d’un prédicteur mesure sa capacité à produire des prédictions correctes. C’est le rapport du nombre de bonnes prédictions sur le nombre total de prédictions.
Prédiction de la cible : Selon son type, un branchement peut avoir une ou plusieurs cibles. Les branchements de type direct ont leur cible directement dé nie dans le code de l’instruction. Elle est donc connue dès que l’instruction est décodée. Néanmoins, elle est quand même prédite pour éviter l’insertion de bulles le temps que le branchement arrive à l’étage de décodage. Cependant, cette prédiction est très simple puisqu’une fois que le branchement a été rencontré pour la première fois, sa cible peut être enregistrée. Comme elle ne change pas au cours de l’exécution, tant que cet enregistrement existera, la prédiction donnée sera toujours exacte. La structure qui est utilisée pour enregistrer la cible des branchements est le tampon des cibles des branchements ou Branch Target Bu er (BTB). Il est généralement organisé sous la forme d’une mémoire associative dont la taille et le niveau d’associativité influent directement sur sa précision. En e et, sa précision dépend uniquement de sa capacité à retenir les cibles qui y ont été enregistrées.
Le BTB est aussi utilisé pour l’autre type de branchements, les branchements indirects. Ceux-ci ont leur cible qui est stockée dans un registre. C’est donc l’exécution du programme qui calcule dynamiquement cette cible. Celle-ci peut donc changer à chaque instance dynamique du branchement. Comme ce n’est pas toujours le cas, le BTB parvient à être relativement efficace sur ce type de branchements. Cependant, il est possible de concevoir un prédicteur dont le rôle est de prédire la cible des branchements indirects.
Prédiction de la direction
Le domaine de prédiction de la direction a beaucoup plus été exploré par la recherche que celui de la prédiction de la cible. Cela s’explique par la difficulté qu’il y a à concevoir un prédicteur de direction précis et à la relative simplicité du problème posé par la prédiction de la direction, notamment pour les branchements directs. Il existe de nombreux types de prédicteurs de direction. Ce document en liste quelques uns, mais ne prétend pas être exhaustif.
Comme un prédicteur de branchements est essentiellement une structure qui enregistre le comportement dynamique des branchements, un historique de ce comportement est conservé par le prédicteur et ensuite utilisé pour produire la prédiction. Cet historique peut être conservé de différentes manières, plus ou moins exactes. L’historique exact consiste en une suite de bits, 0 pour la direction non pris et 1 pour la direction pris. On constate deux grandes familles de prédicteurs à historique exact. Ceux qui conservent un historique pour chaque branchement, les prédicteurs à historique local, et ceux qui conservent l’historique global, c’est-à-dire la suite des directions de la suite des branchements qui sont traités par le pipeline. Une manière moins exacte consiste à enregistrer le comportement du branchement dans un automate. Celui-ci est généralement implémenté à l’aide d’un compteur à saturation.
Table des matières
Introduction
1 Architecture d’un processeur moderne
1.1 Les instructions et le programme
1.1.1 Représentation des instructions
1.1.2 Les registres
1.1.3 Registre source et registre destination
1.1.4 État architectural
1.2 Le pipe line simple
1.2.1 Les différents étages du pipeline
1.2.2 Mécanisme de contournement
1.2.3 Parallélisme apporté par le pipeline
1.2.4 Limitations
1.3 Le pipeline superscalaire
1.3.1 Limitations spécifiques
1.4 Principe de l’exécution dans le désordre
1.4.1 Vue d’ensemble
1.4.2 Renommage des registres
1.4.3 Mécanisme de lancement des instructions
1.4.4 Réseau de bypass
1.4.5 File des loads et des stores et parallélisme mémoire
1.4.6 Tampon de réordonnancement et validation des instructions
1.5 Problèmes liés aux branchements
1.5.1 Prédiction de branchements
1.5.2 Instructions prédiquées
2 Prédiction de branchements et réduction de la pénalité lors d’une mauvaise prédiction
2.1 Prédiction de branchements
2.1.1 Prédiction de lacible
2.1.2 Cas spécifiques des appels de fonctions et des retours
2.1.3 Prédiction de la direction
2.1.4 Fonctionnement du prédicteur TAGE
2.2 Reconvergence du flot de contrôle et indépendance de contrôle
2.2.1 Reconvergence du flot de contrôle
2.2.2 Indépendance de contrôle
2.2.3 Exploitation de la reconvergence du flot de contrôle et de l’indépendance de contrôle
2.2.4 Diffcultés liées à l’exploitation de l’indépendance de contrôle
2.3 État de l’art des travaux visant à réduire la pénalité due à une mauvaise prédiction
2.3.1 Étude de l’indépendance de contrôle
2.3.2 Selective Branch Recovery
2.3.3 Transparent Control Independence
2.3.4 Skipper
2.3.5 Ginger
2.3.6 Register Integration
2.3.7 Recycling Waste
3 SYRANT: allocation symétrique des ressources sur les chemins pris et non pris
3.1 Principe de l’allocation forcée des ressources de SYRANT
3.2 Description détaillée du mécanisme SYRANT
3.2.1 Détection du point de reconvergence: la ABL/SBL
3.2.2 Identification des instructions indépendantes du contrôle et respect des dépendances de données
3.2.3 Continuer l’exécution du mauvais chemin après la correction d’une mauvaise prédiction
3.2.4 Correspondance artificielle de la taille des chemins
3.2.5 Invalidation sélective d’instructions en utilisant SYRANT
3.2.6 Considérations sur la complexité matérielle du mécanisme
3.3 Utilisation des branchements calculés sur le mauvais chemin pour améliorer la prédiction de branchements
3.4 Limitation de la taille des vides
3.5 Évaluation des performances
3.5.1 Caractéristiques du simulateur
3.5.2 Jeu de tests
3.5.3 Taux de mauvaises prédictions des programmes de test
3.5.4 Caractérisation partielle et détection de la reconvergence
3.5.5 Résultats de SYRANT et de la prédiction SBL
3.5.6 Commentaires sur les résultats
3.5.7 Changement de la taille du ROB
3.5.8 Limitation du nombre d’instructions lancées par cycle
3.6 Conclusion
4 Instructions prédiquées et if-conversion
4.1 Instructions prédiquées
4.1.1 Définition
4.1.2 Utilisations
4.1.3 Prédication partielle et prédication totale
4.1.4 Implémentation matérielle
4.1.5 Spécificités de la prédication dans le jeu d’instructions ARM
4.2 Travaux traitant des instructions prédiquées
4.2.1 Bénéfices de la if-conversion
4.2.2 Interaction des instructions prédiquées et de la prédiction de branchements
4.2.3 Travaux portant sur le problème des définitions multiples
5 SPREPI :prédication et rejeu sélectif pour les instructions prédiquées
5.1 Prédictions élective de prédicats
5.1.1 Groupe prédiqué
5.1.2 Prédicteur sélectif de prédicats
5.1.3 Utilisation de la prédiction
5.2 Rejeu sélectif pour les mauvaises prédictions de prédicats
5.2.1 Utilisation symétrique des ressources
5.2.2 Initialisation d’un rejeu lors d’une mauvaise prédiction de prédicat
5.2.3 Identification des résultats valides
5.2.4 SPREPI
5.3 Étude expérimentale
5.3.1 Paramètres du simulateur
5.3.2 Jeu de tests
5.3.3 Ratio d’instructions prédiquées dans les programmes de test
5.3.4 Résultats de simulations
5.4 Conclusion et perspectives
Conclusion
Publications personnelles
Bibliographie
