Fonctionnement d'un ordinateur/L'émission dans l'ordre des instructions

Dans ce chapitre, nous allons voir les processeurs à émission dans l'ordre et allons parler longuement des dépendances de données. Pour rappel, deux instructions ont une dépendance de données quand elles accèdent (en lecture ou écriture) au même registre ou à la même adresse mémoire. Le cas typique est celui où une instruction a besoin du résultat d'une instruction précédente pour s’exécuter. C'est le cas le plus évident, mais on a aussi des cas moins intuitifs. Voyons lesquels et comment ceux-ci sont gérés par le pipeline.

Les dépendances de données

Deux instructions ont une dépendance de données quand elles accèdent (en lecture ou écriture) à la même donnée, c'est à dire au même registre ou la même adresse mémoire. En tout, cela fait quatre possibilités :

• Read after read : Deux instructions lisent la même donnée, mais pas en même temps.
• Read after write : Une instruction a pour opérande le résultat d'une autre : elle lit le résultat écrit par la première.
• Write after write : Deux instructions écrivent dans le même registre ou la même adresse mémoire, mais pas en même temps.
• Write after read : Une instruction lit une donnée qui est modifiée ultérieurement par une autre instruction.

Pour les dépendances Read after read, on peut mettre les deux instructions dans n'importe quel ordre, cela ne pose aucun problème. Ce ne sont pas de vraies dépendances et je les présente par pur souci d'exhaustivité. Par contre, ce n'est pas le cas avec les trois autres types de dépendances, qui imposent que la première instruction s'exécute avant la seconde, au moins partiellement. Elle doit terminer son exécution, avant que la seconde soit démarrée. Quand on parle de "terminer" ou de "démarrer", on fait référence aux lectures et écritures effectuées par l'instruction. Voici comment sont gérées les trois types de dépendances :

• Read after write : La première instruction doit écrire son résultat avant que la seconde le lise.
• Write after write : La première instruction doit écrire son résultat avant la seconde.
• Write after read : La première doit effectuer la lecture avant que la seconde n'écrive, n'écrase la donnée lue.

Pour simplifier les explications, nous allons appeler ces trois dépendances : dépendances RAW, WAR et WAW.

Les dépendances de registre et mémoire

Une autre distinction sépare les dépendances de registre et les dépendances d'adresse. Une dépendance de donnée survient quand deux instructions lisent/écrivent le même registre ou la même adresse mémoire. Et c'est là qu'une petite subtilité survient, car les accès mémoire se distinguent des autres instructions. Dans la suite du cours, nous allons supposer une architecture LOAD-STORE dans la plupart des cas. Une telle architecture a une séparation stricte entre accès mémoire et les autres instructions. Les accès mémoire regroupent les instructions LOAD et STORE, qui se distinguent des autres instructions. Pour simplifier, les autres instructions seront appelées des opérations, ou encore des instructions de calcul.

Les dépendances de registre surviennent quand deux instructions lisent ou écrivent le même registre. Le cas typique est celui où une instruction lit un registre et qu'une autre écrit dedans, mais il faut aussi tenir compte du cas avec deux écritures dans le même registre. Les dépendances d'adresse surviennent quand deux instructions mémoire lisent/écrivent dans une même adresse mémoire. Là encore, on a le cas des dépendances RAW, WAW et WAR.

Les dépendances d'adresse se manifestent sur tous les pipelines, même ceux qui ne sont pas multicycles. La raison est que les écritures se font à la toute fin du pipeline, pour gérer les exceptions précises, alors que les lectures se font quelques étages avant. Il peut alors y avoir quelques problèmes, lorsque plusieurs instructions mémoire se suivent. Imaginez par exemple qu'une lecture s'exécute avant qu'une écriture atteigne la fin du pipeline. Si les deux instructions accèdent à la même donnée, on a une dépendance d'adresse de type RAW. Le cas sera étudié dans le chapitre sur le contournement.

Un point important est que la gestion des dépendances est différente entre les dépendances de registre et les dépendances d'adresse. Détecter une dépendance de registre demande de comparer les registres utilisés par deux instructions. Par contre, détecter les dépendances d'adresse demande de comparer les adresses lues/écrites. Et autant les registres lus/écrit sont connus dès que l'instruction est décodée, autant les adresses sont souvent calculées à l'exécution ou mémorisées dans des registres. Les deux types de dépendances sont donc le fait de circuits séparés, qui sont dans des étages de pipeline distincts. La gestion des dépendances d'adresse est le fait de l'unité d'accès mémoire et notamment de la file d'écriture, les autres dépendances sont gérées pendant/après l'étape de décodage d'instruction. Aussi, il est important de séparer les deux le plus possible.

Les dépendances de registre

