Procedimiento, mecanismo y producto de programa informático para ejecutar varias tareas en un procesador multihilo y para proporcionar estimaciones del peor tiempo de ejecución.

Procedimiento para ejecutar varias tareas en un procesador multihilo,

MT, teniendo cada tarea, para cada recursohardware compartido de un conjunto predeterminado de recursos hardware compartidos en el procesador MT, unretardo temporal artificial asociado que se introduce cuando dichas tareas acceden a dicho recurso hardwarecompartido, comprendiendo el procedimiento las etapas de:

a. Establecer, para cada recurso hardware compartido y cada tarea a retrasar de forma artificial, el retraso artificial aaplicar a cada acceso de dicha tarea a dicho recurso hardware compartido;

b. Realizar los siguientes pasos (b1) a (b4) en el acceso de cada tarea a retrasar de forma artificial a cada recursohardware compartido en el conjunto predeterminado de recursos hardware compartidos en el procesador MT:

b1. Verificar si una solicitud está lista para ser enviada a dicho recurso hardware compartido;

En caso de resultado positivo,

b2. Verificar si el recurso hardware compartido está listo para aceptar dicha solicitud;

En caso de resultado positivo,

b3. Retrasar dicha solicitud según el retraso artificial establecido para dicho recurso hardware compartido;

b4. Permitir que la solicitud de la tarea acceda a dicho recurso hardware compartido.

Procedimiento, mecanismo y producto de programa informático para ejecutar varias tareas en un procesador multihilo y para proporcionar estimaciones del peor tiempo de ejecución [0001] La presente invención se refiere a un procedimiento para ejecutar varias tareas en un procesador multihilo (MT -multithreaded) , teniendo cada tarea, para cada recurso hardware compartido de un conjunto predeterminado de recursos hardware compartidos en el procesador MT, un valor de tiempo asociado correspondiente a un retraso artificial introducido cuando dicha tarea accede a dicho recurso hardware compartido. Más específicamente, la invención se refiere a un procedimiento para retrasar artificialmente los accesos de hilos que se ejecutan en un procesador multihilo a los recursos hardware compartidos de dicho procesador multihilo, estando configurado por el usuario el retraso artificial que se introduce en cada acceso a los recursos hardware compartidos.

La invención también se refiere a un mecanismo para ejecutar varias tareas en un procesador MT adecuado para llevar a cabo dicho procedimiento.

El mecanismo de la invención permite determinar la sensibilidad de una tarea determinada a los conflictos inter-tarea cuando la tarea se ejecuta en un procesador multihilo junto con otras tareas. El mecanismo también permite ejecutar simultáneamente varias tareas en tiempo real estricto (HRT - Hard Real-Time) junto con cero o más tareas en tiempo real no estricto (NHRT - Non Hard-Real Time) en el mismo procesador MT, de tal manera que se puede proporcionar una estimación segura del peor tiempo de ejecución (WCET - worst-case execution time) de las tareas HRT cuando se ejecutan en el procesador MT.

Preferiblemente, la invención se aplica en sistemas en tiempo real embebidos.

DEFINICIONES

Algunos de los términos en toda la siguiente descripción se refieren a componentes de sistema particulares. Como un experto en la técnica apreciará, las compañías de microprocesadores pueden referirse a un componente mediante diferentes nombres. Este documento no tiene la intención de distinguir entre componentes que difieren en el nombre, sino en la función.

Con el término "acople" o "acoples" o "conectar" se pretende expresar una conexión eléctrica directa o indirecta. Por lo tanto, si un primer dispositivo se acopla a un segundo dispositivo, esta conexión puede ser por medio de una conexión eléctrica directa o por medio de una conexión eléctrica indirecta a través de otros dispositivos y conexiones.

