Fonctionnement d'un ordinateur/Les mémoires associatives

Les mémoires associatives ont un fonctionnement 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. On les appelle aussi des mémoires adressables par contenu, ou encore Content-adressed Memory (CAM) en anglais. Dans ce qui suit, nous utiliserons parfois l'abréviation CAM pour désigner les mémoires associatives.

Les mémoires associatives semblent assez bizarres au premier abord. Quand on y réfléchit, à quoi cela peut-il bien servir de récupérer l'adresse d'une donnée ? La réponse est que les mémoires associatives ont été conçues pour répondre à une problématique assez connue des programmeurs : la recherche d'une donnée dans un ensemble. Généralement, les données manipulées par un programme sont regroupées dans des structures de données organisées : tableaux, listes, graphes, sets, tables de hachage, arbres, etc. Et il arrive fréquemment que l'on recherche une donnée bien précise dedans. Certaines structures de données sont conçues pour accélérer cette recherche, ce qui donne des gains de performance bienvenus, mais au prix d'une complexité de programmation non-négligeable. Les mémoires associatives sont une solution matérielle alternative bien plus rapide. Le processeur envoie la donnée recherchée à la mémoire associative, et celle-ci répond avec son adresse en quelques cycles d'horloge de la mémoire.

Les mémoires associatives dépassent rarement quelques mébioctets et nous n'avons pas encore de mémoire associative capable de mémoriser un gibioctet de mémoire. Leur faible capacité fait qu'elles sont utilisées dans certaines applications bien précises, où les structures de données sont petites. La contrainte de la taille des données fait que ces situations sont très rares. Un cas d'utilisation basique est celui des routeurs, des équipements réseaux qui servent d'intermédiaire de transmission. Chaque routeur contient une table CAM et une table de routage, qui sont souvent implémentées avec des mémoires associatives. Nous en reparlerons dans le chapitre sur le matériel réseau. Elles sont normalement utilisées en supplément d'une mémoire RAM principale. Il arrive plus rarement que la mémoire associative soit utilisée comme mémoire principale. Mais cette situation est assez rare car les mémoires associatives ont souvent une faible capacité.

L'interface des mémoires associatives

Une mémoire associative prend en entrée une donnée et renvoie son adresse. Le bus de donnée est donc accessible en lecture/écriture, comme sur une mémoire normale. Par contre, son bus d'adresse est accessible en lecture et en écriture, c'est une entrée/sortie. L'usage du bus d'adresse comme entrée est similaire à celui d'une mémoire normale : il faut bien écrire des données dans la mémoire associative, ce qui demande de l'adresser comme une mémoire normale. Par contre, le fonctionnement normal de la mémoire associative, à savoir récupérer l'adresse d'une donnée, demande d'utiliser le bus d'adresse comme une sortie, de lire l'adresse dessus.

Principe de fonctionnement d'une mémoire associative

Lorsque l'on recherche une donnée dans une mémoire CAM, il se peut que la donnée demandée ne soit pas présente en mémoire. La mémoire CAM doit donc préciser si elle a trouvé la donnée recherchée avec un signal dédié. Un autre problème survient quand la donnée est présente en plusieurs exemplaires en mémoire : la mémoire renvoie alors le premier exemplaire rencontré (celui dont l'adresse est la plus petite). D'autres mémoires renvoient aussi les autres exemplaires, qui sont envoyées une par une au processeur.

Signal trouvé sur une mémoire associative

Notons que tout ce qui a été dit dans les deux paragraphes précédent ne vaut que pour le port de lecture de la mémoire. Les mémoires associatives ont généralement un autre port, qui est un port d'écriture, qui fonctionne comme pour une mémoire normale. Après tout, les donnée présentes dans la mémoire associatives viennent bien de quelque part. Elles sont écrites dans la mémoire associative par le processeur, en passant par ce port d'écriture. Sur ce port, on envoie l'adresse et la donnée à écrire, en même temps ou l'une après l'autre, comme pour une mémoire RAM. Le port d'écriture est géré comme pour une mémoire RAM : la mémoire associative contient un décodeur d'adresse, connecté aux cellules mémoires, et tout ce qu'il faut pour fabriquer une mémoire RAM normale, excepté que le port de lecture est retiré. Cela fait partie des raisons pour lesquelles les mémoires associatives sont plus chères et ont une capacité moindre : elles contiennent plus de circuits à capacité égale. On doit ajouter les circuits qui rendent la mémoire associative, en plus des circuits d'une RAM quasi-normale pour le port d'écriture.

