Fonctionnement d'un ordinateur/Les processeurs superscalaires

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, c'est pas assez ! Les concepteurs de processeurs ont inventés des processeurs qui émettent plusieurs instructions par cycle : les processeurs à émissions multiples.

Les processeurs à émission multiple sont de deux types : les processeurs VLIW et les processeurs superscalaires. Nous mettons les processeurs VLIW de côté en attendant le prochain chapitre. La raison est que ces derniers ont un jeu d'instruction spécialisé qui expose le parallélisme d'instruction directement au niveau des instructions, là où les processeurs superscalaires restent des processeurs au jeu d'instruction normal.

Un processeur superscalaire éxécute plusieurs instructions en parallèle. Il charge plusieurs instructions en même temps, les décode en parallèle, puis les exécute sur des unités de calculs séparées. De plus, il faut gérer les dépendances entre instructions, répartir les instructions sur différentes unités de calcul, et cela n'est pas une mince affaire. Certains processeurs superscalaires n'utilisent pas l'exécution dans le désordre, tandis que d'autres le font. La différence principale entre les deux est qu'un processeur superscalaire répartit les instructions sur les unités de calcul à l’exécution, là où un processeur VLIW délègue cette tâche au compilateur.

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

Les processeurs superscalaires : vision globale de leur implémentation modifier

Un processeur superscalaire n'est pas si différent d'un processeur pipeliné normal. Rappelez-vous que les processeurs pipelinés incorporent déjà plusieurs pipelines de longueurs différentes. Pour rappel, le pipeline du processeur est décomposé en plusieurs parties.

  • La première partie, l’amont (front end), prend en charge les étages communs à toutes les instructions : la mise à jour du program counter, le chargement, l'étage de décodage, etc.
  • L'amont est suivi par le chemin de données, découpé en plusieurs unités adaptées à un certain type d'instructions, chacune formant ce qu'on appelle un aval (back end). Il y a un aval pour les instructions arithmétiques et logiques, un autre pour les opérations d'accès mémoire, un autre pour les instructions flottantes, et ainsi de suite.
 
Pipeline avec un aval et un amont (back-end et front-end).

