Planificación de multi-procesadores.

Un método de planificar tareas de procesamiento en un aparato de cálculo de multi-procesadores (100,

200),estando las tareas asociadas con al menos un plazo respectivo, implicando el método la comunicación entre unafunción de planificación de tareas global (102, 202) y una pluralidad de funciones de planificación de tareas locales(112, 212), estando cada función de planificación de tareas local asociada con un procesador (108, 208) respectivo,que comprende:

- guardar, en la función de planificación de tareas global, información del estatus actualizada relativa a :

- cualquier procesador en reposo,

- momentos del tiempo en los que se espera que cualquier procesador esté en reposo,

- valores de relajación asociados con cualquier procesador,

comprendiendo también el método:

- planificar, en la función de planificación de tareas global, las tareas de:

- enviar tareas a las funciones de planificación de tareas locales, estando el envío condicionado por lainformación de estatus,

- llamar a tareas desde las funciones de planificación de tareas locales en algún procesador que noesté en reposo y enviar alguna tarea llamada a una función de planificación de tareas local en unprocesador que no esté en reposo,

- recibir, desde las funciones de planificación de tareas locales, tareas interrumpidas y enviar cualquiertarea interrumpida recibida a una función de planificación de tareas local, estando el envíocondicionado a la información de estatus,

donde el hecho de guardar la información de estatus actualizada comprende:

- recibir, desde cada función de planificación de tareas local, un valor de relajación de planificación calculadorespectivo que es la diferencia mínima entre los plazos de finalización para tareas y los tiempos definalización de tarea esperados con tareas actualmente enviadas a cada procesador respectivo, ydonde la planificación de una tarea comprende:

- comprobar si existe un procesador en reposo y, si es así, enviar la tarea a la función de planificación detareas local del procesador en reposo,

si no:

- calcular un tiempo de finalización esperado de la tarea, siendo el cálculo relativo a una situación que implicaa la existencia de un procesador en reposo,

- calcular un valor de relajación de tarea como una diferencia entre el plazo para la tarea y el tiempo definalización esperado calculado para la tarea,

- comprobar si la relajación de la tarea calculada es mayor que una diferencia entre el momento del tiempomás temprano en el que algún procesador se espera que esté en reposo y el tiempo actual y, si es así, enviarla tarea a la función de planificación de tareas local de ese procesador,

si no:

- enviar la tarea a la función de planificación de tareas local del procesador que tenga el mayor valor derelajación de planificación.

Planificación de multi-procesadores Campo técnico La presente invención se refiere a la planificación de tareas de procesamiento en un sistema que tiene una pluralidad de unidades de procesamiento.

Antecedentes La planificación de tareas de software ha sido extensamente investigada durante más de cuarenta años, y continúa siendo un tema de intensa investigación y desarrollo. Una razón es que nunca hay una planificación ideal. Sin embargo, la planificación de tareas en un solo procesador es muy bien conocida, y se ha probado que heurísticas bien conocidas resultan óptimas para tareas en tiempo real en un único procesador.

Las planificaciones de tareas sobre un grupo de procesadores están menos exploradas. La dimensión añadida de múltiples procesadores da lugar a varios planteamientos que gestionan la complejidad añadida. Ejemplos de planteamientos básicos incluyen:

Planificación global, migración completa. En este planteamiento hay una sola cola para todos los procesadores (planificación global) y migración completa, es decir los procesadores puede en cualquier momento interrumpir una tarea en favor de una tarea de mayor prioridad, dejando que la tarea interrumpida sea manejada más tarde por otro procesador. Planificación global, migración limitada. En este planteamiento hay también una sola cola para todos los procesadores. Una vez que una tarea es asumida por un procesador, es completada sin interrupción por el mismo procesador. Planificación local, particionada. En este planteamiento, hay una cola separada para cada procesador. Las tareas de un cierto tipo siempre llegan a una cierta cola. Planificación de dos niveles, o híbrida. En este planteamiento, hay una cola global para todos los procesadores. Las tareas son distribuidas desde la cola global a colas locales para cada procesador.

Para sistemas reales distribuidos o de multi-núcleo, es también necesario considerar el impacto de los retardos de envío, el rendimiento del sistema de memoria y la estructura de interconexión. Éstos añaden impedimentos no triviales al rendimiento para un sistema de multi-procesadores.

