Fonctionnement d'un ordinateur/Les mémoires FIFO et LIFO

Les mémoires FIFO et LIFO conservent les données triées dans l'ordre d'écriture (l'ordre d'arrivée). La différence est qu'une lecture dans une mémoire FIFO renvoie la donnée la plus ancienne, alors que pour une mémoire LIFO, elle renverra la donnée la plus récente, celle ajoutée en dernier dans la mémoire. Dans les deux cas, la lecture sera destructrice : la donnée lue est effacée. Di autrement, une mémoire FIFO renvoie des données dans leur ordre d'arrivée, alors qu'une LIFO renvoie les données dans l'ordre inverse.

Fonctionnement des mémoires FIFO-LIFO.

On peut voir les mémoires FIFO comme des files d'attente, des mémoires qui permettent de mettre en attente des données tant qu'un composant n'est pas prêt. Seules deux opérations sont possibles sur de telles mémoires : mettre en attente une donnée (enqueue, en anglais) et lire la donnée la plus ancienne (dequeue, en anglais).

Fonctionnement d'une file (mémoire FIFO).

De même, on peut voir les mémoires LIFO comme des piles de données : toute écriture empilera une donnée au sommet de cette mémoire LIFO (on dit qu'on push la donnée), alors qu'une lecture enlèvera la donnée au sommet de la pile (on dit qu'on pop la donnée).

Fonctionnement d'une pile (mémoire LIFO).

L'utilité des mémoires LFIO et FIFO

En soi, les mémoires LIFO sont assez rares. Les seules utilisations connues sont liées à la pile d'appel du processeur, que nous verrons d'ici une dizaine de chapitres. Il existe quelques processeurs qui placent cette pile d'appel dans une mémoire LIFO séparée, mais ce n'est pas le cas sur la quasi-totalité des processeurs récents. Il a existé quelques processeurs qui intégraient le sommet de la pile d'appel dans une mémoire LIFO intégrée au processeur, mais ce n'est plus d'actualité. Il en existe dans les unités de prédiction de branchement des processeurs modernes, pour la prédiction des retour de fonction, mais c'est un sujet que nous aborderons dans la fin du cours.

Les mémoires FIFO sont beaucoup plus utiles. Elles sont surtout utilisées pour mettre en attente des données ou commandes, tout en conservant leur ordre d'arrivée. Si on utilise une mémoire FIFO dans cet optique, elle prend le nom de mémoire tampon. L'utilisation principale des mémoires tampons est l’interfaçage de deux composants de vitesse différentes qui doivent communiquer entre eux. Le composant rapide émet des commandes à destination du composant lent, mais le fait à un rythme discontinu, par rafales entrecoupées de "moments de silence". Lors d’une rafale, le composant lent met en attente les commandes dans la mémoire FIFO et il les consomme progressivement lors des moments de silence.

On retrouve des mémoires tampons dans beaucoup de matériel électronique : dans les disques durs, des les lecteurs de CD/DVD, dans les processeurs, dans les cartes réseau, etc. Prenons par exemple le cas d'un disque dur : il reçoit régulièrement, de la part du processeur, des commandes de lecture écriture et les données associées. Mais le disque dur étant un périphérique assez lent, il doit mettre en attente les commandes/données réceptionnées avant de pouvoir les traiter. Et cette mise en attente doit conserver l'ordre d'arrivée des commandes, sans quoi on ne lirait pas les données demandés dans le bon ordre. Pour cela, les commandes sont stockées dans une mémoire FIFO et sont consommées au fur et à mesure. On trouve le même genre de logique dans les cartes réseau, qui reçoivent des paquets de données à un rythme discontinu, qu'elles doivent parfois mettre en attente tant que la carte réseau n'a pas terminé de gérer le paquet précédent.

L'interface d'une mémoire FIFO/LIFO

Les mémoires FIFO/LIFO possèdent un bus de commande assez simple, sans bus d'adresse vu que ces mémoires ne sont pas adressables. Il contient les bits CS et OE, le signal d'horloge et quelques bits de commande annexes comme un bit R/W.

La mémoire FIFO/LIFO doit indiquer quand celle-ci est pleine, à savoir qu'elle ne peut plus accepter de nouvelle donnée en écriture. Elle doit aussi indiquer quand elle est vide, ce qui signifie qu'il n'y a pas possibilité de lire son contenu. Pour cela, la mémoire possède deux sorties nommées FULL et EMPTY. Ces deux bits indiquent respectivement si la mémoire est pleine ou vide, quand ils sont à 1.

Les mémoires FIFO/LIFO les plus simples n'ont qu'un seul port qui sert à la fois pour la lecture et l'écriture, mais elles sont cependant rares. Dans les faits, les mémoires FIFO sont presque toujours des mémoires double ports, avec un port pour la lecture et un autre pour les écritures. Du fait de la présence de deux ports dédiés, le bit R/W est souvent séparé en deux bits distincts : un bit Write Enable sur le port d'écriture, qui indique qu'une écriture est demandée, et un bit Read Enable sur le port de lecture qui indique qu'une lecture est demandée. La séparation du bit R/W en deux bits séparés pour chaque port s'expliquera dans les paragraphes suivants.

Les mémoires FIFO/LIFO sont souvent des mémoires synchrones, les implémentations asynchrones étant plus rares. Elles ont donc au moins une entrée pour le signal d'horloge. Point important, de nombreuses mémoires FIFO ont une fréquence pour la lecture qui est distincte de la fréquence pour l'écriture. En conséquence, elles reçoivent deux signaux d'horloge sur deux entrées séparées : un pour la lecture et un pour l'écriture. La présence de deux fréquences s'explique par le fait que les mémoires FIFO servent à interfacer deux composants qui ont des vitesses différentes, comme un disque dur et un processeur, un périphérique et un chipset de carte mère, etc. D'ailleurs, c'est ce qui explique que le bit R/W soit scindé en deux bits, un par port : les deux ports n'allant pas à la même vitesse, ils ne peuvent pas partager un même bit d'entrée sans que cela ne pose problème.

L'interface la plus classique pour une mémoire FIFO/LIFO est illustrée ci-dessous. On voit la présence d'un port d'écriture séparé du port de lecture, et la présence de deux signaux d'horloge distincts pour chaque port.

Interface des mémoires FIFO et LIFO

Les mémoires LIFO

Les mémoires LIFO peuvent se concevoir en utilisant une mémoire RAM, couplée à un registre. Les données y sont écrites à des adresses successives : on commence par remplir la RAM à l'adresse 0, puis on poursuit adresse après adresse, ce qui garantit que la donnée la plus récente soit au sommet de la pile. Tout ce qu'il y a à faire est de mémoriser l'adresse de la donnée la plus récente, dans un registre appelé le pointeur de pile. Cette adresse donne directement la position de la donnée au sommet de la pile, celle à lire lors d'une lecture. Le pointeur de pile est incrémenté à chaque écriture, pour pointer sur l'adresse de la nouvelle donnée. De même, il est décrémenté à chaque lecture, vu que les lectures sont destructrices (elles effacent la donnée lue).

La gestion des bits EMPTY et FULL est relativement simple : il suffit de comparer le pointeur de pile avec l'adresse minimale et maximale. Si le pointeur de pile et l'adresse maximale sont égaux, cela signifie que toutes les cases mémoires sont remplies : la mémoire est pleine. Quand le pointeur de pile pointe sur l'adresse minimale (0), la mémoire est vide.

Microarchitecture d'une mémoire LIFO

Il est aussi possible, bien que plus compliqué, de créer des LIFO à partir de registres. Pour cela, il suffit d'enchainer des registres les uns à la suite des autres. Les données peuvent passer d'un registre à son suivant, ou d'un registre aux précédents. Toutes les lectures ou écritures ont lieu dans le même registre, celui qui contient le sommet de la pile. Quand on écrit une donnée, celle-ci est placée dans ce registre de sommet de pile. Pour éviter de perdre des données, celles-ci sont déplacées de leur registre actuel au précédent. Toutes les données sont donc décalées d'un registres, avant l'écriture de la donnée au sommet de pile. Lors d'une lecture, le sommet de la pile est effacé. Pour cela, toutes les données sont avancées d'un registre, en passant du registre actuel au suivant. Les échanges de données entre registres sont gérés par divers circuits d’interfaçage, commandés par un gigantesque circuit combinatoire (le contrôleur mémoire).

Mémoire LIFO fabriquée à partir de registres

Les mémoires FIFO

Les FIFO de taille fixe

Les mémoires FIFO les plus simples ont une taille fixe, à savoir qu'elles contiennent toujours le même nombre de données mises en attente. Elles peuvent se fabriquer en enchainant des registres.

Register based parallel SAM

Il est aussi possible de fabriquer une FIFO en utilisant plusieurs registres à décalages. Chaque registre à décalage contient un bit pour chaque byte mis en attente. Le circuit en question est décrit dans le schéma ci-dessous.

FIFO de m bytes de n bits fabriquées avec des registres à décalages

Les FIFO de taille variable

La plupart des applications requièrent des FIFOs qui mémorisent un nombre variable de données. De telles FIFO de taille variable peuvent se fabriquer à partir d'une mémoire RAM en y ajoutant deux compteurs/registres et quelques circuits annexes. Les deux compteurs mémorisent l'adresse de la donnée la plus ancienne, ainsi que l'adresse de la plus récente, à savoir l'adresse à laquelle écrire la prochaine donnée à enqueue, et l'adresse de lecture pour la prochaine donnée à dequeue. Quand une donnée est retirée, l'adresse la plus récente est décrémentée, pour pointer sur la prochaine donnée. Quand une donnée est ajoutée, l'adresse la plus ancienne est incrémentée pour pointer sur la bonne donnée.

Mémoire FIFO construite avec une RAM.

Petit détail : quand on ajoute des instructions dans la mémoire, il se peut que l'on arrive au bout, à l'adresse maximale, même s'il reste de la place à cause des retraits de données. La prochaine entrée à être remplie sera celle numérotée 0, et on poursuivra ainsi de suite. Une telle situation est illustrée ci-dessous.

Débordement de FIFO.

La gestion des bits EMPTY et FULL se fait par comparaison des deux compteurs. S'ils sont égaux, c'est que la pile est soit vide, soit pleine. On peut faire la différence selon la dernière opération : la pile est vide si c'est une lecture et pleine si c'est une écriture. Une simple bascule suffit pour mémoriser le type de la dernière opération. Un simple circuit combinatoire contenant un comparateur permet alors de gérer les flags simplement.

FIFO pleine ou vide.

L'implémentation des deux compteurs

L'implémentation d'une mémoire FIFO demande donc d'utiliser deux compteurs. Vous vous attendez à ce que ces deux compteurs soient des compteurs binaires normaux, pas quelque chose d'exotique. Mais dans les faits, il est parfaitement possible d'utiliser des compteurs en anneau, ou des registres à décalage à rétroaction linéaire, ou des compteurs modulo comme compteurs dans une FIFO.

Premièrement, rien n'impose que les compteurs comptent de 1 en 1. Dans les faits, la séquence comptée peut être arbitraire : tout ce qui compte est qu'elle est la même entre les deux compteurs, pour vérifier si la RAM est pleine ou vide. Et cela amène à une optimisation assez simple : on peut utiliser des registres à décalage à rétroaction linéaire (LFSR ), au lieu de compteurs binaires usuels. Le résultat fonctionnera de la même façon vu de l'extérieur : on aura une FIFO qui fonctionne normalement, sans problèmes particuliers. Certes, la mémoire RAM ne sera pas remplie en partant de l'adresse 0, puis en remplissant la mémoire en sautant d'une adresse à sa voisine. A la place, les données seront ajoutées dans un ordre différent, mais qui ne change globalement pas grand chose. Les raisons de faire ainsi sont que les compteurs à base de LFSR est qu'ils sont plus simples à concevoir, moins gourmands en circuits et plus rapides. Le seul défaut est que les LFSR ne peuvent en effet pas contenir la valeur 0, ce qui fait qu'une adresse est gâchée. Mais sur les FIFOs assez grosses, le gain en vitesse et l'économie de circuits liée au compteur vaut la peine de gâcher une adresse.

Deuxièmement, rien n'impose que le compteur contienne une valeur codée en binaire. L'encodage de la valeur en binaire est cependant nécessaire pour adresser la mémoire RAM, mais il suffit d'ajouter un circuit pour traduire le contenu du compteur en binaire usuel pour cela. Sur les FIFO avec un port de lecture et un port d'écriture cadencés à des fréquences différentes, on utilise deux compteurs qui encodent des entiers en code Gray. La raison à cela est que les deux compteurs sont respectivement dans le port de lecture et dans le port d'écriture, et sont donc cadencés à deux fréquences différentes. Et la différence de fréquence entre compteurs peut causer des soucis pour calculer les bits EMPTY et FULL. Pour le dire autrement, la FIFO contient deux domaines d'horloge qui doivent communiquer entre eux pour calculer les bits EMPTY et FULL. C'est un cas de clock domain crossing tel que vu dans le chapitre sur le signal d'horloge, et la solution est alors celle évoquée dans ce chapitre : utiliser le code Gray.

Lors de l'incrémentation d'un compteur, tous les bits ne sont pas modifiés en même temps : les bits de poids faible sont typiquement modifiés avant les autres. Évidemment, à la fin de l'incrémentation, on obtient le résultat final, correct. Mais pendant le temps de calcul, le compteur peut se retrouver dans un état transitoire, où certains bits ont été modifiés mais pas les autres. Or, le comparateur qui s'occupe de déterminer les bits EMPTY et FULL est cadencé de manière à être au moins aussi rapide que le plus rapide des deux compteurs. Le comparateur est donc plus rapide que le compteur le plus lent et peut "voir" cet état transitoire. Il se peut que le comparateur compare le contenu du compteur le plus rapide avec l'état transitoire de l'autre, ce qui donnera un résultat temporairement faux. L'usage de compteurs en code Gray permet d'éviter ce problème : vu que seul un bit est modifié lors d'une incrémentation/décrémentation, les états transitoires n'existent tout simplement pas.