Sistema de procesamiento de datos y dispositivo de computación.

El sistema comprende:

- unos dispositivos de computación que procesan en paralelo parte de un algoritmo, de manera concurrente y sincronizada;

- unos medios de comunicación que interconectan a dichos dispositivos de computación entre sí;

- unos medios de control conectados con dichos medios de comunicación y con dichos dispositivos de computación y previstos para controlarlos;

- unos medios de sincronización que comprenden, en uno (T1) o más de dichos dispositivos de computación, una unidad de monitorización y desbloqueo (Ua) configurada para comparar los datos de las entradas (a, b) de su dispositivo de computación (T1) con una condición lógica determinada y, si existe coincidencia, generar una señal de desbloqueo de una unidad de procesamiento (U1) del dispositivo de computación (T1).

El dispositivo está configurado para formar, con otros dispositivos, un sistema de procesamiento como el propuesto.

Sistema de procesamiento de datos y dispositivo de computación.

Sector de la técnica La presente invención concierne, en general, y en un primer aspecto, a un sistema de procesamiento de datos formado por unos dispositivos de computación operando en paralelo para procesar, en su conjunto, un algoritmo, de manera concurrente y sincronizada, dividiendo el algoritmo en partes y distribuyéndolas entre los dispositivos de computación, y en particular a un sistema que comprende unos medios de sincronización integrados en los dispositivos de computación.

Un segundo aspecto de la invención concierne a un dispositivo de computación configurado para formar, con otros dispositivos de computación análogos, un sistema de procesamiento como el propuesto por el primer aspecto.

Estado de la técnica anterior Son conocidos, desde hace mucho tiempo, sistemas de procesamiento en paralelo orientados a concurrencia que ejecutan una tarea, algoritmo o aplicación con un cierto grado de complicación, mediante la utilización de una pluralidad de procesadores interconectados, con una capacidad de procesamiento limitada, de manera que no se requiere de la inclusión de elementos con una alta capacidad de procesamiento, que en ocasiones, en función de las tareas a ejecutar, podrían estar infrautilizados, sino que el trabajo a realizar se reparte entre parte o la totalidad de los referidos procesadores de capacidad de procesamiento limitada.

Uno de tales procesadores de capacidad de procesamiento limitada que alcanzó gran fama tiempo atrás, para constituir dichos sistemas de procesamiento paralelo y concurrente, es el conocido como "transputer", cuya utilización con el paso de los años disminuyó considerablemente.

Existen numerosos documentos de patente que describen propuestas relativas a dichos sistemas de procesamiento en paralelo. A continuación se exponen algunos de ellos, como muestra significativa del estado de la técnica.

En la solicitud de patente EP-A-0570729 se describen, en su apartado de estado de la técnica, diferentes propuestas de sistemas que incluyen procesadores trabajando en paralelo, incluyendo "transputers" (tal como el "Inmos Transputer T800") , topologías de interconexionado en forma de hipercubo, etc. En particular, en dicha solicitud se propone un sistema para procesar de manera masiva, y en paralelo, diferentes aplicaciones, que incorpora una pluralidad de elementos con capacidad de memoria y de multiprocesamiento, o PMEs, que en dicha solicitud se definen como unos elementos muy similares a los conocidos de manera convencional como "transputers". Según un ejemplo de realización descrito en EP-A-0570729, se propone interconectar a los PMEs mediante una topología de hipercubo modificada, que básicamente consiste en combinar una topología de hipercubo con una de anillo. Asimismo, se indica que cada PME tiene capacidad para procesar tanto instrucciones SIMD como MIMD. También se indica en EP-A0570729 la posibilidad de "customizar", es decir programar a medida, los diseños lógicos o las funciones a ejecutar por unas sub-secciones de cada PME.

La patente US5016163 propone un sistema de procesamiento en paralelo formado por una pluralidad de "transputers" interconectados, por ejemplo mediante un hipercubo. El sistema incluye unos medios de control que dividen un algoritmo en sub-algoritmos, los cuales asignan a cada uno de los "transputers", con el fin de realizar un procesamiento en paralelo de dicho algoritmo.

Otros de tales procesadores de capacidad de procesamiento limitada son los denominados ASIP (Procesador de Aplicación de Instrucción Específica) , los cuales en ocasiones incluyen además de unas instrucciones básicas unas instrucciones a medida, o "custom", tal como se describe, por ejemplo, en los siguientes dos documentos de patente.

