En computación paralela , el robo de trabajo es una estrategia de programación para programas informáticos multiproceso . Resuelve el problema de ejecutar un cálculo multiproceso dinámico , que puede "generar" nuevos subprocesos de ejecución, en una computadora multiproceso estático , con una cantidad fija de procesadores (o núcleos ). Lo hace de manera eficiente en términos de tiempo de ejecución, uso de memoria y comunicación entre procesadores.
En un planificador que roba trabajo, cada procesador de un sistema informático tiene una cola de elementos de trabajo (tareas computacionales, subprocesos) que debe realizar. Cada elemento de trabajo consta de una serie de instrucciones que se deben ejecutar de forma secuencial, pero en el transcurso de su ejecución, un elemento de trabajo también puede generar nuevos elementos de trabajo que se puedan ejecutar en paralelo con el resto de su trabajo. Estos nuevos elementos se colocan inicialmente en la cola del procesador que ejecuta el elemento de trabajo. Cuando un procesador se queda sin trabajo, examina las colas de los demás procesadores y "roba" sus elementos de trabajo. En efecto, el robo de trabajo distribuye el trabajo de programación entre los procesadores inactivos y, mientras todos los procesadores tengan trabajo que hacer, no se produce ninguna sobrecarga de programación. [1]
El robo de trabajo contrasta con el uso compartido del trabajo , otro enfoque de programación popular para subprocesos múltiples dinámicos, donde cada elemento de trabajo se programa en un procesador cuando se genera. En comparación con este enfoque, el robo de trabajo reduce la cantidad de migración de procesos entre procesadores, porque no se produce dicha migración cuando todos los procesadores tienen trabajo que hacer. [2]
La idea del robo de trabajo se remonta a la implementación del lenguaje de programación Multilisp y al trabajo sobre lenguajes de programación funcional paralelos en la década de 1980. [2] Se emplea en el programador del lenguaje de programación Cilk , [3] el marco de trabajo de bifurcación/unión de Java , [4] la biblioteca de tareas paralelas de .NET , [5] y el entorno de ejecución Rust Tokio . [6] [7]
El robo de trabajo está diseñado para un modelo de bifurcación-unión "estricto" de computación paralela, lo que significa que una computación puede verse como un gráfico acíclico dirigido con una única fuente (inicio de la computación) y un único sumidero (final de la computación). Cada nodo de este gráfico representa una bifurcación o una unión . Las bifurcaciones producen múltiples cálculos lógicamente paralelos , denominados de diversas formas "hilos" [2] o "cadenas". [8] Los bordes representan computación en serie. [9] [nota 1]
Como ejemplo, considere el siguiente programa trivial fork-join en sintaxis similar a Cilk :
función f(a, b): c ← horquilla g(a) d ← h(b) unirse devuelve c + dfunción g(a): devuelve un × 2función h(a): b ← horquilla g(a) c ← a + 1 unirse devolver b + c
La llamada a la función f(1, 2) da lugar al siguiente gráfico de cálculo:
En el gráfico, cuando dos aristas salen de un nodo, los cálculos representados por las etiquetas de las aristas son lógicamente paralelos: pueden realizarse en paralelo o secuencialmente. El cálculo solo puede continuar más allá de un nodo de unión cuando se hayan completado los cálculos representados por sus aristas entrantes. El trabajo de un programador, ahora, es asignar los cálculos (aristas) a los procesadores de una manera que haga que todo el cálculo se ejecute hasta su finalización en el orden correcto (según lo restringido por los nodos de unión), preferiblemente lo más rápido posible.
La versión aleatoria del algoritmo de robo de trabajo presentado por Blumofe y Leiserson mantiene varios subprocesos de ejecución y los programa en procesadores. Cada uno de los procesadores tiene una cola de subprocesos de doble extremo (deque). Los extremos de la deque se denominan "superior" e "inferior".
Cada procesador que tiene un hilo actual para ejecutar, ejecuta las instrucciones en el hilo una por una, hasta que encuentra una instrucción que causa uno de cuatro comportamientos "especiales": [2] : 10
Inicialmente, un cálculo consta de un único hilo y se asigna a un procesador, mientras que los demás procesadores comienzan inactivos. Cualquier procesador que se vuelve inactivo inicia el proceso real de robo de trabajo, lo que significa lo siguiente:
Nótese que, en la regla para spawn , Blumofe y Leiserson sugieren que el hilo "padre" ejecute su nuevo hilo, como si estuviera realizando una llamada a una función (en el programa tipo C f(x); g(y); , la llamada a la función f se completa antes de que se realice la llamada a g ). Esto se llama "robo de continuación", porque la continuación de la función puede ser robada mientras se ejecuta el hilo generado, y es el algoritmo de programación utilizado en Cilk Plus . [8] No es la única forma de implementar el robo de trabajo; la estrategia alternativa se llama "robo de hijos" y es más fácil de implementar como una biblioteca , sin soporte del compilador . [8] El robo de hijos es utilizado por Threading Building Blocks , la Task Parallel Library de Microsoft y OpenMP , aunque este último le da al programador control sobre qué estrategia se utiliza. [8 ]
Se han propuesto varias variantes de robo de trabajo. La variante aleatoria debida a Blumofe y Leiserson ejecuta un cálculo paralelo en el tiempo esperado en los procesadores; aquí, es el trabajo , o la cantidad de tiempo requerida para ejecutar el cálculo en una computadora en serie, y es el lapso , la cantidad de tiempo requerida en una máquina infinitamente paralela. [nota 2] Esto significa que, en expectativa , el tiempo requerido es como máximo un factor constante multiplicado por el mínimo teórico. [2] Sin embargo, el tiempo de ejecución (en particular, el número de robos ejecutados) puede ser exponencial en el peor de los casos. [10] También se ha analizado teórica y prácticamente una variante localizada, en la que un procesador intenta robar su propio trabajo siempre que esté libre. [11] [12]
Un cálculo programado por la versión de Blumofe–Leiserson de robo de trabajo utiliza espacio de pila , si fuera el uso de pila del mismo cálculo en un solo procesador, [2] ajustándose a la propia definición anterior de los autores de eficiencia espacial. [13] Este límite requiere robo de continuación; en un programador de robo de hijos, no se cumple, como se puede ver en el siguiente ejemplo: [8]
para i = 0 a n: bifurcación f(i) unión
En una implementación de robo de niños, todas las llamadas "bifurcadas" a f se colocan en una cola de trabajo que crece hasta alcanzar un tamaño n , que puede hacerse arbitrariamente grande.
El algoritmo de robo de trabajo, como se ha descrito anteriormente, y su análisis, suponen un entorno informático en el que se programa un cálculo en un conjunto de procesadores dedicados. En un entorno de multiprogramación (multitarea), el algoritmo debe modificarse para programar las tareas de cálculo en un grupo de subprocesos de trabajo , que a su vez son programados en los procesadores reales por un programador del sistema operativo . En cualquier momento dado, el programador del sistema operativo asignará al proceso de robo de trabajo una cantidad P A ≤ P de los P procesadores de la computadora, porque otros procesos pueden estar utilizando los procesadores restantes. En este contexto, el robo de trabajo con un grupo de P subprocesos de trabajo tiene el problema de que los trabajadores que actúan como ladrones pueden causar un bloqueo activo : pueden bloquear la ejecución de trabajadores que realmente generarían tareas útiles. [14] [15]
Para esta situación se ha ideado una variante del robo de trabajo, que ejecuta un cálculo en el tiempo esperado.
donde P avg es el número promedio de procesadores asignados al cálculo por el programador del SO durante el tiempo de ejecución del cálculo. [16] El programador de trabajo multiprogramación se diferencia de la versión tradicional en dos aspectos:
Los intentos de mejorar el ladrón de trabajo de multiprogramación se han centrado en problemas de localidad de caché [12] y estructuras de datos de cola mejoradas. [17]
Varios algoritmos de programación para cálculos multiproceso dinámicos compiten con el robo de trabajo. Además del enfoque tradicional de compartir trabajo, existe un planificador llamado PDF ( parallel depth-first ) que mejora los límites de espacio del robo de trabajo, [18] y ofrece un mejor rendimiento en algunas situaciones en las que los núcleos de un multiprocesador de chip comparten una caché. [1]
