Fonctionnement d'un ordinateur/Le parallélisme mémoire

Dans ce chapitre, nous allons voir les techniques qui permettent de gérer plusieurs accès mémoire simultanés directement au niveau du cache ou de la mémoire RAM. Par plusieurs accès mémoire simultanés, vous pensez sans doute à l'usage de cache multiports, voire de mémoires RAM multiport. C'est en effet une solution, mais ce n'est clairement pas la seule. Par exemple, il est possible de pipeliner l'accès au cache, voire à la mémoire RAM. Il existe de nombreuses techniques de parallélisme mémoire, et nous allons les voir dans ce chapitre.

Pour donner un exemple, il est possible de pipeliner les accès mémoire. Il est possible de pipeliner l'accès au cache et/ou l'accès à la mémoire, et nous verrons comment faire dans ce chapitre. Pipeliner l'accès au cache est une technique en vigueur dans les processeurs modernes, qu'ils aient ou non un pipeline dynamique. Par contre, pipeliner la mémoire est une technique ancienne, aujourd'hui peu utilisée. Elle était utilisée sur des très vieux ordinateurs, qui avaient un pipeline mais pas de mémoire cache. Mais de nos jours, les mémoires SDRAM et DDR ne sont pas adaptées pour ça, il est très difficile de les pipeliner correctement.

Le parallélisme mémoire est utile aussi bien sur des processeurs à émission dans l'ordre que dans le désordre. Par exemple, un processeur in-order avec des lectures non-bloquantes peut en profiter. Il peut techniquement lancer une seconde lecture, après avoir rencontré une première lecture non-bloquante. En général, le nombre de lectures consécutives est cependant limité à moins d'une dizaine. À l'opposé, les processeurs sans lectures non-bloquantes profitent pas du parallélisme mémoire. À la rigueur, ils peuvent en profiter s'ils intègrent des techniques de préchargement. Pendant que le processeur exécute une lecture/écriture, il peut précharger une autre donnée en parallèle. Inutile de dire que sans pipeline processeur, le parallélisme mémoire ne sert pas à grand-chose.

Le line fill buffer et les techniques associées

Lors d'un défaut de cache, le processeur doit attendre que toute la ligne de cache soit chargée avant d'être utilisable. Or, la taille d'une ligne de cache est supérieure à la largeur du bus mémoire, ce qui fait qu'une ligne de cache est chargée en plusieurs fois, morceaux par morceaux, mot mémoire par mot mémoire. Le chargement peut se faire directement dans le cache, mais ce n'est pas une solution très pratique. À la place, beaucoup de processeurs ajoutent une mémoire tampon entre la RAM et le cache, appelée le tampon de remplissage de ligne (line-fill buffer) dans les processeurs modernes. Lors d'un défaut de cache, le processeur charge la donnée de la RAM dans le tampon de remplissage de ligne, mot mémoire par mot mémoire. Une fois plein, le tampon de remplissage de ligne est recopié dans la ligne de cache.

Le tampon de remplissage de ligne contient une ligne de cache, si ce n'est que certains bits de contrôle ne sont pas présents. Le tampon de remplissage de ligne contient un bit de validité pour chaque mot mémoire de la ligne de cache, qui indiquent si le mot mémoire a été chargé. Par exemple, prenons un processeur 64 bits, qui gère donc des mots mémoire de 8 octets, avec des lignes de cache 256 octets/32 mots mémoire. Le tampon de remplissage de ligne contiendra 32 bits de validité. Si le processeur a chargé les 6 premiers mots mémoire, les 6 premiers bits de validité seront mis à 1, les autres seront encore à zéro. Il faut noter que la disponibilité de la ligne complète se détermine assez facilement en faisant un ET logique entre tous les bits de validité. Le processeur sait ainsi quand la ligne de cache est disponible entièrement et donc quand la transférer dans le cache.

La même chose existe avec une hiérarchie de cache, sauf que l'on trouve une mémoire tampon entre chaque niveau de cache. Il y a un tampon de remplissage de ligne entre le cache L1 et le cache L2, entre le cache L2 et le L3, etc. Si le cache ne gère qu'un seul défaut de cache à la fois, le fill line buffer est une mémoire très simple, qui ne mémorise qu'une seule ligne de cache. Et cela vaut aussi bien pour un cache bloquant que non-bloquant. Mais sur les caches capables de gérer plusieurs défauts simultanés, le tampon de remplissage de ligne est une mémoire de type FIFO ou LIFO, capable de mémoriser plusieurs lignes de cache.

Notons que le tampon de remplissage de ligne est très utile pour implémenter certaines techniques, par exemple le contournement du cache. Nous avions vu dans le chapitre sur le cache que certains accès mémoire doivent contourner le cache, pour des raisons de cohérence des caches. C'est notamment nécessaire pour accéder aux périphériques, mais c'est aussi utile pour des raisons de performances dans des cas très spécifiques. Les accès qui contournent le cache se font directement dans le tampon de remplissage de ligne : le processeur écrit ou lit les données depuis ce tampon de remplissage de ligne, sans accéder au cache.

L'early restart et le critical word load

La présence du line buffer permet une optimisation assez intéressante, qui permet de réduire la latence des défauts de cache. L'optimisation consiste à lire un mot mémoire dans le tampon de remplissage de ligne, même si la ligne de cache complète n'a pas encore été chargée. Il existe deux manières de faire cela, qui portent les noms d'early restart et de critical word load. La première est la version la plus simple, la seconde est plus complexe mais plus performante.

Avec la technique d'early restart, la ligne de cache est chargée normalement, en partant de son premier mot mémoire. Dès que le mot mémoire lu/écrit par le processeur est copié dans le line fill buffer, il est envoyé au processeur immédiatement. Illustrons le tout par un exemple, où une ligne de cache fait 16 mots mémoire. Le processeur effectue une lecture, qui lit le 5ème mot mémoire. Sans early restart, le processeur doit charger les 16 mots mémoire avant de faire la lecture dans le cache. Avec early restart, le processeur reçoit la donnée dès que le 5ème mot mémoire est disponible. Le processeur doit attendre que les 4 premiers mots mémoire soient chargés, puis le 5ème mot mémoire arrive et est envoyé directement au processeur, il est lu directement depuis le line fill buffer. Les 11 mots mémoire suivants sont ensuite chargés dans le cache pendant que le processeur fait des calculs dans son coin.