En la solicitud de patente EP-A-1701250 se propone un microordenador formado por un microprocesador con capacidad para funcionar en un modo ASIP, para el cual el microprocesador se diseña con un conjunto de instrucciones básicas y con un conjunto de instrucciones "custom", es decir a medida, con su correspondiente hardware a medida. En dicha solicitud se indican como ASIPs disponibles comercialmente los siguientes: "Altera's NIOS", descrito en "Nios embedded processor system developement", "Tensilica's Xtensa", descrito por R.E. González en "Xtensa: A configurable and extensible processor", IEEE Micro, 20 (2) , 2000; y "HP's and STMicroelectronics' Lx", descritos por P. Faraboschi et al. en "Lx: a technology platform for customizable VLIW embedded processing", Proc. of ISCA, 2000.

En la patente US7398502 se propone un método y un sistema para realizar un procesamiento concurrente con una FPGA. En su apartado de estado de la técnica se dan por conocidas propuestas relativas a la utilización de un conjunto de instrucciones a medida en un ASIP, adicionales a un conjunto de instrucciones convencionales, así como de arquitecturas de memoria también a medida.

Uno de los grandes problemas que afectan a la mayoría de sistemas de procesamiento en paralelo orientados a concurrencia, y que hizo que los mismos no tuviesen tanto éxito como se preveía en un principio, es el relativo a la sincronización de los diferentes elementos del sistema, que puede provocar desde errores en los resultados, debidos por ejemplo a que el inicio del procesamiento por parte de un segundo procesador del sistema de unos datos disponibles en una memoria se produzca antes de que un primer procesador haya registrado el resultado de su procesamiento en dicha memoria, hasta una baja eficiencia del sistema en general, por ejemplo por tener trabajando a dicho segundo procesador antes de lo debido.

Es conocida la utilización, en tales sistemas, de mecanismos de sincronización implementados mediante software, en particular se tiene conocimiento de la utilización de la instrucción denominada "alting" en el lenguaje de procesos OCCAM.

Explicación de la invención Los presentes inventores consideran que es necesario ofrecer una alternativa al estado de la técnica que supere los inconvenientes de los que adolecen los sistemas convencionales, en particular por lo que se refiere a los medios utilizados para llevar a cabo la mencionada sincronización.

Con tal fin, la presente invención concierne, en un primer aspecto, a un sistema de procesamiento de datos, que comprende de manera en sí conocida:

- una pluralidad de dispositivos de computación operando en paralelo para procesar, cada uno de ellos, parte de un algoritmo, de manera concurrente y sincronizada;

- unos medios de comunicación configurados para interconectar, por unas respectivas entradas y salidas de datos, a dichos dispositivos de computación entre sí; y

- unos medios de control en conexión con dichos medios de comunicación y con dichos dispositivos de computación, y previstos para controlarlos.

A diferencia de los sistemas convencionales, el propuesto por el primer aspecto de la presente invención comprende unos medios de sincronización que comprenden, en parte o en la totalidad de dichos dispositivos de computación, una unidad de monitorización y desbloqueo, en conexión con las entradas de su respectivo dispositivo de computación y configurada para comparar los datos de dichas entradas con unos datos relativos a una condición lógica determinada, y para generar una señal de desbloqueo con el fin de desbloquear el funcionamiento, previamente bloqueado, de como mínimo una unidad de procesamiento del dispositivo de computación, en función de que exista coincidencia de datos en dicha comparación.

Se consigue así mantener en un estado de suspensión, o "standby", a parte del dispositivo de computación, como mínimo a su unidad de procesamiento, mientras los datos disponibles en su entrada no son los adecuados para su procesamiento por su parte, es decir no cumplen la mencionada condición lógica determinada. Con ello se logra no hacer trabajar inútilmente a dicha unidad de procesamiento cuando no es necesario, disminuyendo así el consumo total del sistema y aumentando la eficiencia y el aprovechamiento de los recursos del sistema al mantener en suspensión a las unidades de procesamiento, y opcionalmente a otros elementos asociados a las mismas, de varios de los dispositivos de computación incluidos en el sistema, cuando no es necesario que estén operando.

