Fonctionnement d'un ordinateur/Processeurs à émissions multiples

Les processeurs vus auparavant ne peuvent émettre au maximum qu'une instruction par cycle d'horloge : ce sont des processeurs à émission unique. Et quand on court après la performance, on en veut toujours plus : un IPC de 1, c'est pas assez ! Pour cela, les concepteurs de processeurs ont inventés des processeurs qui émettent plusieurs instructions par cycle : les processeurs à émissions multiples.

Processeurs superscalaires

Pour que cela fonctionne, il faut répartir les instructions sur différentes unités de calcul, et cela n'est pas une mince affaire. Si le processeur répartit les instructions sur les unités de calcul à l’exécution, on parle de processeur superscalaire. Certains processeurs superscalaires n'utilisent pas l'exécution dans le désordre, tandis que d'autres le font. Pour que le processeur répartisse ses instructions sur plusieurs unités de calcul, il faut modifier toutes les étapes entre le chargement et les unités de calcul.

Pipeline simplifié (à cinq étages) d'un processeur superscalaire. On voit bien que plusieurs instructions sont chargées en même temps.

Chargement

Sur les processeurs superscalaires, l'unité de chargement charge un bloc de mémoire de taille fixe, qui contient plusieurs instructions (le program counter est modifié en conséquence). Ceci dit, il faut convenablement gérer le cas où un branchement pris se retrouve en plein milieu d'un bloc. Dans ce qui va suivre, un morceau de code sans branchement est appelé un bloc de base (basic block). Si certains processeurs éxecutent toutes les instructions d'un bloc, sauf celles qui suivent un branchement pris, d'autres permettent de charger les instructions de destination du branchement et de les placer à sa suite. Ils vont charger deux blocs à la fois et les fusionner en un seul qui ne contient que les instructions présumées utiles (exécutées). Le principe peut se généraliser avec un nombre de blocs supérieur à deux.

Ces processeurs utilisent des unités de prédiction de branchement capables de prédire plusieurs branchements par cycle, au minimum l'adresse du bloc à charger et la ou les adresses de destination des branchements dans le bloc. De plus, on doit charger deux blocs de mémoire en une fois, via des caches d'instruction multiports. Il faut aussi ajouter un circuit pour assembler plusieurs morceaux de blocs en un seul : le fusionneur (merger). Le résultat en sortie du fusionneur est ce qu'on appelle une trace.

Cache de traces

Si jamais un bloc est rechargé et que ses branchements sont pris à l'identique, le résultat du fusionneur sera le même. Il est intéressant de conserver cette trace dans un cache de traces pour la réutiliser ultérieurement. Pour stocker une trace, rien de plus facile : il suffit de conserver le résultat obtenu par le fusionneur. Mais il reste encore à déterminer si une trace peut être réutilisée. Une trace est réutilisable quand le premier bloc de base est identique, les branchements sont toujours à la même place dans la trace et les prédictions de branchement restent identiques. Dans ces conditions, le tag du cache de traces doit contenir l'adresse de départ du premier bloc de base, la position des branchements dans la trace et le résultat des prédictions utilisées pour construire la trace. Le résultat des prédictions de branchement utilisées pour construire la trace est stocké sous la forme d'une suite de bits : si la trace contient n branchements, le n-ième bit vaut 1 si ce branchement a été pris, et 0 sinon. Même chose pour la position des branchements dans la trace : le bit numéro n indique si la n-ième instruction de la trace est un branchement : si c'est le cas, il vaut 1, et 0 sinon. Pour savoir si une trace est réutilisable, l'unité de chargement envoie l'adresse de chargement au cache de traces, le reste des informations étant fournie par l'unité de prédiction de branchement. Si le tag est identique, alors on a un succès de cache de traces, et la trace est envoyée directement au décodeur. Sinon, la trace est chargée depuis le cache d'instructions et assemblée.

La présence d'un cache de traces se marie très bien avec une unité de prédiction de branchement capable de prédire un grand nombre de branchements par cycle. Malheureusement, ces unités de prédiction de branchement sont très complexes et bouffent du circuit. Les concepteurs de processeurs préfèrent utiliser une unité de prédiction de branchement normale, qui ne peut prédire l'adresse que d'un seul bloc de base. Pour pouvoir utiliser un cache de traces avec une unité de prédiction aussi simple, les concepteurs de processeurs vont ajouter une seconde unité de prédiction, spécialisée dans le cache de traces.