En général, on trouve les avals suivants :

  • un aval pour les instructions entières ;
  • un aval pour les instructions flottantes ;
  • un aval pour les accès mémoire (calcul d'adresse inclu) ;
  • éventuellement un aval pour les tests et les branchements.

Les processeurs superscalaires basiques, sans duplication d'aval modifier

Un processeur non-superscalaire n'utilise qu'un seul aval à la fois, alors qu'un processeur superscalaire peut utiliser plusieurs avals en même temps. Pour qu'un processeur superscalaire répartisse ses instructions sur plusieurs avals, il faut modifier toutes les étapes de l'amont.

Le cas le plus simple de processeur superscalaire dispose de deux pipelines séparés : un pour les instructions arithmétiques entières, un autre pour les opérations flottantes. Il est ainsi possible d'exécuter une opération entière et une opération flottante en parallèle. Le processeur dispose pour cela d'une FPU séparée de l'ALU entière, mais aussi de banc de registres séparés pour les entiers et les flottants. Le séquenceur devait aussi être conçu pour, naturellement.

Il est aussi possible d'utiliser l'aval pour les accès mémoire en parallèle des autres avals. Cela demande que l'aval dispose de ses propres unités de calcul d'adresse, afin que les calculs d'adresse ne soient pas effectués par l'ALU entière, sans quoi cela ne sert à rien de les séparer.

L'aval pour les branchements/tests peut ausis être exploité en parallèle des autres, mais cela demande pas mal de modifications assez lourdes du processeur. Il faut notamment éviter le cas où une instruction éxecutée en parallèle du branchement l'est pas erreur, en cas de mauvaise prédiction de branchement.

Les processeurs superscalaires complexes, avec duplication d'aval modifier

Pour plus de performances, il faut dupliquer les avals, ce qui signifie dupliquer des unités de calcul. Dans les faits, cela signifie souvent utiliser plusieurs unités de calcul séparées. Pendant qu'une unité de calcul exécute une instruction, l'autre ALU peut en exécuter une autre. Un processeur superscalaire capable d'exécuter 5 instructions en même temps dispose ainsi de 5 unités de calcul séparées. Une première solution duplique l'unité de calcul entière. On a alors plusieurs ALU entières séparées, qui peuvent effectuer des calculs différents en parallèle.

Notons que les deux méthodes précédentes peuvent se combiner. Par exemple, le processeur Alpha 21164 utilisait deux ALU entières et deux ALU flottantes, ce qui permettait d'exécuter 4 instructions en parallèle : deux opérations entières, deux opérations flottantes. Il disposait donc de 4 pipelines, 2 entiers et 2 flottants. Les deux pipelines flottants ne sont pas identiuqes : l'un gére la multiplication, l'autre les autres opérations. Le tout est illustré ci-dessous, on voit qu'il y a aussi des unités de calcul d'adresse, mais elles ne sont pas utilisables en parallèles des unités de calcul entières.

 
Microarchitecture de l'Alpha 21264

Il est même possible de dupliquer les unités de calcul d'adresse, de branchement, et autres. Le diagramme ci-dessous décrit une architecture superscalaire avec 4 ALU entières, 2 ALU flottantes, et 2 unités mémoire.

 
DiagramaRISC

Exemple : le Pentium 1/MMX et les pipelines U/V modifier

Un autre exemple de processeur superscalaire est celui du premier Pentium, qui disposait de deux pipelines nommés U et V. On pouvait en tirer parti lorsque deux instructions consécutives pouvaient être exécutées en parallèles. Il fallait certaines conditions pour cela : les deux instructions ne devaient pas avoir de dépendances, par exemple.

Chose peu courante, les deux pipelines n'étaient pas identiques. Les pipelines U et V n'exécutaient pas les mêmes instructions, certaines étaient partagées, d'autres spécifiques au pipeline U, d'autres au pipeline V. Le pipeline U pouvait exécuter toutes les instructions, mais le pipeline V était beaucoup plus limité.

Les instructions suivantes étaient exécutables dans les deux pipelines, ce qui fait qu'on pouvait en faire deux en même temps :

  • l'instruction MOV, dépend du mode d'adressage ;
  • les instructions de gestion de la pile PUSH et POP, dépend du mode d'adressage ;
  • Les instructions arithmétiques INC, DEC, ADD, SUB ;
  • l'instruction de comparaison CMP ;
  • les instructions bit à bit AND, OR, XOR ;
  • l'instruction de calcul d'adresse LEA ;
  • l'instruction NOP, qui ne fait rien.

Les instructions suivantes sont exécutables dans le pipeline U :

  • les décalages et rotations, mais seulement pour certains opérandes ou pour certains modes d'adressage.
  • les autres instructions arithmétiques entières, comme la multiplication et la division, mais elles ne permettent pas d'exécuter une opération dans le pipeline V en parallèle.

Les branchements sont exécutables dans les deux pipelines, mais on ne peut exécuter une autre opération en parallèle qu'à la condition que le branchement soit exécuté dans le pipeline V.

Les deux pipelines disposaient d'une unité de calcul entière, ainsi que d'une unité de calcul d'adresse, mais elles n'étaient pas identiques. L'unité de calcul d'adresse du pipeline V ne pouvait effectuer que l'instruction LEA, pas les autres. L'unité de calcul entière du pipeline V gérait les opérations bit à bit, les additions et soustractions (et les comparaisons, qui sont des soustractions déguisées), mais pas les multiplications et les divisions. Le circuit pour les décalages/rotations n'est pas dupliqué, ce qui fait que ces opérations sont disponibles seulement dans le pipeline U. L'unité flottante était à part, mais faisait techniquement partie du pipeline U : impossible d'exécuter des instructions flottantes en parallèle des instructions entières. Il en est de même pour l'unité de calcul vectoriel MMX sur le Pentium MMX.

 
Microarchitecture de l'Intel Pentium MMX. On voit que certaines unités de calcul sont dupliquées.

Le chemin de données modifier

L'utilisation de plusieurs unités de calcul a des conséquences sur le chemin de données. Elles touchent le banc de registres, ainsi que sur les circuits de contournement. Voyons ce que cela implique.

L'accès au banc de registres modifier

É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é. De plus, le banc de registre doit être relié à toutes les unités de calcul en même temps, ce qui fait 2 ports de lecture par unité de calcul. Et avec plusieurs dizaines d'unités de calcul différentes, le câblage est tout simplement ignoble. Et plus un banc de registres a de ports, plus il utilise de circuits, est compliqué à concevoir, consomme de courant et chauffe. Mais diverses optimisations permettent de réduire le nombre de ports assez simplement.

La première solution duplique le banc de registres en plusieurs exemplaires qui contiennent exactement les mêmes données. Un exemple est celui des processeurs POWER, Alpha 21264 et Alpha 21464. Sur ces processeurs, le banc de registre est dupliqué en plusieurs exemplaires, qui contiennent exactement les mêmes données. Les lectures en RAM et les résultats des opérations sont envoyées à tous les bancs de registres, afin de garantir que leur contenu est identique. Le banc de registre est dupliqué en autant d'exemplaires qu'il y a d'unité de calcul. Chaque exemplaire a exactement deux ports de lecture, une par opérande, au lieu de plusieurs dizaines. La conception du processeur est simplifiée, que ce soit au niveau du câblage, que de la conception des bancs de registres.

 
Banc de registres distribué.

Un autre solution utilise un banc de registre unique, mais n'utilise pas 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).

Le contournement modifier

Pour rappel, la technique du contournement (register bypass) permet au résultat d'une instruction d'être immédiatement utilisable en sortie de l'ALU, avant même d'être enregistré dans les registres. Implémenter la technique du contournement demande d'utiliser des multiplexeurs pour relier la sortie de l'unité de calcul sur son entrée si besoin. il faut aussi des comparateurs pour détecter des dépendances de données.

 
Pipeline Bypass

Avec plusieurs unités de calcul, la sortie de chaque ALU doit être reliée aux entrées de toutes les autres, avec les comparateurs qui vont avec ! Sur les processeurs ayant plusieurs d'unités de calculs, cela demande beaucoup de circuits. Pour limiter la casse, on ne relie pas toutes les unités de calcul ensemble. À la place, on préfère regrouper ces unités de calcul dans différents blocs séparés qu'on appelle des agglomérats (cluster). Le contournement est alors rendu possible entre les unités d'un même agglomérat, mais pas entre agglomérats différents. Cette agglomération peut aussi prendre en compte les interconnections entre unités de calcul et registres. C'est-à-dire que les registres peuvent être agglomérés. Et cela peut se faire de plusieurs façons différentes.

Une première solution, déjà vue dans les chapitres sur la micro-architecture d'un processeur, consiste à découper le banc de registres en plusieurs bancs de registres plus petits. Il faut juste prévoir un réseau d'interconnexions pour échanger des données entre bancs de registres. Dans la plupart des cas, cette séparation est invisible du point de vue de l'assembleur et du langage machine. Le processeur se charge de transférer les données entre bancs de registres suivant les besoins. Sur d'autres processeurs, les transferts de données se font via une instruction spéciale, souvent appelée COPY.

 
Banc de registres distribué.

Sur d'autres processeurs, on utilise une hiérarchie de registres : d'un côté, des bancs de registres locaux (Local Register File) directement connectés aux unités de calcul, un banc de registres global (Global Register File) plus gros, lui-même relié à la mémoire, qui ressemble à une mémoire de type local store. Le processeur dispose d'instructions pour transférer des données entre les bancs de registres, ainsi qu'avec la mémoire. Outre son rôle d'intermédiaire, le banc de registres global sert à transférer des données entre les bancs de registres locaux, où à stocker des données globales utilisées par des Clusters d'ALU différents. Un processeur de flux possède des instructions capables de transférer des données entre le banc de registre global et la mémoire RAM, qui sont capables de faire des accès mémoires en enjambées, en Scatter-Gather, etc.

 
Hiérarchie de registres.

Certains chercheurs ont adapté cette hiérarchie de bancs de registres de façon à ce que les bancs de registres reliés aux unités de calcul se comportent comme des caches. Suivant l’implémentation, les écritures et lecture en mémoire peuvent lire ou écrire dans tous les niveaux de cache, ou uniquement dans le niveau de banc de registres le plus proche de la mémoire. Il faut noter que le préchargement est possible entre bancs de registres. Dans d'autres travaux, on préfère y stocker les résultats qui ne sont pas utilisés après un contournement : ces valeurs sont écrites dans tous les niveaux de la hiérarchie des registres, tandis que les valeurs contournées sont écrites uniquement dans les registres des niveaux inférieurs.

Sur de nombreux processeurs, un branchement est exécuté par une unité de calcul spécialisée. Or les registres à lire pour déterminer l'adresse de destination du branchement ne sont pas forcément dans le même agglomérat que cette unité de calcul. Pour éviter cela, certains processeurs disposent d'une unité de calcul des branchements dans chaque agglomérat. Dans les cas où plusieurs unités veulent modifier le program counter en même temps, un système de contrôle général décide quelle unité a la priorité sur les autres. Mais d'autres processeurs fonctionnent autrement : seul un agglomérat possède une unité de branchement, qui peut recevoir des résultats de tests de toutes les autres unités de calcul, quel que soit l’agglomérat.

L'étape de chargement superscalaire modifier

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).