Dans ce qui va suivre, nous allons nous limiter aux dépendances liées aux registres, et mettre de côté les dépendances d'adresse. Intuitivement, on se dit que de les dépendances de registres concernent les instructions arithmétiques, mais les instructions d'accès mémoire peuvent avoir des dépendances de registre avec d'autres instructions. L'instruction STORE lit la donnée à écrire et son adresse dans les registres, elle a donc potentiellement des dépendances de registre, à cause des registre opérande. Si une autre instruction lit/écrit ces registres opérandes, une dépendance de registre survient. L'instruction LOAD est dans un cas similaire, : elle récupère l'adresse à lire dans un registre opérande (la plupart du temps), et écrit la donnée lue dans un autre registre de destination. Ce qui fait deux sources de dépendances de registre : le registre opérande, le registre de destination. Si une instruction de calcul ou une autre instruction mémoire lit/écrit dans ces registres, une dépendance de donnée a lieu.

Dans ce chapitre, nous allons nous préoccuper des trois dépendances de registres suivantes :

• Read after write : Une instruction lit un registre dans laquelle l'instruction précédente a écrit.
• Write after read : Une instruction lit un registre pour récupérer une opérande, mais ce registre est ensuite écrasé par une instruction ultérieure.
• Write after write : Deux instructions écrivent dans le même registre, mais à des instants différents.

Pour simplifier les explications, nous allons appeler ces trois dépendances : dépendances RAW, WAR et WAW.

Les dépendances RAW et WAW, imposent que la première instruction ait écrit son résultat avant que la seconde lise ses opérandes. Si on ne fait pas ça, la seconde instruction lit des opérandes invalides ou voit son écriture écrasée par une écriture précédente. Pour éviter cela, la seconde instruction doit être démarrée quand la première s'est totalement terminée. Insérer des bulles de pipeline est donc une nécessité. Mais diverses optimisations permettent de mitiger l'impact des dépendances de données. Par exemple, dans le prochain chapitre, nous parlerons de la technique du contournement, qui permet de supprimer les bulles de pipeline pour les dépendances RAW. Les dépendances WAW et WAR peuvent aussi être totalement supprimées par des techniques de renommages de registres, qui auront leur chapitre dédié.

Les dépendances présentes dépendent du pipeline

Le support des exceptions précises supprime pas mal de dépendances de données. Le fait que les écritures mémoire garantit que les écritures se fassent dans l'ordre du programme, il n'y a pas de situations où une écriture soit exécutée avant une écriture antérieure. Et cela suffit à faire disparaitre les dépendances WAW. De même, les dépendances d'adresse WAR sont impossibles avec des exceptions précises, car les écritures se font à la fin du pipeline, après les lectures.

Même sans exceptions précises, les dépendances WAR n'existent tout simplement pas sur la plupart des pipelines. En pratique, les dépendances WAR n'apparaissent que sur les processeurs dits à exécution dans le désordre, et encore, seulement si on n'utilise pas de renommage de registre, ce qui n'est plus le cas depuis des décennies. Les dépendances WAW, quant à elles, n'apparaissent que sur les pipelines dynamiques, ceux qui supportent des instructions multicycles, ou si les écritures prennent plusieurs étages.

Dépendance	Pipeline	Solutions
RAW	Tous les pipelines	Bulles de pipeline	Contournement
WAW	Pipelines dynamiques		Renommage de registres
WAR	Pipelines dynamiques avec exécution dans le désordre

Les dépendances WAR et WAW sont souvent appelées des dépendances de nom (naming dependency) et sont opposées aux dépendances vraies (true dependency), à savoir les dépendances RAW. Les dépendances WAR et WAW viennent du fait qu'un même registre nommé est réutilisé plusieurs fois pour des données différentes. Elles n'existeraient pas si on utilisait un registre pour chaque donnée, qui est écrit une fois, lu une ou plusieurs fois, mais jamais écrasé. Et on peut les faire disparaitre avec des techniques dites de renommage de registre, qui feront l'objet d'un chapitre ultérieur.

L'émission d'une instruction et les bulles de pipeline

Les dépendances imposent qu'une première instruction soit totalement terminée avant qu'on démarre la seconde, ou du moins qu'elle ait progressé suffisamment dans le pipeline. Pour cela, il suffit de retarder l'exécution de la seconde instruction tant que les conditions nécessaires pour son exécution ne sont pas réunies. Par exemple, prenons le cas où une instruction a pour opérande le résultat d'une autre : la seconde doit attendre que le résultat de la première soit calculé avant de démarrer, il se peut qu'elle soit retardée durant quelques cycles pour cela.

