Fonctionnement d'un ordinateur/Les accès mémoires et le pipeline

Dans les chapitres précédents, nous avons vu que le processeur pouvait implémenter trois types de pipelines différents. Le plus simple est le pipeline 1-cycle, où toutes les instructions se font en un cycle. Par exemple, le pipeline RISC classique est un pipeline 1-cycle, conçu pour les accès mémoire fassent un seul cycle d'horloge. Mais dans la réalité, les accès mémoire prennent plus de cycles. 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. Les latences ne sont pas compatibles avec un pipeline en un cycle.

Les autres types de pipeline ne font pas mieux. Que ce soit les pipeline multicycle, ou dynamiques, ils gèrent des instructions multicycles. Et vous vous dites sans doute que les accès mémoire sont des instructions multicycles, et ce n'est pas faux, mais elles légèrement à part des autres. Le problème est que leur latence n'est pas connue à l'avance, on ne sait pas combien de cycles d'horloge elles vont prendre. Les techniques utilisées sur les pipelines multicycle/dynamiques ne fonctionnent pas du tout. Par exemple, un accès mémoire peut durer au maximum une centaine, voire un millier de cycles d'horloges si la donnée est lue/écrite en mémoire RAM. Le pipeline doit pouvoir gérer ce genre de situation, à savoir des instructions dont la durée est inconnue. Les solutions à cela sont assez nombreuses.

Les micro-opérations mémoire sur les pipelines multicycles

Prenons d'abord le cas des pipelines multicycles, sur lesquels les instructions font toutes le même nombre d’horloge. Les instructions se calent toutes sur l'instruction la plus lente. Elles peuvent finir leurs calculs en quelques cycles, mais l'écriture du résultat dans les registres est retardée de manière à respecter le nombre de cycles d'horloge adéquat. Les instructions d'accès mémoire ne font pas exception : elles s'exécutent en plusieurs cycles.

Par contre, elles doivent respecter le fonctionnement en pipeline, ce qui fait que les accès mémoire doivent être pipelinés ! Pour cela, il n'y a pas 36 solutions : il faut pipeliner l'accès à la mémoire. La méthode la plus simple pipeline l'accès au cache, l'autre pipeline l'accès à la mémoire. La première méthode est toujours en vigueur dans les processeur modernes, même ceux avec un pipeline dynamique. Pipeliner la mémoire est une méthode assez ancienne, utilisée sur les anciens ordinateurs historiques, qui ne disposaient pas de cache, mais avaient bien un pipeline (et parfois, de l'exécution dans le désordre et du renommage de registres).

Le mini-pipelining des calculs d'adresse

Beaucoup de processeurs des années 2000 avaient une fréquence peu élevée comparé aux standard d'aujourd'hui, ce qui fait que leur cache avait bien un temps d'accès d'un cycle d'horloge. Mais ils étaient quand même capables de pipeliner les accès mémoire. L'accès au cache se faisait en deux cycles d'horloge, avec un cycle pour calculer une adresse et un cycle pour l'accès mémoire proprement dit. C'était le cas sur les processeurs AMD d'architecture K5 et K6, sur les processeurs Intel d'architecture P6 (Pentium 2 et 3) et quelques autres.

L'avantage de faire ainsi est que l'on peut pipeliner les micro-opérations mémoire alors que l'accès au cache se fait en un cycle d'horloge. Deux micro-opérations mémoire peuvent s'exécuter en même temps sans trop de problèmes. Un autre avantage est que l'on peut réutiliser les unités de calcul normale pour faire les calculs d'adresse. Les processeurs AMD Athlon utilisaient cette technique : les unités de calcul étaient soit utilisées comme unité de calcul entières, soit pour calculer des adresses.

La technique marche aussi bien sur les pipeline dynamiques que multicycle. Avec un pipeline dynamique, Les micro-opérations entières sont alors plus courtes d'un cycle que les micro-opérations de lecture/écriture. Mais avec un pipeline multicycle, on se retrouve avec une organisation assez proche du pipeline RISC classique, avec deux étages EXEC et MEM pour chaque instruction.