Le critical word load est une optimisation de la technique précédente où le chargement de la ligne de cache commence directement à la donnée demandée par le processeur. Pour reprendre l'exemple précédent, où le processeur demande le 5ème mot mémoire sur 16, le critical word load charge le 5ème mot mémoire en premier et l'envoie au processeur, ce qui fait qu'il est chargé très rapidement. Pas besoin d'attendre que le processeur charge les 4 mots mémoire précédents comme avec l'early restart. Dans le détail, le processeur charge le 5ème mot mémoire en premier, puis charge les 11 suivants, et termine par les 4 mots mémoire du début. En clair, le critical word load commence par charger le mot mémoire lu, puis les blocs suivants, avant de revenir au début du bloc pour charger les blocs restants. Ainsi, la donnée demandée par le processeur sera la première disponible.

Pour cela, l'organisation du tampon de remplissage de ligne est modifiée de manière à rendre cela possible. Il a une taille égale à une ligne de cache complète, qui contient elle-même plusieurs mots mémoire. Dans le line-fill buffer, chaque mot mémoire est stocké avec un tag, qui indique l'adresse du mot mémoire stocké dans le line-fill buffer. Le line-fill buffer est donc un cache un peu particulier, qui fonctionne comme un cache du point de vue du processeur, comme une mémoire FIFO pour les transferts avec le cache. Ainsi, un processeur qui veut lire dans le cache après un défaut peut accéder à la donnée directement depuis le tampon de remplissage de ligne, alors que la ligne de cache n'a pas encore été totalement recopiée en mémoire.

Les caches pipelinés

Il est possible de pipeliner l'accès au cache, ce qui demande juste de rajouter des registres au bon endroits et quelques circuits de contrôle. Pipeliner l'accès au cache est une technique en vigueur dans les processeurs modernes, même ceux avec un pipeline dynamique. Et l'implémentation peut se faire de plusieurs manières différentes. Il faut dire que découper une mémoire cache en plusieurs étapes peut se faire de plusieurs manière. Commençons par la plus simple.

Beaucoup de processeurs des années 2000 avaient une fréquence peu élevée comparée aux standards d'aujourd'hui, ce qui fait que leur cache avait bien un temps d'accès d'un cycle d'horloge. Mais l'accès au cache se faisait en deux cycles d'horloge : un cycle pour calculer une adresse et un cycle pour l'accès mémoire proprement dit. Et ces deux étapes étaient pipelinées, à savoir que deux micro-opérations mémoire peuvent s'exécuter en même temps : une dans l'étage de calcul d'adresse, une autre dans le cache. L'unité mémoire était donc pipelinée, alors que l'accès au cache ne l'était pas. Les processeurs qui implémentaient cette technique regroupent les micro-architectures K5 et K6 d'AMD, les processeurs Intel de micro-architecture P6 (Pentium 2 et 3) et quelques autres.

Il est aussi possible de pipeliner l'accès au cache lui-même. 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.

Le pipelining des caches direct-mapped

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.

Cache directement adressé pipeliné - deux étages

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.

Cache directement adressé pipeliné - trois étages

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.

Le pipelining des caches splittés/sériels

Il est aussi possible de pipeliner un cache dits splittés, aussi appelés à 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 caches non bloquants

Un cache bloquant est un cache auquel le processeur ne peut pas accéder pendant un défaut de cache. Il faut attendre que la lecture ou écriture en RAM soit terminée avant de pouvoir utiliser de nouveau le cache. Un cache non bloquant n'a pas ce problème : on peut l'utiliser pendant un défaut de cache. Les caches non bloquants permettent de démarrer une nouvelle lecture ou écriture alors qu'une autre est en cours, ce qui permet d'exécuter plusieurs lectures ou écritures en même temps.

Les Miss Handling Status Registers

Lors d'un défaut de cache, la mémoire RAM est consultée pendant le défaut de cache, mais le cache est inutilisé. Un défaut de cache n'utilise pas le cache, ce n'est qu'un accès en mémoire RAM, sur le bus mémoire (ou un accès aux niveaux de cache inférieurs, peu importe). Le cache en lui-même est laissé libre, rien n’empêche d'y accéder, il est en réalité intrinsèquement non-bloquant. Les caches, bloquants comme non-bloquants, sont en réalité composés d'une mémoire cache proprement dite, entourée de circuits qui servent d'interface entre le processeur et le cache lui-même. Et parmi les circuits tout autour, certains gèrent l'accès au cache lors d'un défaut de cache. Ils sont regroupés sous le terme de Miss Handling Architecture (MHA). La différence entre un cache bloquant et un cache non-bloquant est en réalité liée à l'implémentation de la MHA.

Les caches bloquants coupent volontairement l'accès au cache lors d'un défaut, car les défauts sont plus simples à gérer ainsi. Le défaut de cache rapatrie une donnée depuis la RAM, qui sera écrite dans le cache. Et il ne faut pas qu'une tentative d'accès à cette donnée ait lieu avant qu'elle ne soit chargée. Mais ce blocage est général et touche tout le cache, alors que seule une ligne de cache est concernée par le défaut de cache.

L'idée derrière un cache non-bloquant est que seule la ligne de cache est bloquée, mais les autres sont accessibles. L'idée est alors de mémoriser les lignes de cache concernées par le défaut de cache, afin d'en bloquer l'accès. À chaque accès, on vérifie si la ligne de cache est déjà réservée par un défaut de cache. La lecture/écriture est alors bloquée si c'est le cas, mais elle accepte les accès sinon. Pour cela, la Miss Handling Architecture contient des registres qui mémorisent des informations sur les défauts de cache en cours. Ils portent le nom de miss status handling registers, que j’appellerais dorénavant MSHR, qui sont aussi appelés des miss buffer.

Le contenu des MSHR varie beaucoup suivant le processeur, mais ces derniers stockent au minimum les informations suivantes :

• Le numéro de la ligne de cache dans laquelle les données sont chargées.
• Un bit de validité qui indique si le MSHR est vide ou pas, qui est mis à 0 quand le défaut de cache est résolu.
• Un ou plusieurs champs de lecture/écriture, qui contiennent des informations sur la lecture/écriture.
  • Pour une lecture, elle contient des informations sur la destination de la donnée, à savoir qui prévenir quand le défaut de cache est terminé. C'est parfois un nom/numéro de registre (celui dans lequel charger la donnée), mais c'est souvent le numéro de l'entrée dans le load/store queue.
  • Pour les écritures, elle contient la donnée à écrire, ou éventuellement un numéro de load/store queue où se trouve la donnée à écrire.

Il faut noter que le bus mémoire ne peut gérer qu'un seul défaut de cache à la fois. Aussi, il est intéressant de regarder ce qui se passe lorsqu'un second défaut de cache survient, pendant qu'un premier est en cours. Dans ce cas, il y a deux réponses qui correspondent à deux types de caches non-bloquants, qui portent les noms barbares de caches de type succès après défaut et défaut après défaut. Sur le premier type, il ne peut pas y avoir plusieurs défauts de cache simultanés. Dès qu'un second défaut de cache survient, le cache stoppe son activité et on ne peut plus démarrer de nouvelle lecture/écriture, tant que le premier défaut de cache n'est pas résolu. Le second type est plus souple et autorise la survenue de plusieurs défauts de cache simultanés. Du moins, jusqu'à une certaine limite, car le cache ne peut supporter qu'un nombre limité d'accès mémoires simultanés (pipelinés).