Certains processeurs superscalaires exécutent toutes les instructions d'un bloc, sauf celles qui suivent un branchement pris. L'unité de chargement coupe le bloc chargé au niveau du premier branchement non-pris, remplit les vides avec des NOP, avant d'envoyer le tout à l'unité de décodage. Le processeur détermine quels branchements sont pris ou non avec la prédiction de branchements.

 
Fetch sur un processeur superscalaire avec prédiction de branchements.

D'autres chargent les instructions de destination du branchement et les placent à sa suite. Ils chargent deux blocs à la fois et les fusionnent 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.

 
Cache d'instructions autoaligné.

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.

 
Implémentation d'un cache d'instructions autoaligné.

Le cache de traces modifier

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. Mais il reste à déterminer si une trace peut être réutilisée.

Une trace est réutilisable quand le premier bloc de base est identique et que les prédictions de branchement restent identiques. Pour vérifier cela, le tag du cache de traces contient l'adresse 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.

 
Cache de traces.

Certains caches de traces peuvent stocker plusieurs traces différentes pour une même 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 est sous-optimal. Mais 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 et le processeur charge les portions de la trace qui sont valides depuis le cache de traces. Une autre solution consiste à reconstituer les traces à la volée. Il suffit de mémoriser les blocs de base dans des caches dédiés et les assembler par un fusionneur. 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.

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 gourmandes en circuits. 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.