Por lo que se refiere a la entrada en el mencionado estado de suspensión, es decir al bloqueo de la unidad de procesamiento de un dispositivo de computación, para llevarla a cabo en el sistema...

1. Sistema de procesamiento de datos, del tipo que comprende:

- una pluralidad de dispositivos de computación (T1-T5) operando en paralelo para procesar, cada uno de ellos, parte de un algoritmo, de manera concurrente y sincronizada;

- unos medios de comunicación configurados para interconectar, por unas respectivas entradas y salidas de datos, a dichos dispositivos de computación (T1-T5) entre sí;

- unos medios de control en conexión con dichos medios de comunicación y con dichos dispositivos de computación (T1-T5) , y previstos para controlarlos;

estando dicho sistema de procesamiento de datos caracterizado porque comprende unos medios de sincronización que comprenden, en al menos parte (T1-T4) de dichos dispositivos de computación (T1-T5) , una unidad de monitorización y desbloqueo (Ua) , en conexión con las entradas (a, b) de su respectivo dispositivo de computación (T1-T4) y configurada para comparar los datos de dichas entradas (a, b) con unos datos relativos a una condición lógica determinada, y para generar una señal de desbloqueo con el fin de desbloquear el funcionamiento, previamente bloqueado, de al menos una unidad de procesamiento (U1) del dispositivo de computación (T1-T4) , en función de que exista coincidencia de datos en dicha comparación.

2. Sistema según la reivindicación 1, caracterizado porque dichos medios de sincronización comprenden, en al menos parte (T1-T4) de dichos dispositivos de computación (T1-T5) , unos medios de bloqueo/desbloqueo configurados para bloquear el funcionamiento de al menos dicha unidad de procesamiento (U1) de su respectivo dispositivo de computación (T1-T4) .

3. Sistema según la reivindicación 2, caracterizado porque dichos medios de bloqueo/desbloqueo están en conexión con dichos medios de control y con dicha unidad de procesamiento (U1) de su respectivo dispositivo de computación (T1-T4) , y configurados para llevar a cabo dicho bloqueo del funcionamiento de al menos dicha unidad de procesamiento (U1) bajo el mando de dichos medios de control.

4. Sistema según la reivindicación 2 ó 3, caracterizado porque dichos medios de bloqueo/desbloqueo están conectados con una salida de dicha unidad de monitorización y desbloqueo (Ua) , y configurados para llevar a cabo dicho desbloqueo del funcionamiento de al menos dicha unidad de procesamiento (U1) , en respuesta a la recepción de dicha señal de desbloqueo.

5. Sistema según la reivindicación 2, caracterizado porque dichos medios de bloqueo/desbloqueo comprenden a dicha unidad de monitorización y desbloqueo (Ua) , y porque ésta (Ua) está configurada también para generar una señal de bloqueo con el fin de bloquear el funcionamiento de al menos dicha unidad de procesamiento (U1) , en función de que exista discrepancia de datos en dicha comparación.

6. Sistema de procesamiento de datos según cualquiera de las reivindicaciones anteriores, caracterizado porque cada uno de dichos dispositivos de computación (T1-T5) comprende al menos una unidad de procesamiento (U1) , al menos una memoria interna (M1-M3) , y, formando parte de dichos medios de comunicación, al menos dos puertos de entrada de datos (Ps2a, Ps2b) y al menos un puerto de salida de datos (Pm) .

7. Sistema según la reivindicación 6, caracterizado porque el conjunto de todas las memorias internas (M1-M3) de todos los dispositivos de computación (T1-T5) conforman el total de memoria del sistema utilizable para el procesamiento de dicho algoritmo.

8. Sistema según cualquiera de las reivindicaciones anteriores, caracterizado porque dichos medios de control están configurados para controlar a dichos medios de comunicación para realizar una interconexión lógica entre dichos dispositivos de computación (T1-T5) implementando una determinada topología, seleccionable de entre una pluralidad de topologías, y/o para que dichos medios de comunicación permitan que el sistema opere según una técnica de multidifusión.

9. Sistema según la reivindicación 8, caracterizado porque dichos medios de control tienen acceso a datos referentes a dicha pluralidad de topologías, las cuales son predeterminadas, y porque están configurados para seleccionar dicha topología determinada, de manera automática o previa intervención de un usuario, seleccionando los datos referentes a la misma.