Les accès simultanés à une même ligne de cache

Il arrive que le processeur fasse plusieurs accès mémoire simultanés à la même ligne de cache. Si la ligne de cache en question n'a pas encore été chargée dans le cache, alors on a plusieurs défauts de cache consécutifs pour la même ligne de cache, et le cache non-bloquant doit gérer la situation. Pour la suite, il va falloir faire une petite distinction entre les défauts primaires et secondaires. Imaginons qu'un défaut de cache ait lieu et demande à charger une donnée dans la ligne de cache numéro N. Il s'agit du premier défaut impliquant cette ligne de cache précise, ce qui lui vaut le nom de défaut de cache primaire. Mais par la suite, d'autres accès mémoire à la même ligne de cache ont lieu, alors que la ligne de cache n'est pas encore disponible. Dans ce cas, il s'agit de défauts de cache secondaires.

Pour l'unité d'accès mémoire, les défauts de cache primaire et secondaire sont différents (ils prennent tous une entrée dans la load/store queue). Mais pour le cache, ils ne correspondent qu'à un seul accès au cache : celui qui demande de charger la ligne de cache demandée. Les défauts de cache primaire et secondaire à la même ligne de cache se voient attribuer un MSHR unique. La gestion des défauts de cache secondaires dépend du cache non-bloquant. La solution la plus simple ne permet pas les défauts de cache secondaires. Le cache ne permet pas deux défauts de cache simultanés pour la même ligne de cache. Les autres solutions le permettent, en fusionnant des accès simultanés à la même ligne de cache en un seul au niveau des MSHR. Dans tous les cas, détecter les défauts de cache secondaires sont un problème qu'il faut détecter.

La Miss Handling Architecture doit détecter les défauts de cache secondaire. Pour cela, elle procède comme suit. Lors de chaque défaut de cache, la MHA récupère le numéro de la ligne de cache associé. Il vérifie alors chaque MSHR pour vérifier s'il contient le numéro en question. S'il n'y a aucune correspondance dans les MSHR, alors c'est signe que le défaut de cache est un défaut primaire. Mais s'il y en a une, alors c'est un défaut secondaire. Évidemment, cela signifie que lors d'un défaut de cache, le numéro de ligne de cache est envoyé à tous les MSHR, pour comparaison. Les MSHR sont donc regroupés dans une mémoire associative, une sorte de mini-cache, faciliter l'implémentation.

Lors d'un défaut de cache primaire, l'accès à un cache non-bloquant se fait comme suit : le processeur envoie une adresse au cache, accède à celui-ci, et détecte la survenue d'un défaut de cache. Il en profite alors pour attribuer une ligne de cache dans laquelle sera chargée ce défaut. L'attribution est très simple dans le cas des caches direct mapped, ou associatifs par voie, pour lesquels l'attribution se fait assez simplement. Il mémorise alors cette information dans les MSHR, après avoir vérifié que le défaut de cache n'était pas un défaut secondaire.

Lors des accès ultérieurs à une adresse proche, censée être dans la même ligne de cache, le processeur va encore une fois rencontrer un défaut de cache. Il va alors déterminer le numéro de la ligne de cache associée à l'adresse, et comparer ce numéro avec les MSHRs. Si un MSHR contient ce numéro, c'est signe que le défaut de cache est un défaut secondaire. La MHA réagit alors différemment selon le processeur considéré. Une première solution n'autorise pas les défauts de cache secondaires. Si l'un d'entre eux survient, le processeur est gelé par un pipeline stall, une bulle de pipeline. Une autre solution fusionne les défauts de cache secondaires avec le défaut de cache primaire : tout cela ne correspond qu'à un seul défaut de cache pour lui.

Les MSHR simples

Un cache non-bloquant à MSHR simple contient juste plusieurs MSHR qui mémorisent juste un numéro de ligne de cache, un bit de validité, le champ de lecture/écriture, et l'adresse exacte de lecture/écriture. Avec cette organisation, il est possible d'avoir plusieurs défauts de cache séparés, mais à la condition que chaque défaut accède à une ligne de cache différente. Deux accès simultanés à une même ligne de cache ne sont pas possibles, les défauts de cache secondaires ne sont pas autorisés. Ainsi, chaque défaut de cache se voit attribuer son propre MSHR, chacun contient un numéro de ligne de cache différent.

Pour comprendre pourquoi c'est impossible de gérer les défauts secondaires, il faut regarder le champ de lecture/écriture. Si on veut effectuer plusieurs écritures consécutives à la même adresse, le MSHR n'aura pas de quoi mémoriser les deux données à écrire. Il pourra mémoriser la première donnée à écrire, pas la seconde. Même chose lors d'une lecture : le champ lecture/écriture peut mémorisr la destination de la première lecture, pas de la seconde.

L'avantage est que la MHA n'a besoin que des MSHR et de quelques circuits annexes. Les autres solutions rajoutent des circuits annexes pour gérer les défauts de cache secondaires, qui utilisent beaucoup de circuits. Le cout en circuit est donc élevé, mais le gain en performance est là. Passons maintenant aux caches non-bloquants qui autorisent les défauts de cache secondaire. La solution la plus simple consiste à utiliser

Les MSHR adressés implicitement

Avec les MSHR adressés implicitement, il est possible de fusionner plusieurs accès mémoire à une même ligne de cache, mais sous une condition très importante : ces accès lisent/écrivent des mots mémoire différents. Par exemple, imaginons qu'une ligne de cache contienne 8 mots mémoire de 64 bits. Si un premier accès mémoire lit le mot mémoire numéro 7 (dernier mot mémoire de la ligne), et le second accès le mot mémoire numéro 3, alors la fusion est possible. Mais si deux accès mémoire veulent lire/écrire le mot mémoire numéro 7, alors la fusion n'est pas possible et le processeur se bloque, un pipeline stall survient.

Un MSHR adressé implicitement est un MSHR simple, qui contient naturellement un numéro de ligne de cache (tag) et un bit de validité, sauf que le champ de lecture/écriture est dupliqué. Les différents champs lecture/écriture d'un MSHR sont regroupés dans une mémoire RAM/cache qui contient autant d'entrées qu'il y a de mot mémoire dans une ligne de cache. Chaque entrée de la table est associée à un mot mémoire de la ligne de cache et stocke des informations sur celui-ci. Une entrée mémorise, au minimum :

