Memoria direccionable por 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. ^[1]

La unidad de reconocimiento de palabras de datos fue propuesta por Dudley Allen Buck en 1955. ^[2]

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 toda la memoria para ver si esa palabra de datos está almacenada en alguna parte. 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 . ^[3]

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). ^{[ cita requerida ]}

Implementaciones de semiconductores

CAM es mucho más rápido que RAM en aplicaciones de búsqueda de datos. Sin embargo, CAM tiene desventajas en cuanto a costos. A diferencia de un chip RAM , que tiene celdas de almacenamiento simples, cada bit de memoria individualen 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 usando un método menos costoso. Una implementación temprana exitosa fue un IC y un sistema de procesador asociativo de propósito general. ^[4]

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 . ^{[ cita requerida ]}

CAM ternarios

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 ) ^[5] permite un tercer estado coincidente de X o no importapara 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, reduciendo la latencia del switch.

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 unaAND bit a bit con la máscara de red y comparándola 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 ). ^[6]

Otras aplicaciones CAM incluyen:

• CPU controladores de caché totalmente asociativos y búferes de búsqueda de traducción (TLB)
• Motores de base de datos
• Hardware de compresión de datos
• Redes neuronales artificiales ^[7]
• Sistema de Prevención de Intrusión
• Varias computadoras personalizadas, como Goodyear STARAN , fueron construidas para implementar CAM.

Ver también

• Red de contenido direccionable
• Procesador paralelo direccionable de contenido
• Sistema de archivos o almacenamiento direccionable por contenido
• Memoria distribuida escasa
• Espacio de tupla

Referencias

1. Pagiamtzis y Sheikholeslami (2006), págs. 712–713
2. TRW Computer Division Archivado el 5 de agosto de 2011 en Wayback Machine , 1963, p. 17.
3. Hannum y col. (2004)
4. Storman y col. (1992)
5. Hucaby, David (2004). Guía de certificación del examen CCNP BCMSN: Autoestudio CCNP . ISBN 9781587200779.
6. Varghese, George , Algoritmos de red: un enfoque interdisciplinario para diseñar dispositivos de red rápidos , Morgan Kaufmann, 2005
7. Hinton, Geoffrey E. (1984). "Representaciones distribuidas" .

Bibliografía

• Anargyros Krikelis, Charles C. Weems (editores) (1997). Procesadores y procesadores asociativos , IEEE Computer Science Press. ISBN 0-8186-7661-2 
• Hannum y col. (2004). Sistema y método para restablecer e inicializar una matriz completamente asociativa a un estado conocido en el momento del encendido o mediante un estado específico de la máquina . Patente de Estados Unidos 6.823.434. Disponible buscando en http://patft.uspto.gov/netahtml/PTO/search-bool.html
• Pagiamtis, K .; Sheikholeslami, A. (2006). "Circuitos y arquitecturas de memoria direccionable por contenido (CAM): un tutorial y una encuesta" (PDF) . Revista IEEE de circuitos de estado sólido . 41 (3): 712–727. Código bibliográfico : 2006IJSSC..41..712P . doi : 10.1109 / JSSC.2005.864128 .
• Stormon, CD; Troullinos, NB; Saleh, EM; Chavan, AV; Brule, MR; Oldfield, JV; Un IC y un sistema de procesador asociativo CMOS de propósito general, Coherent Research Inc., East Syracuse, NY, EE. UU., IEEE Micro, diciembre de 1992, volumen: 12 Edición: 6.
• División de informática de TRW. (1963). Primer informe provisional sobre la utilización óptima de computadoras y técnicas informáticas en los sistemas de control de armas a bordo . (Proyecto BuWeps RM1004 M88-3U1). Alexandria, Virginia: Centro de documentación de defensa para información científica y técnica.

Enlaces externos

• Primer CAM
• Circuitos y arquitecturas de memoria direccionable por contenido (CAM): un tutorial y una encuesta
• Aspex: arquitectura de computadora construida alrededor de la memoria asociativa
• Inicio del esfuerzo de especificación Serial Lookaside (casi al final de la página 1)
• Acuerdo de interfaz OIF Serial Lookaside
• Procesamiento aritmético usando memoria asociativa
• SimpleRBM : una máquina de Boltzmann restringida muy pequeña , que incluye un algoritmo de entrenamiento, que es una especie de memoria direccionable de contenido de vectores de bits.