La microarchitecture des mémoires associatives

Si on omet tout ce qui a rapport au port d'écriture, l'intérieur d'une mémoire associative est organisée autour de deux fonctions : vérifier la présence d'une donnée dans chaque case mémoire (effectuer une comparaison, donc), et déterminer l'adresse d'une case mémoire sélectionnée.

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 donnée est présente en plusieurs exemplaires dans la mémoire, 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.

Les cellules CAM des mémoires associatives

Avec une mémoire associative normale, la comparaison réalisée par chaque case mémoire est une comparaison d'égalité stricte : on vérifie que la donnée en entrée correspond exactement à la donnée dans la case mémoire. Cela demande de comparer chaque bit d'entrée avec le bit correspondant mémorisé, avant de combiner les résultats de ces comparaisons. Pour faciliter la compréhension, nous allons considérer que la comparaison est intégrée directement dans la cellule mémoire. En clair, chaque cellule d'une CAM compare le bit d'entrée avec son contenu et fournit un résultat de 1 bit : il vaut 1 si les deux sont identiques, 0 sinon. L'interface d'une cellule mémoire associative contient donc deux entrées et une sortie : une sortie pour le résultat de la comparaison, une entrée pour le bit d'entrée, et une entrée write enable qui dit s'il faut faire la comparaison avec le bit d'entrée ou écrire le bit d'entrée dans la cellule. Une cellule mémoire de ce genre sera appelée une cellule CAM dans ce qui suit.

Interface d'une cellule mémoire associative.

Les cellules CAM avec une porte NXOR/XOR

La comparaison de deux bits est un problème des plus simples. Rappelons que nous avions vu dans le chapitre sur les comparateurs qu'un comparateur qui vérifie l"égalité de deux bits n'est autre qu'une porte NXOR. Ce faisant, dans leur implémentation la plus naïve, chaque cellule CAM incorpore une porte NXOR pour comparer le bit d'entrée avec le bit mémorisé. Une cellule CAM ressemble donc à ceci :

Cellule mémoire associative naïve.

Pour limiter le nombre de portes logiques utilisées pour le comparateur, les circuits de comparaison sont fusionnés avec les cellules mémoires. Concrètement, la porte NXOR est fusionnée avec la cellule mémoire, en bidouillant le circuit directement au niveau des transistors. Et cela peut se faire de deux manières, la première donnant les cellules CAM de type NOR et la seconde les cellules mémoire de type NAND. Les cellules CAM de type NOR sont de loin les plus performantes mais consomment beaucoup d'énergie, alors que c'est l'inverse pour les cellules CAM de type NAND.

Précisons que cette distinction entre cellules mémoire de type NOR et NAND n'a rien à voir avec les mémoires FLASH de type NOR et NAND.

Comparateur séparé à la case mémoire

Comparateur intégré à la case mémoire

Les cellules CAM de type NAND

Avec les cellules CAM de type NAND, le câblage est le suivant :

Cellule CAM de type NAND.

Voici comment elle fonctionne :

Cellule CAM de type NAND - fonctionnement

Les cellules CAM de type NOR

Une cellule CAM de type NOR ressemble à ceci :

Cellule CAM de type 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 cellule CAM de type NOR.

Les performances des cellules de mémoire CAM

Comme vous pouvez le constater plus haut, les cellules CAM contiennent beaucoup de transistors, surtout quand on les compare avec des cellules de SRAM, voire de DRAM. Une cellule de CAM NOR contient 4 transistors, plus une cellule de SRAM (la bascule D), ce qui fait 10 transistors au total. Une cellule de CAM NAND en contient 2, plus la bascule D/cellule de SRAM, ce qui fait 8 au total. Quelques optimisations diverses permettent d'économiser 1 ou 2 transistors, mais guère plus, ce qui donne entre 6 et 9 transistors dans le meilleur des cas.