• Un champ de lecture/écriture qui contient soit la destination de la lecture, soit la donnée à écrire.
• Un bit R/W permettant d'interpréter correctement le champ de lecture/écriture.
• Un bit de validité pour chaque entrée de la table, qui dit si un défaut de cache antérieur accède déjà à ce mot mémoire.

La fusion de deux défauts de cache est ainsi assez simple. Un défaut de cache primaire/secondaire configure l'entrée associée au mot mémoire lu/écrit. Si un défaut secondaire ultérieur lit/écrit un mot mémoire différent (dont le bit de validité de l'entrée dans la table est à zéro), pas de conflit : il configure une autre entrée, vide. Mais s'il lit/écrit un mot mémoire pour lequel l'entrée de la table est occupée, il y a conflit, le processeur est bloqué par un pipeline stall, une bulle de pipeline. Avec cette organisation, le nombre de MSHR indique combien de lignes de cache peuvent être lues en même temps depuis la mémoire. Quant au nombre d'entrées par MSHR, il détermine combien d'accès mémoires qui ne se recouvrent pas peuvent avoir lieu en même temps.

Les MSHR adressés explicitement

Les MSHR adressés explicitement n'ont pas les contraintes des MSHR adressés implicitement. Avec eux, il est possible d'avoir plusieurs défauts de cache pointant vers la même ligne de cache, mais aussi vers le même mot mémoire. De tels défauts de cache apparaissent sur les processeurs à exécution dans le désordre, mais sont très rares, voire inexistants, sur les processeurs in-order.

L'idée est encore que chaque MSHR est associée à une table mémoire qui mémorise des entrées. Cette table n'est autre qu'une mémoire FIFO. Sauf que cette fois-ci, une entrée n'est pas associée à un mot mémoire. Une entrée est associée à un défaut de cache. Une entrée mémorise là encore la destination de la lecture ou la donnée de l'écriture suivi du bit R/W, ainsi que d'un bit de validité par entrée, mais aussi : la position du mot mémoire lu dans la ligne de cache. C'est cette dernière information qui n'était pas présente dans les MSHR adressés implicitement. De plus, le nombre d'entrée par MSHR n'est pas égal au nombre de mots mémoires dans une ligne de cache, mais peut être arbitrairement grand.

L'avantage d'un tel cache est qu'il est capable de traité les défauts secondaires concernant un même mot mémoire, et ce, car les accès à la ligne de cache concernée se produisent dans l'ordre de génération des défauts (la table mémoire est une FIFO).

Les MSHRs inversés

Généralement, plus on veut supporter de défauts de cache, plus le nombre de MSHR et d'entrées augmente. Mais au-delà d'un certain nombre d'entrées et de MSHR, les MSHR adressés implicitement et explicitement ont tendance à bouffer un peu trop de circuits. Utiliser une organisation un peu moins gourmande en circuits est donc une nécessité. Cette organisation plus économe se base sur des MSHR inversés.

Les MSHR inversés ne contiennent qu'une seule entrée, en quelque sorte : au lieu d’utiliser n MSHR de m entrées chacun, on va utiliser n × m MSHR inversés. La différence, c'est que plusieurs MSHR peuvent contenir un tag identique, contrairement aux MSHR adressés implicitement et explicitement. Lorsqu'un défaut de cache a lieu, chaque MSHR est vérifié. Si jamais aucun MSHR ne contient de tag identique à celui utilisé par le défaut, un MSHR vide est choisi pour stocker ce défaut, et une requête de lecture en mémoire est lancée. Dans le cas contraire, un MSHR est réservé au défaut de cache, mais la requête n'est pas lancée. Quand la donnée est disponible, les MSHR correspondant à la ligne qui vient d'être chargée vont être utilisés un par un pour résoudre les défauts de cache en attente.

Les MSHR intégrés au cache

Certains chercheurs ont remarqué que pendant qu'une ligne de cache est en train de subir un défaut de cache, celle-ci reste inutilisée, et son contenu est destiné à être perdu une fois le défaut de cache résolu. Ils se sont dit que, plutôt que d'utiliser des MSHR séparés, il vaudrait mieux utiliser la ligne de cache pour stocker les informations sur les défauts de cache en attente dans cette ligne de cache.

Pour éviter tout problème, il faut rajouter un bit dans les bits de contrôle de la ligne de cache, qui sert à indiquer que la ligne de cache est occupée : un défaut de cache a eu lieu dans cette ligne, et elle stocke donc des informations pour résoudre les défauts de cache.

L'entrelacement mémoire

Nous venons de voir comment une mémoire cache peut gérer plusieurs accès mémoire simultanés. Il se trouve que ce genre d'optimisation dépasse largement le cadre du cache. Les mémoires RAM ne sont pas en reste, elles aussi ! Il est possible de pipeliner l'accès à une mémoire RAM, en utilisant des techniques dites d'entrelacement. Précisons cependant que cette optimisation n'est pas utilisée sur les mémoires SDRAM ou DDR modernes, du moins pas sans modifications majeures. Mais divers ordinateurs assez anciens, dont des superordinateurs, ont utilisé cette technique.

La technique demande d'utiliser plusieurs mémoires séparées. Sur les anciens ordinateurs, les mémoires en question sont des chips mémoire, à savoir des circuits intégrés de DRAM. Pour faire plus général, nous allons utiliser le terme de banques, ou encore de bancs mémoire. La différence est qu'il existe des mémoires multi-banque, qui regroupent plusieurs banques indépendantes dans un seul boitier, dans un seul chip mémoire. En clair, de telles mémoires regroupent plusieurs sous-mémoires dans un seul circuit intégré. Il est aussi possible d'utiliser plusieurs chips mémoire séparés, chacun ayant une banque. Reste à combiner ces banques pour former un pseudo-pipeline.

Utiliser plusieurs banques sans entrelacement

Sans optimisation particulière, les adresses sont réparties dans les banques comme indiqué ci-dessous. Il s'agit de ce qui s'appelle un arrangement horizontal, et nous avions vu celui-ci dans le chapiutre sur les mémoires SDRAM.

Répartition des adresses sans entrelacement.

Avec cet arrangement, les bits de poids fort de l'adresse sont utilisées pour sélectionner la banque adéquate, et le reste de l'adresse est envoyé sur le bus d'adresse. Les adresses mémoire sont alors découpées comme suit :

Adresse mémoire

Adresse de banque	Adresse dans la banque
Quelques bits de poids fort	Reste de l'adresse

L'entrelacement change cette répartition, afin d'accélérer les accès mémoire. L'entrelacement classique vise à améliorer les accès à des adresses mémoires consécutives, mais des formes plus évoluées d'entrelacement visent à optimiser des accès mémoire arbitraires. Voyons-les dans l'ordre, du plus simple au plus complexe.