Considerando la planificación global con migración completa, es bien conocido que el procesamiento de tareas en orden ascendente de plazos, “Plazo más Temprano Primero” (EDF – Earliest Deadline First, en inglés) , no es óptimo para el multi-procesador. Existen conjuntos de tareas que se aproximan a una utilización global cero, mientras que todavía no es planificable mediante EDF. Además, el uso de EDF con migración completa puede provocar una media de una migración por tarea. Si el número de procesadores es grande, el número de invocaciones del planificador puede también colapsar a un único nodo, independientemente de que EDF sea un algoritmo simple.

Un algoritmo popular para la planificación de multi-núcleo global es “El de Menor Relajación Primero” (LLF – Least Laxity First, en inglés) , que tiene mejores propiedades que el EDF. Por su parte, es capaz de utilizar la mitad de la capacidad agregada para tareas en tiempo real. No obstante, como el EDF, el LLF también provoca una gran cantidad de migraciones y de invocaciones del planificador. Además, la complejidad de cálculo del LLF es ligeramente mayor que la del planteamiento del EDF.

Para poder aumentar más la utilización disponible para procesamiento en tiempo real, es factible utilizar uno de los planificadores de multi-núcleo óptimos, bien el algoritmo de “Imparcialidad Proporcional” (Pfair - Proportionate Fair, en inglés) o “Tiempo de Ejecución restante Local más Largo Primero” (LLREF – Largest Local Remaining Execution time First, en inglés) . El algoritmo PFair, no obstante, provoca una cantidad de migraciones incluso mayor que el EDF. Aunque LLREF produce una menor cantidad de invocaciones del planificador y menos migraciones, el LLREF necesita conocer cuándo será liberada la siguiente tarea para ser liberada. Por esta razón el LLREF puede ser considerado un algoritmo que no es muy adecuado para el procesamiento en tiempo real.

Los algoritmos de planificación global como FP, EDF, LLF, PFair, etc., pueden ser académicamente interesantes, pero fallan cuando son aplicados a un sistema real con retardos y un rendimiento limitado del sistema de memoria. Con una carga cada vez mayor, estos planificadores provocan una cantidad de migraciones de tarea cada vez mayor. Puesto que las migraciones de tarea implican un aumento de carga, la frecuencia de migración también aumentará. Bajo ciertas condiciones, particularmente cerca de algún límite de utilización práctico, el aumento de carga de las migraciones se acelera, conduciendo a una carga inestable que rápidamente inutiliza todo el sistema.

Un ejemplo de planificación de la técnica anterior en un sistema de procesador de multi-núcleo se describe en la publicación de la solicitud de patente de US 2007/0220517. No obstante, la planificación descrita en esta memoria 2

50 55 60

está asociada con los respectivos inconvenientes de las altas velocidades de migración y, en caso de utilizar EDF, una baja utilización en tiempo real. El modo de planificación de histéresis descrito en el documento de US 2007/0220517 puede mejorar el resultado, pero también aumenta los tiempos de respuesta, lo que limita su utilidad para aplicaciones en tiempo real duras.

El documento que sigue describe una estructura de planificador en tiempo real de dos niveles (Calidad de Servicio/QoS – Quality of Service, en inglés) en multi-grupos y mallas.

LIGANG HE ET AL: “Dynamic Scheduling of Parallel Jobs with QoS Demands in Multiclusters and Grids” GRID COMPUTING, 2004. PROCEEDINGS. FIFTH IEEE/ACM INTERNATIONAL WORKSHOP ON PITTSBURGH, PA, USA 08-08 NOV. 2004, PISCATAWAY, NJ, USA. IEEE, 8 de Noviembre de 2004 (2004-11-08) , páginas 402-409, XPO10769526.

El aspecto particular de la rellamada y la redistribución de tareas puestas en cola para procesadores ocupados a procesadores en reposo es una estrategia bien conocida (”robo de tarea/trabajo”) , como puede encontrarse por ejemplo en el siguiente documento:

YUE, J.: “Global Backfilling Scheduling in Multiclusters” LECTURE NOTES IN COMPUTER SCIENCE LNCS3285, 2004, páginas 232-239, XP002541638

Compendio La invención se define en las reivindicaciones 1 y 2 independientes del método, y de manera correspondiente en la reivindicación 17 del dispositivo y en una correspondiente reivindicación 18 para un programa de ordenador.

