La memoria direccionable por contenido ( CAM ) es un tipo especial de memoria de computadora que se utiliza en ciertas aplicaciones de búsqueda de muy alta velocidad. También se la conoce como memoria asociativa o almacenamiento asociativo y compara los datos de búsqueda de entrada con una tabla de datos almacenados y devuelve la dirección de los datos coincidentes. [1]
CAM se utiliza con frecuencia en dispositivos de red , donde acelera el reenvío de información de operaciones de base y tabla de enrutamiento . Este tipo de memoria asociativa también se utiliza en la memoria caché. En la memoria caché asociativa, tanto la dirección como el contenido se almacenan uno al lado del otro. Cuando la dirección coincide, el contenido correspondiente se recupera de la memoria caché.
Dudley Allen Buck inventó el concepto de memoria direccionable por contenido en 1955. A Buck se le atribuye la idea de la unidad de reconocimiento . [2]
A diferencia de la memoria de computadora estándar, la memoria de acceso aleatorio (RAM), en la que el usuario proporciona una dirección de memoria y la RAM devuelve la palabra de datos almacenada en esa dirección, una CAM está diseñada de tal manera que el usuario proporciona una palabra de datos y la CAM busca en toda su memoria para ver si esa palabra de datos está almacenada en algún lugar de ella. Si se encuentra la palabra de datos, la CAM devuelve una lista de una o más direcciones de almacenamiento donde se encontró la palabra. Por lo tanto, una CAM es la encarnación de hardware de lo que en términos de software se llamaría una matriz asociativa .
Un concepto similar se puede encontrar en la unidad de reconocimiento de palabras de datos , tal como lo propuso Dudley Allen Buck en 1955. [3]
Una definición de interfaz importante para CAM y otros motores de búsqueda de red se especificó en un acuerdo de interoperabilidad llamado Interfaz Look-Aside (LA-1 y LA-1B) desarrollado por el Network Processing Forum . [4] Integrated Device Technology , Cypress Semiconductor , IBM , Broadcom y otros han producido numerosos dispositivos que cumplen con el acuerdo de interoperabilidad . El 11 de diciembre de 2007, el OIF publicó el acuerdo de interfaz de look-aside serial (SLA). [ cita requerida ]
El CAM es mucho más rápido que la RAM en aplicaciones de búsqueda de datos. Sin embargo, el CAM tiene desventajas en términos de costo. A diferencia de un chip RAM , que tiene celdas de almacenamiento simples, cada bit de memoria individual en un CAM completamente paralelo debe tener su propio circuito de comparación asociado para detectar una coincidencia entre el bit almacenado y el bit de entrada. Además, las salidas de coincidencia de cada celda en la palabra de datos deben combinarse para producir una señal de coincidencia de palabra de datos completa. Los circuitos adicionales aumentan el tamaño físico y el costo de fabricación del chip CAM. Los circuitos adicionales también aumentan la disipación de energía ya que cada circuito de comparación está activo en cada ciclo de reloj. En consecuencia, el CAM se usa solo en aplicaciones especializadas donde la velocidad de búsqueda no se puede lograr utilizando un método menos costoso. Una implementación temprana exitosa fue un sistema y circuito integrado de procesador asociativo de propósito general. [5]
A principios de la década de 2000, varias empresas de semiconductores, entre ellas Cypress , IDT , Netlogic , Sibercore [6] y MOSAID, introdujeron productos CAM destinados a aplicaciones de redes. Estos productos se denominaban motores de búsqueda de red (NSE), aceleradores de búsqueda de red (NSA) y procesadores basados en el conocimiento (KBP), pero eran esencialmente CAM con interfaces especializadas y funciones optimizadas para redes. Actualmente, Broadcom ofrece varias familias de KBP. [7]
Para lograr un equilibrio diferente entre velocidad, tamaño de memoria y costo, algunas implementaciones emulan la función de CAM mediante el uso de diseños de búsqueda de árbol o hash estándar en hardware, utilizando trucos de hardware como replicación o canalización para acelerar el rendimiento efectivo. Estos diseños se utilizan a menudo en enrutadores . [ cita requerida ] El algoritmo Lulea es una implementación eficiente para búsquedas de coincidencias de prefijo más largo como se requiere en las tablas de enrutamiento de Internet.
El CAM binario es el tipo más simple de CAM y utiliza palabras de búsqueda de datos que consisten completamente en 1 y 0. El CAM ternario ( TCAM ) [8] permite un tercer estado coincidente de X o no importa para uno o más bits en la palabra almacenada, agregando así flexibilidad a la búsqueda. Por ejemplo, una palabra almacenada de 10XX0 en un CAM ternario coincidirá con cualquiera de las cuatro palabras de búsqueda 10000 , 10010 , 10100 o 10110. La flexibilidad de búsqueda agregada tiene un costo adicional sobre el CAM binario ya que la celda de memoria interna ahora debe codificar tres estados posibles en lugar de los dos para el CAM binario. Este estado adicional generalmente se implementa agregando un bit de máscara ( bit de cuidado o no importa ) a cada celda de memoria. En 2013, IBM fabricó un TCAM no volátil utilizando celdas de 2 transistores/2 almacenamientos resistivos (2T-2R). [9] Un grupo de científicos internacionales publicó recientemente un diseño de TCAM que utiliza FeFET ferroeléctrico híbrido. [10]
La memoria direccionable por contenido se utiliza a menudo en dispositivos de redes informáticas . Por ejemplo, cuando un conmutador de red recibe una trama de datos de uno de sus puertos, actualiza una tabla interna con la dirección MAC de origen de la trama y el puerto en el que se recibió. A continuación, busca la dirección MAC de destino en la tabla para determinar a qué puerto se debe reenviar la trama y la envía por ese puerto. La tabla de direcciones MAC suele implementarse con un CAM binario para que se pueda encontrar el puerto de destino muy rápidamente, lo que reduce la latencia del conmutador.
Los CAM ternarios se utilizan a menudo en enrutadores de red , donde cada dirección tiene dos partes: el prefijo de red , que puede variar en tamaño según la configuración de la subred , y la dirección de host, que ocupa los bits restantes. Cada subred tiene una máscara de red que especifica qué bits de la dirección son el prefijo de red y qué bits son la dirección de host. El enrutamiento se realiza consultando una tabla de enrutamiento mantenida por el enrutador que contiene cada prefijo de red de destino conocido, la máscara de red asociada y la información necesaria para enrutar los paquetes a ese destino. En una implementación de software simple, el enrutador compara la dirección de destino del paquete que se va a enrutar con cada entrada en la tabla de enrutamiento, realizando un AND bit a bit con la máscara de red y comparándolo con el prefijo de red. Si son iguales, se utiliza la información de enrutamiento correspondiente para reenviar el paquete. El uso de un CAM ternario para la tabla de enrutamiento hace que el proceso de búsqueda sea muy eficiente. Las direcciones se almacenan sin importar la parte de host de la dirección, por lo que buscar la dirección de destino en el CAM recupera inmediatamente la entrada de enrutamiento correcta; tanto el enmascaramiento como la comparación los realiza el hardware del CAM. Esto funciona si (a) las entradas se almacenan en orden decreciente de longitud de máscara de red y (b) el hardware devuelve solo la primera entrada coincidente; por lo tanto, se utiliza la coincidencia con la máscara de red más larga ( coincidencia de prefijo más larga ). [11]
Otras aplicaciones CAM incluyen:
La TLB es una pequeña memoria asociativa que asigna direcciones virtuales a direcciones reales.