Les processeurs détectent les dépendances de registre dans un circuit spécialisé, appelé l'unité d'émission. Elle est parfois fusionnée avec l'unité de décodage d'instruction, mais nous allons surtout étudier le cas où elle est séparée. Si une instruction a une dépendance bloquante, elle est bloquée dans l'étage d'émission en attendant de pouvoir s'exécuter. Durant ce temps d'attente, on insère des vides après l'unité d'émission : certains étages seront inoccupés et n'auront rien à faire. Ces vides sont appelés des calages (stall), ou bulles de pipeline (pipeline bubble). Les étages qui sont situés avant l'atage d'émission sont eux gelés, la progression des instructions dedans est stoppée.

Pipeline bubble

Le terme "émission" reviendra souvent dans la suite du cours. On dira qu'une instruction est émise si elle est envoyée au chemin de donnée, qu'elle quitte l'unité d'émission. Une instruction peut être émise si elle n'a pas de dépendance bloquante, qu'elle peut s'exécuter. Elle rentre alors dans le chemin de donnée, lit ses opérandes et s'exécute. L'unité d'émission est donc la toute fin de l'unité de contrôle, du séquenceur, c'est le point d'entrée du chemin de données.

Dans la suite du cours, nous verrons de nombreux cas dans lesquels insérer des bulles de pipeline est une obligation si on veut que le processeur fonctionne correctement. Il s'agit là d'une fonctionnalité très importante de tous les pipelines, anciens comme modernes. Évidemment, les bulles de pipeline sont une source de perte de performance : le pipeline ne fait rien tant qu'une instruction n'est pas terminée, ce qui va à l'encontre du principe du pipeline. Et de nombreuses techniques d'optimisations visent à réduire l'utilisation de ces bulles de pipeline le plus possible. D'ailleurs, nous passerons les prochains chapitres à parler de ces optimisations.

La détection des dépendances de données

Le processeur doit détecter les dépendances de données entre instructions. Les dépendances de registres se détectent en comparant entre eux les registres utilisés par les instructions. Les registres étant connus dès la sortie de l'étape de décodage, la détection des dépendances de données se fait de manière précoce, avant même l'exécution des instructions. Une sacré différence avec les dépendances d'adresse, qui demandent que les adresses soient calculées et lues dans les registres avant qu'on puisse détecter les dépendances.

La détection des dépendances de registre se fait dans l'étage d'émission, situé juste après l'étage de décodage d'instruction. L'unité d'émission reçoit une instruction décodée et vérifie ses dépendances avec les instructions dans le pipeline. À chaque cycle d'horloge, l'unité d'émission analyse une instruction décodée appelée instruction candidate. Elle détecte si cette instruction candidate a une dépendance avec une instruction déjà dans le pipeline. Les instructions dans le pipeline n'ont pas encore enregistrées leurs résultats dans les registres, soit parce qu'elles sont en cours d'exécution, qu'elles lisent leurs opérandes, peut importe. Elles seront appelées instructions "en vol".

Pour cela, l'unité d'émission compare les registres utilisés par l'instruction candidate et les instructions dans le pipeline. Il n'y a pas de dépendance si ces registres sont différents, alors qu'il y a dépendance dans le cas contraire. Pour être plus précis, il faut cependant faire une différence entre les registres opérandes et de destination. Les registres opérandes sont ceux qui sont lus, ceux où sont les opérandes. Le registre de destination d'une instruction est celui dans lequel on enregistre le résultat. Les quatre situations possibles sont les suivantes :

• Un des registres opérande est à lire (opérande) par une instruction dans le pipeline : pas de dépendance.
• Un des registres opérande est écrit (destination) par une instruction dans le pipeline : dépendance RAW.
• Un des registres de destination est à lire (opérande) par une instruction dans le pipeline : potentielle dépendance WAR, mais seulement sur des pipelines pathologiques jamais utilisés.
• Un des registres de destination est écrit (destination) par une instruction dans le pipeline : dépendance WAW.

Notez que pour les lectures, on part du principe que les instructions en vol n'ont pas encore lu leurs registres opérandes. Dès qu'elles ont lu les opérandes en question, les dépendances liées disparaissent. Pareil pour les écritures, sauf que celles-ci ont lieu à la toute fin du pipeline. Les écritures en attente ont donc lieu quand l'instruction termine.

		Instruction candidate
		Registres opérandes	Registre destination
Instructions en vol	Registres pas encore lus (opérandes)	Pas de dépendances (dépendance RAR inoffensive)	Dépendance WAR potentielle, pas en pratique
	Registre pas encore écrits (destination)	Dépendance RAW	Dépendance WAW

L'algorithme est donc le suivant : une lecture est autorisée en absence d'écriture (dans le même registre), une écriture est autorisée en absence de lecture (dans le même registre). Cependant, on peut grandement simplifier l'algorithme et ne pas tenir compte des dépendances WAR, qui n'existent pas sur la plupart des pipelines dynamiques sans exécution dans le désordre. Le tableau se simplifie en retirant les dépendances inutiles, seule la dernière ligne nous intéresse au final.

		Instruction candidate
		Registres opérandes	Registre destination