Con el término "procesador multihilo" se pretende expresar cualquier tipo de procesador que permite ejecutar más de un hilo al mismo tiempo y tiene algunos recursos hardware compartidos entre los hilos. Ejemplos de procesadores multihilo son: procesadores multihilo simultáneo (simultaneous multithreading processors) , procesadores multihilo de grano fino (fine grain multithreading processors) , procesadores multihilo de grano grueso (coarse grain multithreading processors) , procesadores multinúcleo (multicore processors) , o cualquier combinación de los mismos.

El término "tarea en tiempo real estricto" ("Hard Real-Time task") o "tarea HRT" se refiere a aquellas tareas que requieren una previsibilidad temporal absoluta (absolute time-predictability) de tal manera que nunca deberían perderse un límite temporal (deadline) de ejecución. En cambio, el término "tarea en tiempo real no estricto" ("Non-Hard Real-Time task") o "tarea NHRT" se refiere a las tareas con restricciones de tiempo real débiles o tareas en tiempo real débil (tareas SRT - soft-real time) , que están más relajadas en el sentido de que ocasionalmente podrían perderse límites temporales; o tareas sin restricciones de tiempo (tareas no en tiempo real o tareas NRT - Non Real-Time) .

El término "recurso" se refiere por defecto a un recurso hardware.

El término "interacción inter-tarea" ("inter-tarea interaction") o "conflicto inter-tarea" ("inter-tarea conflict") se refiere a la interacción/conflicto que sufre un hilo en los recursos debido a la ejecución de otras tareas. Es decir, es posible decir que una tarea sufre una interacción/conflicto inter-tarea en un recurso compartido cuando dicha tarea va a utilizar un recurso y éste es utilizado por cualquier otra tarea.

ESTADO DE LA TÉCNICA ANTERIOR

Tradicionalmente, los procesadores para mercados en tiempo real estricto embebidos (embedded hard realtime markets) típicamente se han caracterizado por una arquitectura sencilla, con pipelines cortas y ejecución en orden (in-order execution) con el fin de facilitar el cálculo del peor tiempo de ejecución (WCET) . Sin embargo, un porcentaje significativo de los sistemas de aplicación en tiempo real requieren o pueden mejorar su funcionalidad, si los procesadores pudieran proporcionar un rendimiento mayor que estas arquitecturas simples. Estas tareas van desde las aplicaciones en tiempo real débil como aplicaciones de codificación y decodificación de vídeo, hasta aplicaciones en tiempo real estricto como aplicaciones de automoción, aviónicas y sistemas de control industriales.

Los procesadores multihilo pueden ofrecer este rendimiento adicional requerido por los sistemas en tiempo real. Los procesadores Multihilo (MT) permiten la ejecución de varias tareas al mismo tiempo, lo que conduce tanto a un mayor rendimiento como a una reducción del número de procesadores requeridos en un sistema dado. Por otra parte, la compartición de recursos en estos procesadores les permite tener unos buenos ratios "rendimiento/coste" y "rendimiento/consumo de energía". Esta característica hace que los procesadores MT sean una buena opción para los sistemas en tiempo real embebidos.

Sin embargo, al mismo tiempo, la compartición de recursos provoca que la ejecución de tareas pase a ser altamente variable, puesto que las tareas interactúan de manera desconocida con las otras tareas en tiempo real estricto (HRT) y en tiempo real no estricto (NHRT) . Esto hace que los procesadores MT sean inadecuados para sistemas en tiempo real embebidos. Es decir, hay un gran inconveniente que impide el uso de procesadores MT en los sistemas en tiempo real embebidos: el tiempo de ejecución de las tareas en un procesador MT se vuelve altamente imprevisible dado que las tareas comparten recursos dinámicamente en tiempo de ejecución de forma imprevisible. Bajo estas circunstancias, no se pueden garantizar las restricciones en tiempo real de los sistemas embebidos.

