Programación de tareas paralelas

Problema de optimización en informática.

La programación de tareas paralelas (también llamada programación de trabajos paralelos ^{[1] [2]} o programación de procesamiento paralelo ^[3] ) es un problema de optimización en informática e investigación de operaciones . Es una variante de la programación óptima del trabajo . En un problema general de programación de trabajos, se nos dan n trabajos J ₁ ,  J ₂ , ...,  J _n de diferentes tiempos de procesamiento, que deben programarse en m máquinas mientras se intenta minimizar el intervalo de tiempo (la duración total del programa). (es decir, cuando todos los trabajos hayan terminado de procesarse). En la variante específica conocida como programación de tareas paralelas , todas las máquinas son idénticas. Cada trabajo j tiene un parámetro de longitud p _j y un parámetro de tamaño q _j , y debe ejecutarse durante exactamente p _j pasos de tiempo en exactamente q _j máquinas en paralelo .

Veltman et al. ^[4] y Drozdowski ^[3] denotan este problema con la notación de tres campos introducida por Graham et al. ^[5] P significa que hay varias máquinas idénticas funcionando en paralelo; tamaño _j significa que cada trabajo tiene un parámetro de tamaño; C _max significa que el objetivo es minimizar el tiempo máximo de finalización. Algunos autores utilizan en su lugar. ^[1] Tenga en cuenta que el problema de la programación de máquinas paralelas es un caso especial de programación de tareas paralelas donde para todos j , es decir, cada trabajo debe ejecutarse en una sola máquina. ${\displaystyle P|size_{j}|C_{\max }}$ ${\displaystyle P|m_{j}|C_{\max }}$ ${\displaystyle size_{j}=1}$

Los orígenes de la formulación de este problema se remontan a 1960. ^[6] Para este problema, no existe ningún algoritmo de aproximación de tiempo polinomial con una relación menor que a menos que . ^{[ cita necesaria ]} ${\displaystyle 3/2}$ ${\displaystyle P=NP}$

Definición

Hay un conjunto de trabajos y máquinas idénticas. Cada trabajo tiene un tiempo de procesamiento (también llamado longitud de j ) y requiere el uso simultáneo de máquinas durante su ejecución (también llamado tamaño o ancho de j). ${\displaystyle {\mathcal {J}}}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle j\in {\mathcal {J}}}$ ${\displaystyle p_{j}\in \mathbb {N} }$ ${\displaystyle q_{j}\in \mathbb {N} }$

Un cronograma asigna a cada trabajo una hora de inicio y un conjunto de máquinas en las que se procesará. Un cronograma es factible si cada procesador ejecuta como máximo un trabajo en un momento dado. El objetivo del problema denotado por es encontrar un cronograma con una longitud mínima , también llamado makepan del cronograma. Una condición suficiente para la viabilidad de un cronograma es la siguiente ${\displaystyle j\in {\mathcal {J}}}$ ${\displaystyle s_{j}\in \mathbb {N} _{0}}$ ${\displaystyle m_{j}\subseteq \{1,\dots ,m\}}$ ${\displaystyle |m_{j}|=q_{j}}$ ${\displaystyle P|size_{j}|C_{\max }}$ ${\displaystyle C_{\max }=\max _{j\in {\mathcal {J}}}(s_{j}+p_{j})}$

${\displaystyle \sum _{j\in {\mathcal {J}},s_{j}\leq t<s_{j}+p_{j}}q_{j}\leq m\,\forall t\in \{s_{1},\dots ,s_{n}\}}$.

Si esta propiedad se cumple para todas las horas de inicio, se puede generar un cronograma factible asignando máquinas libres a los trabajos en cada momento comenzando con time . ^{[1] [2]} Además, el número de intervalos de máquina utilizados por los trabajos y los intervalos de inactividad en cada paso de tiempo pueden estar limitados por . ^[1] Aquí un intervalo de máquina es un conjunto de máquinas consecutivas de cardinalidad máxima tal que todas las máquinas en este conjunto están procesando el mismo trabajo. Un intervalo de máquina está completamente especificado por el índice de su primera y última máquina. Por tanto, es posible obtener una forma compacta de codificar la salida con tamaño polinómico. ${\displaystyle t=0}$ ${\displaystyle |{\mathcal {J}}|+1}$

Dureza computacional