Instructions en vol	Registre pas encore écrits (destination)	Dépendance RAW	Dépendance WAW

L'exécution dans l'ordre et dans le désordre des instructions

Nous venons de voir que les dépendances de données posent des problèmes qu'un pipeline de longueur variable doit résoudre. La solution la plus simple retarde les instructions candidates problématiques de quelques cycles d'horloges. Si une instruction a une dépendance problématique avec une autre, il suffit simplement de l’exécuter avec un retard de cycles. Pour cela, lorsqu'une instruction multicycle est démarrée, les instructions problématiques sont bloquées à l'étage de décodage en attendant le bon moment. Pour cela, on utilise des bulles de pipeline (pipeline bubble), pour retarder l'instruction fautive dans l'unité de décodage.

Bulle de pipeline.

Notons que cette technique exécute des instructions indépendantes dans des unités de calcul séparées. Dans l'exemple précédent avec une instruction multicycle suivie par une instruction normale, le processeur détecte les situations où ce n'est pas grave si la seconde instruction finisse avant la première : on peut alors lancer la seconde instruction immédiatement sans attendre. Il y a donc un gain en performance. Un point important est que cette technique émet les instructions dans l'ordre, mais qu'elles peuvent s'exécuter dans le désordre et terminer dans le désordre. En clair, les instructions sont injectées dans les unités de calcul dans l'ordre, mais en sortent dans le désordre.

Pour éviter les bulles de pipeline, les processeurs modernes incorporent des optimisations assez intéressantes. Nous verrons la technique du contournement dans le chapitre suivant. Elle permet de réduire l'usage de bulles de pipeline en cas de dépendance Read after write. Une solution complémentaire est ce qu'on appelle l'exécution dans le désordre, une optimisation commune sur les processeurs modernes qui sera vue en détail dans plusieurs chapitres dans la suite du cours.

L'idée est que si une instruction problématique est bloquée dans l'unité de décodage/émission, elle est juste mise en attente, elle ne bloque pas le pipeline. Le processeur regarde les instructions suivantes et vérifie si certaines d'entre elles peuvent s'exécuter. Les instructions mises en attente sont exécutées dès que possible, elles ont la priorité. La gestion de la mise en attente des instructions problématiques est assez complexe et implique de les stocker dans des mémoires spécifiques. Là encore, il faut que les instructions exécutées en parallèle ne manipulent pas les mêmes données, ni les mêmes registres, ni les mêmes adresses mémoires.

La toute première implémentation de l'exécution dans le désordre était sur l'ordinateur CDC 6600, suivi par son successeur le CDC 7600. Il intégrait un circuit appelé le scoreboard, qui gérait l'exécution dans le désordre. Décrire le circuit en question est assez compliqué, aussi je le laisse de côté pour le moment. Sachez le terme scoreboard est resté et a été élargit à tout circuit d'émission, qu'il soit dans le désordre ou dans l'ordre.

L'étage d'émission : la génération de bulles de pipeline

Maintenant, voyons comment est implémenté l'étage d'émission (issue), qui détecte les situations problématiques et rajoute des bulles de pipeline si besoin. Il suit immédiatement l'étage de décodage, et est situé avant le chemin de données. Le rôle de l'unité d'émission est de générer les bulles de pipeline. Si elle reçoit une instruction problématique, elle la bloque dans l'unité d'émission et génère des bulles de pipeline, tant que la dépendance n'est pas réglée. Mais si l'instruction peut s'exécuter, elle l'envoie dans la suite du pipeline. On dit qu'elle émet l'instruction.

L'émission est donc l'envoi d'une micro-opération dans le pipeline, si les conditions sont réunies. Un point important de l'émission est que le processeur émet une instruction par cycle, en absence de dépendance de données, mais aussi en absence de dépendances structurelles, les deux étant détectées par l'unité d'émission.

La gestion des dépendances de données

Pour rappel, l'unité d'émission détecte les dépendances entre une instruction candidate et les instructions déjà dans le pipeline, aussi appelées instructions "en vol". L'unité d'émission détecte les dépendances entre l'instruction candidate et chaque instruction en vol. Pour rappel, les dépendances de données se détectent en comparant les instructions de deux opérandes. Vu que les dépendances WAR sont très rares, et n'existent pas sur les pipelines normaux, on ne tient compte que des dépendances RAW et WAW. Les détecter demande de comparer les registres de l'instruction candidate, avec les registres de destination des instructions en vol.

	Instruction candidate
	Registres opérandes	Registre destination
