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.
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).
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).
L'interface d'une mémoire FIFO/LIFOModifier
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.
FIFO et LIFO peuvent se concevoir soit avec des registres à décalage, soit en utilisant une mémoire adressable, la dernière méthode étant de loin la plus courante.
Les mémoires LIFOModifier
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.
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).
Les mémoires FIFOModifier
Les mémoires FIFO 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.
Les FIFO de taille fixeModifier
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.
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.
Les FIFO de taille variableModifier
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 registres et quelques circuits annexes. Les deux registres 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.
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.
La gestion des bits EMPTY et FULL se fait par comparaison des deux registres. 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.