Certains caches de traces permettent de stocker plusieurs traces différentes pour une seule adresse de départ, avec une trace par ensemble de prédiction. Mais d'autres caches de traces n'autorisent qu'une seule trace par adresse de départ, ce qui diminue la quantité de succès de cache de traces. Sur ces caches, on peut limiter la casse on utilisant des correspondances partielles. Si jamais les prédictions de branchement et la position des branchements n'est pas strictement identique, il arrive quand même que les premières prédictions et les premiers branchements soient les mêmes. Dans ce cas, on peut alors réutiliser les blocs de base concernés : le processeur charge les portions de la trace qui sont valides depuis le cache de traces.

Si les correspondances partielles permettent de limiter la casse, une autre solution est possible : mémoriser les blocs de base dans des caches de blocs de base, et les assembler par un fusionneur pour reconstituer les traces. Par exemple, au lieu d'utiliser un cache de traces dont chaque ligne peut contenir quatre blocs de base, on va utiliser quatre caches de blocs de base. Cela permet de supprimer la redondance que l'on trouve dans les traces, quand elles se partagent des blocs de base identiques, ce qui est avantageux à mémoire égale.

Décodeur d'instruction

Le séquenceur est lui aussi modifié : celui-ci est maintenant capable de décoder plusieurs instructions à la fois (et il peut aussi éventuellement renommer les registres de ces instructions). Pour ce faire, on peut utiliser un seul décodeur pour décoder plusieurs instructions par cycle, ou plusieurs séquenceurs séparés. Dans certains cas, le séquenceur peut fusionner plusieurs instructions consécutives en une seule micro-instruction. Par exemple, un processeur peut décider de fusionner une instruction de test suivie d'un branchement en une seule micro-opération effectuant les deux en une fois. Cette fusion se fait lors du décodage simultané de plusieurs instructions en même temps.

Unité de renommage

Sur les processeurs superscalaires, l'unité de renommage de registres doit renommer plusieurs instructions à la fois. Mais elle doit aussi gérer le cas où ces instructions ont des dépendances entre elles. Pour faire simple, celle-ci renomme les registres sans tenir compte des dépendances, pour ensuite corriger le résultat après.

Seules les dépendances lecture-après-écriture doivent être détectées, les autres étant supprimées par le renommage de registres. Repérer ce genre de dépendances se fait assez simplement : il suffit de regarder si un registre de destination d'une instruction est un opérande d'une instruction suivante.

Ensuite, il faut corriger le résultat du renommage en fonction des dépendances. Si une instruction n'a pas de dépendance avec une autre, on la laisse telle quelle. Dans le cas contraire, un registre opérande sera identique avec le registre de destination d'une instruction précédente. Dans ce cas, le registre opérande n'est pas le bon après renommage : on doit le remplacer par le registre de destination de l'instruction avec laquelle il y a dépendance. Cela se fait simplement en utilisant un multiplexeur dont les entrées sont reliées à l'unité de détection des dépendances. On doit faire ce replacement pour chaque registre opérande.

Unité d'émission

Sur un processeur à émission multiple, l'unité d'émission doit, en plus de ses fonctions habituelles, détecter les dépendances entre instructions à émettre simultanément. L'unité d'émission d'un processeur superscalaire se voit donc ajouter un nouvel étage pour les dépendances entre instructions à émettre. Sur les processeurs superscalaires à exécution dans l’ordre, il faut aussi gérer l'alignement des instructions dans la fenêtre d'instruction. Dans le cas le plus simple, les instructions sont chargées par blocs et on doit attendre que toutes les instructions du bloc soient émises pour charger un nouveau bloc. Avec la seconde méthode, La fenêtre d'instruction fonctionne comme une fenêtre glissante, qui se déplace de plusieurs crans à chaque cycle d'horloge.

Accès au banc de registres