Instructions en vol Registres pas encore écrits (destination)	Dépendance RAW	Dépendance WAW

L'unité d'émission doit connaitre les registres de destination des instructions en vol, ce qui peut se faire de plusieurs manières. La première méthode utilise le fait que les noms de registres sont propagés dans le pipeline, comme tous les signaux de commande. Dans ces conditions, rien n’empêche de relier les registres tampons chargés de la propagation à l'unité d'émission. L'unité d'émission est donc un paquet de comparateurs reliés par des portes OU. En sortie, elle fournit un signal STALL, qui indique s'il faut sortir une bulle de pipeline ou non. Pour un pipeline à N étages maximum, cela demande de faire N comparaisons.

Détection des dépendances dans un pipeline.

Une autre implémentation, beaucoup plus économe en circuits, se limite à un simple registre de réservation. Il permet à une instruction de réserver en écriture son registre de destination. Par réservé, on veut dire que le registre ne peut pas être écrit par une autre instruction. Les registres qui ne sont pas réservés sont dit libres ou disponibles. Si une instruction candidate veut lire ce registre, c'est signe qu'il y a une dépendance RAW : elle veut lire un registre réservé, qui est destiné à être écrit par une instruction en vol. Si elle veut écrire, c'est signe qu'elle veut écrire dans un registre où une autre instruction veut écrire : c'est une dépendance WAW. Dans les deux cas, l'instruction n'est pas émise.

Le registre encode les registres réservés en représentation one-hot modifiée. Chaque bit est associé à un registre. Le bit numéro 0 est associé au registre numéro 0, le bit numéro 1 au registre numéro 1, etc. Un registre est réservé en mettant le bit associé à 1.

Registre de réservation

Registre 7	Registre 6	Registre 5	Registre 4	Registre 3	Registre 2	Registre 1	Registre 0
0	0	1	0	0	1	0	0

Il existe une seconde possibilité, où les registres réservés sont à 0 et les registres libres à 1. Nous l’appellerons le registre de disponibilité.

Avant d'émettre une instruction, l'unité d'émission extrait les registres opérande/destination et les convertis dans la même représentation que le registre de réservation, à savoir en représentation one-hot. Le circuit de traduction binaire vers one-hot est, pour rappel, un simple décodeur. Puis, on fait un OU logique entre les sorties des décodeurs. Le résultat est un masque qui indique quels registres sont lus par l'instruction, encodé en représentation one-hot. Appelons-le le masque d'opérandes. Le masque est alors comparé au registre de réservation pour vérifier si l'instruction peut être émise.

Unité d'émission simple, dans l'ordre

Si l'émission est autorisée, le registre de réservation est là aussi mis à jour. La mise à jour du registre de réservation à l'émission est simple : on prend le registre de destination, encodé en one-hot, et on le combine avec le registre de réservation, en faisant un simple OU logique. Le registre de réservationest aussi mis à jour dès qu'une instruction enregistre son résultat dans les registres, ou alors dès qu'il est disponible pour le contournement. Le bit associé au registre repasse alors à 0 (ou à 1). Sans contournement, la mise à jour se fait alors à la toute fin de l'instruction, quand elle se termine, lors de la dernière étape d'enregistrement, à la fin de son pipeline. Avec, elle se fait quand l'instruction quitte l'unité de calcul.

Vous aurez peut-être remarqué, mais une différence est que les pipelines fixes retardent les écritures dans le banc de registre avec des registres d'échelonnage, les pipelines dynamique retardent l'émission des instructions. Les deux méthodes ont sensiblement le même résultat.

Le registre de consultation permet de désigner les registres qui vont être lus par les instructions en vol. Je précise bien : les registres qui n'ont pas encore été lus. Les registres en question sont dit consulté, les autres sont dit non-consultés. Il est interdit d'écrire dans un registre consulté, c'est signe d'une dépendance WAR. Il faut noter que beaucoup de pipeline s'en passent car ils n'ont pas de dépendances WAR. Le registre de consultation est mis à jour dès que l'opérande est lue. Et cela arrive assez tôt dans le pipeline, au bout de quelques cycles grand maximum. Sur beaucoup de pipelines, il n'est pas présent dans il est impossible qu'une écriture ait lieu avant qu'une lecture ait démarrée. Mais sur les pipelines où de telles dépendances sont possibles, il faut en tenir compte.

Il existe quelques rares processeurs qui fusionnent le registre de réservation et de consultation en un seul. Le registre contient autant de bits que de registres, chaque bit indique si le registre associé est pas encore lu/écrit. De tels implémentations détectent alors toutes les dépendances, même les dépendances Read After Read. Elles tendent à être très conservatrices. Un exemple est le co-processeur vectoriel VFP9-S d'ARM. Leur implémentation est simple, mais il peut y avoir un cout en performance.