10. Sistema según la reivindicación 9, caracterizado porque dicha topología determinada es una topología de hipercubo de n dimensiones.

11. Sistema según la reivindicación 8, 9 y 10, caracterizado porque dichos medios de control están configurados para controlar a dichos dispositivos de conmutación (T1-T5) para que adapten su funcionamiento a la topología implementada y/o a dicha multidifusión.

12. Sistema según cualquiera de las reivindicaciones8a11, caracterizado porque al menos parte de las conexiones entre dispositivos de conmutación (T1-T5) pertenecientes a dichos medios de comunicación, están configuradas para implementar una función adicional a la de la simple transmisión de datos.

13. Sistema según la reivindicación 12, caracterizado porque cada una de dichas conexiones configuradas para implementar dicha función adicional comprende una memoria interna para almacenar de manera temporal unos datos a transmitir a un dispositivo de computación (T1-T5) , bajo el control de dichos medios de control.

14. Sistema según cualquiera de las reivindicaciones anteriores, caracterizado porque cada uno de dichos dispositivos de computación (T1-T5) es un transputer.

15. Sistema según cualquiera de las reivindicaciones anteriores, caracterizado porque todos dichos dispositivos de computación (T1-T5) tienen una arquitectura interna igual en al menos la mayor parte de sus componentes.

16. Sistema según la reivindicación 15, caracterizado porque dicha unidad de procesamiento (U1) es una unidad aritmético-lógica, ALU, y porque existen diferentes diseños de ALUs en función de la tarea a ejecutar para la cual se encuentre dedicado el dispositivo de computación (T1-T5) al que pertenezcan.

17. Sistema según la reivindicación 15 ó 16, caracterizado porque es modular, siendo cada uno de dichos dispositivos de computación (T1-T5) un módulo, y estando dichos medios de control configurados para seleccionar, de manera automática o previa intervención de un usuario, el número y tipo de módulos a incluir en el sistema, así como las conexiones entre los mismos, en función del algoritmo a ejecutar.

18. Sistema según cualquiera de las reivindicaciones anteriores, caracterizado porque está previsto para realizar un procesamiento de datos en tiempo real.

19. Dispositivo de computación, del tipo que está configurado para procesar parte de un algoritmo, de manera concurrente y sincronizada con otros dispositivos de computación análogos, caracterizado porque comprende unos medios de sincronización que comprenden una unidad de monitorización y desbloqueo (Ua) , en conexión con las entradas (a, b) de dicho dispositivo de computación (T1) y configurada para comparar los datos de dichas entradas (a, b) con unos datos relativos a una condición lógica determinada, y para generar una señal de desbloqueo con el fin de desbloquear el funcionamiento, previamente bloqueado, de al menos una unidad de procesamiento (U1) del dispositivo de computación (T1) , en función de que exista coincidencia de datos en dicha comparación.

20. Dispositivo de computación según la reivindicación 19, caracterizado porque reúne las características técnicas de uno de dichos dispositivos de computación (T1-T5) del sistema propuesto según cualquiera de las reivindicaciones 1 a 18.

OFICINA ESPAÑOLA DE PATENTES Y MARCAS

Nº solicitud: 200902000

ESPAÑA

Fecha de presentación de la solicitud: 16.10.2009

Fecha de prioridad:

INFORME SOBRE EL ESTADO DE LA TECNICA

51 Int. Cl. : G06F15/163 (2006.01) G06F15/80 (2006.01)

DOCUMENTOS RELEVANTES

4. 54. A US 5404550 A (HORST) 04.04.1995, columna 6, línea.

3. 63; figuras 2, 4. 1-20 A US 4574348 A (SCALLON) 04.03.1986, columna 1, línea 59 - columna 2, línea 3; columna 5, 1-20 líneas 19-53; figura 5. A US 5175824 A (SODERBERY et al.) 29.12.1992, columna 1, línea 66 - columna 2, línea 20; 1-20 columna 4, línea.

2. 50. Categoría de los documentos citados X: de particular relevancia Y: de particular relevancia combinado con otro/s de la misma categoría A: refleja el estado de la técnica O: referido a divulgación no escrita P: publicado entre la fecha de prioridad y la de presentación de la solicitud E: documento anterior, pero publicado después de la fecha de presentación de la solicitud El presente informe ha sido realizado • para todas las reivindicaciones • para las reivindicaciones nº : Fecha de realización del informe 24.03.2011 Examinador M. Alvarez Moreno Página 1/4