Les caches pipelinés

Avec un cache pipeliné, l'accès au cache ne se fait pas en un seul cycle, mais en plusieurs. Cependant, on peut lancer un nouvel accès au cache à chaque cycle d'horloge, comme un processeur pipeliné lance une nouvelle instruction à chaque cycle. L'implémentation est assez simple : il suffit d'ajouter des registres dans le cache. Pour cela, on profite que le cache est composé de plusieurs composants séparés, qui échangent des données dans un ordre bien précis, d'un composant à un autre. De plus, le trajet des informations dans un cache est linéaire, ce qui les rend parfois pour l'usage d'un pipeline.

Voici ce qui se passe avec un cache directement adressé. Pour rappel ce genre de cache est conçu en combinant une mémoire RAM, généralement une SRAM, avec quelques circuits de comparaison et un MUX. L'accès au cache se fait globalement en deux étapes : la première lit la donnée et le tag dans la SRAM, et on utilise les deux dans une seconde étape. Nous avions vu il y a quelques chapitre comment pipeliner des mémoires, dans le chapitre sur les mémoires évoluées. Et bien ces méthodes peuvent s'utiliser pour la mémoire RAM interne au cache !L'idée est d'insérer un registre entre la sortie de la RAM et la suite du cache, pour en faire un cache pipéliné, à deux étages. Le premier étage lit dans la SRAM, le second fait le reste. L'implémentation sur les caches associatifs à plusieurs voies est globalement la même à quelques détails près.

Avec le circuit précédent, il est possible d'aller plus loin, cette fois en pipelinant l'accès à la mémoire RAM interne au cache. Pour comprendre comment, rappelons qu'une mémoire SRAM est composée d'un plan mémoire et d'un décodeur. L'accès à la mémoire demande d'abord que le décodeur fasse son travail pour sélectionner la case mémoire adéquate, puis ensuite la lecture ou écriture a lieu dans cette case mémoire. L'accès se fait donc en deux étapes successives séparées, on a juste à mettre un registre entre les deux. Il suffit donc de mettre un gros registre entre le décodeur et le plan mémoire.

Et on peut aller encore plus loin en découpant le décodeur en deux circuits séparés. En effet, rappelez-vous le chapitre sur les circuits de sélection : nous avions vu qu'il est possible de créer des décodeurs en assemblant des décodeurs plus petits, contrôlés par un circuit de prédécodage. Et bien on peut encore une ajouter un registre entre ce circuit de prédécodage et les petits décodeurs.

Théoriquement, toute l'adresse est fournie d'un seul coup au cache, la quasi-totalité des processeurs présentent l'adresse complète à un cache pipeliné. Mais le Pentium 4 fait autrement. Il faut noter que les premiers étages manipulent l'indice dans la SRAM, qui est dans les bits de poids faible, alors que les étages ultérieurs manipulent le tag qui est dans les bits de poids fort. Les concepteurs du Pentium 4 ont alors décidé de présenter les bits de poids faible lors du premier cycle d'accès au cache, puis ceux de poids fort au second cycle. Pour cela, l'ALU fonctionnait à une fréquence double de celle du processeur, tout comme le cache L1. Il n'y avait pas de pipeline proprement dit, mais cela réduisait grandement la latence d'accès au cache.

Il est aussi possible de pipeliner un cache à accès sériel. Pour rappel, les caches à accès sériel vérifient si il y a succès ou défaut de cache, avant d'accéder aux lignes de cache en cas de succès. Ils font donc différemment des autres caches, qui accèdent à une ligne de cache, avant de déterminer s'il y a succès ou défaut en lisant le tag de la ligne de cache. Les caches sériels disposent de deux SRAM : une pour les tags des lignes de cache et une pour les données. Ils accèdent à la SRAM pour les tags, avant d’accéder à la SRAM des données en cas de succès de cache. Vu que l'accès se fait en deux étapes, une vérification des tags suivie de la lecture/écriture des données, il est facile à pipeliner.

