Sistema y método de lectura y escritura de una memoria digital.

Sistema y método de lectura y escritura de una memoria digital (1) que permite acelerar la localización de uno o más datos que se desean buscar (5) segmentando dicha memoria digital (1) en una pluralidad de segmentos (11) que son leídos en paralelo.

Cada segmento (11) está conectado a, al menos, un comparador (3) a través de al menos un puerto de lectura (12), permitiendo implementar topologías con múltiples puertos de lectura (12) y/o con múltiples búsquedas simultáneas mediante múltiples bancos de comparadores (3).

Sistema y método de lectura y escritura de una memoria digital.

Objeto de la invención La presente invención se refiere al campo de la tecnología electrónica digital, y más concretamente, a la gestión de una memoria digital.

Antecedentes de la invención Son muchas las aplicaciones que requieren un rápido acceso a datos almacenados en memorias digitales para su correcto funcionamiento. Es el caso, por ejemplo, de protocolos de redundancia como el protocolo de redundancia paralela (PRP, del inglés 'Parallel Redundancy Protocol') y el protocolo de redundancia sin cortes de alta disponibilidad (HSR, del inglés 'High-availability Seamless Redundancy Protocol'; recogido en el estándar IEC62439 -3, edición 2, 2012) . Tanto las redes PRP como HSR se basan en el uso controlado de tramas duplicadas, por lo que los nodos de la red deben almacenar las tramas que han recibido anteriormente durante un cierto tiempo, para así decidir si las tramas recibidas a continuación deben ser reenviadas, eliminadas o aceptadas.

Una de las aplicaciones de las redes PRP y HSR son los buses de proceso y de estación en subestaciones, de acuerdo con el estándar IEC61850 -90 -4, edición 1, publicado en diciembre de 2013. Debido a que estas redes soportan tipos de tráfico con exigencias en cuanto a su tiempo de retardo, es necesario que el proceso de gestión y local ización de tramas en memoria se realice de forma eficiente y en un tiempo lo más reducido posible.

