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 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 las operaciones de la base de información de reenvío y de la 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 manera que el usuario proporciona una palabra de datos y la CAM busca su toda la memoria para ver si esa palabra de datos está almacenada en algún lugar de ella. Si se encuentra la palabra de datos, el CAM devuelve una lista de una o más direcciones de almacenamiento donde se encontró la palabra. Por tanto, una CAM es la encarnación 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 , propuesta por 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 Look-Aside Interface (LA-1 y LA-1B) desarrollado por 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, la OIF publicó el acuerdo de interfaz serial look-aside (SLA). [ cita necesaria ]
CAM es mucho más rápida que RAM en aplicaciones de búsqueda de datos. Sin embargo, la CAM tiene desventajas de costos. 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 coste de fabricación del chip CAM. El circuito adicional también aumenta la disipación de energía ya que cada circuito de comparación está activo en cada ciclo de reloj. En consecuencia, CAM se utiliza sólo en aplicaciones especializadas donde la velocidad de búsqueda no se puede lograr utilizando un método menos costoso. Una de las primeras implementaciones exitosas fue un sistema y un procesador integrado asociativo de uso general. [5]
A principios de la década de 2000, varias empresas de semiconductores, incluidas Cypress , IDT , Netlogic , Sibercore [6] y MOSAID, introdujeron productos CAM destinados a aplicaciones de redes. Estos productos se denominaron 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 búsqueda de árbol estándar o diseños de hash 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 necesaria ] El algoritmo de Lulea es una implementación eficiente para búsquedas de coincidencias de prefijos más largas, como se requiere en las tablas de enrutamiento de Internet.
CAM binario es el tipo más simple de CAM y utiliza palabras de búsqueda de datos que consisten enteramente en 1 y 0 . CAM ternario ( TCAM ) [8] permite un tercer estado coincidente de X o no se preocupa por uno o más bits en la palabra almacenada, lo que agrega 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 adicional tiene un costo adicional respecto al CAM binario, ya que la celda de memoria interna ahora debe codificar tres estados posibles en lugar de los dos del CAM binario. Este estado adicional generalmente se implementa agregando un bit de máscara ( bit de atención o no importa ) a cada celda de memoria. En 2013, IBM fabricó una TCAM no volátil utilizando celdas de almacenamiento de 2 transistores/2 resistivas (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ó. Luego 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 generalmente se implementa con un CAM binario para que el puerto de destino se pueda encontrar muy rápidamente, lo que reduce la latencia del conmutador.
Las CAM ternarias se suelen utilizar en enrutadores de red , donde cada dirección tiene dos partes: el prefijo de red , que puede variar de tamaño según la configuración de la subred , y la dirección del 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 del 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 paquetes a ese destino. En una implementación de software simple, el enrutador compara la dirección de destino del paquete 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 utilizando la parte del host de la dirección, por lo que al buscar la dirección de destino en el CAM se recupera inmediatamente la entrada de ruta correcta; Tanto el enmascaramiento como la comparación se realizan mediante el hardware CAM. Esto funciona si (a) las entradas se almacenan en orden decreciente de longitud de máscara de red y (b) el hardware devuelve sólo 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:
El TLB es una pequeña memoria asociativa que asigna direcciones virtuales a reales.