Pipeliner le cache permet de régler le problème des accès au cache L1, et elle est tout le temps utilisé sur les processeurs modernes. Mais que faire en cas de défaut de cache ?

Les micro-opération mémoire sur les pipelines dynamiques

Passons maintenant à la manière dont pipelines dynamiques, de longueur variable, gèrent les accès mémoire. Les accès mémoire ont une latence qui est inconnue, ce qui pose de nombreux problèmes, notamment pour détecter les dépendances de données. 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. Quand une micro-opération d'accès mémoire est émise, le processeur cesse d'émettre des instructions, il émet juste des bulles de pipeline. C'est la solution la plus simple, mais elle est imparfaite.

Les lectures non-bloquantes

Une optimisation profite de l'unité de calcul en parallèle de l'unité d'accès mémoire. 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. L'idée de base est assez simple : si le processeur rencontre une lecture, il continue d’exécuter des instructions malgré tout, en parallèle de la lecture, si elles sont indépendantes de la lecture. Les instructions indépendantes d'une lecture s’exécutent pendant que celle-ci attend la mémoire ou le cache. Cette technique s'appelle les lectures non-bloquantes. Elle a été utilisée sur le processeur ARM Cortex A53 et sur son successeur, l'ARM Cortex A510, avec un certain succès.

Les lectures non-bloquante 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.

Mais faire ainsi fait naitre pas mal de problèmes liés aux dépendances de données. Le premier problème est qu'il se peut qu'une instruction ultérieure 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'instruction de calcul ne doit pas s’exécuter tant que la donnée n'a pas été chargée. Un autre cas est celui où une instruction écrit dans le registre de destination de la lecture. Sans lectures non-bloquantes, la lecture a lieu avant, ce qui fait que la lecture écrit dans ce registre, qui est ensuite modifié par l'instruction ultérieure. Mais avec des lectures non-bloquantes, l'instruction qui écrit dans ce registre ne doit pas démarrer tant que la lecture n'est pas terminée.

L'implémentation de cette technique est assez simple, et se fait soit dans l'unité de décodage, soit dans l'unité d'émission. Les deux sont possibles mais nous allons partir sur l'unité d'émission. Dans les deux cas précédents, on remarque que les problèmes ont lieu quand une instruction ultérieure veut lire/écrire le registre de destination de la lecture, à savoir le registre où on charge la donnée lue. Pour détecter les instructions dépendantes d'une lecture, l'unité d'émission marque le registre de destination de la lecture comme « invalide », du moins tant que la lecture n'a pas écrit son résultat dedans. Pour marquer les registres comme valides ou invalides, on utilise un registre dont chaque bit est associé à un 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.

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

Le processeur ROCK, annulé en 2010, utilisait une version améliorée de la technique précédente, 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. A 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é.

L'émission optimiste des micro-opérations mémoire

Une autre solution part du principe que l'accès mémoire va accéder au cache, qu'il n'y aura pas de défaut de cache. Le pipeline est conçu pour fonctionner avec la durée d'accès au cache L1 et gère les défauts de cache autrement. Pour simplifier, disons que l'accès au cache L1 se fait en deux cycle d'horloge, dans deux étages dédiés, avec accès pipeliné au cache. Si l'accès mémoire entraine un succès de cache, alors l'instruction s’exécute normalement et en temps imparti, elle suit la progression normale dans le pipeline. Mais dès qu'on défaut de cache est détecté, on gèle le processeur en attendant que le défaut de cache se termine. L'unité d'accès mémoire prévient le séquenceur quand la lecture ou écriture est terminée, ce qui lui permet de savoir quand reprendre l’exécution.