Cellule CAM de type NOR.

En comparaison, une cellule de mémoire SRAM contient 6 transistors en tout, pour une cellule double port, transistor de sélection inclut. Cela ne fait que 1 à 3 transistors de plus, mais cela réduit la densité des mémoires CAM par rapport aux mémoires SRAM d'un facteur qui va de 10 à 50%. Les mémoires CAM ont donc une capacité généralement assez faible, plus faible que celle des SRAM qui n'est déjà pas terrible. Ne faisons même pas la comparaison avec les mémoires DRAM, qui elles ont une densité près de 10 fois meilleures dans le pire des cas. Autant dire que les mémoires CAM sont chères et que l'on ne peut pas en mettre beaucoup dans un ordinateur. C'est sans doute la raison pour laquelle leur utilisation est des plus réduites, limitée à quelques routeurs/switchs et quelques autres circuits assez rares.

La combinaison des résultats des comparaisons pour un mot mémoire

Les cellules CAM comparent le bit stocké avec le bit d'entrée, ce qui donne un résultat de comparaison pour un bit. Les résultats des comparaisons sont alors combinés ensemble, pour donner un signal "trouve/non-trouvé" qui indique si le mot mémoire correspond au mot envoyé en entrée. Dans le cas le plus simple, on utilise une porte ET à plusieurs entrées pour combiner les résultats. Mais il s'agit là d'un circuit assez naïf et diverses techniques permettent de combiner les résultats comparaisons de 1 bit sans elle. Cela permet d'économiser des circuits, mais aussi de gagner en performances et/ou en consommation d'énergie. Il existe deux grandes méthodes pour cela.

Avec la première méthode, le signal en question est déterminé avec le circuit donné ci-dessous. Le transistor du dessus 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 cellule CAM a une sortie à zéro. Dans le cas contraire, le fil aura été préchargé avec une tension correspondant à un 1 sur la sortie et y restera durant tout le temps nécessaires : on aura un 1 en sortie.

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

La seconde méthode relie les cellules CAM d'un mot mémoire ensemble comme indiqué dans le schéma ci-dessous. Chaque cellule mémoire a un résultat de comparaison inversé : il vaut 0 quand le bit de la cellule CAM est identique au bit d'entrée, et vaut 1 sinon. Si toutes les cellules CAM correspondent aux bits d'entrée, le signal final sera mis à la masse (à zéro). Et inversement, il suffit qu'une seule cellule CAM 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 d'entrée et le mot mémoire sont identiques, et 1 sinon.

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

En théorie, les deux méthodes peuvent s'utiliser indifféremment avec les cellules NOR ou NAND, mais elles ont des avantages et inconvénients similaires à celles des cellules NOR et NAND. La première méthode a de bonnes performances et une consommation d'énergie importante, comme les cellules NOR, ce qui fait qu'elle est utilisée avec elles. L'autre a une bonne consommation d'énergie mais de mauvaises performances, au même titre que les cellules NAND, ce qui fait qu'elle est utilisée avec elles. Il existe cependant des CAM hybrides, pour lesquelles on a des cellules NOR avec un agencement NAND, ou l'inverse.

Les mémoires associatives avec opérations de masquage intégrées

Les mémoires associatives vues précédemment sont les plus simples possibles, dans le sens où elles ne font que vérifier l'égalité de la donnée d'entrée pour chaque case mémoire. Mais d'autres mémoires associatives sont plus complexes et permettent d'effectuer facilement des opérations de masquage facilement. Nous avons vu les opérations de masquage dans le chapitre sur les opérations bit à bit, mais un petit rappel ne fait pas de mal. Le masquage permet d'ignorer certains bits lors de la comparaison, de sélectionner seulement certains bits sur lesquels la comparaison sera effectuée. L'utilité du masquage sur les mémoires associatives n'est pas évidente, mais on peut cependant dire qu'il est très utilisé sur les routeurs, notamment pour leur table de routage.

Pour implémenter le masquage, il existe trois méthodes distinctes : celle des CAM avec un masque fournit en entrée, les CAM avec masquage intégré, et les CAM ternaires. Les deux méthodes se ressemblent beaucoup, mais il y a quelques différences qui permettent de séparer les deux types.