La macrofusion modifier

Notons que certaines techniques permettent au décodeur de fusionner des instructions en une seule micro-opération. Par exemple, il est possible de fusionner une multiplication suivie d'une addition en une seule instruction MAD (multiply and add), si les conditions adéquates sont réunies pour les opérandes. Comme autre exemple, il est possible de fusionner un calcul d'adresse suivi d'une lecture à l'adresse calculée en une seule micro-opération d'accès mémoire.

Cette technique n'est pas exclusive aux processeur superscalaires et fonctionne si tout processeur avec un pipeline, mais elle fonctionne au mieux sur ces processeurs, du fait de leur capacité à charger plusieurs instructions à la fois. Cette fusion est faite avant le décodage, quand les instructions sont encore dans l'instruction queue, la prefetch input queue, la mémoire tampon située entre l'étage de chargement et l'étage de décodage.

Le séquenceur d'un processeur superscalaire modifier

Le séquenceur d'un processeur superscalaire est modifié, afin de pouvoir décoder plusieurs instructions à la fois. Ce n'est pas le cas général, mais la présence de plusieurs décodeurs est très fréquent sur les processeur superscalaires. De plus, les unités de renommage et d'émission doivent être modifiées.

Les décodeurs d'instructions superscalaires modifier

Un processeur superscalaire contient généralement plusieurs décodeurs, chacun pouvant décoder une instruction en parallèle des autres. Prenons par exemple un processeur RISC dont toutes les instructions font 32 bits. Un processeur superscalaire de ce type peut charger des blocs de 128 bits, ce qui permet de charger 4 instructions d'un seul coup. Et pour les décoder, le décodage se fera dans quatre décodeurs séparés, qui fonctionneront en parallèle.

Pour donner un exemple assez particulier, prenons le cas des processeurs RISC-V. Sur ce jeu d'instruction, il existe des instructions longues de 32 bits et des instructions courtes de 16 bits. Le chargement des instructions se fait par blocs de 32 bits, ce qui permet de charger une instruction de 32 bits, ou deux instructions de 16 bits. Pour simplifier, supposons que les instructions sont alignées sur des blocs de 32 bits, ce qui signifie qu'un bloc chargé contient soit une instruction de 32 bits, soit deux instructions de 16 bits. On ne tient pas compte des cas où une instruction de 16 bit est immédiatement suivie par une instruction de 32 bits à cheval sur deux blocs. Il est possible de créer un processeur RISC-V partiellement superscalaire en utilisant deux voies : une avec un décodeur pour les instructions 32 bits et une autre voie contenant deux décodeurs pour les instructions de 16 bits. Ainsi, lors du chargement d'un bloc de deux instructions courtes, les deux instructions sont chacune décodées par un décodeur séparé.

Il est même possible de décoder les instructions dans les deux voies en parallèle, avant de choisir quel est celui qui a raison. Sans cette méthode, on doit identifier si le bloc contient une instruction longue ou deux instructions courtes, avant d'envoyer les instructions au décodeur adéquat. Mais avec cette méthode, l'identification du nombre d'instruction se fait en parallèle du décodage proprement dit. Évidemment, une des deux voies donnera des résultats aberrants et totalement faux, mais l'autre donnera le bon résultat. Il suffit de choisir le bon résultat en sortie avec un multiplexeur.

 
Décodage des instructions à longueur variable dans l'exemple du RISC-V, où les instructions font 32 ou 16 bits et sont alignées.

L'unité de renommage superscalaire modifier

Sur un processeur à émission multiple, l'unité de renommage de registres doit renommer plusieurs instructions à la fois, mais aussi gérer les dépendances entre instructions. Pour cela, elle renomme les registres sans tenir compte des dépendances, pour ensuite corriger le résultat.

 
Unité de renommage superscalaire.

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.

 
Détection des dépendances sur un processeur superscalaire.

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.

 
Correction des dépendances sur un processeur superscalaire.

L'unité d'émission superscalaire modifier

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.