La gestion de la disponibilité des ALUs

L'étage d'émission détecte aussi les dépendances structurelles au niveau de l'unité de calcul. Elle apparaissent quand deux instructions veulent exécuter une instruction en même temps, sur la même ALU. Elles impliquent généralement des instructions multicycles, qui occupent une unité de calcul pendant plusieurs cycles. Un exemple est celui où on veut faire deux multiplications à la suite, en supposant qu'une multiplication fasse 5 cycles : la seconde doit attendre que la première se termine car le multiplieur est occupé pendant ce temps. Face à une dépendance structurelle de ce type, l'unité d'émission met la seconde instruction en attente, tant que l'unité de calcul est occupée. L'unité d'émission émet des bulles de pipeline si le processeur utilise l'émission dans l'ordre. Reste à détecter les conflits d'accès, les dépendances structurelles.

Une solution consiste à déterminer les paires d'instructions consécutives qui peuvent donner lieu à des dépendances structurelles. Par exemple, si une instruction de multiplication est dans le pipeline, je sais que je ne peux pas démarrer de nouvelle multiplication immédiatement après, s'il n'y a qu'un seul multiplieur. Détecter les dépendances structurelles consiste à comparer l'opcode de l'instruction à émettre, avec les opcodes des instructions en cours d’exécution dans le pipeline. Si jamais l'opcode de l'instruction à émettre et une opcode dans le pipeline forment une paire d'opérations interdite, il y a dépendance structurelle et on doit insérer des bulles de pipeline.

Une autre solution mémorise un bit pour chaque ALU qui indique si elle est occupée. L'ensemble des bits est appelé le vecteur de disponibilité des ALUs.

Vecteur de disponibilité des ALUs

ADD1 BUSY	ADD2 BUSY	MUL BUSY	COMP CUSY	LOAD /STORE BUSY
0	0	1	0	0

Avant d'émettre une instruction, l'unité d'émission vérifie si une unité de calcul adéquate est disponible. Pour cela, chaque instruction est associée à un masque qui précise quelles unité de calcul peuvent l'exécuter. Détecter une dépendance structurelle demande une simple opération de masquage entre ce masque et le vecteur de disponibilité des ALUs.

Masque par instruction, associé au vecteur de disponibilité précédent

	ADD1 BUSY	ADD2 BUSY	MUL BUSY	COMP CUSY	LOAD /STORE BUSY
ADD	1	1	0	0	0
MUL	0	0	1	0	0
COMP	0	0	0	1	0
LOAD	0	0	0	0	1
STORE	0	0	0	0	1

Toute la difficulté tient dans la mise à jour des bits de disponibilité des ALUs. Une solution assez simple intègre des compteurs dans le processeur pour chaque bit de disponibilité. La technique part du principe que la durée de chaque instruction est connue et qu'on peut l'utiliser pour initialiser un compteur. Lors de l'émission d'une instruction sur une ALU, le compteur associé à l'ALU est initialisé avec le nombre de cycles de l'instruction. Il est décrémenté à chaque cycle d'horloge. Une fois qu'il atteint 0, le bit de disponibilité est mis à 0.

Une autre solution délègue cette tâche à l'unité de calcul. Dès qu'un calcul se termine sur l'ALU, l'unité de calcul prévient qu'elle est libre avec un signal FREE qu'elle envoie à l'unité d'émission. L'avantage est que la solution prend en charge naturellement le cas où les opérations sont de durée variable. Un exemple est celui d'un additionneur à saut de retenue, où la durée d'une addition dépend de la propagation de la retenue. Un autre exemple est celui de certains multiplieurs itératifs (qui font la multiplication en effectuant une suite de décalages et d'addition), qui fournissent le résultat en avance pour certaines opérandes. Ou encore les circuits diviseurs par décalage/soustraction qui s’arrêtent dès que le dividende partiel tombe à zéro. Et d'ailleurs, on va voit que cette solution marche assez bien pour les instructions mémoire.

L'émission et les micro-opérations mémoire

Les micro-opérations mémoires sont gérées par l'unité mémoire, ou encore la Load-Store Unit. Nous utiliserons le terme unité mémoire dans la suite du cours. L'unité mémoire est pour le moment une sorte de boite noire, dont on ne détaillera pas l'intérieur, et dont seules les entrées et sorties nous sont accessibles. L'unité d'émission la considère d'ailleurs comme telle. L'unité mémoire prend en entrée des opérandes, à savoir les adresses à lire/écrire, éventuellement la donnée à écrire. En sortie, elle fournit la donnée lue et le registre de destination dans lequel enregistrer la donnée. Les entrées et sorties sont reliées au réseau de contournement, ainsi qu'aux registres.