Les CAM avec masquage fournit en entrée

Sur les CAM avec masquage fournit en entrée, les bits sélectionnés pour la comparaison sont précisés par un masque, un nombre de la même taille que les cases mémoires. Le masque est envoyé à la mémoire via un second bus, séparé du bus de données. Le masque est alors appliqué à toutes les cases mémoires. Notons que si le contenu d'une cellule n'est pas à prendre en compte, alors le résultat de l'application du masque doit être un 1 : sans cela, la porte ET à plusieurs entrées (ou son remplacement) ne donnerait pas le bon résultat. Pour implémenter ce comportement, il suffit de rajouter un circuit qui prend en entrée : le bit du masque et le résultat de la comparaison. On peut établir la table de vérité du circuit en question et appliquer les méthodes vues dans le chapitre sur les circuits combinatoires, mais le résultat sera dépend du format du masque. En effet, deux méthodes sont possibles pour gérer un masque.

• Avec la première, les bits à ignorer sont indiqués par un 0 alors que les bits sélectionnés sont indiqués par des 1.
• Avec la seconde méthode, c'est l'inverse : les bits à ignorer sont indiqués par des 1 et les autres par des 0.

La seconde méthode donne un circuit légèrement plus simple, où l'application du masque demande de faire un OU logique entre le bit du masque et la cellule mémoire associée. Il suffit donc de rajouter une porte OU à chaque cellule mémoire, entre la bascule D et la porte NXOR. Une autre manière de voir les choses est de rajouter un circuit de masquage à chaque case mémoire, qui s'intercale entre les cellules mémoires et le circuit qui combine les résultats de comparaison de 1 bit. Ce circuit est constitué d'une couche de portes OU, ou de tout autre circuit compatible avec le format du masque utilisé.

Cellule CAM avec masque

Les CAM avec masquage intégré

Sur d'autres mémoires associatives plus complexes, chaque case mémoire mémorise son propre masque attitré. Il n'y a alors pas de masque envoyé à toutes les cases mémoires en même temps, mais un masque par case mémoire. L'interface de la mémoire CAM change alors quelque peu, car il faut pouvoir indiquer si l'on souhaite écrire soit une donnée, soit un masque dans une case mémoire. Cette méthode peut s'implémenter de deux manière équivalentes. La première est que chaque case mémoire contient en réalité deux registres, deux cases mémoires : un pour la case mémoire proprement dit, et un autre pour le masque. Ces deux registres sont connectés au circuit de masquage, puis au circuit qui combine les résultats de comparaison de 1 bit. Une autre manière équivalente demande d'utiliser deux bits de SRAM par cellules mémoires : un qui code la valeur 0 ou 1, et un pour le bit du masque associé. Le bit qui indique si la valeur stockée est X est prioritaire sur l'autre. En clair, chaque case mémoire stocke son propre masque.

Cellule CAM avec masque intégré à la cellule mémoire

Il est cependant possible d'optimiser le tout pour réduire les circuits de comparaison, en travaillant directement au niveau des transistors. On peut notamment s'inspirer des méthodes vues pour les cellules CAM normales, avec une organisation de type NAND ou NOR. Une telle cellule demande 2 bascules SRAM, ce qui fait 2 × 6 = 12 transistors. Il faut aussi ajouter les circuits de comparaison, ce qui rajoute 4 à 6 transistors. Un défaut de cette approche est qu'elle augmente la taille de la cellule mémoire, ce qui réduit donc la densité de la mémoire. La capacité de la mémoire CAM s'en ressent, car les cellules CAM sont très grosses et prennent beaucoup de transistors. Les cellules CAM de ce type les plus optimisées utilisent entre 16 et 20 transistors par cellules, ce qui est énorme comparé aux 6 transistors d'une cellule SRAM, déjà assez imposante. Autant dire que les mémoires de ce type sont des plus rares.

Cellule CAM d'une CAM avec masque intégré dans la cellule mémoire.

Les CAM ternaires