A nivel de hardware, la imprevisibilidad introducida por la compartición de recursos se ha evitado proporcionando un aislamiento total en la ejecución de tareas en tiempo-real estricto. Es decir, el hardware permite la ejecución de una tarea HRT y tareas NHRT proporcionando una ejecución de la tarea HRT libre de interacciones. En esta categoría se encuentran los documentos [A. El-Haj-Mahmoud, A. S. AL-Zawawi, A. Anantaraman, and E. Rotenberg. Virtual Multiprocessor: An Analyzable, High-Performance Microarchitecture for Real-Time Computing. Proceedings of the 2005 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES’05) , pp. 213-224, September 2005] y[Infineon Technologies AG. TricoreTM2 Architecture Manual]. En el primer documento, los autores proponen una arquitectura que proporciona una ejecución libre de interferencias entre los hilos en una arquitectura MT que permite la ejecución de hilos HRT. Esta propuesta exige que la arquitectura del procesador sea alterada de manera que no se permite que haya interacción entre hilos. En el último, se permite la ejecución de una tarea NHRT en segundo plano (background) sólo cuando la tarea HRT en primer plano (foreground) experimenta una ausencia de instrucción en caché (instruction cache miss) . La tarea NHRT nunca puede retrasar la tarea HRT.

Con el fin de lograr el aislamiento completo, la arquitectura propuesta impide cualquier interferencia entre los hilos. Esto requiere cambios significativos a nivel de arquitectura: todos los buffers se duplican para cada hilo, las unidades funcionales son asumidas totalmente segmentadas (pipelined) por lo que cada una puede procesar una nueva operación por ciclo, las cachés normales no están permitidas, etc.

En una solicitud de patente europea (del mismo solicitante de la presente solicitud) con el título "Un procesador multihilo y un mecanismo y un procedimiento para ejecutar una tarea en tiempo real estricto en un procesador multihilo" ("A multithreaded processor and a mechanism and a method for executing one hard real-time task in a multithreaded processor") se propone un procedimiento y un mecanismo para ejecutar una tarea HRT simple junto con varias tareas NRT y tareas SRT. En la solución propuesta, el... [Seguir leyendo]

1. Procedimiento para ejecutar varias tareas en un procesador multihilo, MT, teniendo cada tarea, para cada recurso hardware compartido de un conjunto predeterminado de recursos hardware compartidos en el procesador MT, un retardo temporal artificial asociado que se introduce cuando dichas tareas acceden a dicho recurso hardware compartido, comprendiendo el procedimiento las etapas de:

a. Establecer, para cada recurso hardware compartido y cada tarea a retrasar de forma artificial, el retraso artificial a aplicar a cada acceso de dicha tarea a dicho recurso hardware compartido;

b. Realizar los siguientes pasos (b1) a (b4) en el acceso de cada tarea a retrasar de forma artificial a cada recurso hardware compartido en el conjunto predeterminado de recursos hardware compartidos en el procesador MT: b1. Verificar si una solicitud está lista para ser enviada a dicho recurso hardware compartido; En caso de resultado positivo, b2. Verificar si el recurso hardware compartido está listo para aceptar dicha solicitud; En caso de resultado positivo,

b3. Retrasar dicha solicitud según el retraso artificial establecido para dicho recurso hardware compartido; b4. Permitir que la solicitud de la tarea acceda a dicho recurso hardware compartido.

2. Procedimiento de acuerdo con la reivindicación 1, que comprende además las etapas de:

c. Almacenar el retraso artificial establecido en la etapa (a) ;

d. Obtener, antes de la etapa (e) , el retraso artificial almacenado.

3. Mecanismo adaptado para ejecutar varias tareas en un procesador multihilo; MT; de acuerdo con el procedimiento de la reivindicación 1, teniendo cada tarea, para cada recurso hardware compartido de un conjunto predeterminado de recursos hardware compartidos en el procesador MT, un retardo temporal artificial asociado que se introduce cuando dicha tarea accede a dicho recurso hardware compartido, en el que el mecanismo comprende medios para establecer, para cada recurso hardware compartido en el conjunto predeterminado de recursos hardware compartidos y cada tarea a retrasar de forma artificial, el retraso artificial a aplicar a cada acceso de dicha tarea a dicho recurso hardware compartido;