Este problema es NP-difícil incluso cuando sólo hay dos máquinas y los tamaños de todos los trabajos lo son (es decir, cada trabajo debe ejecutarse sólo en una única máquina). Este caso especial, denotado por , es una variante del problema de partición , que se sabe que es NP-hard. ${\displaystyle q_{j}=1}$ ${\displaystyle P2||C_{\max }}$

Cuando el número de máquinas m es como máximo 3, es decir: para las variantes y , existe un algoritmo de tiempo pseudopolinomial , que resuelve el problema exactamente. ^[7] ${\displaystyle P2|size_{j}|C_{\max }}$ ${\displaystyle P3|size_{j}|C_{\max }}$

Por el contrario, cuando el número de máquinas es al menos 4, es decir: para las variantes de cualquiera , el problema también es fuertemente NP-duro ^[8] (este resultado mejoró un resultado anterior ^[7] que mostraba una fuerte dureza NP para ) . ${\displaystyle Pm|size_{j}|C_{\max }}$ ${\displaystyle m\geq 4}$ ${\displaystyle m\geq 5}$

Si el número de máquinas no está limitado por una constante, entonces no puede haber ningún algoritmo de aproximación con una relación de aproximación menor que a menos que . Esto es válido incluso para el caso especial en el que el tiempo de procesamiento de todos los trabajos es , ya que este caso especial es equivalente al problema de embalaje del contenedor : cada paso de tiempo corresponde a un contenedor, m es el tamaño del contenedor, cada trabajo corresponde a un artículo de tamaño q _j , y minimizar el makepan corresponde a minimizar el número de contenedores. ${\displaystyle 3/2}$ ${\displaystyle P=NP}$ ${\displaystyle p_{j}=1}$

Variantes

Se han estudiado varias variantes de este problema. ^[3] Las siguientes variantes también se han considerado en combinación entre sí.

Trabajos contiguos : En esta variante, las máquinas tienen un orden fijo . En lugar de asignar los trabajos a cualquier subconjunto , los trabajos deben asignarse a un intervalo contiguo de máquinas. Este problema corresponde a la formulación del problema del embalaje en tiras . ${\displaystyle (M_{1},\dots ,M_{m})}$ ${\displaystyle m_{j}\subseteq \{M_{1},\dots ,M_{m}\}}$

Múltiples plataformas: En esta variante el conjunto de máquinas se divide en plataformas independientes. Un trabajo programado solo puede utilizar las máquinas de una plataforma y no se le permite abarcar varias plataformas cuando se procesa.

Trabajos moldeables : en esta variante, cada trabajo tiene un conjunto de recuentos de máquinas factibles . Para cada conteo , el trabajo se puede procesar en d máquinas en paralelo, y en este caso, su tiempo de procesamiento será . Para programar un trabajo , un algoritmo tiene que elegir un recuento de máquinas y asignar j a una hora de inicio y a las máquinas durante el intervalo de tiempo. Una suposición habitual para este tipo de problema es que la carga de trabajo total de un trabajo, que se define como , es no creciente para un número creciente de máquinas. ${\displaystyle j\in {\mathcal {J}}}$ ${\displaystyle D_{j}\subseteq \{1,\dots m\}}$ ${\displaystyle d\in D_{j}}$ ${\displaystyle p_{j,d}}$ ${\displaystyle j\in {\mathcal {J}}}$ ${\displaystyle d\in D_{j}}$ ${\displaystyle s_{j}}$ ${\displaystyle d}$ ${\displaystyle [s_{j},s_{j}+p_{j,d}).}$ ${\displaystyle d\cdot p_{j,d}}$

Fechas de lanzamiento : en esta variante, indicada por , no todos los trabajos están disponibles en el momento 0; cada trabajo j está disponible en un momento fijo y conocido r _j . Se debe programar después de esa hora. ${\displaystyle P|size_{j},r_{j}|C_{\max }}$

Prelación : en esta variante, indicada por, es posible interrumpir trabajos que ya se están ejecutando y programar otros trabajos que estén disponibles en ese momento. ${\displaystyle P|size_{j},r_{j},{\text{pmtn}}|C_{\max }}$

Algoritmos

