En la 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 dinámicamente multiproceso , uno que puede "generar" nuevos subprocesos de ejecución, en una computadora estáticamente multiproceso , con un número fijo 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 programador de robo de trabajo, cada procesador en un sistema informático tiene una cola de elementos de trabajo (tareas computacionales, subprocesos) para realizar. Cada elemento de trabajo consta de una serie de instrucciones, que se ejecutarán secuencialmente, pero en el curso de su ejecución, un elemento de trabajo también puede generar nuevos elementos de trabajo que se pueden ejecutar de manera factible en paralelo con su otro 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, mira las colas de los otros procesadores y "roba" sus elementos de trabajo. En efecto, el robo de trabajo distribuye el trabajo de programación entre los procesadores inactivos y, siempre que todos los procesadores tengan trabajo que hacer, no se producirá una sobrecarga de programación. [1]
El robo de trabajo contrasta con el trabajo compartido , otro enfoque de programación popular para el subproceso múltiple dinámico, 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 dicha migración no ocurre 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 en lenguajes de programación funcional paralelos en la década de 1980. [2] Se emplea en el planificador para el lenguaje de programación Cilk , [3] el marco Java fork / join, [4] la biblioteca paralela de tareas .NET , [5] y el tiempo de ejecución de Rust Tokio. [6]
Modelo de ejecución
El robo de trabajo está diseñado para un modelo "estricto" de unión en bifurcación de cálculo paralelo, lo que significa que un cálculo puede verse como un gráfico acíclico dirigido con una sola fuente (inicio del cálculo) y un único sumidero (final del cálculo). Cada nodo de este gráfico representa una bifurcación o una combinación . Las bifurcaciones producen múltiples cálculos lógicamente paralelos , denominados "hilos" [2] o "hilos". [7] Los bordes representan el cálculo en serie. [8] [nota 1]
Como ejemplo, considere el siguiente programa trivial fork-join con una sintaxis similar a Cilk :
función f (a, b): c ← horquilla g (a) d ← h (b) entrar volver c + dfunción g (a): devolver un × 2función h (a): b ← horquilla g (a) c ← a + 1 entrar volver b + c
La llamada de función f (1, 2) da lugar al siguiente gráfico de cálculo:
En el gráfico, cuando dos bordes salen de un nodo, los cálculos representados por las etiquetas de los bordes 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 los cálculos representados por sus bordes entrantes estén completos. El trabajo de un programador, ahora, es asignar los cálculos (bordes) 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.
Algoritmo
La versión aleatoria del algoritmo de robo de trabajo presentado por Blumofe y Leiserson mantiene varios hilos de ejecución y los programa enprocesadores. Cada uno de los procesadores tiene una cola de dos extremos (deque) de subprocesos. Llame a los extremos del deque "superior" e "inferior".
Cada procesador que tiene un subproceso actual para ejecutar, ejecuta las instrucciones en el subproceso una por una, hasta que encuentra una instrucción que causa uno de cuatro comportamientos "especiales": [2] : 10
- Una instrucción de generación hace que se cree un nuevo hilo. El hilo actual se coloca en la parte inferior del deque y el procesador comienza a ejecutar el nuevo hilo.
- Una instrucción de estancamiento es aquella que detiene temporalmente la ejecución de su hilo. El procesador saca un hilo de la parte inferior de su deque y comienza a ejecutar ese hilo. Si su deque está vacío, comienza a robar trabajo, explicado a continuación.
- Una instrucción puede causar un hilo para morir . El comportamiento en este caso es el mismo que para una instrucción que se detiene.
- Una instrucción puede habilitar otro hilo. El otro subproceso se empuja hacia la parte inferior del deque, pero el procesador continúa la ejecución de su subproceso actual.
Inicialmente, un cálculo consta de un solo subproceso y se asigna a algún procesador, mientras que los otros procesadores comienzan inactivos. Cualquier procesador que quede inactivo inicia el proceso real de robo de trabajo, lo que significa lo siguiente:
- elige otro procesador uniformemente al azar;
- si el deque del otro procesador no está vacío, saca el subproceso más alto del deque y comienza a ejecutarlo;
- si no, repita.
Robo de niños versus robo de continuación
Tenga en cuenta que, en la regla para desovar , y Blumofe Leiserson sugieren que el hilo "padre" ejecutar su nuevo hilo, como si la realización de una llamada de función (en el C-como el programa f (x); g (y); , la función llamada a f se completa antes de 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 . [7] No es la única forma de implementar el robo de trabajo; la estrategia alternativa se llama "robo de niños" y es más fácil de implementar como biblioteca , sin soporte de compilador . [7] El robo de niños es utilizado por Threading Building Blocks , Task Parallel Library de Microsoft y OpenMP , aunque este último le da al programador control sobre qué estrategia se usa. [7]
Eficiencia
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 procesadores; aquí,es el trabajo , o la cantidad de tiempo necesaria para ejecutar el cálculo en una computadora en serie, yes el lapso , la cantidad de tiempo requerido 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 enEn el peor de los casos. [9] También se ha analizado teórica y prácticamente una variante localizada, en la que un procesador intenta recuperar su propio trabajo cuando está libre. [10] [11]
Uso del espacio
Un cálculo programado por la versión Blumofe-Leiserson de los usos del robo de trabajo espacio de pila , sifueron el uso de pila de la misma computación en un solo procesador, [2] encajando con la definición anterior de eficiencia del espacio de los autores. [12] Este límite requiere un robo continuo; en un programador de robo de niños, no se mantiene, como se puede ver en el siguiente ejemplo: [7]
para i = 0 a n: tenedor f (i) uno a
En una implementación de robo de niños, todas las llamadas "bifurcadas" a f se colocan en una cola de trabajo que, por lo tanto, crece al tamaño n , que puede hacerse arbitrariamente grande.
Variante de multiprogramación
El algoritmo de robo de trabajo descrito anteriormente, y su análisis, asumen 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 tareas de cálculo en un grupo de subprocesos de trabajo , que a su vez se programan en los procesadores reales por un programador del sistema operativo . En cualquier momento, el programador del sistema operativo asignará al proceso de robo de trabajo algún número P A ≤ P de los procesadores P en la computadora, porque otros procesos pueden estar usando los procesadores restantes. En esta configuración, el robo de trabajo con un grupo de subprocesos de trabajo P tiene el problema de que los trabajadores que actúan como ladrones pueden causar un bloqueo : pueden bloquear la ejecución de trabajadores que en realidad generarían tareas útiles. [13] [14]
Para esta situación se ha ideado una variante de 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 sistema operativo durante el tiempo de ejecución del cálculo. [15] El planificador de trabajo de multiprogramación se diferencia de la versión tradicional en dos aspectos:
- Sus colas no se bloquean . Mientras que en procesadores dedicados, el acceso a las colas se puede sincronizar mediante bloqueos , esto no es aconsejable en un entorno de multiprogramación, ya que el sistema operativo podría adelantarse al subproceso de trabajo que mantiene el bloqueo, bloqueando el progreso de cualquier otro trabajador que intente acceder a la misma cola. .
- Antes de cada intento de robar trabajo, un hilo de trabajo llama a " rendimiento "llamada del sistema que cede el procesador en el que está programado para el sistema operativo, con el fin de evitar la inanición .
Los intentos de mejorar el ladrón de trabajos de multiprogramación se han centrado en problemas de localidad de caché [11] y estructuras de datos de cola mejoradas. [dieciséis]
Alternativas
Varios algoritmos de programación para cálculos dinámicamente multiproceso compiten con el robo de trabajo. Además del enfoque tradicional de trabajo compartido, hay un programador llamado paralelo en profundidad primero (PDF) que mejora los límites de espacio del robo de trabajo, [17] además de ofrecer un mejor rendimiento en algunas situaciones en las que los núcleos de un multiprocesador de chips comparten un caché. . [1]
Notas
- ^ En la presentación original, los cálculos seriales también se representaban como nodos, y un borde dirigido representaba la relación "seguida de".
- ^ Ver análisis de algoritmos paralelos para definiciones.
Referencias
- ^ a b Chen, Shimin; Gibbons, Phillip B .; Kozuch, Michael; Liaskovitis, Vasileios; Ailamaki, Anastassia; Blelloch, Guy E .; Falsafi, Babak; Arreglar, Limor; Hardavellas, Nikos; Mowry, Todd C .; Wilkerson, Chris (2007). Programación de subprocesos para el uso compartido de caché constructivo en CMP (PDF) . Proc. ACM Symp. sobre arquitecturas y algoritmos paralelos. págs. 105-115.
- ^ a b c d e f Blumofe, Robert D .; Leiserson, Charles E. (1999). "Programación de cálculos multiproceso por robo de trabajo" (PDF) . J ACM . 46 (5): 720–748. doi : 10.1145 / 324133.324234 .
- ^ Blumofe, Robert D .; Joerg, Christopher F .; Kuszmaul, Bradley C .; Leiserson, Charles E .; Randall, Keith H .; Zhou, Yuli (1996). "Cilk: un eficiente sistema de ejecución multiproceso". Revista de Computación Paralela y Distribuida . 37 (1): 55–69. doi : 10.1006 / jpdc.1996.0107 .
- ^ Doug Lea (2000). Un marco de unión / bifurcación de Java (PDF) . Conf. ACM en Java.
- ^ Leijen, Daan; Schulte, Wolfram; Burckhardt, Sebastián (2009). "El diseño de una biblioteca de tareas paralelas". Avisos ACM SIGPLAN . 44 (10): 227. CiteSeerX 10.1.1.146.4197 . doi : 10.1145 / 1639949.1640106 .
- ^ "¿Qué es Tokio? · Tokio" . tokio.rs . Consultado el 27 de mayo de 2020 .
- ^ a b c d e Robison, Arch (15 de enero de 2014). Introducción a la programación de la bifurcación: unir el paralelismo con el robo de trabajo (PDF) (Informe técnico). ISO / IEC JTC 1 / SC 22 / WG 21 — El Comité de Normas C ++ . N3872.
- ^ Halpern, Pablo (24 de septiembre de 2012). Paralelismo estricto de bifurcación-unión (PDF) (Informe técnico). ISO / IEC JTC 1 / SC 22 / WG 21 — El Comité de Normas C ++ . N3409 = 12-0099.
- ^ Leiserson, Charles E .; Schardl, Tao B .; Suksompong, Warut (2016). "Límites superiores del número de robos en árboles enraizados". Teoría de los sistemas informáticos . 58 (2): 223–240. arXiv : 1706.08219 . doi : 10.1007 / s00224-015-9613-9 .
- ^ Suksompong, Warut; Leiserson, Charles E .; Schardl, Tao B. (2016). "Sobre la eficacia del robo de trabajo localizado". Cartas de procesamiento de información . 116 (2): 100–106. arXiv : 1804.04773 . doi : 10.1016 / j.ipl.2015.10.002 .
- ^ a b Acar, Umut A .; Blelloch, Guy E .; Blumofe, Robert D. (2002). "La localidad de datos del robo de trabajo" (PDF) . Teoría de los sistemas informáticos . 35 (3): 321–347. CiteSeerX 10.1.1.19.3459 . doi : 10.1007 / s00224-002-1057-3 .
- ^ Blumofe, Robert D .; Leiserson, Charles E. (1998). "Programación eficiente del espacio de cálculos multiproceso". SIAM J. Comput . 27 (1): 202–229. CiteSeerX 10.1.1.48.9822 . doi : 10.1137 / s0097539793259471 .
- ^ Ding, Xiaoning; Wang, Kaibo; Gibbons, Phillip B .; Zhang, Xiaodong (2012). BWS: robo de trabajo equilibrado para multinúcleos de tiempo compartido (PDF) . EuroSys.
- ^ Blumofe, Robert D .; Papadopoulos, Dionisios (1998). El desempeño del robo de trabajo en entornos multiprogramados (informe técnico). Universidad de Texas en Austin , Departamento de Ciencias de la Computación. CiteSeerX 10.1.1.48.2247 .
- ^ Arora, Nimar S .; Blumofe, Robert D .; Plaxton, C. Greg (2001). "Programación de subprocesos para multiprocesadores multiprogramados" (PDF) . Teoría de los sistemas informáticos . 34 (2): 115-144. doi : 10.1007 / s002240011004 .
- ^ Chase, David R .; Lev, Yosef (2005). Deque de robo de trabajo circular dinámico . ACM Symp. sobre paralelismo en algoritmos y arquitecturas. CiteSeerX 10.1.1.170.1097 .
- ^ Blelloch, Guy E .; Gibbons, Phillip B .; Matias, Yossi (1999). "Programación demostrablemente eficiente para idiomas con paralelismo detallado" (PDF) . Revista de la ACM . 46 (2): 281–321. CiteSeerX 10.1.1.48.8238 . doi : 10.1145 / 301970.301974 .