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. Il existe quelques processeurs qui remplacent leurs registres par une mémoire LIFO intégrée au processeur, mais ils ont tous disparus depuis des décennies. Des mémoires LIFO sont intégrées dans les processeurs modernes, au niveau des unités de prédiction de branchement, 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. 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. Elles sont 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.

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. Si le disque dur est déjà en train d'exécuter une commande, il doit mettre en attente les commandes/données réceptionnées pendant ce temps. Et il doit les conserver dans l'ordre d'arrivée, 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.

La mémoire FIFO/LIFO indique quand elle 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. De ce fait, il n'y a pas de bit R/W, mais 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.

Les mémoires FIFO/LIFO sont souvent des mémoires synchrones, les implémentations asynchrones étant plus rares. 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 séparés : 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.

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 séparés. Pour cela, il suffit d'enchainer des registres les uns à la suite des autres. Un registre est le sommet de la pile, toutes les lectures/écritures se font dedans. Lors d'une écriture/insertion, toutes les données sont donc décalées d'un registre, avant l'écriture de la donnée au sommet de pile. Idem lors d'une lecture : le sommet de la pile est lu, puis toutes les données sont déplacées d'un registre, dans le sens inverse de l'écriture. Les échanges de données entre registres sont commandés par un gigantesque circuit combinatoire (le contrôleur mémoire).

Mémoire LIFO fabriquée à partir de registres

Les mémoires FIFO

Il existe deux types de mémoire FIFO : de taille fixe et de taille variable. 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 sont cependant peu utiles. Les FIFO les plus intéressantes peuvent mémoriser un nombre variable de données en attente, qui varie au cours du temps. Il peut y avoir entre 0 et N données en attente, N étant un nombre maximal.

Les FIFO de taille fixe

Les mémoires FIFO de taille fixe 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

Les FIFO de taille variable peuvent se fabriquer à partir d'une mémoire RAM en y ajoutant deux compteurs 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. 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.

Vous vous attendez à ce que ces deux compteurs soient des compteurs binaires normaux, mais il est parfaitement possible d'utiliser des compteurs en anneau, des registres à décalage à rétroaction linéaire, ou des compteurs modulo.

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. Ils sont donc cadencés à deux fréquences différentes, mais ils 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. Faisons quelques rappels.

Lors de l'incrémentation d'un compteur binaire, tous les bits ne sont pas modifiés en même temps : les bits de poids faible sont typiquement modifiés avant les autres. Le compteur passe donc dans plusieurs états transitoires où seule une partie des bits a été incrémenté. Le comparateur qui détermine les bits EMPTY et FULL peut "voir" cet état transitoire et l'utiliser pour calculer un résultat, ce qui donnera un résultat temporairement faux. L'usage de compteurs en code Gray résout ce problème : un seul bit est modifié lors d'une incrémentation/décrémentation, les états transitoires n'existent pas.

Il est aussi possible d'utiliser des registres à décalage à rétroaction linéaire (LFSR), au lieu de compteurs binaires. Le résultat fonctionne de la même façon vu de l'extérieur. 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. À 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.