Memoria direccionable por contenido - Content-addressable memory

Memoria direccionable de contenido

La memoria direccionable por contenido ( CAM ) es un tipo especial de memoria de computadora que se usa 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.

La unidad de reconocimiento de palabras de datos fue propuesta por Dudley Allen Buck en 1955.

CAM se utiliza con frecuencia en dispositivos de red donde acelera el reenvío de la base de información y las operaciones 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 obtiene de la memoria caché.

Matriz asociativa de hardware

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 su memoria completa 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 realización de hardware de lo que en términos de software se llamaría una matriz asociativa .

Estándares

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 . Integrated Device Technology , Cypress Semiconductor , IBM , Broadcom y otros han fabricado numerosos dispositivos que cumplen con el acuerdo de interoperabilidad . El 11 de diciembre de 2007, la OIF publicó el acuerdo de interfaz serial lookaside (SLA).

Implementaciones de semiconductores

Célula CAM binaria CMOS que consta de una célula SRAM 6T más 4 transistores de comparación. Cuando los datos de las líneas de búsqueda (SL) difieren de los datos almacenados en la celda a través de las líneas de bits (BL), la línea de coincidencia (ML) se reducirá para indicar una falta de coincidencia. Si ninguna de las celdas de una línea de coincidencia indica un bit no coincidente, la línea de coincidencia permanecerá alta en el nivel de precarga para indicar una coincidencia de palabras. Ambas líneas de búsqueda se pueden mantener en "0" lógico como una condición de búsqueda indiferente. Las líneas de búsqueda y las líneas de bits se pueden combinar en un solo par de líneas de datos.

CAM es mucho más rápido que RAM en aplicaciones de búsqueda de datos. Sin embargo, el CAM tiene desventajas en cuanto a 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 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, CAM se usa solo en aplicaciones especializadas donde la velocidad de búsqueda no se puede lograr con un método menos costoso. Una implementación temprana exitosa fue un IC y un sistema de procesador asociativo de propósito general.

A principios de la década de 2000, varias empresas de semiconductores, incluidas Cypress , IDT , Netlogic , Sibercore y MOSAID, introdujeron productos CAM dirigidos 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.

Implementaciones alternativas

Para lograr un equilibrio diferente entre la velocidad, el tamaño de la memoria y el costo, algunas implementaciones emulan la función de CAM mediante la búsqueda de árbol estándar o diseños hash en el hardware, utilizando trucos de hardware como la replicación o la canalización para acelerar el rendimiento efectivo. Estos diseños se utilizan a menudo en enrutadores . El algoritmo de Lulea es una implementación eficiente para las búsquedas de coincidencia de prefijo más largas, según se requiere en las tablas de enrutamiento de Internet.

CAM ternarios

Célula CAM ternaria CMOS que consta de dos células SRAM 6T más 4 transistores de comparación. Niveles lógicos normalmente opuestos, ya sea '0' y '1' o '1' y '0' se almacenarán en las dos celdas. Para una condición de indiferencia, '0' se almacenará en ambas celdas para que la línea de coincidencia ML no se reduzca para ninguna combinación de datos de línea de búsqueda (SL).

La CAM binaria es el tipo más simple de CAM y utiliza palabras de búsqueda de datos que constan en su totalidad de unos y ceros . Ternary CAM ( TCAM ) permite un tercer estado de coincidencia de X o no se preocupan 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 sobre la CAM binaria, ya que la celda de memoria interna ahora debe codificar tres estados posibles en lugar de los dos para la CAM binaria. Este estado adicional se implementa típicamente agregando un bit de máscara (bit de "cuidado" o "no importa") a cada celda de memoria.

Aplicaciones de ejemplo

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 a ese puerto. La tabla de direcciones MAC generalmente se implementa con una CAM binaria para que el puerto de destino se pueda encontrar muy rápidamente, lo que reduce la latencia del conmutador.

Las CAM ternarias 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 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 las implementaciones de software, el enrutador compara la dirección de destino del paquete que se 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, la información de enrutamiento correspondiente se utiliza 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 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 enrutamiento correcta; tanto el enmascaramiento como la comparación se realizan mediante el hardware CAM. Esto funciona si (a) las entradas se almacenan en orden de longitud de máscara de red decreciente, 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 ).

Otras aplicaciones CAM incluyen:

Ver también

Referencias

Bibliografía

enlaces externos