medios para verificar si una solicitud está lista para ser enviada a dicho recurso compartido;

medios para verificar si el recurso compartido está listo para aceptar dicha solicitud;

medios para retrasar dicha petición según el retraso artificial establecido para dicho recurso compartido; y

medios para permitir que la solicitud de la tarea acceda a dicho recurso compartido.

4. Procesador multihilo (MT) caracterizado por el hecho de que comprende un mecanismo para ejecutar varias tareas de acuerdo con la reivindicación 3.

5. Producto de programa informático que comprende instrucciones de programa para hacer que un ordenador realice el procedimiento para ejecutar varias tareas en un procesador MT según una cualquiera de las reivindicaciones 1 ó 2.

6. Producto de programa informático según la reivindicación 5, incorporado en medios de almacenamiento.

7. Producto de programa informático según la reivindicación 5, portado en una señal portadora.

8. Procedimiento para ejecutar varias tareas en tiempo real estricto (HRT) simultáneamente en un procesador multihilo (MT) que comprende las etapas de:

e. Establecer un conjunto de parámetros relacionados con la configuración del procesador MT;

f. Determinar, de acuerdo con el conjunto de parámetros establecido, el retardo máximo, para cada recurso de un conjunto predeterminado de recursos compartidos por al menos dos de las tareas HRT en el procesador MT, que cada una de dichas tareas HRT puede sufrir cuando accede a dicho recurso compartido;

g. Ejecutar cada tarea HRT de forma aislada de acuerdo con el procedimiento para ejecutar varias tareas en un procesador MT de acuerdo con cualquiera de las reivindicaciones 1 o 2, en el que el retraso artificial establecido

para la tarea es el retardo máximo determinado en el paso (f) y se retrasa cada tarea HRT al acceder a cada recurso compartido de acuerdo con dicho retraso artificial;

h. Calcular el peor tiempo de ejecución (WCET) para cada tarea HRT de acuerdo con la ejecución de dicha tarea HRT en la etapa (g) , que tiene en cuenta el conjunto de parámetros de la configuración del procesador MT;

i. verificar si el WCET calculado para cada tarea HRT se ajusta a una determinada planificación adecuada de las tareas HRT;

En caso de resultado positivo,

j. Configurar el procesador MT en un modo en el que no se introduce retraso artificial a las tareas HRT cuando dichas tareas acceden a recursos compartidos;

k. Ejecutar las tareas HRT de acuerdo con dicho modo.

9. Procedimiento para ejecutar varias tareas en tiempo real estricto (HRT) simultáneamente en un procesador MT según la reivindicación 8, y ejecutar simultáneamente al menos una tarea NHRT, en el que, en la etapa (f) , el conjunto predeterminado de recursos son compartidos por al menos dos tareas de cualquiera de las tareas HRT y la tarea NHRT, en el que, en la etapa (j) , ninguna de las tareas HRT o la tarea NHRT es retrasada de forma artificial al acceder a un recurso compartido, y en el que, en la etapa (k) , se ejecutan las tareas HRT y la tarea NHRT.

10. Procedimiento según una cualquiera de las reivindicaciones 8 ó 9, en el que el conjunto de parámetros de la configuración del procesador MT comprende al menos uno de los siguientes parámetros: el número de tareas HRT a ejecutar, el número de tareas NHRT a ejecutar, y la política de arbitraje que concede acceso a cada recurso compartido.

11. Procedimiento según una cualquiera de las reivindicaciones 8 a 10, en el que, en caso de resultado negativo en la etapa (i) , el control del procedimiento pasa a la etapa (e) .

12. Procedimiento según una cualquiera de las reivindicaciones 8 a 11, en el que, en la etapa (i) , el WCET calculado para cada tarea HRT se ajusta a la planificación determinada adecuada de las tareas HRT cuando el WCET de cada tarea HRT es menor que el límite temporal de dicha tarea HRT.