Une alternative aux opérations de masquage proprement dit est d'utiliser des mémoires associatives ternaires. Pour bien les comprendre, il faut les comparer avec les mémoires associatives normales. Avec une mémoire associative normale, chaque cellule mémoire stocke un bit, qui vaut 0 et 1, mais ne peut pas prendre d'autres valeurs. Avec une mémoire associative ternaire, chaque cellule mémoire stocke non pas un bit, mais un trit, c’est-à-dire une valeur qui peut prendre trois valeurs : 0, 1 ou une troisième valeur nommée X. Sur les mémoires associatives ternaires, cette valeur est utilisée pour signaler que l'on se moque de la valeur réelle du trit, ce qui lui vaut le nom de valeur "don't care". Et c'est cette valeur X qui permet de faciliter l'implémentation des opérations de masquage. Lorsque l'on compare un bit avec cette valeur X, le résultat sera toujours 1 (vrai). Par exemple, si on compare la valeur 0101 0010 1010 avec la valeur 01XX XXX0 1010, le résultat sera vrai : les deux sont considérés comme identiques dans la comparaison. Pareil si on compare la valeur 0100 0000 1010 avec la valeur 01XX XXX0 1010 ou 0111 1110 1010 avec la valeur 01XX XXX0 1010.

Formellement, ces mémoires associatives ternaires ne sont pas différentes des mémoires associatives avec un masque intégré dans chaque case mémoire. La différence est au niveau de l'interface : l'interface d'une CAM ternaire est plus complexe et ne fait pas la distinction entre donnée stockée et masque. À l'opposé, les CAM avec masque intégré permettent de spécifier séparément le masque de la donnée pour chaque case mémoire. Mais au niveau du fonctionnement interne, les deux types de CAM se ressemblent beaucoup. D'ailleurs, les CAM ternaires sont souvent implémentées par une CAM avec masque intégré, avec un bit de masque pour chaque cellule mémoire, à laquelle on rajoute quelques circuits annexes pour l'interface. Mais il existe des mémoires associatives ternaires pour lesquelles le stockage du bit de donnée et du masque se font sans utiliser deux cellules mémoires. Elles sont plus rares, plus chères, mais elles existent.

Les mémoires associatives bit-sérielles

Les circuits comparateurs des mémoires associatives sont gourmands et utilisent beaucoup de circuits. Les optimisations vues plus haut limitent quelque peu la casse, sans trop nuire aux performances, mais elles ne sont pas une panacée. Mais il existe une solution qui permet de drastiquement économiser sur les circuits de comparaison, qu détriment des performances. L'idée est que la comparaison entre donnée d'entrée et case mémoire se fasse un bit après l'autre, plutôt que tous les bits en même temps. Pour prendre un exemple, prenons une mémoire dont les cases mémoires font 16 bits. Les techniques précédentes comparaient les 16 bits de la case mémoire avec les 16 bits de l'entrée en même temps, en parallèle, avant de combiner les comparaisons pour obtenir un résultat. L'optimisation est de faire les 16 comparaisons bit à bit non pas en même temps, mais l'une après l'autre, et de combiner les résultats autrement.

Avec cette méthode, la comparaison bit à bit est effectuée par un comparateur d'égalité sériel, un circuit que nous avions vu dans le chapitre sur les comparateurs, qui vérifie l'égalité de deux nombres bits par bit. Rappelons que ce circuit ne fait pas que comparer deux bits : il mémorise le résultat des comparaisons précédentes et le combine avec la comparaison en cours. Il fait donc à la fois la comparaison bit à bit et la combinaison des résultats. Pour cela, il intègre une bascule qui mémorise le résultat de la comparaison des bits précédents. L'avantage est que les circuits de comparaison sont beaucoup plus simples. Le comparateur parallèle utilise beaucoup de transistors, alors qu'un comparateur sériel utilise au maximum une bascule et deux portes logiques, moins s'il est optimisé. Au final, l'économie en portes logiques et en consommation électrique est drastique et peut être utilisée pour augmenter la capacité de la mémoire associative. Par contre, le traitement bit par bit fait qu'on met plus de temps pour faire la comparaison, ce qui réduit les performances.

