En informática , la programación de grupos es un algoritmo de programación para sistemas paralelos que programa subprocesos o procesos relacionados para que se ejecuten simultáneamente en diferentes procesadores . Por lo general, estos serán subprocesos que pertenecen todos al mismo proceso, pero también pueden ser de diferentes procesos, donde los procesos podrían tener una relación productor-consumidor o provenir del mismo programa MPI .
La programación de pandillas se utiliza para garantizar que si dos o más subprocesos o procesos se comunican entre sí, todos estarán listos para comunicarse al mismo tiempo. Si no estaban programados por pandillas, entonces uno podría esperar para enviar o recibir un mensaje a otro mientras duerme, y viceversa. Cuando los procesadores están suscritos en exceso y la programación de grupos no se usa dentro de un grupo de procesos o subprocesos que se comunican entre sí, cada evento de comunicación podría sufrir la sobrecarga de un cambio de contexto .
La programación de pandillas se basa en una estructura de datos llamada matriz Ousterhout. En esta matriz, cada fila representa un intervalo de tiempo y cada columna un procesador. Los subprocesos o procesos de cada trabajo se empaquetan en una sola fila de la matriz. [1] Durante la ejecución, se realiza un cambio de contexto coordinado en todos los nodos para cambiar de los procesos de una fila a los de la siguiente.
La programación de pandillas es más estricta que la programación conjunta . [2] Requiere que todos los subprocesos del mismo proceso se ejecuten simultáneamente, mientras que la programación conjunta permite fragmentos , que son conjuntos de subprocesos que no se ejecutan al mismo tiempo con el resto del grupo.
La programación de pandillas se implementó y usó en modo de producción en varias máquinas paralelas, sobre todo en la Connection Machine CM-5.
Tipos
Bolsa de pandillas (BoG)
En la programación de grupos, ocurre un mapeo uno a uno, lo que significa que cada tarea se mapeará a un procesador. Por lo general, los trabajos se consideran como pandillas independientes, pero con un esquema de bolsa de pandillas, todas las pandillas se pueden combinar y enviar juntas al sistema. Cuando se ejecutan trabajos en el sistema, la ejecución nunca se puede completar hasta que todas las bandas que pertenecen al mismo BoG completen sus ejecuciones. [3] Por lo tanto, si una pandilla perteneciente a algún trabajo completa su ejecución, tendrá que esperar hasta que todas las pandillas completen sus ejecuciones. Esto conduce a un aumento de la sobrecarga de retardo de sincronización.
Tiempo de respuesta de Bag of Gangs se define como el intervalo de tiempo desde la llegada del BoG al despachador de la red hasta la finalización de los trabajos de todas las sub-bandas que pertenecen al BoG. El tiempo medio de respuesta se define de la siguiente manera:
Tiempo de respuesta (RT) =. [3]
El tiempo de respuesta se ve afectado aún más cuando llega un trabajo prioritario. Siempre que un trabajo de prioridad llega al sistema, ese trabajo tendrá prioridad con respecto a todos los demás trabajos, incluso sobre los que se están ejecutando actualmente en los procesadores. En este caso, cuando llega un trabajo prioritario, el subgrupo que se está ejecutando actualmente en el sistema se detendrá y todo el progreso realizado se perderá y deberá rehacerse. Esta interrupción del trabajo retrasará aún más el tiempo total de respuesta del BoG. [3]
Adaptado por orden de llegada (AFCFS)
El esquema adaptado por orden de llegada (AFCFS) es la versión adaptada del esquema por orden de llegada. Según el esquema de primero en llegar, primero en ser atendido, cualquier trabajo que ocurra primero se reenviará para su ejecución. Pero en el esquema AFCFS, una vez que un trabajo llega al sistema, el trabajo no se programará a menos y hasta que estén disponibles suficientes procesadores para la ejecución del trabajo respectivo. [3] Cuando un trabajo grande llega al sistema y está presente al comienzo de la cola lista, pero no hay suficientes procesadores disponibles, entonces una política AFCFS programará el trabajo más pequeño para el que hay suficientes procesadores disponibles, incluso si ese trabajo está en la parte de atrás de la cola. En otras palabras, este esquema favorece los trabajos más pequeños en comparación con los trabajos más grandes en función de la disponibilidad del procesador, por lo que esto conducirá a una mayor fragmentación en el sistema. [3] [4]
La pandilla más grande primero en servir (LGFS)
En el esquema de ejecución anterior, las tareas que corresponden al aumento del tamaño del trabajo se colocan en una cola, con las tareas que pertenecen a la pandilla más grande programadas primero, pero este método de ejecución tiende a llevar a la falta de recursos de los trabajos más pequeños y, por lo tanto, es no apto para ser ejecutado en sistemas donde el número de procesadores es comparativamente bajo. [5]
El AFCFS y LGFS también tienen que lidiar con posibles fallas del procesador. En tal caso, las tareas que se ejecutan en ese procesador se envían a otros procesadores para su ejecución. Las tareas esperan en la cabeza de la cola de estos procesadores mientras se repara el procesador actual.
Hay dos escenarios que surgen del problema anterior: [5]
- Caso de bloqueo: los procesadores asignados a los trabajos interrumpidos están bloqueados y no pueden ejecutar otros trabajos en su cola hasta que se borren los trabajos de los procesadores dañados. [5]
- Caso sin bloqueo: este caso se produce cuando los trabajos que ya se están ejecutando en los procesadores se procesan antes en lugar de esperar a que los trabajos bloqueados reanuden la ejecución. [5]
Programación de pandillas emparejadas
La programación grupal mientras se ejecutan los procesos vinculados de E / S mantiene las CPU inactivas mientras esperan respuestas de los otros procesadores, mientras que los procesadores inactivos se pueden utilizar para ejecutar tareas. Si el grupo consiste en una combinación de CPU y Procesos de E / S, dado que estos procesos interfieren poco en el funcionamiento de los demás, se pueden definir algoritmos para mantener ocupados tanto a la CPU como a las E / S al mismo tiempo y aprovechando el paralelismo. Este método presentaría la idea de hacer coincidir pares de bandas, una basada en E / S y una vinculada a la CPU. Cada pandilla asumiría que está trabajando de forma aislada, ya que utilizan diferentes dispositivos. [6]
Algoritmo de programación
- Caso general: en el caso general, se designa un nodo central en la red para manejar la asignación de tareas y la asignación de recursos. Mantiene la información en una matriz de Ousterhout. En la programación de grupo estricta, se selecciona una fila a la vez, después de lo cual un programador de nodos programa un proceso en la celda respectiva de esa fila. [6]
- Pandilla emparejada: en la programación de pandillas pareadas, se seleccionan dos filas en lugar de una, una para cada pandilla de E / S vinculada y pandilla de CPU. Queda a discreción del programador local asignar trabajos a los procesadores apropiados para obtener el máximo paralelismo permitido. [6]
Métodos de sincronización
Programación simultánea de pandillas (CGS)
La programación de pandillas concurrentes es un algoritmo altamente escalable y versátil y asume la existencia de un sincronizador que utiliza el reloj interno de cada nodo. CGS consta principalmente de los siguientes tres componentes. [7]
- Módulo de procesador / memoria (también llamado elemento de procesamiento).
- Red bidireccional que permite la comunicación 1-1.
- Un sincronizador que realiza la sincronización de todos los PE después de un intervalo constante.
El algoritmo de sincronización se realiza en dos etapas. [7]
- Cuando la carga cambia, el programador de la interfaz de usuario crea una tabla de tiempo dedicada.
- Luego, el programador local sigue la tabla de tiempo cambiando entre los trabajos que les ha distribuido el programador de la interfaz.
Suponemos la existencia de un sincronizador que envía la señal a todos los nodos de un clúster en un intervalo constante. El CGS utiliza el hecho de que los eventos más comunes que ocurren en una PC son las interrupciones del temporizador y utilizan el mismo parámetro para ser el reloj interno. [7]
- Se inicializa un contador común que se incrementa cada vez que se encuentra una interrupción y se designa como el reloj interno del sistema operativo.
- Todos los nodos se sincronizan después de un intervalo de verificación 't' y utilizan los relojes internos de los nodos individuales.
- Si después del tiempo t no hay discrepancia entre el reloj individual de los nodos y el reloj global, se amplía el intervalo de tiempo t. De lo contrario, se acorta.
- Compruebe y actualice constantemente el intervalo de comprobación t.
COMPARTIR el sistema de programación
El sistema de programación SHARE utiliza el sistema de reloj interno de cada nodo y se sincroniza mediante el protocolo NTP . El sabor de la programación se implementa mediante la recopilación de trabajos con los mismos requisitos de recursos en un grupo y la ejecución de los mismos durante un intervalo de tiempo predefinido. Los trabajos incompletos se reemplazan una vez que se agota el intervalo de tiempo. [8]
La memoria local del nodo se utiliza como espacio de intercambio para trabajos preferentes. Las principales ventajas del sistema programado SHARE son que garantiza el tiempo de servicio para los trabajos aceptados y admite trabajos tanto por lotes como interactivos.
Sincronización:
Cada grupo de procesos que utilizan los mismos recursos se asigna a un procesador diferente. El sistema SHARE consta principalmente de tres módulos colaboradores. [8]
- Un programador global: este programador dirige al programador local el orden específico en el que ejecutar sus procesos (miembros de pandillas locales).
- Un programador local: una vez que el programador local proporciona los trabajos para ejecutar por el programador global, se asegura de que solo uno de los procesos paralelos se ejecute en cualquiera de los procesadores en un intervalo de tiempo determinado. El programador local requiere un cambio de contexto para apropiarse de un trabajo una vez que su intervalo de tiempo ha expirado y cambiar uno nuevo en su lugar.
- Interfaz con el sistema de comunicación: el subsistema de comunicación debe satisfacer varios requisitos que aumentan en gran medida los requisitos generales del planificador. Consisten principalmente en:
- Eficiencia: debe exponer el rendimiento del hardware de la interconexión al nivel del cliente.
- Control de acceso: debe administrar el acceso al subsistema de comunicación
- Protección y seguridad: La interconexión debe mantener la separación de los procesadores al no permitir que uno afecte el desempeño del otro.
- Multiprotocolo: la interconexión debe poder mapear varios protocolos simultáneamente para satisfacer las diferentes necesidades del cliente.
Criterios de empaque
Se crea una nueva ranura cuando no podemos empaquetar el trabajo en la ranura disponible. En caso de que se abra una nueva ranura incluso si el trabajo se puede empaquetar en la ranura disponible, entonces aumentará la fracción de ejecución que es igual a uno sobre el número de ranuras utilizadas. Por lo tanto, se han ideado ciertos algoritmos sobre criterios de empaque y se mencionan a continuación:
Algoritmo basado en capacidad
Este algoritmo monitorea la capacidad de las ranuras y decide si es necesario abrir una nueva ranura. Hay dos variantes de este algoritmo:
1. Primer ajuste. Aquí, se comprueba la capacidad de las ranuras utilizadas en un orden secuencial y luego se elige la primera que tenga capacidad suficiente. Si ninguna de las ranuras disponibles tiene suficiente capacidad, se abre una nueva ranura y los elementos de procesamiento (PE) se asignan en la ranura en orden secuencial. [9]
2. Mejor ajuste. A diferencia del primer ajuste, las ranuras utilizadas se clasifican según la capacidad, pero no en orden secuencial. Se elige la ranura con la menor capacidad suficiente. Si ninguna de las ranuras utilizadas tiene capacidad suficiente, solo se abre una nueva ranura. Una vez que se abre la nueva ranura, los elementos de procesamiento (PE) se asignan en la ranura en orden secuencial según el algoritmo anterior. [9]
Algoritmos basados en izquierda-derecha
Este algoritmo es una versión modificada del algoritmo de mejor ajuste. En el algoritmo de mejor ajuste, los PE se asignan en un orden secuencial, pero en este algoritmo, los PE se pueden insertar desde ambas direcciones para reducir la superposición entre diferentes conjuntos de PE asignados a diferentes trabajos. [9]
1. De izquierda a derecha por tamaño. Aquí, los PE se pueden insertar en orden secuencial y en orden secuencial inverso según el tamaño del trabajo. Si el tamaño del trabajo es pequeño, los PE se insertan de izquierda a derecha y si el trabajo es grande, los PE se insertan de derecha a izquierda. [9]
2. De izquierda a derecha por ranuras. A diferencia del algoritmo anterior, donde la elección se basaba en el tamaño del trabajo, aquí la elección depende de la ranura. Ahora, los espacios se indican como llenados, es decir, llenados desde la izquierda o desde la derecha. Los PE se asignan al trabajo en el mismo orden. El número de ranuras en ambos lados es aproximadamente igual, por lo que cuando se abre una nueva ranura, la dirección se indica en función del número de ranuras en ambas direcciones. [9]
Algoritmos basados en carga
Tanto los algoritmos basados en la capacidad como los basados en la izquierda-derecha no se adaptan a la carga de los PE individuales. Los algoritmos basados en carga tienen en cuenta la carga en el PE individual al tiempo que rastrean la superposición entre conjuntos de PE asignados a diferentes trabajos. [9]
1. Carga máxima mínima. En este esquema, los PE se ordenan en función de la carga que cada trabajo tendrá en los PE. La disponibilidad de los PE libres en la ranura determina la capacidad de la ranura. Suponga que los PE se asignan a un trabajo que tiene hilos, el PE en el orden de carga (último) determinará la carga máxima que puede tener cualquier PE que esté disponible en la ranura. Se elige la ranura que tiene una carga máxima mínima en cualquier PE y se utilizan varios PE libres menos cargados en la ranura. [9]
2. Carga media mínima. A diferencia del esquema anterior, en el que las ranuras se eligieron en función de la carga máxima mínima en PE, aquí las ranuras se eligen en función del promedio de la carga en el PE menos cargados. [9]
Algoritmo basado en amigos
En este algoritmo, los PE se asignan en grupos, no individualmente. Los PE se dividen primero en grupos que son potencia de dos. A cada miembro del grupo se le asignará un controlador y cuando llega un trabajo de tamaño n, se le asigna un controlador de tamaño 2 [lg 2] (la potencia más pequeña a 2 que es mayor o igual que n). El controlador se asigna clasificando primero todas las ranuras utilizadas y luego identificando grupos de 2 [lg 2] procesadores libres contiguos. Si un controlador tiene todos los PE libres en algunas de las ranuras, solo se le asignará un trabajo recién llegado a ese controlador. De lo contrario, se abre una nueva ranura. [9]
Algoritmo basado en migración
En todos los algoritmos mencionados anteriormente, la política de colocación inicial es fija y los trabajos se asignan a los PE en función de eso. Sin embargo, este esquema migra trabajos de un conjunto de PE a otro conjunto de PE, lo que a su vez mejora la fracción de ejecución del sistema. [9]
Ver también
Referencias
- Programación de pandillas, tiempo compartido en computadoras paralelas, SC98, noviembre de 1998 (un resumen)
- Características de rendimiento de la programación de pandillas en entornos multiprogramados, SC97, noviembre de 1997
- ^ Dror G. Feitelson (1996). Esquemas de empaque para la programación de pandillas . En Estrategias de programación de trabajos para el procesamiento paralelo, Springer-Verlag Lecture Notes in Computer Science Vol. 1162, págs. 89-110.
- ^ Feitelson, Dror G .; Rudolph, Larry (1992). "Beneficios de rendimiento de programación de pandillas para la sincronización de grano fino". Revista de Computación Paralela y Distribuida . 16 (4): 306–318. CiteSeerX 10.1.1.79.7070 . doi : 10.1016 / 0743-7315 (92) 90014-e .
- ^ a b c d e Papazachos, Zafeirios C .; Karatza, Helen D. (agosto de 2010). "Evaluación del desempeño de la programación de bolsas de pandillas en un sistema distribuido heterogéneo". Revista de sistemas y software . 83 (8): 1346-1354. doi : 10.1016 / j.jss.2010.01.009 .
- ^ Zafeirios C. Papazachos, Helen D. Karatza, "Evaluación del desempeño de la programación de pandillas en un sistema de dos clústeres con migraciones", IPDPS , 2009, Simposio de procesamiento en paralelo y distribuido, Simposio de procesamiento internacional, paralelo y distribuido, International 2009, págs. 1-8, doi : 10.1109 / IPDPS.2009.5161172
- ^ a b c d "Análisis de rendimiento de la programación de pandillas en un sistema distribuido bajo fallas de procesador" (PDF) .
- ^ a b c "Programación de pandillas emparejadas" (PDF) .
- ^ a b c Hyoudou, Kazuki; Kozakai, Yasuyuki; Nakayama, Yasuichi (2007). "Una implementación de un programador de pandillas concurrente para un sistema de clúster basado en PC". Sistemas y computadoras en Japón . 38 (3): 39–48. doi : 10.1002 / scj.20458 .
- ^ a b Sociedad, Ieee Computer (1996). Programación de grupos para sistemas multiprocesadores distribuidos altamente eficientes . Fronteras '96. págs. 4–. ISBN 9780818675515.
- ^ a b c d e f g h yo j "Esquemas de embalaje para la programación de pandillas" (PDF) .