Pour cela, il y a plusieurs solutions. La solution la plus simple gèle le pipeline en cas de défaut de cache. Par geler, on veut dire que le processeur cesse de charge des instructions et que chaque instruction reste dans l'étage où elle est au moment du gel. L'implémentation la plus simple de ce gel est la suivante : chaque étage fournit un signal qui indique s'il faut geler le pipeline ou non, et le tout est envoyé au séquenceur. Le séquenceur déclenche un gel en cessant d'envoyer le signal d'horloge aux registres du pipeline, qui restent dans leur état en attendant que le gel soit levé. Ce gel du pipeline s'appelle un pipeline stall.

Un point important est qu'un pipeline stall n'est pas exactement une bulle de pipeline. Une bulle de pipeline géle le pipeline, comme un pipeline stall, mais c'est leur seule ressemblance. La différence est qu'une bulle de pipeline est le fait de l'unité d'émission, éventuellement de l'unité de décodage. Mais un pipeline stall est quelque chose de plus général, qui n'est pas forcément déclenché par l'unité d'émission/décodage. Ici, en l’occurrence, le stall est géré par l'unité d'accès mémoire.

Une autre solution gère les défauts de cache avec les circuits pour les exceptions précises. L'idée est qu'un défaut de cache est géré comme une exception, mais qui ne quitterait pas le processeur. L'instruction mémoire déclenche un défaut de cache est traitée comme une exception, à savoir que les instructions mémoire qui la suivent sont invalidées. Le processeur est alors mis en mode exception, où il ne charge rien, en attendant que le défaut de cache soit terminé. Une fois le défaut de cache traité, l'instruction mémoire redémarre, mais elle finira sur un succès de cache lors de cette seconde tentative.

Une autre solution, bien plus agressive, est utilisée sur le processeur Pentium4. Il s'agit d'une modification de la technique précédente, qui utilise une solution élégante pour gérer ces ratés de prédiction. La solution évite de geler le pipeline lors d'un défaut de cache. La solution est appelée un pipeline à répétition.

Les pipelines à répétition

Sur les pipelines à répétition (replay pipeline), on lance une instruction sans savoir quelle est la latence et on exécute celle-ci en boucle tant que son résultat n'est pas valide. Pour cela, le pipeline se voit ajouter une sorte de boucle, en plus du pipeline mémoire normal. Les instructions se propagent à la fois dans la boucle et dans le pipeline normal. Les étages de la boucle servent juste à propager les signaux de commande de l'instruction, sans rien faire de spécial. Dans le pipeline qui exécute l'instruction, ces signaux de commande sont consommés au fur et à mesure, ce qui fait qu'à la fin du pipeline, il ne reste plus rien de l'instruction originale. D'où la présence de la boucle, qui sert à conserver les signaux de commande.

L'étage final de la boucle vérifie que l'instruction n'a pas été émise trop tôt avec un scoreboard, et il regarde si l'instruction a donné lieu à un défaut de cache ou non. Si l'instruction a donné un bon résultat, une nouvelle instruction est envoyée dans le pipeline. Dans le cas contraire, l'instruction refera encore un tour dans le pipeline. Dans ce cas, l'unité de vérification va devoir envoyer un signal à l'unité d'émission pour lui dire « réserve un cycle pour l'instruction que je vais faire boucler ».

Un point intéressant est que les micro-opérations dépendantes de la lecture sont elles aussi exécutées en avance et ré-exécutées si besoin. Prenons l'exemple d'une lecture qui lit l'opérande manquante d'une addition. Vu qu'il y a a quelques cycles entre l'émission et les unités de calcul, le processeur émet l'addition en avance de quelques cycles, pour qu'elle arrive à l'ALU en temps voulu. En théorie, l'addition ne doit être lancée en avance que si on sait avec certitude que les opérandes seront lues une fois qu'elle arrive à l'ALU. Une addition dépendante d'une lecture doit donc attendre que la lecture termine avant d'être démarrée. Mais avec le système de replay, l'addition est exécutée en avance, avant qu'on sache si ses opérandes sont disponibles. Si jamais un défaut de cache a lieu, l'addition aura atteint l'ALU sans les bonnes opérandes. Elle est alors r-exécutée par le système de replay autant de fois que nécessaire.

