Mémoire adressable par contenu

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Mémoire associative)

Une mémoire adressable par le contenu (CAM, en anglais Content-Addressable Memory) est un type de mémoire informatique spécial, utilisé dans certaines applications pour la recherche à très haute vitesse. Elle est aussi connue sous le nom de mémoire associative (associative memory, associative storage, ou associative array).

Tableaux associatifs matériels[modifier | modifier le code]

Contrairement aux mémoires informatiques standards (random access memory ou RAM) pour lesquelles l'application utilisatrice fournit une adresse mémoire et la RAM renvoie la donnée stockée à cette adresse, une CAM est conçue de manière que l'application utilisatrice fournisse un mot de donnée et la CAM recherche dans toute la mémoire pour voir si ce mot y est stocké. Si le mot est trouvé, le CAM renvoie une liste d'une ou plusieurs adresses où le mot a été trouvé (et dans certaines architectures, il renvoie également le mot de donnée, ou d'autres morceaux de données associés). Ainsi, une CAM est l'équivalent matériel de ce que l'on appelle un tableau associatif en logiciel.

Implémentations dans un semiconducteur[modifier | modifier le code]

Parce qu'une CAM est conçue pour chercher dans toute sa mémoire en une seule opération, il est plus rapide que la RAM dans toutes les applications de recherche d'un contenu ou de traduction inverse. Le revers de la médaille est qu'au contraire de la RAM, qui a des cellules de stockage simples, chaque bit de mémoire individuel dans une CAM complètement parallèle doit avoir son propre circuit de comparaison pour détecter une correspondance entre le bit stocké et le bit d'entrée. En plus, les sorties de correspondances de chaque cellule du mot de donnée doivent être combinées pour aboutir à un signal correspondant au mot entier. Le circuit additionnel augmente la taille physique de la puce CAM ce qui augmente le coût de fabrication, et augmente également la puissance de dissipation puisque chaque circuit de comparaison est actif à chaque cycle d'horloge. En conséquence, un CAM n'est utilisé que dans les applications spécialisées où la vitesse de recherche ne peut pas être atteinte en utilisant une méthode moins coûteuse, et couramment dans les Switch réseau.

Implémentations alternatives[modifier | modifier le code]

Pour aboutir à un compromis différent entre la vitesse, la taille mémoire, et le coût, certaines implémentations émulent le fonctionnement de la CAM en mettant en œuvre une recherche dans un arbre standard ou dans une table de hachage, au niveau matériel et en utilisant des astuces matérielles comme la réplication ou le pipelining pour améliorer le rendement. Ces techniques sont souvent utilisées dans les routeurs.

Standards pour les mémoires adressables par contenu[modifier | modifier le code]

Une définition d'interface majeure pour les CAM et autres éléments de recherche de réseau a été spécifiée dans l’Interoperability Agreement appelé Look-Aside Interface (LA-1 et LA-1B) développé par le Network Processing Forum, qui ensuite a fusionné avec l’Optical Internetworking Forum (OIF). Beaucoup de composants ont été produits par Integrated Device Technology (en), Cypress Semiconductor, IBM, et d'autres sociétés du LA interface agreement. Le , l’OIF a annoncé avoir initié un projet pour créer une spécification lookaside (SLA) série.

CAM ternaires (TCAM)[modifier | modifier le code]

La CAM binaire est le type le plus simple de CAM qui utilise la recherche de données ne contenant que des 1s et 0s. La CAM ternaire (TCAM) permet un troisième état de correspondance appelé "X" ou "quelconque" pour un ou plusieurs bits dans le mot de donnée stocké, permettant l'ajout de flexibilité dans la recherche. Par exemple, une CAM ternaire pourrait avoir un mot stocké de "10XX0" qui correspondra aux recherches des mots "10000", "10010", "10100", ou "10110". La flexibilité de recherche additionnelle vient avec un coût additionnel par rapport aux CAM binaires parce que la cellule de mémoire interne doit à présent encoder les trois possibilités d'état au lieu des deux d'une CAM binaire. Cet état additionnel est typiquement implémenté en ajoutant un bit de masque (bit "care" ou "don't care" (quelconque)) à chaque cellule mémoire.


Exemples d'applications[modifier | modifier le code]

La mémoire adressable par le contenu est souvent utilisée dans les composants réseaux informatiques. Par exemple, lorsqu'un commutateur réseau (switch) reçoit un datagramme de l'un de ses ports, il met à jour une table interne avec l'adresse MAC source du paquet et le port d'entrée. Il recherche alors l'adresse MAC de destination dans la table pour déterminer vers quel port le datagramme doit être transmis, et l'envoie sur ce port. La table d'adresse MAC est usuellement implémentée par une CAM binaire de telle sorte que le port de destination puisse être trouvé très rapidement, réduisant la latence du switch.

Les CAM ternaires sont souvent utilisées dans les routeurs, où chaque adresse est composée de deux parties : l'adresse du réseau, dont la taille peut varier en fonction de la configuration du sous-réseau, et l'adresse de la machine, qui occupe les bits restants. Chaque sous-réseau a un masque réseau qui spécifie quels bits de l'adresse identifient le réseau et quels bits identifient la machine. Le routage est fait en consultant une table de routage maintenue par le routeur qui contient chaque réseau de destination connu, le masque réseau associé, et l'information nécessaire pour acheminer les datagrammes à ces destinations. Sans CAM, un routeur doit comparer les adresses de destination du datagramme à acheminer avec chaque entrée de la table de routage, effectuant un ET bit-à-bit avec le masque réseau et en comparant avec l'adresse réseau. S’ils sont égaux, l'information acheminement correspondant est utilisée pour réexpédier le datagramme. En utilisant une CAM ternaire pour la table de routage on rend la tâche de recherche beaucoup plus efficace. Les adresses sont enregistrées en spécifiant quels bits machine sont quelconques, et donc la recherche dans la CAM renvoie immédiatement l'adresse de routage correcte ; à la fois le masque et la comparaison sont effectués par le matériel CAM.

Parmi les autres applications des CAM on recense :

Notes et références[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • Anargyos Krikelis, Charles C. Weems (editors) (1997) Associative Processing and Processors, IEEE Computer Science Press. (ISBN 0-8186-7661-2)

Liens externes[modifier | modifier le code]