INFORME DEL ESTADO DE LA TÉCNICA

Nº de solicitud: 200902000

Documentación mínima buscada (sistema de clasificación seguido de los símbolos de clasificación) G06F Bases de datos electrónicas consultadas durante la búsqueda (nombre de la base de datos y, si es posible, términos de búsqueda utilizados) INVENES, EPODOC, WPI

Informe del Estado de la Técnica Página 2/4

OPINIÓN ESCRITA

Nº de solicitud: 200902000

Fecha de Realización de la Opinión Escrita: 24.03.2011

Declaración

Se considera que la solicitud cumple con el requisito de aplicación industrial. Este requisito fue evaluado durante la fase de examen formal y técnico de la solicitud (Artículo 31.2 Ley 11/1986) .

Base de la Opinión.

La presente opinión se ha realizado sobre la base de la solicitud de patente tal y como se publica.

Informe del Estado de la Técnica Página 3/4

OPINIÓN ESCRITA

Nº de solicitud: 200902000

1. Documentos considerados.

A continuación se relacionan los documentos pertenecientes al estado de la técnica tomados en consideración para la realización de esta opinión.

2. Declaración motivada según los artículos 29.6 y 29.7 del Reglamento de ejecución de la Ley 11/1986, de 20 de marzo, de Patentes sobre la novedad y la actividad inventiva; citas y explicaciones en apoyo de esta declaración Los documentos D01, D02, D03 y D04 se citan a efectos de mostrar el estado de la técnica. Todos ellos se refieren a sistemas de procesamiento paralelo y solucionan el problema de sincronización de formas diferentes. El documento D01 [columna 2, líne.

49. columna 3, línea 7; columna 3, líne.

55. columna 4, línea 4; columna 4, línea.

4. 54] incorpora un "controlador de sincronización" asociado a cada procesador. Un procesador entra en estado de espera cuando detecta (mediante las instrucciones a ejecutar) que debe sincronizarse con otros procesadores. El "controlador de sincronización" es el encargado de generar una señal de sincronización y detectar las solicitudes de sincronización de otros procesadores; el procesador reanuda el procesamiento cuando se lo notifica su "controlador de sincronización" asociado. Por lo tanto el bloqueo (parada) y el desbloqueo (reanudación) se realizan en función de las instrucciones programación. El documento D02 [figuras 2 y 4; columna 6, línea.

3. 63] dispone de una "lógica de sincronización" común que se encarga de proporcionar las señales de sincronización a los procesadores en función de una señal de indicación de estado recibida desde el resto de los procesadores. En el documento D03 [columna 1, líne.

59. columna 2, línea 3; columna 5, líneas 19 53; figura 5] la sincronización se consigue mediante la utilización de una única instrucción compleja, transmitida simultáneamente a las unidades de procesamiento, que fuerza la sincronización en la ejecución. El documento D04 [columna 1, líne.

66. columna 2, línea 20; columna 4, línea.

25. 50] muestra una arquitectura basada en el flujo de tareas. Existe una lista enlazada de paquetes de memoria, los cuales contienen un elemento de datos, la siguiente instrucción a ejecutar y un enlace al siguiente paquete de memoria. Dentro del paquete de memoria existe un bit de bloqueo que es utilizado por las diversas instrucciones a ejecutar para realizar la sincronización. Puede verse que todos los documentos anteriores muestran sistemas donde la sincronización viene determinada por elementos externos a la unidad de procesamiento (instrucciones del programa o controladores que manejan señales de sincronización) lo cual difiere completamente de la solución aportada por la solicitud en estudio. En ninguno de los casos cada unidad de procesamiento dispone, de forma independiente, de medios para comparar dos datos de entrada y en función de una condición lógica determinada generar una señal de desbloqueo.

A la vista de los documentos anteriores, tanto el sistema como el dispositivo definidos en las reivindicaciones independientes 1 y 19 se considera que tienen novedad y actividad inventiva según los artículos 6.1 y 8.1 de la Ley de Patentes.

De igual forma las sucesivas reivindicaciones dependientes 2-18 y 20 tienen novedad y actividad inventiva según los artículos 6.1 y 8.1 de la Ley de Patentes.

Informe del Estado de la Técnica Página 4/4