Mémoire adressable par le contenu - Content-addressable memory
La mémoire adressable par le contenu ( CAM ) est un type spécial de mémoire informatique utilisé dans certaines applications de recherche à très grande vitesse. Il est également connu sous le nom de mémoire associative ou de stockage associatif et compare les données de recherche d'entrée à une table de données stockées et renvoie l'adresse des données correspondantes.
L'unité de reconnaissance de mots de données a été proposée par Dudley Allen Buck en 1955.
CAM est fréquemment utilisé dans les périphériques réseau où il accélère les opérations de transfert de base d'informations et de table de routage . Ce type de mémoire associative est également utilisé en mémoire cache. Dans la mémoire cache associative, l'adresse et le contenu sont stockés côte à côte. Lorsque l'adresse correspond, le contenu correspondant est extrait de la mémoire cache.
Tableau associatif matériel
Contrairement à la mémoire informatique standard, la mémoire vive (RAM), dans laquelle l'utilisateur fournit une adresse mémoire et la RAM renvoie le mot de données stocké à cette adresse, une CAM est conçue de telle sorte que l'utilisateur fournisse un mot de données et que la CAM recherche son toute la mémoire pour voir si ce mot de données est stocké n'importe où dedans. Si le mot de données est trouvé, le CAM renvoie une liste d'une ou plusieurs adresses de stockage où le mot a été trouvé. Ainsi, un CAM est l'incarnation matérielle de ce que l'on appellerait en termes logiciels un tableau associatif .
Normes
Une définition d'interface majeure pour les CAM et autres moteurs de recherche de réseau a été spécifiée dans un accord d'interopérabilité appelé Look-Aside Interface (LA-1 et LA-1B) développé par le Network Processing Forum . De nombreux dispositifs conformes à l'accord d'interopérabilité ont été produits par Integrated Device Technology , Cypress Semiconductor , IBM , Broadcom et d'autres. Le 11 décembre 2007, l'OIF a publié le contrat d'interface Serial Lookaside (SLA).
Implémentations de semi-conducteurs
La CAM est beaucoup plus rapide que la RAM dans les applications de recherche de données. Cependant, le CAM présente des inconvénients de coût. Contrairement à une puce RAM , qui a de simples cellules de stockage, chaque bit de mémoire individuel dans une CAM entièrement parallèle doit avoir son propre circuit de comparaison associé pour détecter une correspondance entre le bit stocké et le bit d'entrée. De plus, les sorties de correspondance de chaque cellule dans le mot de données doivent être combinées pour produire un signal de correspondance de mot de données complet. Les circuits supplémentaires augmentent la taille physique et le coût de fabrication de la puce CAM. Le circuit supplémentaire augmente également la dissipation de puissance puisque chaque circuit de comparaison est actif à chaque cycle d'horloge. Par conséquent, la FAO n'est utilisée que dans des applications spécialisées où la vitesse de recherche ne peut pas être atteinte en utilisant une méthode moins coûteuse. Une première mise en œuvre réussie a été un circuit intégré et un système de processeur associatif à usage général.
Au début des années 2000, plusieurs sociétés de semi-conducteurs, dont Cypress , IDT , Netlogic , Sibercore et MOSAID, ont introduit des produits de FAO ciblant les applications de mise en réseau. Ces produits étaient étiquetés moteurs de recherche réseau (NSE), accélérateurs de recherche réseau (NSA) et processeurs basés sur les connaissances (KBP), mais étaient essentiellement des CAM avec des interfaces spécialisées et des fonctionnalités optimisées pour la mise en réseau. À l' heure actuelle Broadcom propose plusieurs familles de KBps.
Implémentations alternatives
Pour atteindre un équilibre différent entre la vitesse, la taille de la mémoire et le coût, certaines implémentations émulent la fonction de CAM en utilisant une recherche d'arborescence standard ou des conceptions de hachage dans le matériel, en utilisant des astuces matérielles telles que la réplication ou le pipeline pour accélérer les performances efficaces. Ces conceptions sont souvent utilisées dans les routeurs . L' algorithme Lulea est une implémentation efficace pour les recherches de correspondance de préfixe les plus longues requises dans les tables de routage Internet.
CAM Ternaires
La CAM binaire est le type de CAM le plus simple et utilise des mots de recherche de données entièrement composés de 1 et de 0 . Ternary CAM ( TCAM ) permet un troisième état de correspondance de X ou ne se soucie pas d'un ou plusieurs bits dans le mot stocké, ajoutant ainsi de la flexibilité à la recherche. Par exemple, un mot stocké de "10XX0" dans un CAM ternaire correspondra à l'un des quatre mots de recherche "10000", "10010", "10100" ou "10110". La flexibilité de recherche supplémentaire a un coût supplémentaire par rapport à la CAM binaire car la cellule de mémoire interne doit maintenant coder trois états possibles au lieu des deux pour la CAM binaire. Cet état supplémentaire est typiquement implémenté en ajoutant un bit de masque (bit "attention" ou "pas d'attention") à chaque cellule mémoire.
Exemples d'applications
La mémoire adressable par le contenu est souvent utilisée dans les périphériques de mise en réseau informatique . Par exemple, lorsqu'un commutateur réseau reçoit une trame de données de l'un de ses ports, il met à jour une table interne avec l' adresse MAC source de la trame et le port sur lequel elle a été reçue. Il recherche ensuite l'adresse MAC de destination dans le tableau pour déterminer vers quel port la trame doit être transférée et l'envoie sur ce port. La table d'adresses MAC est généralement implémentée avec un CAM binaire afin que le port de destination puisse être trouvé très rapidement, réduisant ainsi la latence du commutateur.
Les CAM ternaires sont souvent utilisées dans les routeurs réseau , où chaque adresse comporte deux parties : le préfixe réseau , dont la taille peut varier en fonction de la configuration du sous - réseau , et l'adresse hôte, qui occupe les bits restants. Chaque sous-réseau a un masque de réseau qui spécifie quels bits de l'adresse sont le préfixe du réseau et quels bits sont l'adresse de l'hôte. Le routage est effectué en consultant une table de routage gérée par le routeur qui contient chaque préfixe de réseau de destination connu, le masque de réseau associé et les informations nécessaires pour acheminer les paquets vers cette destination. Dans les implémentations logicielles, le routeur compare l'adresse de destination du paquet à acheminer avec chaque entrée de la table de routage, en effectuant un ET au niveau du bit avec le masque de réseau et en le comparant avec le préfixe de réseau. S'ils sont égaux, les informations de routage correspondantes sont utilisées pour transmettre le paquet. L'utilisation d'un CAM ternaire pour la table de routage rend le processus de recherche très efficace. Les adresses sont stockées en ne tenant pas compte de la partie hôte de l'adresse, donc la recherche de l'adresse de destination dans le CAM récupère immédiatement l'entrée de routage correcte ; le masquage et la comparaison sont effectués par le matériel CAM. Cela fonctionne si (a) les entrées sont stockées par ordre décroissant de longueur de masque de réseau, et (b) le matériel ne renvoie que la première entrée correspondante ; ainsi, la correspondance avec le masque de réseau le plus long ( correspondance de préfixe la plus longue ) est utilisée.
Les autres applications de FAO incluent :
- Contrôleurs de cache entièrement associatifs et tampons lookaside de traduction
- Moteurs de base de données
- Matériel de compression de données
- Réseaux de neurones artificiels
- Systèmes de prévention des intrusions
- Processeurs réseau
- Plusieurs ordinateurs personnalisés, comme le Goodyear STARAN , ont été construits pour implémenter la FAO.
Voir également
- Réseau adressable par le contenu
- Processeur parallèle adressable par le contenu
- Stockage adressable par le contenu ou système de fichiers
- Mémoire distribuée éparse
- Espace de tuples
Les références
Bibliographie
- Anargyros Krikelis, Charles C. Weems (éditeurs) (1997). Traitement associatif et processeurs , IEEE Computer Science Press. ISBN 0-8186-7661-2
- US 6823434 , Hannum et al., "Système et méthode de réinitialisation et d'initialisation d'un réseau entièrement associatif à un état connu à la mise sous tension ou via un état spécifique à la machine", publié en 2004
- Pagiamtis, K.; Sheikholeslami, A. (2006). « Circuits et architectures de mémoire adressable par contenu (CAM) : un didacticiel et une enquête" (PDF) . Journal IEEE des circuits à semi-conducteurs . 41 (3) : 712-727. Bibcode : 2006IJSSC..41..712P . doi : 10.1109/JSSC.2005.864128 . S2CID 11178331 .
- Stormon, CD ; Troullinos, N.-B.; Saleh, EM ; Chavan, AV ; Brulé, MR ; Oldfield, JV; Un circuit intégré et un système de processeur associatif CMOS à usage général, Coherent Research Inc., East Syracuse, NY, États-Unis, IEEE Micro, décembre 1992, Volume: 12 Issue:6.
- Division informatique de TRW. (1963). Premier rapport intermédiaire sur l'utilisation optimale des ordinateurs et des techniques informatiques dans les systèmes de contrôle des armes à bord des navires . (BuWeps-Projet RM1004 M88-3U1). Alexandria, Virginie : Centre de documentation de la défense pour l'information scientifique et technique.
Liens externes
- Amorce CAM
- Circuits et architectures de mémoire adressable par le contenu (CAM) : un tutoriel et une enquête
- Aspex - Architecture informatique construite autour de la mémoire associative
- Lancement de l'effort de spécification Serial Lookaside (près du bas de la page 1)
- Contrat d'interface OIF Serial Lookaside
- Traitement arithmétique utilisant la mémoire associative
- SimpleRBM - une très petite machine de Boltzmann restreinte , comprenant un algorithme d'apprentissage, qui est une sorte de mémoire adressable par contenu de vecteurs binaires.