Émettre plusieurs instructions en même temps signifie lire ou écrire plusieurs opérandes à la fois : le nombre de ports du banc de registres doit être augmenté. Mais ces ports ajoutés sont souvent sous-utilisés en situation réelle. On peut en profiter pour ne pas utiliser autant de ports que le pire des cas le demanderait. Pour cela, le processeur doit détecter quand il n'y a pas assez de ports pour servir toutes les instructions : l'unité d'émission devra alors mettre en attente certaines instructions, le temps que les ports se libèrent. Cette détection est réalisée par un circuit d'arbitrage spécialisé, l’arbitre du banc de registres (register file arbiter).

Processeurs VLIW

Les processeurs superscalaires sont tout de même assez complexes et gourmands en circuits : en conséquence, ils chauffent, consomment de l’électricité, etc. On peut améliorer la situation en déléguant le travail de réorganisation des instructions et leur répartition sur les unités de calcul hors du processeur. C'est ainsi que les processeurs VLIW, ou very long instruction word, sont nés. Ces processeurs sont des processeurs qui n'utilisent pas l'exécution dans le désordre, ce qui fait qu'ils ne peuvent rien contre les dépendances qui ne peuvent être supprimées qu'à l’exécution, comme celles liées aux accès mémoires.

Faisceaux d’instructions

Ces processeurs exécutent des faisceaux d’instructions (bundle), des regroupements de plusieurs instructions. Ces instructions peuvent s'exécuter en parallèle sur différentes unités de calcul, mais le faisceau est chargé en une seule fois.

Pipeline simplifié d'un processeur VLIW. On voit que le faisceau est chargé en un cycle d'horloge, mais que les instructions sont exécutées en même temps dans des unités de calcul séparées.

Quand le compilateur regroupe des instructions dans un faisceau, il se peut qu'il ne puisse pas remplir tout le faisceau avec des instructions indépendantes. Sur les anciens processeurs VLIW, les instructions VLIW (les faisceaux) étaient de taille fixe, ce qui forcait le compilateur à remplir d'éventuels vides avec des NOP, diminuant la densité de code. La majorité des processeurs VLIW récents utilise des faisceaux de longueur variable, supprimant ces NOP.

Chaque instruction d'un faisceau doit expliciter quelle unité de calcul doit la prendre en charge. Et à ce petit jeu, il existe deux possibilités, respectivement nommées encodage par position et par nommage. Avec la première méthode, la position de l'instruction dans le faisceau détermine l'ALU à utiliser. Un faisceau est découpé en créneaux (slot), chacun étant attribué à une ALU. Avec la seconde solution, chaque instruction d'un faisceau contient un numéro qui indique l'unité de calcul à utiliser. Cette technique est déclinée en deux formes : soit on trouve un identifiant d'ALU par instruction, soit on utilise un identifiant pour tout le faisceau, qui permet à lui seul de déterminer l'unité associée à chaque instruction.

Dépendances intra-faisceaux

Quelques petites difficultés arrivent quand des instructions d'un faisceau manipulent le même registre. Les problèmes apparaissent avec des écritures, notamment quand une instruction lit un registre écrit par une autre instruction. Dans ce cas, le processeur peut gérer la situation de trois manières différentes :

• la lecture du registre renvoie la valeur avant l'écriture ;
• la lecture va lire la valeur écrite par l'écriture ;
• le processeur interdit à deux instructions d'un même faisceau de lire et écrire le même registre.

Exceptions

Que faire lorsqu'une instruction lève une exception dans un faisceau, que se passe-t-il pour les autres instructions ? Là encore, il existe diverses manières de gérer la situation.

