Mémoire adressable par le contenu - Content-addressable memory

Contenu de la mémoire adressable

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

Cellule CAM binaire CMOS composée d'une cellule SRAM 6T plus 4 transistors de comparaison. Lorsque les données sur les lignes de recherche (SL) diffèrent des données stockées dans la cellule via les lignes de bits (BL), la ligne de correspondance (ML) sera tirée vers le bas pour indiquer une non-concordance. Si aucune des cellules sur une ligne de correspondance n'indique un bit non concordant, la ligne de correspondance restera élevée au niveau de précharge pour indiquer une correspondance de mot. Les deux lignes de recherche peuvent être maintenues à « 0 » logique en tant que condition de recherche indifférente. Les lignes de recherche et les lignes de bits peuvent être fusionnées en une seule paire de lignes de données.

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

Cellule CAM ternaire CMOS composée de deux cellules SRAM 6T plus 4 transistors de comparaison. Des niveaux logiques normalement opposés, '0' et '1' ou '1' et '0' seront stockés dans les deux cellules. Pour une condition indifférente « 0 » sera stockée dans les deux cellules afin que la ligne de correspondance ML ne soit pas tirée vers le bas pour aucune combinaison de données de ligne de recherche (SL).

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 :

Voir également

Les références

Bibliographie

Liens externes