Fonctionnement d'un ordinateur/Les mémoires associatives

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

Les mémoires associatives servent à accélérer la recherche d'une donnée dans un ensemble de données. Leur fonctionnement est totalement opposé aux mémoires adressables normales : au lieu d'envoyer l'adresse pour accéder à la donnée, on envoie la donnée pour récupérer son adresse. Évidemment, il se peut que la donnée demandée ne soit pas présente en mémoire, qui doit préciser si elle a trouvé la donnée recherchée avec un signal dédié. Si la donnée est présente en plusieurs exemplaires en mémoire, la mémoire renvoie le premier exemplaire rencontré (celui dont l'adresse est la plus petite). Certaines mémoires renvoient aussi les autres exemplaires, qui sont envoyées une par une au processeur.

Mémoires associatives[modifier | modifier le wikicode]

Le plan mémoire d'une mémoire associative a deux fonctions : mémoriser des mots mémoires et vérifier la présence d'une donnée dans chaque case mémoire (effectuer une comparaison, donc). Dans une mémoire associative, la donnée à rechercher dans la mémoire est envoyée à toutes les cases mémoires simultanément et toutes les comparaisons sont effectuées en parallèle.

Plan mémoire d'une mémoire associative.

Une fois la case mémoire qui contient la donnée identifiée, il faut déduire son adresse. Si vous regardez bien, le problème qui est posé est l'exact inverse de celui qu'on trouve dans une mémoire adressable : on n'a pas l'adresse, mais les signaux sont là. La traduction va donc devoir se faire par un circuit assez semblable au décodeur : l'encodeur. Dans le cas où la mémoire doit gérer le cas où plusieurs mots contiennent la donnée demandée, la solution la plus simple est d'en sélectionner un seul, généralement celui qui a l'adresse la plus petite (ou la plus grande). Pour cela, l'encodeur doit subir quelques modifications et devenir un encodeur à priorité.

Intérieur d'une mémoire associative.

Cellules NOR[modifier | modifier le wikicode]

Pour limiter le nombre de portes logiques utilisées pour le comparateur, les circuits de comparaison sont fusionnés avec les cellules mémoires. La première possibilité d'intégration est celle-ci :

Case mémoire associative à base de NOR.

Pour comprendre son fonctionnement, il suffit de se rappeler que les transistors se ferment quand on place un 1 sur la grille. De plus, le signal trouvé est mis à 1 par un stratagème technique si les transistors du circuit ne le connectent pas à la masse. Ce qui donne ceci :

Fonctionnement d'une mémoire associative NOR.

Les signaux trouvé/non-trouvé des différents bits d'un seul mot sont alors reliés ensemble comme ci-dessous. Le transistor du dessus sert à mettre notre signal trouvé/non-trouvé de notre mot mémoire à 1. Il s'ouvre durant un moment afin de précharger le fil qui transportera le signal. Le signal sera relié au zéro volt si une seule case mémoire a une sortie à zéro. Dans le cas contraire, le fil contiendra encore une tension correspondant à un 1 sur la sortie.

Gestion de la précharge des cases mémoires associatives à base de NOR.

Cellule NAND[modifier | modifier le wikicode]

Une autre manière consiste à relier les cellules d'un mot mémoire ensemble comme indiqué dans le schéma ci-dessous. Chaque cellule mémoire va avoir un signal trouvé/non-trouvé inversé : il vaut 0 quand le bit de la cellule et le bit du bus de données sont identiques, et vaut 1 sinon. Si toutes les cellules sont identiques aux bits correspondants du bus de données, le singal final sera mis à la masse (à zéro). Et inversement, il suffit qu'une seule cellule ouvre son transistor pour que le signal soit relié à la tension d'alimentation. En somme, le signal obtenu vaut zéro si jamais la donnée et le contenu du mot sont identiques, et 1 sinon.

Gestion de la précharge des cases mémoires associatives à base de NAND.

Il est alors possible de câbler la cellule mémoire d'une autre façon, indiquée sur le schéma ci-dessous :

Case mémoire associative à base de NAND.

Architectures associatives[modifier | modifier le wikicode]

Il est possible d'utiliser une mémoire associative en supplément d'une RAM normale, mais aussi comme mémoire principale sur une architecture Harvard. Toutefois, ces architectures ne sont pas les seules à utiliser des mémoires associatives. Il est maintenant temps de voir les processeurs associatifs, des sortes de mémoires associatives sous stéroïdes. Sur une mémoire associative, on peut comparer la donnée passée en entrée avec chaque mot mémoire. Avec un processeur associatif, les mots sélectionnés par une comparaison vont rester sélectionnés durant un ou plusieurs cycles. Pendant ce temps, on pourra demander à notre processeur d'effectuer des calculs ou des branchements dessus. En gros, on peut effectuer des opérations identiques sur un grand nombre de mots en parallèle. Encore mieux : il est possible pour notre mémoire de sélectionner les bits à prendre en compte dans une comparaison, et de laisser tranquille les autres. Pour cela, il suffit d'envoyer à la mémoire un masque, qui permettra de savoir quels bits sont à prendre en compte dans chaque donnée : si son i-éme bit est à 1, le bit correspondant de la donnée est à prendre en compte dans notre comparaison. Ce masque est envoyé à la mémoire via un second bus, séparé du bus de données.

On peut signaler qu'il existe plusieurs types de processeurs associatifs. Le premier type correspond à ce qu'on appelle les processeurs totalement parallèles, où l'ALU est capable de traiter tous les bits du mot d'un seul coup.

Case mémoire d'un processeur associatif totalement parallèle.

Pour économiser des circuits, on peut castrer l'ALU qui ne peut plus traiter qu'un seul bit à la fois : on rentre alors dans la catégorie des architectures dites sérielles. Pour pouvoir traiter un bit à la fois, le mot mémoire est implémenté avec un registre à décalage.

Case mémoire d'un processeur associatif bit serial avec une bascule.

Pour donner un exemple d'opération sur une architecture bit-sérielle, je vais prendre l'exemple d'un test d'égalité entre un Byte qui contient la valeur 1100, et une donnée qui vaut 0100. Pour effectuer ce test, notre processeur va devoir comparer chaque bit un par un en utilisant une porte NXOR, tout en prenant en compte le bit indiquant le résultat des comparaisons précédentes avec une porte ET. Le résultat de la comparaison est disponible dans notre bascule de 1 bit une fois la comparaison terminée. Notre bascule sera donc reliée à la sortie sur laquelle on envoie le signal Trouvé / Non-trouvé. Mais cette bascule peut aussi servir dans d'autres opérations. Par exemple, si notre processeur implémente des opérations d'addition, notre addition peut se faire bit par bit. Notre bascule sert alors à stocker la retenue de l'addition des deux bits précédents.

Illustration d'une opération sur un processeur word-serial.