13. Mecanismo adaptado para ejecutar varias tareas HRT simultáneamente en un procesador multihilo (MT) caracterizado por el hecho de que comprende medios para establecer un conjunto de parámetros relativos a la configuración del procesador MT; medios para determinar, de acuerdo con el conjunto de parámetros establecido, el retardo máximo, para cada recurso de un conjunto predeterminado de recursos compartidos por al menos dos de las tareas HRT en el procesador MT, que cada una de dichas tareas HRT pueden sufrir cuando accede a dicho recurso compartido; el mecanismo según la reivindicación 3 para ejecutar varias tareas en un procesador MT para ejecutar cada tarea HRT de forma aislada, en el que el retraso artificial establecido para la tarea es el retraso máximo y se retrasa cada tarea HRT cuando accede a cada recurso compartido de acuerdo con dicho retardo artificial; medios para calcular el peor tiempo de ejecución (WCET) para cada tarea HRT, que tiene en cuenta el conjunto de parámetros de la configuración del procesador MT; medios para verificar si el WCET calculado para cada tarea HRT se ajusta a una determinada planificación adecuada de las tareas HRT; medios para configurar el procesador MT en un modo en el cual no se introduce retraso artificial a las tareas HRT cuando dichas tareas acceden a recursos compartidos; medios para ejecutar las tareas HRT de acuerdo con dicho modo.

14. Mecanismo para ejecutar varias tareas en tiempo real estricto (HRT) simultáneamente en un procesador MT según la reivindicación 13, y ejecutar simultáneamente al menos una tarea NHRT, en el que, el conjunto predeterminado de recursos son compartidos por al menos dos tareas de cualquiera de las tareas HRT y la tarea NHRT, en el que, ninguna de las tareas HRT o la tarea NHRT es retrasada artificialmente cuando accede a un recurso compartido, y en el que los medios para ejecutar las tareas HRT ejecuta las tareas HRT y la tarea NHRT.

15. Procesador multihilo (MT) caracterizado por el hecho de que comprende un mecanismo para ejecutar varias tareas de acuerdo con una cualquiera de las reivindicaciones 13 ó 14.

16. Producto de programa informático que comprende instrucciones de programa para hacer que un ordenador realice el procedimiento para ejecutar varias tareas en un procesador MT según una cualquiera de las reivindicaciones 8 a 12.

REFERENCIAS CITADAS EN LA DESCRIPCIÓN

Esta lista de referencias citadas por el solicitante es únicamente para la comodidad del lector. No forma parte del documento de la patente europea. A pesar del cuidado tenido en la recopilación de las referencias, no se pueden 5 excluir errores u omisiones y la EPO niega toda responsabilidad en este sentido.

Literatura diferente de patentes citadas en la descripción • A. EL-HAJ-MAHMOUD; A. S. AL-ZAWAWI ; A. ANANTARAMAN ; E. ROTENBERG. Virtual Multiprocessor: An Analyzable, High-Performance Microarchitecture for Real-Time Computing.

Proceedings of the 2005 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES’05, September 2005.

21. 224

• THOMAS LUNDQVIST ; PER STENSTRÖM. Timing Anomalies in Dynamically Scheduled Microprocessors Thomas. Proceedings of the 20th IEEE Real- Time Systems Symposium (RTSS, December 1999, 12-21

• JAN REINEKE ; BJÖRN WACHTER ; STEPHAN THESING ; REINHARD WILHELM ; ILIA POLIAN ; JOCHEN EISINGER ; BERND BECKER. A Definition and Classification of Timing Anomalies. 7th International Workshop on Worst-Case Execution Time (WCET) Analysis, July 2006 [0091]

• ALEXANDRU ANDREI ; PETRU ELES ; ZEBO PENG ; JAKOB ROSEN. Predictable Implementation of Real-Time Applications on Multiprocessor Systems-on-Chip. Proceedings of the 21 st International Conference on VLSI Design, 2008, 103110 [0092]