En général, l'adresse est lue dans les registres, mais elle peut aussi être fournie par le réseau de contournement. Mais certains modes d'adressage font que l'adresse doit être calculée. L'adressage base + indice est un bon exemple : il demande de calculer l'adresse à lire/écrire avec une addition et éventuellement un décalage. Dans le chapitre sur le pipeline, nous avons vu que les calculs d'adresse peuvent être effectués soit dans les unités de calcul entières, soit dans l'unité mémoire elle-même. Et les deux solutions ne sont pas équivalentes, elles ont chacune leurs avantages et leurs défauts. Un des avantages est lié au décodage des instructions, à savoir si les instructions mémoire sont décodées en une ou deux micro-opérations.

La solution la plus simple est celle qui effectue les calculs d'adresse dans l'unité mémoire elle-même. L'interface de l'unité mémoire est modifiée, de manière à pouvoir lui envoyer les indices et décalages nécessaires au calcul d'adresse. Si l'unité mémoire effectue les calculs d'adresse, les instructions mémoire sont décodées en une seule micro-opération, qui est envoyée à l'unité mémoire. Pas besoin de micro-opération séparée pour le calcul d'adresse. Le défaut de cette méthode est que l'unité mémoire doit incorporer une unité de calcul d'adresse, ce qui ajoute quelques circuits redondants avec l'ALU entière. Mais les circuits ajoutés se résument à des additionneurs et un circuit de décalage, ce qui est très léger. De nos jours, tous les processeurs font les calculs d'adresse dans l'unité mémoire. Le fait que le décodage soit simplifié l'emporte haut la main, comparé aux économies liées à l'unité de calcul d'adresse.

Unité mémoire avec calcul d'adresse intégré, dans un pipeline.

Vous vous dites sans doute que les accès mémoire sont des instructions multicycles, et ce n'est pas faux. Mais elles se distinguent des autres instructions multicycle par leur temps d'exécution variable. Un accès au cache peut prendre deux à trois cycles d’horloge, un accès au cache L2 prend facilement 10 cycles, et un accès en RAM une centaine. Vu que leur latence n'est pas connue à l'avance, les techniques utilisées sur les pipelines multicycle/dynamiques ne fonctionnent pas parfaitement. La gestion des dépendances de données est notamment totalement différente.

Gérer les accès mémoire demande, entre autres, de gérer la disponibilité de l'unité mémoire. Mais contrairement aux instructions de calcul, les accès mémoire ont pour défaut qu'ils ont un nombre de cycles variable. Sur la plupart des processeurs, l'accès au cache se fait rapidement, mais l'accès à la mémoire est très lent. Et l'unité d'émission doit gérer la disponibilité de l'unité mémoire.

Dans ce qui suit, nous partons du principe que l'unité mémoire ne peut faire qu'un seul accès mémoire à la fois. Hypothèse crédible, mais certains processeurs avec exécution dans le désordre fonctionnent autrement. L'unité mémoire prévient elle-même de sa disponibilité. Elle est reliée à l'unité d'émission via un fil MEM_UNIT_READY qui prévient qu'elle est disponible et peut accepter un nouvel accès mémoire. Si le bit MEM_UNIT_READY est à 1, l'unité mémoire est inutilisé, il n'y a pas d'accès mémoire en cours. Par contre, si ce bit est à 0, alors un accès mémoire est en cours et l'unité mémoire ne peut pas accepter de nouvel accès mémoire.

L'unité d'émission tient en compte de ce bit pour décider de l'émission des instructions en cours. De plus, elle l'utilise pour déterminer si le registre de destination est disponible. Quand le signal MEM_UNIT_READY passe de 0 à 1, le no/numéro du registre destination est disponible en sortie de l'unité mémoire. Il est alors envoyé à l'unité d'émission et le registre de disponibilité est mis à jour.

Implémentation du stall lors d'un accès mémoire dans l'unité d'émission

Pour éviter tout problème, l'idéal est de stopper l'exécution d'autres instructions tant qu'un accès mémoire a lieu. Les instructions qui suivent l'accès mémoire sont mises en attente tant qu'il n'est pas terminé. En clair, on bloque le pipeline, l'unité d'émission cesse d'émettre des instructions et émet juste des bulles de pipeline. Pour cela, dès que l'unité d'émission émet une micro-opération mémoire, elle émet des bulles de pipeline à sa suite tant que le signal MEM_UNIT_READY est à 0. Une fois l'accès mémoire terminé, l'unité d'accès mémoire met le signal MEM_UNIT_READY à 1, ce qui prévient l'unité d'émission. L'émission des instructions reprend. C'est la solution la plus simple, mais elle est imparfaite.

Les lectures non-bloquantes