Esta necesidad, con niveles de exigencia variables, aparece también en diversas aplicaciones, como por ejemplo, en conmutadores Ethemet, tanto estándar como incorporando protocolos PRP y HSR. En este caso, los conmutadores deben almacenar en memoria los puertos de salida asociados a cada dirección de Control de Acceso al Medio (MAC, del inglés 'Media Access Control") de destino.

A la hora de implementar las memorias digitales necesarias para el correcto funcionamiento de las aplicaciones descritas, se conocen en el estado de la técnica distintas estructuras, entre las que cabe destacar las memorias de acceso aleatorio (RAM, del inglés 'Random Access Memor y ) ; las memorias asociativas, también denominadas memorias direccionables por contenido (CAM, del inglés 'Content Addressable Memor y ') ; y las tablas de dispersión, también conocidas como tablas fragmentadas (en inglés 'hash table') .

Para localizar un dato almacenado en una memoria RAM, es necesaria la lectura secuencial (posición a posición) de la memoria. Es la opción que menos recursos necesita, pero a cambio tiene asociados los tiempos de búsqueda más elevados, resultando inviables para la mayoría de aplicaciones mencionadas.

Las memorias CAM suponen la combinación de una memoria RAM con un banco de comparadores. Al comprobarse todos lOS datos a la vez, se aumenta notablemente la velocidad de búsqueda. Sin embargo, la 45 comparación en paralelo de todas las posiciones de memoria de la CAM requiere una gran cantidad de recursos, que hace inviable su aplicación en casos de memorias con un número elevado de entradas.

Las tablas de dispersión aplican una función al dato que se desea encontrar, de forma que el resultado de dicha función indica la posición en memoria en la que se encuentra el dato buscado. Como el número de posiciones en memoria es menor que el número posible de datos, se producen colisiones, que son aquellos casos en los que para datos diferentes se obtiene una misma posición en memoria. Este fenómeno debe ser gestionado y minimizado por el sistema, con el consiguiente aumento del tiempo y los recursos necesarios.

A partir de estos tipos básicos de memoria, se han desarrollado distintas estrategias y topologias para la gestión de datos en memoria. Por ejemplo, WO 19901004849 A1 presenta una estructura de memorias en paralelo, teniendo cada memoria su propio buffer, que sirve tanto para leer y escribir como para comunicar con las memorias adyacentes. Otra alternativa es propuesta por US 2003/0235099 A 1, en este caso basada en la replicación del contenido de la memoria en múltiples bancos de datos. Se consigue asi aumentar la velocidad de búsqueda, aunque dicha mejora supone un escalado considerable de los recursos necesarios, tanto a nivel de control como en cuanto al tamaño total de las memorias digitales.

WO 2007/038805 A1 presenta una estructura matricial que comprende múltiples celdas CAM. Sobre dicha estructura se aplica una estrategia que combina búsquedas en serie y en paralelo. La búsqueda es 65 gestionada desde unos medios de control que generan líneas de búsqueda para cada columna de la estructura matricial. US 200510268028 A1 propone una memoria de búsqueda en paralela que comprende una pluralidad de memorias GAM. Unos medios de control generan comandos que indican sobre qué

subconjunto de entradas de las memorias GAM se aplica la búsqueda de datos. US 2002/075714 A 1 presenta una estructura de almacenamiento de datos basada en múltiples memorias GAM, asociadas a un circuito de selección basado en clases. Dependiendo de un código de clase de los datos que se desean localizar, se activan o desactivan las memorias CAM correspondientes.

El problema del tiempo de búsqueda se acentúa cuando la tasa a la que se reciben los datos que se desean localizar (por ejemplo las tramas de red PRP y HSP) es muy elevada. Puesto que los datos se intentan localizar uno a uno, existen escenarios en los que se reciben datos a más velocidad de la que se pueden gestionar. Esta situación puede llegar a provocar saturaciones en los nodos, con el consiguiente incumplimiento de restricciones de tiempo del sistema.

Existen ciertos sistemas de memoria que soportan búsquedas concurrentes, aunque todos ellos presentan limitaciones. US 6374326 81 propone una estructura basada en múltiples bancos de memorias CAM para permitir operaciones de búsqueda concurrentes. Los múltiples bancos se gestionan con una misma clave de búsqueda, de la cual cada banco extrae un subconjunto de bits, que aplica a su búsqueda. Nótese que, en un determinado instante, cada banco de memorias realiza una única búsqueda, pudiendo dicha búsqueda ser distinta a la de los bancos adyacentes. Es decir, esta topología no puede aplicarse para buscar simultáneamente varios datos en una misma memoria CAM, a no ser que se apliquen técnicas de redundancia que aumentan la complejidad del sistema y los recursos necesarios para su funcionamiento.

US 3771139 A1 presenta una memoria asociativa que soporta múltiples búsquedas de contenido simultáneas. En particular, los datos de entrada son almacenados en memoria junto con los datos con los que se desean comparar. A continuación, se inicia un proceso iterativo de comparación bit a bit que se realiza simultáneamente para todas las búsquedas. No obstante, este sistema sólo es más rápido que una memoria GAM convencional si el número de elementos comparados es mayor que una constante determinada por la complejidad de la búsqueda y por la implementación hardware. Adicionalmente, requiere utilizar parte de la capacidad de la memoria para almacenaje de los datos de entrada y de bits de etiquetado del algoritmo.

EP 0, 805, 457 A2 presenta celdas de memoria GAM que incorporan tres circuitos comparadores independientes integrados, permitiendo simultáneamente tres operaciones de comparación sobre cada bit almacenado en la memoria GAM. Adicionalmente, la separación de los puertos de acceso y escritura permite ejecutar simultáneamente operaciones de lectura, escritura y comparación, si bien no en la misma fila. Esta opción está limitada a tres comparaciones simultáneas y, al afectar a la topología de cada celda CAM, no puede ser implementada sobre una memoria genérica.

A pesar de las distintas estrategias empleadas, todos los sistemas de gestión de memoria descritos presentan limitaciones en cuanto al tiempo y los recursos necesa rios para realizar las búsquedas de datos en memoria.

Nótese asimismo que en muchas de las aplicaciones mencionadas, las entradas más antiguas acaban siendo obsoletas con el tiempo. Su presencia en memoria aumenta el número total de entradas, actuando en detrimento del tiempo de búsqueda y de la cantidad de recursos empleados por el sistema. Este problema puede ser solucionado sobrescribiendo las entradas más antiguas de la memoria con entradas 45 más recientes. No obstante, las memorias RAM, CAM y las tablas de dispersión no soportan de manera nativa el control del envejecimiento de las entradas. Es decir, la información almacenada en la memoria no está ordenada cronológicamente ni contiene información temporal sobre cuándo fue almacenada. Para incorporar esta información, es necesario un control adicional externo que determine la antigüedad de cada entrada.... [Seguir leyendo]

, . Sistema de lectura y escritura de al menos una memoria digital (1 l, comprendiendo la al menos una memoria digital (1) una pluralidad de posiciones de memoria (9) agrupadas en una pluralidad de segmentos (11) , cada posición de memoria (9) teniendo capacidad para al menos un dato almacenado (10) ; caracterizado por que comprende: -medios de control (2) adaptados para leer en paralelo la plural idad de segmentos (11) de la al

menos una memoria digital (1 ) , siendo la pluralidad de posiciones de memoria (9) de cada segmento (11) leida secuencialmente;

-y al menos un comparador (3) conectado a al menos un puerto de lectura (12) de cada segmento (11 l. estando el al menos un comparador (3) adaptado pa ra compara r el al menos un dato almacenado (10) con al menos un dato de entrada (5) .

2. Sistema según la reivindicación 1, caracterizado por que cada segmento (11 ) comprende una pluralidad de puertos de lectura (12) , estando cada puerto de lectura (12) conectado a al menos un comparador (3) .

3. Sistema según cualquiera de las reivindicaciones anteriores, caracterizado por que cada puerto de lectura (12) está conectado a una pluralidad de comparadores (3) y por que la pluralidad de comparadores (3) están adaptados para comparar simultáneamente el al menos un dato almacenado (10) de cada segmento (11) con una pluralidad de datos de entrada (5) .

4. Sistema según cualquiera de las reivindicaciones anteriores, caracterizado por que cada posición

de memoria (9) tiene capacidad para una pluralidad de datos almacenados (10) , y por que los comparadores (3) están adaptados para comparar en un mismo cido de reloj la pluralidad de datos almacenados (10) en cada posición de memoria (9) con el al menos un dato de entrada (5) .

5. Sistema según cualquiera de las reivindicaciones anteriores, caracterizado por que comprende además medios de escritura adaptados para escribir sobre la pluralidad de posiciones de memoria (9) en orden secuencial.

6. Sistema según cualquiera de las reivindicaciones anteriores, caracterizado por que comprende además med ios de escritura adaptadOS para almacenar, procesar y controlar una pluralidad de etiquetas indicativas de una antigüedad de la pluralidad de datos almacenados (10) en la pluralidad de posiciones de memoria (9) .

7. Sistema según cualquiera de las reivindicaciones anteriores, caracterizado por que la al menos una memoria digital (1) , los medios de control (2) y los comparadores (3) están implementados en un circuito digital integrado.

8. Sistema según cualquiera de las reivind icaciones anteriores, caracterizado por que los datos almacenados (10) y el al menos un dato de entrada (5) son tramas de un protocolo de redundancia.

9. Sistema según cualquiera de las reivindicaciones 1 a 7, caracterizado por que los datos almacenados (10 ) y el al menos un dato de entrada (5) son direcciones de control de acceso al med io de un conmutador Ethernet.

10. Método de lectura y escritura de una memoria digital (1) , comprendiendo la memoria digital (1) una pluralidad de posiciones de memoria (9) agrupadas en una pluralidad de segmentos (11 ) , cada posición de memoria (9) con capacidad para al menos un dato almacenado (10) , caracterizado por que comprende: -leer en paralelo la pluralidad de segmentos (11) de la memoria digital (1) , siendo la pluralidad

de posiciones de memoria (9) de cada segmento (11) leída secuencialmente.

55. conectar cada segmento (11) con al menos un comparador (3) mediante al menos un puerto de lectura (12) ; -comparar el al menos un dato almacenado (10) con al menos un dato de entrada (5 ) .

. Método según la reivindicación 10, caracterizado por que comprende conectar cada segmento (11 ) con una pluralidad de comparadores (3) a través de una pluralidad de puertos de lectura (12) .

12. Método según cualquiera de las reivindicaciones 10-11, caracterizado por que comprende: -conectar cada puerto de lectura (12) con una pluralidad de comparadores (3) ; -comparar simultáneamente el al menos un dato almacenado (10) de cada segmento (11 ) con 65 una pluralidad de datos de entrada (5) .

13. Método según cualquiera de las reivindicaciones 10-12, caracterizado por que cada posición de memoria (9) tiene capacidad para una pluralidad de datos almacenados (10) y por que el método comprende además comparar la pluralidad de datos almacenados (10) con el al menos un dato de entrada (5) en un mismo ciclo de reloj.

14. Método según cualquiera de las reivindicaciones 10-13, caracterizado por que comprende además escribir sobre la pluralidad de posiciones de memoria (9) en orden secuencial.

15. Método según cualquiera de las reivindicaciones 10 a 14, caracterizado por que comprende además almacenar, procesar y controlar una pluralidad de etiquetas indicativas de una antigüedad 10 de los datos almacenados (10) en la pluralidad de posiciones de memoria (9) .

16. Método según cualquiera de las reivindicaciones 10-15, caracterizado por que los datos almacenados (10) y el al menos un dato de entrada (5) son tramas de un protocolo de redundancia.

17. Método según cualquiera de las reivindicaciones 10-15, caracterizado por que los datos almacenados (10) y el al menos un dato de entrada (5) son direcciones de control de acceso al medio de un conmutador Ethernet.

18. Programa de ordenador que comprende medios de código de programa de ordenador adaptados para realizar las etapas del método según cualquiera de las reivindicaciones 10 a 17, cuando dicho programa se ejecuta en un ordenador, un procesador digital de señal, un circuito integrado especifico de la aplicación, un microprocesador, un microcontrolador o cualquier otra forma de hardware programable.