Por ello, para mejorar las soluciones de la técnica anterior se proporciona, de acuerdo con un primer aspecto, un método de planificar tareas de procesamiento en un aparato de cálculo de multi-procesadores. Las tareas están asociadas con al menos un plazo respectivo. El método implica la comunicación entre una función de planificación de tareas global y una pluralidad de funciones de planificación de tareas local, estando cada función de planificación de tareas local asociada con un procesador respectivo. El método comprende guardar, en la función de planificación global, información del estatus actualizada relativa a cualquier procesador en reposo, a momentos del tiempo en los que se espera que cualquier procesador se encuentre en reposo y a valores de relajación asociados con cualquier procesador. Además, el método comprende planificar, en la función de planificación de tareas global, tareas mediante el envío de tareas a las funciones de planificación de tareas locales y el envío está condicionado por la información de estatus. Las tareas son llamadas de las funciones de planificación de tareas locales y cualquier procesador que no esté en reposo y cualquier tarea llamada es enviada a una función de planificación de tareas local en un procesador en reposo. Las tareas interrumpidas son recibidas desde las funciones de planificación de tareas locales, y cualquier tarea interrumpida recibida es enviada a una función de planificación de tareas local, estando el envío condicionado por la información de estatus.

En otras palabras, las tareas son interrumpidas y devueltas a la función de planificación de tareas global si un procesador no puede terminar la tarea, los procesadores siguen trabajando en la tarea actual durante el mayor tiempo posible, hasta que es necesario cambiar para cumplir el plazo de otra tarea, y los procesadores que pasan a reposo pueden empezar a trabajar en tareas de la cola en otros procesadores. Este planteamiento es una combinación de conceptos. La planificación de lista global en la que una función de planificación de tareas global asigna tareas al nodo “menos ocupado”; una planificación local... [Seguir leyendo]

1. Un método de planificar tareas de procesamiento en un aparato de cálculo de multi-procesadores (100, 200) , estando las tareas asociadas con al menos un plazo respectivo, implicando el método la comunicación entre una función de planificación de tareas global (102, 202) y una pluralidad de funciones de planificación de tareas locales (112, 212) , estando cada función de planificación de tareas local asociada con un procesador (108, 208) respectivo, que comprende:

-guardar, en la función de planificación de tareas global, información del estatus actualizada relativa a :

- cualquier procesador en reposo, -momentos del tiempo en los que se espera que cualquier procesador esté en reposo, -valores de relajación asociados con cualquier procesador,

comprendiendo también el método:

-planificar, en la función de planificación de tareas global, las tareas de:

-enviar tareas a las funciones de planificación de tareas locales, estando el envío condicionado por la

información de estatus, -llamar a tareas desde las funciones de planificación de tareas locales en algún procesador que no esté en reposo y enviar alguna tarea llamada a una función de planificación de tareas local en un procesador que no esté en reposo, -recibir, desde las funciones de planificación de tareas locales, tareas interrumpidas y enviar cualquier

tarea interrumpida recibida a una función de planificación de tareas local, estando el envío condicionado a la información de estatus,

donde el hecho de guardar la información de estatus actualizada comprende:

-recibir, desde cada función de planificación de tareas local, un valor de relajación de planificación calculado respectivo que es la diferencia mínima entre los plazos de finalización para tareas y los tiempos de finalización de tarea esperados con tareas actualmente enviadas a cada procesador respectivo, y

donde la planificación de una tarea comprende:

-comprobar si existe un procesador en reposo y, si es así, enviar la tarea a la función de planificación de tareas local del procesador en reposo,

si no:

- calcular un tiempo de finalización esperado de la tarea, siendo el cálculo relativo a una situación que implica a la existencia de un procesador en reposo, -calcular un valor de relajación de tarea como una diferencia entre el plazo para la tarea y el tiempo de finalización esperado calculado para la tarea,

-comprobar si la relajación de la tarea calculada es mayor que una diferencia entre el momento del tiempo más temprano en el que algún procesador se espera que esté en reposo y el tiempo actual y, si es así, enviar la tarea a la función de planificación de tareas local de ese procesador,

si no:

-enviar la tarea a la función de planificación de tareas local del procesador que tenga el mayor valor de relajación de planificación.

2. Un método de planificar tareas de procesamiento en un aparato de cálculo de multi-procesadores (100, 200) ,

estando las tareas asociadas con al menos un plazo respectivo, implicando el método la comunicación entre una función de planificación de tareas global (102, 202) y una pluralidad de funciones de planificación de tareas locales (112, 212) , estando cada función de planificación de tareas local asociada con un procesador (108, 208) respectivo, que comprende:

-guardar, en la función de planificación de tareas global, información de estatus actualizada relativa a:

- cualquier procesador en reposo, -momentos del tiempo en los que algún procesador se espera que esté en reposo, -valores de relajación asociados con algún procesador,

comprendiendo también el método:

-planificar, en la función de planificación de tareas global, tareas mediante:

-enviar tareas a las funciones de planificación de tareas locales, estando el envío condicionado por la información de estatus, -llamar a tareas desde las funciones de planificación de tareas locales en cualquier procesador que no esté en reposo y enviar alguna tarea llamada a una función de planificación de tareas local en un procesador en reposo,

-recibir, desde las funciones de planificación de tareas locales, tareas interrumpidas y enviar cualquier tarea interrumpida recibida a una función de planificación de tareas local, estando el envío condicionado por la información de estatus,

donde el hecho de guardar información de estatus actualizada comprende:

-recibir, desde cada función de planificación de tareas local, un valor de relajación de planificación calculado respectivo que es una diferencia mínima entre los plazos de finalización para las tareas y los tiempos de finalización de tarea esperados asociados con las tareas enviadas actualmente a cada procesador respectivo, y

donde la planificación de una tarea comprende:

-comprobar si existe un procesador en reposo y, si es así, enviar la tarea a la función de planificación de tareas local del procesador en reposo,

si no:

-comprobar si un plazo de inicio para la tarea es posterior al momento del tiempo más temprano en el que se espera que cualquier procesador esté en reposo y, si es así, enviar la tarea a la función de planificación de 30 tareas local de ese procesador,

si no:

-enviar la tarea a la función de planificación de tareas local del procesador que tenga el valor de relajación de 35 planificación más grande.

3. El método de cualquiera de las reivindicaciones 1 a 2, que comprende, en la función de planificación de tareas global:

-determinar a partir de la información de estatus actualizada si al menos un procesador está en reposo y, si es así: -determinar los datos de decisión de llamada que comprenden información relativa al número total de tareas que se están enviando actualmente a las funciones de planificación de tareas locales, el número de procesadores que no están en reposo e información relativa a cuál de los procesadores es el más ocupado,

-decidir, utilizando los datos de decisión de llamada, si llamar a una tarea desde el procesador más ocupado y, si es así:

- recibir una tarea desde el procesador más ocupado y, -enviar la tarea recibida a la función de planificación de tareas local de un procesador en reposo.

4. El método de la reivindicación 3, que comprende, en una función de planificación de tareas local:

-recibir una solicitud de llamada de tarea desde la función de planificación de tareas global, -estimar si las tareas de la cola pueden cumplir sus respectivos plazos de finalización si son procesados por 55 algún procesador y, dependiendo de la estimación: -devolver una tarea a la función de planificación de tareas global.

5. El método de la reivindicación 4, que comprende, en una función de planificación de tareas local:

-determinar devolver los criterios de selección para decidir qué tarea devolver a la función de planificación de tareas global, comprendiendo la determinación de devolver los criterios de selección cualquiera de:

-una tarea última en una cola de tareas,

50 55 60

-calcular el reenvío de valores de retardo para tareas de la cola y comparar los valores de retardo de reenvío con valores de relajación de las tareas de la cola, -calcular valores de retardo de reenvío para tareas de la cola y determinar un tiempo de inicio respectivo, teniendo en cuenta los valores de retardo de reenvío, en cualquier procesador y comparar estos tiempos de inicio, y a continuación determinar los criterios de selección de devolución:

-devolver una tarea a la función de planificación de tareas global de acuerdo con los criterios de selección de devolución.

6. El método de cualquiera de las reivindicaciones 1 a 5, que comprende, en una función de planificación de tareas local:

- comprobar si la relajación de planificación es menor de cero, y si es así: -calcular un momento del tiempo de expiración que sea el momento del tiempo en el cual una tarea que se está ejecutando actualmente debe detenerse con el fin de que la relajación de planificación sea cero, -interrumpir la tarea que se está ejecutando actualmente, teniendo lugar la interrupción en un intervalo de tiempo que es distinto de cero antes del momento del tiempo de expiración, -devolver la tarea interrumpida a la función de planificación de tareas global, -activar una tarea de la cola, y -recalcular la relajación de planificación.

7. El método de la reivindicación 6, en el que el intervalo de tiempo distinto de cero se determina:

- calculando la relajación de la tarea que se está ejecutando actualmente, -calculando una relajación de asunción para cada tarea de la cola, como la diferencia entre un tiempo de finalización esperado y un plazo de finalización con respecto a un momento del tiempo de inicio asumido común, -identificando la menor relajación de asunción entre las tareas de la cola, -ajustando el intervalo de tiempo distinto de cero, en caso de que la relajación de la tarea que se está ejecutando actualmente sea mayor que la menor relajación de asunción identificada, para un primer valor del intervalo del temporizador, y si no: -ajustando el intervalo de tiempo distinto de cero a un segundo valor del intervalo del temporizador, siendo el segundo valor del intervalo del temporizador mayor que el primer valor del intervalo del temporizador.

8. El método de la reivindicación 6, en el que el intervalo de tiempo distinto de cero se determina:

- calculando la relajación de la tarea que se está ejecutando actualmente, -calculando una relajación de asunción para cada tarea de la cola, como la diferencia entre un tiempo de finalización esperado y un plazo de finalización con respecto a un momento del tiempo de inicio asumido común, -identificando la menor relajación de asunción entre las tareas de la cola, -ajustando el intervalo de tiempo distinto de cero a un valor que es proporcional a la diferencia entre la relajación de la tarea que se está ejecutando actualmente y la menor relajación de asunción e inversamente proporcional a la suma de la relajación de la tarea que se está ejecutando actualmente y la menor relajación de asunción.

9. El método de cualquiera de las reivindicaciones 6 a 8, que comprende, en una función de planificación de tareas local:

- recibir una solicitud de llamada de tarea desde la función de planificación de tareas global, -estimar si las tareas de la cola pueden cumplir sus respectivos plazos de finalización teniendo en cuenta cualquier retardo provocado por salvar y restaurar los datos asociados con la replanificación entre procesadores y, dependiendo de la estimación: -devolver una tarea a la función de planificación de tareas global.

10. El método de cualquiera de las reivindicaciones 1 a 5, que comprende, en una función de planificación de tareas local:

- comprobar si la relajación de planificación es menor de cero y, si es así: -calcular un momento del tiempo de expiración, siendo el momento del tiempo en el cual una tarea que se está ejecutando actualmente debe detener su ejecución con el fin de que la relajación de planificación sea cero, -calcular una relajación de planificación de asunción dada la asunción de que la tarea que se está ejecutando actualmente es replanificada,

-interrumpir, si la relajación de planificación de asunción calculada es positiva, la tarea que se está ejecutando actualmente en un intervalo de tiempo distinto de cero antes del momento del tiempo de expiración, y si no interrumpir la tarea que se está ejecutando actualmente inmediatamente, -activar una tarea de la cola, y

- recalcular la relajación de planificación.

11. El método de cualquiera de las reivindicaciones 1 a 10, que comprende, en una función de planificación de tareas local:

-asignar un nivel de prioridad a cada tarea, -guardar una pluralidad de colas de tareas, conteniendo cada cola tareas que tienen un único nivel de prioridad, y -guardar, en la función de planificación de tareas global, información de estatus actualizada relativa a la pluralidad de colas.

12. El método de cualquiera de las reivindicaciones 1 a 11, en el que la función de planificación de tareas global está asociada con un procesador específico.

13. El método de cualquiera de las reivindicaciones 1 a 11, en el que la función de planificación de tareas global está 20 asociada con una pluralidad de procesadores.

14. El método de cualquiera de las reivindicaciones 1 a 13, en el que el hecho de guardar la información de estatus actualizada comprende:

-guardar una lista de procesadores clasificada en orden de momentos del tiempo ascendentes en los que se espera que los procesadores estén en reposo, y -guardar una lista de procesadores clasificada en orden de relajación descendente.

15. El método de la reivindicación 14, en el que el hecho de guardar la información de estatus actualizada 30 comprende también:

- guardar una lista de primero en entrar primero en salir de procesadores en reposo.

16. Un programa de ordenador que comprende instrucciones de software que, cuando son ejecutadas en un 35 dispositivo de procesamiento de multi-procesadores, lleva a cabo el método de cualquiera de las reivindicaciones 1 a

15.

17. Un dispositivo de procesamiento de multi-procesadores (100, 200, 300) que comprende un medio de procesamiento y de memoria (108, 208, 301, 303, 305) que están configurados de tal manera que es capaz de llevar40 a cabo el método de cualquiera de las reivindicaciones 1 a 15.

18. Un dispositivo de comunicación de telefonía móvil (300) que comprende el dispositivo de procesamiento de multi-procesadores de la reivindicación 17.