Les lectures non-bloquante sont une optimisation qui évite de bloquer le pipeline en cas d'accès mémoire. Elle a été utilisée sur le processeur ARM Cortex A53 et sur son successeur, l'ARM Cortex A510, avec un certain succès. L'idée est de continuer à faire des calculs en parallèle de l'accès mémoire, sous condition que cela ne pose pas de problèmes. Les instructions exécutées en parallèle sont exécutées dans l'unité de calcul, nous allons donc les appeler des opérations. L'unité d'émission ne peut pas émettre de nouvel accès mémoire, mais peut exécuter des opérations en parallèle de la lecture, si elles sont indépendantes de la lecture. Reste à savoir sous quelles conditions les opérations sont indépendants de la lecture.

La technique des lectures non-bloquantes ne se préoccupe pas des dépendances d'adresses. En effet, elles sont gérées par l'unité mémoire, pas par l'unité d'émission. Elle ne se préoccupe que des dépendances de registre. Les lectures et écritures lisent des opérandes dans les registres et ne sont pas émises tant qu'il y a une dépendance avec ces registres. Mais ce qui nous intéresse est ce qui se passe une fois la lecture/écriture émise. Une fois émises, les écritures n'écrivent dans aucun registre et n'ont donc pas de dépendances de registre. Par contre, les lectures écrivent la donnée lue dans un registre de destination, ce qui peut faire apparaitre des dépendances.

Le premier problème est qu'il se peut qu'une opération utilise la donnée lue par l'accès mémoire. Par exemple, la lecture charge une donnée dans un registre et ce registre est ensuite utilisé comme opérande d'une addition. Dans ce cas, l'opération ne doit pas s’exécuter tant que la donnée n'a pas été chargée. Un autre cas est celui où une opération écrit dans le registre de destination de la lecture. Avec des lectures non-bloquantes, l'opération ne doit pas démarrer tant que la lecture n'est pas terminée. Les dépendances pertinentes ici sont des dépendances avec le registre de destination de la lecture.

L'unité d'émission vérifie les dépendances avec le registre de destination de la lecture. Pour cela, l'unité d'émission marque le registre de destination de la lecture comme « réservé », du moins tant que la lecture n'a pas écrit son résultat dedans. Lorsqu'elle émet une lecture, l'unité d'émission marque le registre de destination comme réservé. Elle continue d’émettre des instructions si elles sont indépendantes de ce registre destination, mais bloque l'émission de toute instruction qui l'utilise. Ainsi, les instructions qui ne lisent ou n'écrivent pas ce registre peuvent s'exécuter dans les unités de calcul.

L'implémentation de cette technique demande juste de pouvoir réserver des registres, et consulter les réservations à chaque cycle. Pour marquer les registres comme réservés/non-réservé, l'unité d'émission contient un bit de réservation en lecture par registre. Chaque bit indique si le registre associé contient une donnée valide ou non. Le bit de validité est automatiquement comme invalide quand le processeur démarre une lecture. Le tout est regroupé dans un registre de réservation. Le registre de réservation peut être fusionné avec le registre de disponibilité vu plus haut.

Toute instruction qui a un registre invalide comme opérande est mise en attente. Idem pour les instructions qui ont un registre invalide comme registre de destination. À chaque cycle, l'unité d'émission tente de démarrer une nouvelle instruction et vérifie si elle est dépendante de la lecture. Elle vérifie si l'instruction à émettre a le registre de destination de la lecture comme opérande, ou comme registre de destination. Si c'est le cas, alors l'instruction est bloquée dans le pipeline. Mais dans le cas contraire, l'instruction de calcul est indépendante de l'accès mémoire, et peuvent démarrer sans trop de problèmes.

L'exécution dans le désordre et autres alternatives

Les lectures non-bloquantes peuvent être vues comme une sorte d'exécution dans le désordre limitée aux lectures. La différence avec l'exécution dans le désordre est que la technique des lectures non-bloquantes détecte si une instruction est dépendante d'une lecture, alors que l’exécution dans le désordre détectent toutes les dépendances entre instructions, pas seulement les dépendances avec un accès mémoire.

Le processeur ROCK, annulé en 2010, utilisait une version améliorée des lectures non-bloquantes, appelée la technique des éclaireurs matériels. La différence est que le processeur ne stoppe pas quand il rencontre une instruction dépendante de la lecture. À la place, les instructions dépendantes de la lecture sont mises en attente dans une file d'attente spécialisée, appelée la file d’attente différée (deferred queue), qui est une mémoire FIFO un peu modifiée. Une fois que la lecture renvoie un résultat, le processeur cesse l’exécution des instructions et exécute les instructions mises en attente. Les instructions mises en attente sont exécutées dans l'ordre, avant de reprendre là où le programme s'était arrêté.