Un tel traitement des bits en série s'oppose à une comparaison des bits en parallèle des mémoires précédentes. Ce qui fait que les mémoires de ce type sont appelées des mémoires bit-sérielles. L'idée est simple, mais il reste à l'implémenter. Pour cela, il existe deux grandes solutions, la première utilisant des registres à décalage, l'autre avec un système qui balaye les colonnes de la mémoire une par une.

Les mémoires bit-sérielles basées sur des registres à décalage

L'implémentation la plus simple à comprendre est celle qui utilise des registres à décalage, mais elle a le défaut d'utiliser beaucoup de circuits, comparé aux alternatives. Avec cette implémentation, chaque byte, chaque case mémoire, est stockée dans un registre à décalage, et il en est de même pour le mot d'entrée à comparer. Ainsi, à chaque cycle, les deux bits à comparer sortent de ces deux registres à décalage. La comparaison bit à bit est effectuée par un comparateur d'égalité sériel. Le bit qui sort de la case mémoire est envoyé au comparateur sériel, mais il est aussi réinjecté dans le registre à décalage, afin que la case mémoire ne perde pas son contenu. L'idée est que le contenu de la case mémoire fasse une boucle avant de revenir à son état initial : on applique une opération de rotation dessus.

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

Pour donner un exemple, je vais prendre l'exemple d'un Byte qui contient la valeur 1100, et une donnée d'entrée qui vaut 0100. À chaque cycle d’horloge, le processeur associatif compare un bit de l'entrée avec le bit de même poids dans la case mémoire. La comparaison est le fait d'un circuit comparateur sériel (vu dans le chapitre sur les circuits comparateurs). Le résultat de la comparaison est disponible dans la bascule de 1 bit une fois la comparaison terminée. La bascule est reliée à la sortie sur laquelle on envoie le signal Trouvé / Non-trouvé.

Illustration d'une opération sur un processeur associatif sériel.

Les mémoires bit-sérielles basées sur un système de sélection des colonnes

L’implémentation précédente a quelques défauts, liés à l'usage de registres à décalage. Le fait de devoir déplacer des bits d'une bascule à l'autre n'est pas anodin : cela n'est pas immédiat, sans compter que ça consomme du courant. Autant ce n'est pas du tout un problème d'utiliser un registre à décalage pour le mot d'entrée, autant en utiliser un par case mémoire est déjà plus problématique. Aussi, d'autres mémoires associatives ont corrigé ce problème avec un subterfuge assez intéressant, inspiré du fonctionnement des mémoires RAM.

Vous vous rappelez que les mémoires RAM les plus simples sont organisées en lignes et en colonnes : chaque ligne est une case mémoire, un bit se trouve à l'intersection d'une ligne et d'une colonne. Les mémoires CAM ne sont pas différentes de ce point de vue. L'idée est de n'activer qu'une seule colonne à la fois, du moins pour ce qui est des comparaisons. L'activation de la colonne connecte toutes les cellules CAM de la colonne au comparateur sériel, mais déconnecte les autres. En conséquence, les bits situés sur une même colonne sont envoyés au comparateur en même temps, alors que les autres sont ignorés. Un système de balayage des colonnes active chaque colonne l'une après l'autre, il passe d'une colonne à l'autre de manière cyclique. Ce faisant, le résultat est le même qu'avec l'implémentation avec des registres à décalage, mais sans avoir à déplacer les bits. La consommation d'énergie est donc réduite, sans compter que l'implémentation est légèrement plus rapide.

Les mémoires associatives word-sérielles

les mémoires associatives word-sérielles sont des mémoires associatives qui sont conçues totalement différemment des précédentes. Elles sont conçues à partir d'une mémoire RAM, à laquelle on rajoute des circuits pour simuler une mémoire réellement associative. Là où les mémoires réellement associatives comparent la donnée d'entrée avec toutes les cases mémoires en parallèle, les mémoires associatives word-sérielles comparent avec chaque case mémoire une par une. Les circuits qui entourent la mémoire balayent la mémoire, en partant de l'adresse la plus basse, puis en passant d'une adresse à l'autre. Les circuits en question sont composés d'un comparateur, d'un compteur, et de quelques circuits annexes. Le compteur calcule les adresses à lire à chaque cycle d'horloge, la mémoire RAM est adressée par ce compteur, le comparateur récupère la donnée lue et effectue la comparaison. Dès qu'un match est trouvé, la mémoire associative renvoie le contenu du compteur, qui contient l'adresse du byte adéquat.