L'entrelacement classique

Avec l'entrelacement classique, des adresses consécutives sont réparties dans des banques consécutives. Précisons que cette attribution des adresses n'implique absolument pas la mémoire virtuelle ou n'importe quel mécanisme dans le processeur. La répartition décide que telle adresse mémoire va dans telle banque, à telle adresse dans la banque. Elle est donc le fait du contrôleur mémoire, donc en dehors du processeur (les contrôleurs mémoires n’étaient pas encore intégrés dans le processeur à l'époque).

Répartition des adresses dans une mémoire interleaved.

L'entrelacement simple permet d'accélérer les accès mémoire qui se font à des adresses consécutives. Avec l'entrelacement, chaque accès mémoire tombe dans une banque mémoire différente, ce qui fait qu'on peut démarrer un nouvel accès mémoire à chaque cycle d'horloge. Pendant qu'une banque est occupée par un accès mémoire, on démarre le suivant dans une autre banque, et ainsi de suite. Le tout se termine soit quand on a épuisé toutes les banques libres, soit quand l'accès en rafales se termine. Pas besoin d'attendre que la mémoire ait fini sa lecture/écriture avant de démarrer la lecture/écriture suivante.

Pipelining mémoire

L'animation suivante illustre bien le processus, avec quatres banques.

Pipelining mémoire

L'entrelacement simple utilise les bits de poids faible pour sélectionner la banque, et les bits de poids fort pour la case mémoire.

Adresse mémoire d'une mémoire entrelacée

Précisons que le temps d'accès mémoire ne change pas beaucoup avec l'entrelacement. Par contre, on peut faire plus d'accès mémoire simultanés. On peut démarrer un accès mémoire par cycle d'horloge, mais l'accès en lui-même prend plusieurs cycles. Les mémoires à entrelacement ont donc un débit supérieur aux mémoires qui ne l'utilisent pas.

L'entrelacement classique pourrait être utilisé pour accélérer les transferts entre mémoire RAM et cache, qui se font en blocs d'adresses consécutives. Mais de nos jours, il n'est pas utilisé dans cette optique. Il faut dire qu'il est redondant avec le mode rafale des mémoires DRAM. Les deux font globalement la même chose et on voit mal comment utiliser les deux en même temps. Le mode rafale étant plus simple à implémenter, et plus léger niveau utilisation du bus de commande mémoire, il est préféré à l'entrelacement.

Par contre, l'entrelacement a eu son heure de gloire sur d'anciens processeurs qui n'avaient pas de mémoire cache, alors qu'ils disposaient d'un pipeline. L'exemple typique est celui des nombreux processeurs vectoriels, que nous n'avons pas encore abordé à ce stade du cours. De tels processeurs avaient un pipeline, une unité de calcul fortement pipelinée, et parfois même de l'exécution dans le désordre et du renommage de registres !

L'entrelacement par décalage

L'entrelacement simple est très utile pour les accès en rafle ou équivalents. Par contre, il existe de rares situations où il n'est pas optimal. Une de ces situations est celle des accès en enjambée (en stride), où l'on accède en série à des adresses sont séparées par N mots mémoires.

Accès par enjambées.

De tels accès surviennent quand un logiciel accède à des structures de données spécifiques, à savoir des tableaux de structures, des matrices, ou d'autres structures de données dans le genre. Un cas classique est celui du parcours d'une matrice colonne par colonne. Les matrices de nombres sont mémorisées ligne par ligne, ce qui fait que parcourir une colonne demande de passer d'une ligne à la suivante et de faire des grands sauts en mémoire RAM, mais tous espacés par la même distance.

Avec l'entrelacement simple, les accès en enjambée sont moins performants que les accès à des adresses consécutives, mais cela ne fonctionne pas trop mal. Le pire cas est celui où l'on a N banques et où les données sont justement placées toutes les N adresses. Des accès consécutifs vont tous tomber dans la même banque, on ne peut plus accéder à des banques différentes en parallèle. Mais en dehors de ce cas, on voit une amélioration par rapport à la situation sans entrelacement.

Pour obtenir des performances maximales pour les accès en enjambées, il faut répartir les mots mémoires dans la mémoire autrement. L'organisation idéale est la suivante.

Dans les explications qui vont suivre, la variable N représente le nombre de banques, qui sont numérotées de 0 à N-1.

On commence par organiser les N premières adresses comme une mémoire entrelacée simple : l'adresse 0 correspond à la banque 0, l'adresse 1 à la banque 1, etc. Pour le bloc suivant, on décale tout d'une adresse, à savoir qu'on commence à remplir les banques à partir de la seconde, non de la première. Une fois la fin du bloc atteinte, on finit de remplir le bloc en repartant du début du bloc. Le troisième bloc d'adresse subit le même traitement, sauf qu'on commence à remplir à partir de la seconde banque. Et on poursuit l’assignation des adresses en décalant d'un cran en plus à chaque bloc. Ainsi, chaque bloc verra ses adresses décalées d'un cran en plus comparé au bloc précédent. Si jamais le décalage dépasse la fin d'un bloc, alors on reprend au début.

Mémoire entrelacée par décalage.

En faisant cela, on remarque que les banques situées à N adresses d'intervalle sont différentes. Dans l'exemple du dessus, nous avons ajouté un décalage de 1 à chaque nouveau bloc à remplir. Mais on aurait tout aussi bien pu prendre un décalage de 2, 3, etc. Dans tous les cas, on obtient un entrelacement par décalage. Ce décalage est appelé le pas d'entrelacement, noté P. Le calcul de l'adresse à envoyer à la banque, ainsi que la banque à sélectionner se fait en utilisant les formules suivantes :

• adresse à envoyer à la banque = adresse totale / N ;
• numéro de la banque = (adresse + décalage) modulo N ;
• décalage = (adresse totale * P) mod N.

Avec cet entrelacement par décalage, on peut prouver que la bande passante maximale est atteinte si le nombre de banques est un nombre premier. Seulement, utiliser un nombre de banques premier peut créer des trous dans la mémoire, des mots mémoires inadressables. Malgré ce défaut, la technique a été utilisée sur quelques ordinateurs, avec l'exemple notable du superordinateur Burroughs Scientific Processor. Pour éviter cela, il y a plusieurs solutions. Par exemple, on peut faire en sorte que N et la taille d'une banque soient premiers entre eux : ils ne doivent pas avoir de diviseur commun. Mais en pratique, elles n'ont pas vraiment été implémentées dans une vraie machine, et sont restées à l'état de recherche, aussi je les passe sous silence.

L'entrelacement pseudo-aléatoire