El algoritmo de programación de listas de Garey y Graham ^[9] tiene una relación absoluta , como señalan Turek et al. ^[10] y Ludwig y Tiwari. ^[11] Feldmann, Sgall y Teng ^[12] observaron que la duración de una programación no preventiva producida por el algoritmo de programación de listas es en realidad, en la mayoría de los casos, la duración óptima de la programación preventiva. Amoura et al. presentaron un esquema de aproximación de tiempo polinómico (PTAS) para el caso en el que el número de procesadores es constante, denotado por . ^[13] y Jansen et al. ^[14] Posteriormente, Jansen y Thöle ^[2] encontraron un PTAS para el caso en el que el número de procesadores está acotado polinomialmente en el número de trabajos. En este algoritmo, el número de máquinas aparece polinomialmente en la complejidad temporal del algoritmo. Dado que, en general, el número de máquinas aparece sólo en forma logarítmica en el tamaño de la instancia, este algoritmo es también un esquema de aproximación de tiempo pseudopolinomial. Jansen ^[15] dio una aproximación que cierra la brecha hasta el límite inferior de excepto por un valor arbitrariamente pequeño . ${\displaystyle 2}$ ${\displaystyle (2-1/m)}$ ${\displaystyle m}$ ${\displaystyle Pm|size_{j}|C_{\max }}$ ${\displaystyle (3/2+\varepsilon )}$ ${\displaystyle 3/2}$ ${\displaystyle \varepsilon }$

Diferencias entre trabajos contiguos y no contiguos

Dado un ejemplo del problema de programación de tareas en paralelo, el intervalo de tiempo óptimo puede diferir dependiendo de la restricción de contigüidad de las máquinas. Si los trabajos se pueden programar en máquinas no contiguas, el intervalo de producción óptimo puede ser menor que en el caso de que deban programarse en máquinas contiguas. La diferencia entre programaciones contiguas y no contiguas se demostró por primera vez en 1992 ^[16] en una instancia con tareas, procesadores y . Błądek et al. ^[17] estudiaron estas llamadas diferencias c/nc y demostraron los siguientes puntos: ${\displaystyle n=8}$ ${\displaystyle m=23}$ ${\displaystyle C_{\max }^{nc}=17}$ ${\displaystyle C_{\max }^{c}=18}$

• Para que surja la diferencia ac/nc, debe haber al menos tres tareas con ${\displaystyle q_{j}>1.}$
• Para que surja la diferencia ac/nc, debe haber al menos tres tareas con ${\displaystyle p_{j}>1.}$
• Para que surja ac/nc-difference, se requieren al menos procesadores (y existe una instancia con ac/nc-difference con ). ${\displaystyle m=4}$ ${\displaystyle m=4}$
• Para que surja la diferencia ac/nc, la duración del cronograma no contiguo debe ser al menos ${\displaystyle C_{\max }^{nc}=4.}$
• La máxima diferencia c/nc es al menos y como máximo ${\displaystyle \sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)}$ ${\displaystyle 5/4}$ ${\displaystyle 2.}$
• Decidir si existe una diferencia c/nc en un caso dado es NP-completo.

Además, propusieron las dos conjeturas siguientes, que aún no han sido probadas:

• Para que surja la diferencia ac/nc, se requieren al menos tareas. ${\displaystyle n=7}$
• ${\displaystyle \sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)=5/4}$

Problemas relacionados

Existen problemas de programación relacionados en los que cada trabajo consta de varias operaciones, que deben ejecutarse en secuencia (en lugar de en paralelo). Éstos son los problemas de la programación de taller abierto , la programación de taller de flujo y la programación de taller de trabajo .

Referencias

