Fonctionnement d'un ordinateur/Les mémoires séquentielles

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

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. Pour les mémoires électroniques, on distingue ainsi les registres à décalage des mémoires LIFO et FIFO. Cependant, certaines mémoires magnétiques ou optiques sont des mémoires séquentielles. Pensez notamment aux CD-ROM et aux DVD/Blue-Ray qui peuvent être vu comme des mémoires séquentielles, dans une certaine mesure. 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.

Mémoire à accès séquentiel

Mémoires à base de registres à décalage[modifier | modifier le wikicode]

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'enchainer 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éees 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.

Shift registers based serial SAM

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 coté 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 enchainés les uns à la suite des autres.

Serial SAM layout

Mémoires FIFO et LIFO[modifier | modifier le wikicode]

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.

Interface des mémoires FIFO et LIFO

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.

Mémoires LIFO[modifier | modifier le wikicode]

Les mémoires LIFO sont les plus simples à concevoir en utilisant une mémoire RAM. Celles-ci sont fabriquées à partir d'une mémoire adressable, de préférence une mémoire RAM. Dans cette RAM, les données sont écrites à des adresses successives : on commence par remplir la RAM à l'adresse 0, puis on poursuit adresse après adresse. 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 la position de la donnée la plus récente. Mémoriser la position de la donnée la plus récente demande un simple registre, appelé pointeur de pile, qui mémorise l'adresse de la donnée la plus récente. 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 (celle au sommet de la pile. De plus, la position de la donnée la plus récente permet aussi de stocker les données dans l'ordre. En effet, chaque nouvelle donnée doit juste être stockée à l'adresse suivante, celle qui suit la donnée plus récente. 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.

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'interfacage, commandés par un gigantesque circuit combinatoire (le contrôleur mémoire).

Mémoire LIFO fabriquée à partir de registres

Mémoires FIFO[modifier | modifier le wikicode]

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.

Parallel SAM diagram

FIFO de taille fixe[modifier | modifier le wikicode]

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.

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

FIFO de taille variable[modifier | modifier le wikicode]

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. Or, cette situation est rarement rencontrée dans le monde réel de la réalité véritable. 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. La microarchitecture des mémoires FIFO est semblable à celle des mémoires LIFO, bien qu'elle soit légèrement plus complexe. On y retrouve notamment un registre équivalent au pointeur de pile, mais celui-ci n'est pas tout seul. 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.

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.

Débordement de FIFO.

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.