• on invalide toutes les instructions du faisceau ;
• on invalide uniquement les instructions qui suivent l'exception dans l'ordre du programme (le compilateur doit ajouter quelques informations sur l'ordre des instructions dans le faisceau) ;
• on invalide seulement les instructions qui ont une dépendance avec celle qui a levé l'exception ;
• on exécute toutes les instructions du faisceau, sauf celle qui a levé l'exception.

Processeurs EPIC

Comme on l'a vu, les architectures VLIW ont quelques problèmes. Une faible compatibilité, une code density pouvant être assez mauvaise. De plus, la performance de ces processeurs dépend fortement de l'efficacité du compilateur. Le but de ces architectures est simple : on délègue l'ordonnancement des instructions au compilateur, qui remplace totalement l'Out Of Order. En l'aidant un peu si possible. Pas d'Out Of Order, un peu de Register Rennaming, mais pas trop, et peu de techniques évoluées qui rendent le processeur capable de faire le café.

En 1997, Intel et HP lancèrent un nouveau processeur, l'Itanium. Son architecture ressemblait fortement aux processeurs VLIW, mais avec les défauts en moins. Dans un but marketing évident, Intel et HP prétendirent que l'architecture de ce processeur, bien que ressemblant aux processeurs VLIW, n'était pas du VLIW. Ils appelérent cette nouvelle architecture EPIC, pour Explicit Parallelism Instruction Computing. Il faut avouer que cette architecture avait tout de même de fortes différences avec le VLIW, mais elle avait aussi beaucoup de points communs. Bien évidemment, beaucoup ne furent pas dupes, et une gigantesque controverse vit le jour : est-ce que les architectures EPIC sont des VLIW ou non ? On va passer celle-ci sous silence, et voir un peu ce que peut recouvrir ce terme : EPIC.

Faisceaux

La première différence avec les VLIW vient de ce qu'on met dans les faisceaux. Ceux-ci deviennent des groupes d'instructions indépendantes, délimités par un petit groupe de bits d’arrêt (stop bits) qui indique la fin d'un faisceau. D'autres processeurs utilisent un bit de parallélisme (parallel bit) : un programme est composé d'une suite d'instructions, et chaque instruction termine (ou commence) par un bit qui dit si l'instruction peut s'effectuer en parallèle avec l'instruction encodée.

• 

  Bits d’arrêt.

• 

  Bit de parallélisme.

L'avantage de ces techniques est que la compatibilité est nettement meilleure, de même que les performances. Avec l'usage d'un bit de stop ou de parallélisme, le processeur doit découper le faisceau en instructions et les répartir sur les unités de calcul. Cette répartition est relativement simple : l'opcode de l'instruction suffit pour déduire l'unité de calcul adéquate. En terme de compatibilité, c'est le rêve : on peut rajouter des unités de calcul sans avoir besoin de recompiler. Le processeur pourra alors profiter de leur présence sans rien faire de spécial, juste en répartissant les instructions convenablement. Enfin, on peut aussi citer les avantages en terme de densité de code : pas besoin d'insérer des NOPs dans des slots vides ou de fournir des identifiants d'ALUs, comme avec les processeurs VLIW.

Exceptions différées

L'Itanium implémente ce qu'on appelle les exceptions différées (delayed exception). Avec cette technique, le compilateur peut créer deux versions d'un même code : une version optimisée qui suppose qu'aucune exception matérielle n'est levée, et une autre version peu optimisée qui suppose qu'une exception est levée. Le programme exécute la version optimisée en premier de manière spéculative, mais annule son exécution et repasse sur la version non-optimisée en cas d'exception.

Pour vérifier l’occurrence d'une exception, chaque registre est associé à un bit « rien du tout » (not a thing), mis à 1 s'il contient une valeur invalide. Si une instruction lève une exception, celle-ci écrira un résultat faux dans un registre et le bit « rien du tout » est mis à 1. Les autres instructions propageront ce bit « rien du tout » dans leurs résultats : si un opérande est « rien du tout », le résultat de l'instruction l'est aussi. Une fois le code fini, il suffit d'utiliser une instruction qui teste l'ensemble des bits « rien du tout » et agit en conséquence.

Spéculation sur les lectures

L'Itanium fournit une fonctionnalité similaire pour les lectures, où le code est compilé dans une version optimisée où les lectures sont déplacées sans tenir compte des dépendances, avec un code de secours non-optimisé. Reste ensuite à vérifier que la spéculation était correcte, mais cette vérification ne se fait pas de la même façon selon que la lecture ait été déplacée avant un branchement ou avant une autre écriture. Si on passe une lecture avant un branchement, la lecture et la vérification sont effectuées par les instructions LD.S et CHK.S. Si une dépendance est violée, le processeur lève une exception différée : le bit « rien du tout » du registre contenant la donnée lue est alors mis à 1. CHK.S ne fait rien d'autre que vérifier ce bit. L'Itanium permet de déplacer une lecture avant une écriture, mais délègue la désambigüisation de la mémoire au compilateur. Tout se passe comme avec les branchements, à part que les instructions sont nommées LD.A et CHK.A.

Pour détecter les violations de dépendance, le processeur maintient une liste des lectures spéculatives qui n'ont pas causé de dépendances mémoire, dans un cache : la table des adresses lues en avance (advanced load address table ou ALAT). Ce cache stocke notamment l'adresse, la longueur de la donnée lue, le registre de destination, etc. Toute écriture vérifie si une lecture à la même adresse est présente dans l'ALAT : si c'est le cas, une dépendance a été violée, et la lecture est retirée de l'ALAT.

Bancs de registres rotatifs

Les processeurs EPIC et VLIW utilisent une forme limitée de renommage de registres pour accélérer certaines boucles. Prenons une boucle simple. Nous montrerons le corps de la boucle, à savoir les instructions de la boucle, sans les branchements et instructions de test. Celle-ci se contente d'ajouter 5 à tous les éléments d'un tableau. L'adresse de l’élément du tableau est stockée dans le registre R2, et est incrémentée automatiquement via le mode d'adressage à pré-incrément. Dans le code qui suivra, les crochets serviront à indiquer l'utilisation du mode d'adressage indirect.

loop :

   load R5 [R2] / add 4 R2 ;
   add 5 R5 ; 
   store [R2] R5 ;

La boucle est donc simple. Elle charge l’élément du tableau et calcule l'adresse du prochain élément dans un premier faisceau, le deux pouvant se faire en parallèle. Ensuite, elle ajoute 5 à l’élément. Puis elle l'enregistre. Si on regarde cette boucle du point de vue du pipeline, c'est pas très reluisant : les trois dernières instructions utilisent les mêmes registres et ont donc des dépendances.

On souhaiterait que toutes les instructions soient indépendantes, qu'elles n'utilisent pas les mêmes registres. C'est théoriquement possible : les itérations de la boucle peuvent se recouvrir sans problème, vu qu'elles manipulent des données indépendantes : les éléments du tableau sont manipulés indépendamment. Mais le fait que l'instruction de calcul utilise le même registre que l'instruction de lecture pose quelques problèmes et ajoute une fausse dépendance. Même chose pour le fait que l'écriture utilise le résultat de l'addition, et donc le même registre. Le renommage de registres pourrait les supprimer, mais il n'est pas disponible sur les processeurs VLIW et EPIC.

Pour supprimer ces dépendances, on a inventé les bancs de registres rotatifs (rotating register files). Avec cette technique, un banc de registres est spécialisé dans l’exécution des boucles. De plus, à chaque cycle d'horloge, le nom d'un registre change de manière prévisible. Généralement, le nom d'un registre est augmenté de 1 à chaque cycle d'horloge. Par exemple, le registre nommé R0 à un instant donné devient le registre R1 au cycle d'après. Et c'est la même chose pour tous les registres du banc de registre dédié aux boucles. Évidemment, le code source du programme doit être modifié pour en tenir compte.

Ainsi, le code vu précédemment…

loop :

   load R5 [R2] / add 4 R2 ;
   add 5 R5 ; 
   store [R2] R5 ;

… devient celui-ci.

loop :

   load RB5 [R2] / add 4 R2 ;
   add 5 RB6 ; 
   store [R2] RB7 ;

Si on analyse ce qui se passe dans le pipeline, les instructions des différentes itérations deviennent indépendantes. Ainsi, le LOAD d'une itération ne touchera pas le même registre que le LOAD de l'itération suivante. Le nom de registre sera le même, mais le fait que les noms de registre se décalent à chaque cycle d'horloge fera que ces noms identiques ne correspondent pas au même registre. Les dépendances sont supprimées, et le pipeline est utilisé à pleine puissance. Même chose pour toutes les instructions de la boucle : même nom de registre à chaque itération, mais registres physiques différents.

Cette technique s'implémente avec un simple compteur, qui compte de zéro, jusqu'au nombre de registres dédiés aux boucles. Ce compteur est incrémenté à chaque cycle d'horloge. Pour accéder à un registre, le contenu de ce compteur est ajouté au nom de registre à accéder. Évidemment, cette addition a lieu pour chaque port du banc de registre (avec un seul compteur pour tous les ports).

Exemples d'architectures EPIC (Itanium)

• 

  Itanium 1.

• 

  Itanium 2.