1. Johannes, Berit (1 de octubre de 2006). "Programación de trabajos paralelos para minimizar el espacio de trabajo". Diario de programación . 9 (5): 433–452. doi :10.1007/s10951-006-8497-6. hdl : 20.500.11850/36804 . ISSN  1099-1425. S2CID  18819458.
2. Jansen, Klaus.; Thöle, Ralf. (01 de enero de 2010). "Algoritmos de aproximación para la programación de trabajos paralelos". Revista SIAM de Computación . 39 (8): 3571–3615. doi : 10.1137/080736491. ISSN  0097-5397.
3. Drozdowski, Maciej (2009). "Programación de procesamiento paralelo". Comunicaciones y Redes Informáticas . doi :10.1007/978-1-84882-310-5. ISBN 978-1-84882-309-9. ISSN  1617-7975.
4. Veltman, B; Lageweg, BJ; Lenstra, JK (1 de diciembre de 1990). "Programación multiprocesador con retrasos en la comunicación". Computación paralela . 16 (2): 173–182. doi :10.1016/0167-8191(90)90056-F. ISSN  0167-8191.
5. Graham, RL; Lawler, EL; Lenstra, JK; Rinnooy Kan, AHG (1979). "Optimización y aproximación en secuenciación y programación deterministas: una encuesta" (PDF) . Actas del Instituto de Investigación Avanzada sobre Optimización Discreta y Aplicaciones de Sistemas del Panel de Ciencia de Sistemas de la OTAN y del Simposio de Optimización Discreta . Elsevier. págs. (5) 287–326.
6. Codd, EF (1 de junio de 1960). "Programación multiprograma". Comunicaciones de la ACM . 3 (6): 347–350. doi : 10.1145/367297.367317 . S2CID  14701351.
7. Du, Jianzhong.; Leung, Joseph Y.-T. (1 de noviembre de 1989). "Complejidad de la programación de sistemas de tareas paralelas". Revista SIAM de Matemática Discreta . 2 (4): 473–487. doi :10.1137/0402042. ISSN  0895-4801.
8. Henning, Sören; Jansen, Klaus; Rau, Malin; Schmarje, Lars (1 de enero de 2020). "Resultados de complejidad e inaproximabilidad para la programación de tareas paralelas y el embalaje en tiras". Teoría de los Sistemas Computacionales . 64 (1): 120-140. arXiv : 1705.04587 . doi :10.1007/s00224-019-09910-6. ISSN  1433-0490. S2CID  67168004.
9. Garey, señor; Graham, RL (1 de junio de 1975). "Límites para la programación multiprocesador con restricciones de recursos". Revista SIAM de Computación . 4 (2): 187–200. doi : 10.1137/0204015 . ISSN  0097-5397.
10. Turek, Juan; Lobo, Joel L.; Yu, Philip S. "Algoritmos aproximados que programan tareas paralelizables | Actas del cuarto simposio anual de ACM sobre arquitecturas y algoritmos paralelos". dl.acm.org . doi :10.1145/140901.141909. S2CID  15607549.
11. Luis, Walter; Tiwari, Prasoon (1994). "Programación de tareas paralelas maleables y no maleables | Actas del quinto simposio anual ACM-SIAM sobre algoritmos discretos". Quinto simposio anual {ACM-SIAM} sobre algoritmos discretos (SODA) : 167–176.
12. Feldmann, Anja; Sgall, Jiří; Teng, Shang-Hua (1 de agosto de 1994). "Programación dinámica en máquinas paralelas". Informática Teórica . 130 (1): 49–72. doi : 10.1016/0304-3975(94)90152-X . ISSN  0304-3975.
13. Amora, Abdel Krim; Bampis, Evripidis; Kenyon, Claire; Manoussakis, Yannis (1 de febrero de 2002). "Programación de tareas multiprocesador independientes". Algorítmica . 32 (2): 247–261. doi :10.1007/s00453-001-0076-9. ISSN  1432-0541. S2CID  17256951.
14. Jansen, Klaus; Porkolab, Lorant (1 de marzo de 2002). "Esquemas de aproximación en tiempo lineal para programar tareas paralelas maleables". Algorítmica . 32 (3): 507–520. doi :10.1007/s00453-001-0085-8. hdl : 11858/00-001M-0000-0014-7B6C-D . ISSN  1432-0541. S2CID  2019475.
15. Jansen, Klaus (2012). "Un algoritmo de aproximación (3/2 + ε) para programar tareas paralelas moldeables y no moldeables | Actas del vigésimo cuarto simposio anual de ACM sobre paralelismo en algoritmos y arquitecturas". 24º Simposio {ACM} sobre paralelismo en algoritmos y arquitecturas, {SPAA} . doi :10.1145/2312005.2312048. S2CID  6586439.
16. "Algoritmos aproximados que programan tareas paralelizables | Actas del cuarto simposio anual de ACM sobre arquitecturas y algoritmos paralelos". doi :10.1145/140901.141909. S2CID  15607549. {{cite journal}}: Citar diario requiere |journal=( ayuda )
17. Błądek, Iwo; Drozdowski, Maciej; Guinand, Frédéric; Schepler, Xavier (1 de octubre de 2015). "Sobre la programación de tareas paralelas contiguas y no contiguas". Diario de programación . 18 (5): 487–495. doi : 10.1007/s10951-015-0427-z . ISSN  1099-1425.