Le principe peut s'adapter pour fonctionner avec une hiérarchie de cache. Prenons un exemple : un succès dans le cache L1 dure 3 cycles d'horloge, un succès dans le L2 dure 8 cycles, et un défaut de cache 12 cycles. Imaginons qu'une instruction fasse un défaut de cache dans le L1, et un succès de cache dans le L2. La boucle de 3 cycles utilisée pour le L1 ne permettra pas de gérer efficacement la latence de 8 cycles du L2 : l'instruction devra faire trois tours, soit 9 cycles d'attente, contre 8 idéalement. La solution consiste à retarder le second tour de boucle de quelques cycles, ajoutant une seconde boucle. La seconde boucle ajoute en théorie un retard de 5 cycles : 8 cycles, dont trois en moins pour le premier tour. Pour injecter l'instruction dans la bonne boucle, il suffit d'un multiplexeur commandé par le signal cache hit/miss.

La seconde boucle peut être raccourcie pour une lecture car les micro-opérations dépendantes de la lecture sont émises en avance.

Le même principe peut s'appliquer pour gérer les latences avec des niveaux de cache supérieurs : il faut alors utiliser plusieurs boucles de tailles différentes, en ajoutant des multiplexeurs. Il arrive que plusieurs boucles veuillent faire rentrer une instruction dans le pipeline en même temps, au niveau de l'endroit où les boucles se referment. Dans ce cas, une seule boucle peut réémettre son instruction, les autres étant mises en attente.

Divers mécanismes d'arbitrage, de choix de la boucle sélectionnée pour l'émission, sont possibles : privilégier la boucle dont l'instruction est la plus ancienne (et donc la boucle la plus longue) est la technique la plus fréquente. Mais dans certains cas, mettre une boucle en attente peut bloquer tous les étages précédents, ce qui peut bloquer l'émission de la nouvelle instruction : le processeur se retrouve définitivement bloqué. Dans ce cas, le processeur doit disposer d'un système de détection de ces blocages, ainsi que d'un moyen pour s'en sortir et revenir à la normale (en vidant le pipeline, par exemple).

Pour gérer au mieux les accès à la mémoire RAM, on remplace la boucle dédiée à la latence mémoire par une FIFO, dans laquelle les instructions sont accumulées en attendant le retour de la donnée en mémoire. Quand la donnée est disponible, lue ou écrite en mémoire, un signal est envoyé à cette mémoire, et l'instruction est envoyée directement dans le pipeline. Là encore, il faut gérer les conflits d'accès à l'émission entre les différentes boucles et la file d’attente de répétition, qui peuvent vouloir émettre une instruction en même temps.

On peut aussi adapter le pipeline à répétition pour qu'il gère certaines exceptions : certaines exceptions sont en effet récupérables, et disparaissent si on réexécute l'instruction. Ces exceptions peuvent provenir d'une erreur de prédiction de dépendance entre instructions (on a émis une instruction sans savoir si ses opérandes étaient prêts), ou d'autres problèmes dans le genre. Si jamais une exception récupérable a eu lieu, l'instruction doit être réexécutée, et donc réémise. Elle doit refaire une boucle dans le pipeline. Seul problème : ces exceptions se détectent à des étages très différents dans le pipeline. Dans ce cas, on peut adapter le pipeline pour que chaque exception soit vérifiée et éventuellement réémise dès que possible. On doit donc ajouter plusieurs étages de vérification, ainsi que de nombreuses boucles de réémission.

◄ Retour vers « Les pipelines de longueur variable »

Sommaire du livre

Continuer vers « Les caches non-bloquants » ►