Mémoire associative word-sérielle

Les avantages et inconvénients des mémoires associatives word-sérielles

Il est possible que la mémoire s'arrête au premier match trouvé, mais elle peut aussi continuer et balayer toute la mémoire afin de trouver toutes les cases mémoires qui correspondent à l'entrée, tout dépend de comment la logique de contrôle est conçue. L'avantage de balayer toute la mémoire est que l'on peut savoir si une donnée est présente en plusieurs exemplaires dans la mémoire, et localiser chaque exemplaire. À chaque cycle, la mémoire indique si elle a trouvé un match et quel est l'adresse associée. Le processeur a juste à récupérer les adresses transmises quand un match est trouvé, il récupérera les adresses de chaque exemplaire au fur et à mesure que la mémoire est balayée. En comparaison, les autres mémoires associatives utilisent un encodeur à priorité qui choisit un seule exemplaire de la donnée recherchée.

Un autre avantage de telles architectures est qu'elles utilisent peu de circuits, sans compter qu'elles sont simples à fabriquer. Elles sont économes en circuits essentiellement en raison du faible nombre de comparateurs utilisés. Elles n'utilisent qu'un seul comparateur non-sériel, là où les autres mémoires associatives utilisent un comparateur par case mémoire (comparateur parallèle ou sériel, là n'est pas le propos). Vu le grand nombre de cases mémoires que contient une mémoire réellement associative, l'avantage est aux mémoires associatives word-sérielles.

Par contre, cette économie de circuits se fait au détriment des performances. Le fait que chaque case mémoire soit comparée l’une après l'autre, en série, est clairement un désavantage. Le temps mis pour balayer la mémoire est très long et cette solution n'est praticable que pour des mémoires très petites, dont le temps de balayage est faible. De plus, balayer une mémoire est quelque chose que les ordinateurs normaux savent faire avec un morceau de code adapté. N'importe quel programmeur du dimanche peut coder une boucle qui traverse un tableau ou une autre structure de donnée pour y vérifier la présence d'un élément. Implémenter cette boucle en matériel n'a pas grand intérêt et le gain en performance est généralement mineur. Autant dire que les mémoires associatives word-sérielles sont très rares et n'ont pas vraiment d'utilité.

Les mémoires associatives sérielles par blocs

Il est cependant possible de faire un compromis entre performance et économie de circuit/énergie avec les mémoires associatives word-sérielles. L'idée est d'utiliser plusieurs mémoires RAM internes, au lieu d'une seule, qui sont accédées en parallèle. Ainsi, au lieu de comparer chaque case mémoire une par une, on peut en comparer plusieurs à la fois : autant qu'il y a de mémoires internes. L'idée n'est pas sans rappeler l'organisation en banques et rangées des mémoires RAM modernes. En faisant cela, la comparaison sera plus rapide, mais au prix d'une consommation d'énergie et de circuits plus importante. Les mémoires ainsi créées sont appelées des mémoires associatives sérielles par blocs.

Mémoire associative word-sérielle optimisée

Les mémoires associatives sont assez peu utilisées, surtout les mémoires associatives word-sérielles. Cependant, les mémoires caches leur ressemblent beaucoup et une bonne partie de ce que nous venons de voir sera très utile quand nous verrons les mémoires caches. Si les informations de ce chapitre ne pourrons pas être réutilisées à l'identique, il s'agit cependant d'une introduction particulièrement propédeutique. Vous verrez que les mémoires réellement associative ressemblent beaucoup aux mémoires caches de type totalement associative, que les mémoires associatives word-sérielles ressemblent beaucoup aux caches directement adressés, et que les mémoires associatives word-sérielles optimisées avec plusieurs banques ressemblent beaucoup aux mémoires caches à plusieurs voies. Mais laissons cela de côté pour le moment, les mémoires caches étant abordées dans un chapitre à la fin de ce cours, et passons au prochain chapitre.