Une dernière méthode de répartition consiste à répartir les adresses dans les banques de manière "pseudo-aléatoire". L'idée exacte est de faire passer l'adresse dans une fonction de hachage, plus ou moins complexe. Pour rappel, une fonction de hachage prend une entrée de grande taille et fournit en sortie un résultat de petite taille. Idéalement, elles doivent donner des résultats aussi différents que possible pour des entrées similaires, histoire de simuler une sorte de pseudo-aléatoire. Ici, une adresse est transformée en un numéro de banque.

Une fonction de hachage simple ne fait que permuter des bits de l'adresse pour obtenir son résultat. Elle ne fait qu'échanger des bits de place avant de couper l'adresse en deux morceaux : un pour la sélection de la banque, et un autre pour la sélection de l'adresse dans la banque. Cette permutation est fixe, et ne change pas suivant l'adresse. Des fonctions de hachage plus complexes font des XOR bit à bit entre certains bits de l'adresse.

Les contrôleurs SDRAM/DDR avec "exécution dans le désordre"

Après avoir vu le cas des mémoires RAM, nous allons nous concentrer sur le cas particulier des mémoires SDRAM. Les mémoires SDRAM et DDR modernes sont capables de gérer plusieurs accès simultanés à la mémoire RAM, et leurs contrôleurs mémoire en font tout autant. C'est une différence majeure avec les mémoires asynchrones FPM/EDO, qui n'acceptaient qu'un seul accès mémoire à la fois. Leur contrôleur mémoire n'acceptait qu'un seul accès mémoire à la fois, c'était un contrôleur mémoire bloquant. Les contrôleurs mémoires des SDRAM sont eux non-bloquants et peuvent encaisser une dizaine d'accès mémoire à la fois.

Peu de choses sont connues sur les contrôleurs de SDRAM/DDR modernes, les fabricants ne donnant que peu de détails dessus. Les rares simulateurs qui tentent de décrire leur fonctionnement, comme DRAM SIM I et II, sont particulièrement simples et ne vont pas dans le détail. Néanmoins, le peu qu'on sait est tout de même instructif.

Rappel sur les SDRAM : tampon de ligne et commandes

Les mémoires SDRAM sont des mémoires à tampon de ligne. Elles font un accès mémoire en deux étapes. La première étape recopie une ligne de N * 64 bits dans un tampon interne à la SDRAM. La seconde étape sélectionne une colonne, à savoir une donnée de 64 bits, qui est soit envoyée sur le bus de données pour une lecture, soit modifiée par une écriture.

Mémoire à tampon de ligne

Les accès mémoire sont traduits par un séquenceur mémoire en une série de commandes mémoires, qui sont séparées par des délais mémoire de quelques cycles d'horloge. Les délais sont très précis, et sont à respecter à la lettre. Une lecture ou une écriture se fait en maximum trois commandes : une commande PRECHARGE qui ferme la ligne précédemment utilisée, une commande ACT qui précise l'adresse de la ligne, et une commande READ ou WRITE qui précise l'adresse de la colonne et éventuellement la donnée à écrire.

Pour être plus précis, la commande PRECHARGE précharge les lignes de bits du plan mémoire à une tension particulière, ce qui les vide de leur contenu. Mais c'est un détail sans importance pour ce qui va suivre.

Les SDRAM permettent de se passer de la première étape si des accès consécutifs se font dans la même ligne. Une fois activée, la ligne reste ouverte et on peut accéder plusieurs fois de suite dedans. On a alors juste à préciser l'adresse de colonne dedans. Si un accès mémoire accède à une ligne déjà activée, on dit que c'est un succès de page. Si ce n'est pas le cas, on doit fermer la ligne courante, rouvrir la ligne voulue, et préciser la colonne. C'est alors un défaut de page.

	Cycle 1	Cycle 2	Cycle 3	Cycle 4	Cycle 5	Cycle 6	Cycle 7	Cycle 8	Cycle 9	Cycle 10	Cycle 11	Cycle 12	Cycle 13
Bus de commande/adresse	PRECHARGE	ACT		READ (1)		READ (2)	READ (3)			READ (4)	READ (5)
Bus de données						Donnée READ 1		Donnée READ 2	Donnée READ 3			Donnée READ 4	Donnée READ 5

Les SDRAM sont parfois capables de démarrer une commande avant que la précédente soit terminée. Mais le respect des délais mémoire est très limitant, ce qui fait qu'on ne peut pas parler de réel pipeline, comme c'est le cas sur les processeurs. Parlons plutôt de commandes anticipées.

	Cycle 1	Cycle 2	Cycle 3	Cycle 4	Cycle 5	Cycle 6	Cycle 7	Cycle 8	Cycle 9	Cycle 10	Cycle 11	Cycle 12	Cycle 13
Bus de commande/adresse		ACT		READ (1)				READ (2)
Bus de données						READ 1	READ 1	READ 1	READ 1	READ 2	READ 2	READ 2	READ 2 |

Un dernier point est que les chips mémoires de SDRAM sont composés de plusieurs banques, chacune étant une sorte de mini-mémoire miniature. Chaque banque a son propre décodeur, son propre tampon de ligne, ses propres multiplexeurs de colonne, sa logique de rafraichissement mémoire, etc. C'est comme si une SDRAM regroupait plusieurs mémoires séparées dans un même circuit intégré.

Mémoire multi-banques.

La mise en attente des accès mémoire

Un contrôleur de SDRAM peut accepter plusieurs accès mémoire en même temps. Mais cela ne signifie pas que le contrôleur sera prêt à les traiter immédiatement. Pour éviter tout problème de disponibilité, le contrôleur met en attente les accès mémoire que le processeur lui envoie, pour les exécuter dès que possible. Les accès mémoire sont mis en attente dans une mémoire FIFO, histoire de les exécuter dans leur ordre d'arrivée, notamment pour renvoyer les lectures dans l'ordre demandé. Il y a aussi une mémoire FIFO pour les données à écrire et une FIFO pour les données lues. Cette dernière sert au cas où le cache ne soit pas disponible quand on lui envoie la donnée lue.

Contrôleur mémoire avec mise en attente des requêtes processeur et autres optimisations.

Les lectures anticipées : une forme d'OOO mémoire

La mise en attente des accès mémoire est une optimisation intéressante, mais pas mirifique. Elle permet surtout de ne pas bloquer le processeur si le contrôleur mémoire a du travail sur la planche. Cependant, elle peut être optimisée quand on se rend compte d'une chose : le processeur ne voit que les lectures, pas les écritures. Pour les écritures, il les envoie au contrôleur mémoire et ce dernier fait le travail demandé, le processeur n'est pas prévenu quand une écriture se termine. Mais pour les lectures, c'est différent, car il reçoit la donnée lue. En conséquence, il est possible d'optimiser les écritures sans que le processeur ne voie quoique ce soit.

