Fonctionnement d'un ordinateur/Les mémoires FIFO et LIFO
Les mémoires séquentielles sont des mémoires spécialisées qui ne fonctionnent pas avec des adresses. Contrairement aux mémoires adressables, où l'on peut accéder à n'importe quelle donnée, les mémoires séquentielles ne permettent d’accéder aux données que dans un ordre bien précis. Les données sont stockées dans la mémoire dans un ordre bien précis, qui contraint l'accès en lecture ou en écriture. Il existe plusieurs types de mémoires séquentielles, qui se différencient par l'ordre dans lequel les données sont lues ou écrites, ou encore par leur caractère électronique.magnétique/optique.
Certaines mémoires magnétiques ou optiques sont des mémoires séquentielles. Pensez notamment aux CD-ROM et aux DVD/Blu-ray qui peuvent être vu comme des mémoires séquentielles, dans une certaine mesure. Pour les mémoires électroniques, on distingue ainsi les registres à décalage des mémoires LIFO et FIFO. Si on omet les registres à décalage, les mémoires séquentielles électroniques sont toutes soit des mémoires FIFO, soit des mémoires LIFO. Pour rappel, ces deux types de mémoire 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 ce qui va suivre, nous allons nous restreindre aux mémoires séquentielles qui sont volatiles, la totalité étant électroniques. En clair, nous allons uniquement voir les mémoires FIFO, LIFO et les registres à décalage.
Les mémoires séquentielles électroniques 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 dans cet optique, elle prend le nom de mémoire tampon. Si les mémoires LIFO sont rarement utilisées en tant que mémoire tampon, c'est le cas d'utilisation principal des mémoires FIFO, qui sont beaucoup plus courantes. On retrouve des mémoires FIFO 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.
L'utilisation principale des mémoires FIFO 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. 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 mémoires à base de registres à décalage
Les registres à décalage sont un premier type de mémoires séquentielles. Dans les registres à décalage vus dans le chapitre sur les circuits séquentiels, on ne peut lire ou écrire que bit par bit, ce qui leur vaut le nom de mémoires série. Vous pouvez vous reporter au chapitre sur les circuits séquentiels pour vous remémorer les circuits exacts de chaque type de registre à décalage. On a vu comment les fabriquer il y a quelques chapitres : il suffit d’enchaîner des bascules les unes après les autres. En clair, chaque sortie d'une bascule étant connectée à l'entrée de la suivante. Sans compter que toutes les entrées de commande sont reliées à l'entrée d'horloge/Enable. On obtient alors un registre à entrée et sortie série. Les autres registres à décalage sont des variations de ce registre où des sorties sont ajoutées.
Certains registres à décalage sont plus puissants et permettent de mémoriser plusieurs bytes. La transmission des bytes sur le bus peut se faire soit bit par bit, soit byte par byte. Mais nous allons laisser de côté le cas de la transmission byte par byte, qui correspond à un type de mémoire à part (une mémoire FIFO, que nous allons aborder plus bas). Quand la transmission se fait bit par bit, on obtient un registre à décalage de grande capacité, conçu à partir de registres à décalages plus petits. Précisément, on a un registre à décalage élémentaire par byte, ceux-ci étant enchaînés les uns à la suite des autres.
Les mémoires FIFO et LIFO
Les mémoires FIFO et LIFO sont des mémoires qui gardent leurs 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. Les mémoires FIFO renvoient la donnée la plus ancienne, celle écrite avant toutes les autres.
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).
Ces mémoires sont souvent des mémoires double ports, avec un port pour la lecture et un autre pour les écritures. Chaque port possède un bus de commande assez simple : il n'y a notamment pas de bus d'adresse, vu que ces mémoires ne sont pas adressables. Outre l'entrée d'horloge (pour les FIFO et LIFO synchrones) et les bits CS et OE, on trouve un bit qui sert à déclencher une écriture ou une lecture (Write Enable et Read Enable). La mémoire 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.
Ces deux types de mémoires peuvent se concevoir soit avec des registres à décalage, soit en utilisant une mémoire adressable. La dernière méthode est de loin la plus courante : presque toutes les mémoires FIFO ou LIFO sont conçues en complétant une RAM avec quelques circuits. La construction de FIFO à base de registres est très simple, bien plus que la construction de LIFO avec des registres. Par contre, c'est l'inverse pour la fabrication de FIFO et de LIFO avec une RAM : le principe est très simple pour les LIFO et plus complexe pour les FIFO.
Les mémoires LIFO
Les mémoires LIFO peuvent se concevoir en utilisant une mémoire RAM. 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. En effet, chaque nouvelle donnée doit juste être stockée à l'adresse suivante, celle qui suit la donnée plus récente. Le fait que les lectures soient destructrices ne change pas grand chose au principe.
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 à lire lors d'une lecture, ce qui permet de récupérer la donnée la plus récente, au sommet de la pile. Le pointeur de pile est incrémenté à chaque écriture, pour pointer sur l'adresse pour 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 FIFO
Les mémoires FIFO ont des entrées de plusieurs bits, de même que les sorties. Il faut noter que le cas où entrées et sorties sont séries (de 1 bit) se résume à un simple registre à décalage. On peut donc voir les FIFO comme une amélioration des registres à décalage à entrée et sortie série, pour lesquelles les entrées et sorties sont devenues parallèles. Les deux vont conserver leurs données dans l'ordre d'arrivée. Mais là où un registre à décalage transmet son contenu bit par bit, une FIFO transmet son contenu byte par byte.
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 (souvent des registres à décalage, mais pas forcément). Une FIFO dont le byte a plusieurs bits peut se construire comme un registre à décalage : les bascules sont remplacées par des registres complets : un registre par byte.
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 variable
La méthode précédente est cependant utile uniquement pour les mémoires qui doivent mémoriser un nombre de données fixe, qui ne change jamais. Mais 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 des circuits pour gérer les ajouts et retraits de données.
L'adresse de la donnée la plus ancienne, ainsi que l'adresse de la plus récente sont mémorisées dans deux registres. 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.