Content addressable memory

Mémoire adressable par contenu

Pour les articles homonymes, voir CAM.

La mémoire adressable par contenu (CAM, en anglais Content-Addressable Memory) est un type de mémoire informatique spécial utilisé dans certaines applications de 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

Contrairement aux mémoires informatiques standard (random access memory ou RAM) pour lesquelles l'application utilisatrice fournit une adresse mémoire et la RAM retourne la donnée stockée à cette adresse, un CAM est conçu de telle manière à ce que l'application utilisatrice fournisse un mot de donnée et le CAM cherche dans toute sa mémoire pour voir si ce mot y est stocké. Si le mot est trouvé, le CAM retourne 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ées). Donc, un CAM est l'équivalent matériel de ce que l'on appelle un tableau associatif en logiciel.

Implémentations Semiconducteur

Parce qu'un CAM est conçu 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. Le revers de la médaille, est qu'au contraire de la RAM, chip, qui a des cellules de stockage simples, chaque bit de mémoire individuel dans un 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. La circuiterie additionnelle augmente la taille physique de la puce CAM ce qui augmente le coût de fabrication. La circuiterie supplémentaire 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.

Implémentations alternatives

Pour aboutir à un compromis différent entre la vitesse, la taille mémoire, et le coût, certaines implémentations émulent le fonctionnement du CAM en implémentant une recherche d'arbre standard ou une conception de hash, au niveau matériel, en utilisant des astuces matérielles comme la réplication ou le pipelining pour booster le rendement. Ces conceptions sont souvent utilisées dans les routeurs.

Standards pour la mémoire adressable par contenu

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, Cypress Semiconductor, IBM, et d'autres firmes du LA interface agreement. Le 25 mai 2006, l’OIF a annoncé avoir initié un projet pour créer une spécification lookaside (SLA) série.

CAM ternaires

Le CAM binaire est le type le plus simple de CAM qui utilise la recherche de données ne contenant que des 1s et 0s. Le CAM ternaire 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, un 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 du 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

La mémoire adressable par contenu est souvent utilisée dans les composants réseaux informatiques. Par exemple, lorsqu'un switch réseau reçoit un datagramme de l'un de ses ports, il met à jour une table interne avec la source du paquet adresse MAC 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 un CAM binaire en sorte que le port de destination puisse être trouvé très rapidement, réduisant la latence du switch.

Les CAM ternaires sont souvent utilisés 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 un 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 le CAM renvoie immédiatement l'entrée de routage correcte ; à la fois le masque et la comparaison sont effectués par le matériel CAM.

Parmi les autres applications CAM on recense :

• CPU cache controllers et Translation Lookaside Buffers ;
• moteurs de base de données ;
• matériel de compression de données ;
• Artificial neural networks.

Voir aussi

• Associative array

Bibliographie

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

Liens externes

• CAM Primer
• Content-addressable memory (CAM) circuits and architectures: A tutorial and survey
• Low-power CAM Design Group
• Aspex - Computer architecture built around associative memory
• Initiation of Serial Lookaside specification effort (near bottom of page 1)

Ce document provient de « M%C3%A9moire adressable par contenu ».