Une optimisation possible est alors de changer l'ordre des accès mémoire, histoire de retarder les écritures ou au contraire de les faire en avance. La raison est que les mémoires SDRAM n'aiment pas quand on alterne lectures et écritures. Les délais mémoire, les fameux timings mémoire, sont clairs : faire une suite de lecture ou une suite d'écriture est plus performant que d'alterner entre lectures et écritures. L'idée est alors de changer l'ordre des écritures de manière à les faire en bloc, idem pour les lectures.

L’optimisation est possible, mais à condition que le processeur n'y voie que du feu. Or, vous l'avez deviné, il y a des cas où ces réorganisations ne sont pas possibles, et vous avez sans doute trouvé que la situation était familière. L'optimisation en question est une forme d'exécution dans le désordre des accès mémoire, réalisée par le contrôleur mémoire lui-même ! Et qui dit exécution dans le désordre dit : problèmes liés aux dépendances de données. Changer l'ordre des écritures n'est pas toujours possible, notamment en raison des dépendances RAW, WAR et WAW.

Pour que le processeur n'y voie que du feu, il faut respecter plusieurs critères. Premièrement, les lectures doivent être renvoyées au processeur dans l'ordre. Et quand je dis dans l'ordre, cela veut dire : dans l'ordre d'envoi des lectures au contrôleur mémoire. Les écritures aussi doivent se faire dans l'ordre, histoire qu'une série d'écriture donne le bon résultat final. Le troisième critère est qu'une lecture doit donner le résultat de la dernière écriture à la même adresse. Pour le dire autrement, il faut juste détecter les dépendances RAW.

Concrètement, si on a une série de lectures et d'écritures alternées, on peut regrouper les lectures et les écritures dans deux paquets séparés, à condition qu'aucune lecture ne lise une adresse écrite par une écriture. Mais si une lecture est dépendante d'une écriture, alors la lecture doit attendre que l'écriture se termine, idem pour les lectures suivantes.

Une implémentation basique remplace la mémoire FIFO vue au-dessus, par deux mémoires FIFOs : une pour les lectures, une pour les écritures. Lorsqu'un accès mémoire arrive au séquenceur, il regarde si c'est une lecture ou une écriture et place l'accès mémoire dans la file adéquate. Le fait que ce soit des FIFOs garantit que les lectures se font dans l'ordre, idem pour les écritures. En sortie des deux FIFOs, le séquenceur mémoire détecte les dépendances RAW. Précisément, quand une lecture sort de la mémoire FIFO, il consulte la file d'attente des écritures pour voir si la lecture est dépendante d'une écriture en attente. La lecture attend si c'est le cas, et les écritures sont exécutées à la place.

Séparer lectures et écriture est une source d'optimisation. Il est par exemple possible d'utiliser le réacheminement lecture sur écriture (Store to load forwarding). Il s'agit d'un équivalent de l’optimisation du même nom, utilisée dans le cadre de la désambiguïsation mémoire. Imaginez qu'une lecture accède à une donnée pas encore écrite, en attente dans le contrôleur mémoire. C'est une dépendance RAW assez claire. Dans ce cas, le contrôleur mémoire peut renvoyer la donnée directement depuis ses mémoires FIFOs, sans faire d'accès mémoire en lecture.

Le contrôleur mémoire a tendance à privilégier les lectures, car celles-ci sont cruciales pour l'exécution dans le désordre. Plus elles se font tôt, plus vite le processeur recevra les données et pourra démarrer les instructions dépendantes de cette donnée. Le séquenceur a donc tendance à piocher en priorité dans la file de lecture, plutôt que dans la file d'écriture. À vrai dire, dans le cas idéal, les écritures ne sont faites que quand la file d'écriture est pleine ou quasi pleine...

Prenons l'exemple des coprocesseurs IO 81341 et 81342, qui étaient en réalité des chipsets intégrant un contrôleur SDRAM. Le chipset avait 5 ports : un pour les processeurs, un pour le pont sud (southbridge) et trois pour des canaux DMA. Pour le port processeur, il n'y avait pas de réordonnancement et ce port utilisait une seule mémoire FIFO. Les autres ports utilisaient l'optimisation qu'on vient de voir, et avaient vraisemblablement des files séparées pour les lectures et écritures. Le séquenceur mémoire vérifiait les dépendances mémoire de type RAW et autres.

Double file d'attente pour les lectures et écritures

Le ré-ordonnancement des commandes mémoires

L'optimisation précédente est peu poussée, comparé aux formes d'exécution dans le désordre que les processeurs utilisent. Et on peut se demander si une exécution dans le désordre plus poussé est possible. La réponse est oui : un contrôleur mémoire peut faire des réorganisations bien plus poussées. Par contre, il faut faire une précision très importante : le contrôleur mémoire ne remet pas les accès mémoire dans l'ordre avant de les envoyer au processeur. C'est le processeur qui remet en ordre les accès mémoire, dans sa load queue. En clair : le processeur voit les accès mémoire dans le désordre, c'est lui qui les remet en ordre.

Pour cela, les requêtes mémoire sont "numérotées", à savoir qu'on leur attribue un identifiant binaire. Le contrôleur mémoire exécute les lectures/écritures dans le désordre, mais garde la trace de leur identifiant. Il sait dans quel ordre il exécute les accès mémoire et connait leur latence. Ce qui fait qu'il sait que la donnée lue à tel instant est associée à la requête mémoire numéro X. Pour les lectures, il renvoie la donnée lue avec l'identifiant. Le processeur sait alors à quelle lecture la donnée lue correspond et il se débrouille en interne pour gérer la situation.

Maintenant que ces précisions sont faites, posons cette question : dans quelles situations est-il pertinent de faire des accès mémoire dans le désordre ?

La réponse est : quand plusieurs accès à une même ligne ne sont pas consécutifs, qu'il y a des accès entre les deux. Après ré-ordonnancement, ces accès mémoire à une même ligne sont exécutés l'un à la suite de l'autre, ce qui est beaucoup plus rapide. Pour rendre le tout plus concret, voici un exemple. Imaginez que l'on sait les 3 accès mémoire suivants :

• Une lecture ligne A ;
• PRECHARGE + ACT ;
• Une écriture ligne B ;
• PRECHARGE + ACT ;
• Une lecture ligne A.

Sans réordonnancent, on doit émettre deux commandes PRECHARGE quand on passe d'une ligne à l'autre, et il faut ajouter les commandes ACT avec. Pour éviter cela, le contrôleur mémoire peut retarder l'écriture, ou au contraire avancer la seconde lecture. Le résultat est alors le suivant :

• Lecture ligne A ;
• Lecture ligne A
• PRECHARGE + ACT ;
• Une écriture ligne B.

On a donc deux accès consécutifs à la même ligne, suivi par une écriture dans une autre ligne. La technique marche parce que l'on a un mix adéquat de lectures et d'écritures. Et encore une fois, il faut éviter d'intervertir lectures et écritures à une même adresse, sous peine de problèmes. Encore une fois, les dépendances RAW posent problème !

L'implémentation est assez simple : la ou les mémoires FIFOs précédentes sont remplacées par des mémoires similaires aux fenêtres d'instruction. Le contrôleur mémoire vérifie à chaque cycle les accès en attente, et vérifie à quelle ligne ils accèdent. Il priorise alors les accès qui tombent dans la ligne ouverte : ceux-là sont exécutés avant les autres. S'il n'y en a pas, il prend l'accès mémoire le plus ancien (ordre FIFO). Il teste aussi les dépendances mémoires RAW avant d'envoyer des commandes à la mémoire DDR/SDRAM. une telle solution est appelée l'algorithme FR-FCFS (First Ready-First Come First Serve).

Les optimisations liées à la présence de plusieurs banques

Les optimisations précédentes sont décuplées par la présence de plusieurs banques dans la mémoire SDRAM. Il est en effet possible de faire plusieurs accès mémoire en même temps, dans des banques différentes. Il est possible de lancer un accès mémoire dans deux banques en même temps, par exemple. La seule contrainte est que la SDRAM est limitée à 4 banques actives en même temps.

Pipelining basique sur les SDRAM

	Cycle 1	Cycle 2	Cycle 3	Cycle 4	Cycle 5	Cycle 6	Cycle 7	Cycle 8	Cycle 9	Cycle 10	Cycle 11
Banque Numéro 1				Accès mémoire			Accès mémoire
Banque Numéro 2		Accès mémoire					Accès mémoire
Banque Numéro 3				Accès mémoire				Accès mémoire

Les optimisations précédentes peuvent s'appliquer par banque. Il est par exemple possible d'utiliser une mémoire FIFO par banque. Ainsi, les accès dans une même banque se feront en série, dans l'ordre d'arrivée, mais des accès à des banques différentes se feront dans le désordre. Cela ne pose pas de problème, car les accès se font à des adresses différentes, ce qui fait qu'il n'y a pas de conflits majeurs. Il y a cependant un risque que les lectures se fassent dans le désordre si on n'y prend pas garde.

Gestion parallèle des banques.

Il est aussi possible d'utiliser une file séparée pour les lectures et les écritures, pour chaque banque. Les performances sont alors améliorées comparé à deux files globales pour toute la SDRAM. En idem avec la réorganisation des accès mémoire, pour regrouper les accès à une même ligne.

Un problème avec ces optimisations est qu'il est rare que des accès mémoire se fassent dans des banques séparées. Les accès mémoire tendent à se faire avec une bonne localité spatiale, ce qui fait qu'ils tombent dans une même banque. Heureusement, les contrôleurs SDRAM/DDR modernes incorporent des optimisations pour corriger ce problème. Les optimisations en question sont une forme d'entrelacement adaptée aux mémoires SDRAM. L'entrelacement naïf ne marche pas à cause de la présence du tampon de ligne. Cependant, il peut y avoir un entrelacement entre banques SDRAM. Voyons ce que ça veut dire.

L'entrelacement de banques répartit deux lignes consécutives dans deux banques différentes. Pour comprendre l'idée, prenons un exemple. Imaginons une mémoire avec deux banques et 4 lignes. Imaginons qu'on parcoure/balaye la mémoire RAM en partant des adresses basses. Sans entrelacement de ligne, les accès se feront comme suit, de gauche à droite :

Adresse mémoire

Banque numéro 1				Banque numéro 2
Ligne 1	Ligne 2	Ligne 3	Ligne 4	Ligne 1	Ligne 2	Ligne 3	Ligne 4

Avec l'entrelacement de banques, les accès se feront comme suit :

Adresse mémoire

Banque n°1	Banque n°2	Banque n°1	Banque n°2	Banque n°1	Banque n°2	Banque n°1	Banque n°2
Ligne 1	Ligne 1	Ligne 2	Ligne 2	Ligne 3	Ligne 3	Ligne 4	Ligne 4

L'avantage est que passer d'une ligne à la suivante est plus rapide. Pas besoin de fermer la ligne pour passer à la suivante, on ouvre directement la ligne suivante dans une banque différente, ce qui sera plus rapide. La commande PRECHARGE pourra être envoyée à la seconde banque en avance.

Pour gérer l'entrelacement, le contrôleur de SDRAM prend en entrée l'adresse envoyée par le processeur, et la découpe en plusieurs champs : un pour sélectionner la banque adéquate, un autre pour la ligne, un autre pour la colonne, un autre pour la rangée. Sans entrelacement, les adresses mémoire sont découpées comme suit :

Adresse mémoire

Adresse de banque

Adresse de ligne

Adresse de colonne

Avec l'entrelacement de banques, l'adresse est découpée comme suit.

Adresse mémoire

Adresse de ligne

Adresse de banque

Adresse de colonne (précise à l'octet)

Il est aussi possible de faire la même chose, mais avec les rangées ou en utilisant du dual channel, mais je vais passer cela sous silence. Toujours est-il que les méthodes d'entrelacement sont nombreuses et chaque contrôleur mémoire fait un peu à sa sauce. Ils permettent en général de choisir entre plusieurs entrelacements. Au minimum, ils permettent de désactiver l'entrelacement, d'activer un entrelacement de ligne, et d'autres entrelacements plus complexes, dont certains sont propriétaires et tenus secrets par le fabricant.

L'entrelacement est géré juste avant le séquenceur mémoire, dans un circuit d'entrelacement. Ce dernier intervertit certains bits de l'adresse lors des accès mémoires.

Contrôleur mémoire d'une SDRAM avec entrelacement.

Les contrôleurs de SDRAM précédents sont assez basiques et ne représentent pas les contrôleurs les plus évolués. Ils étaient utilisés sur les anciens PC, à une époque où ils étaient encore sur la carte mère du processeur. Mais de nos jours, le contrôleur mémoire est intégré au processeur. Et il incorpore de nombreuses optimisations afin de gagner en performances. Malheureusement, ces optimisations sont elles-mêmes dépendantes des optimisations intégrées dans le processeur, ce qui fait qu'on ne peut pas en parler ici. Elles demandent que le contrôleur mémoire reçoive plusieurs accès mémoire simultanés, ce qui n'a aucun sens à ce stade du cours. Aussi, nous allons les passer sous silence pour le moment. Nous les verrons dans le chapitre sur le parallélisme mémoire.