En informática , la programación en grupo 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, se trata de subprocesos que pertenecen 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 grupal se utiliza para garantizar que, si dos o más subprocesos o procesos se comunican entre sí, todos estén listos para comunicarse al mismo tiempo. Si no estuvieran programados en grupo, uno podría esperar para enviar o recibir un mensaje a otro mientras está inactivo, y viceversa. Cuando los procesadores están sobrecargados y no se utiliza la programación grupal 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 en grupo se basa en una estructura de datos denominada matriz de Ousterhout. En esta matriz, cada fila representa una porción 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 fila siguiente.
La programación en grupo 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 simultáneamente con el resto del grupo.
La programación de pandillas se implementó y utilizó en modo de producción en varias máquinas paralelas, especialmente en la máquina de conexión CM-5.
En la programación de grupos, se produce una asignación uno a uno, lo que significa que cada tarea se asignará a un procesador. Por lo general, los trabajos se consideran grupos independientes, pero con un esquema de bolsa de grupos, todos los grupos se pueden combinar y enviar juntos al sistema. Cuando se ejecutan trabajos en el sistema, la ejecución nunca se puede completar hasta que y a menos que todos los grupos que pertenecen al mismo BoG completen sus ejecuciones. [3] Por lo tanto, si un grupo que pertenece a algún trabajo completa su ejecución, tendrá que esperar hasta que todos los grupos completen sus ejecuciones. Esto conduce a una mayor sobrecarga de retardo de sincronización.
El tiempo de respuesta de la Bolsa de Bandas se define como el intervalo de tiempo desde la llegada de la Bolsa de Bandas al despachador de red hasta la finalización de los trabajos de todas las subbandas que pertenecen a la Bolsa de Bandas. El tiempo de respuesta promedio 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 prioritario 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 que se haya realizado se perderá y deberá rehacerse. Esta interrupción del trabajo retrasará aún más el tiempo de respuesta total del BoG. [3]
El esquema AFCFS (por sus siglas en inglés, First come firstserved) es la versión adaptada del esquema de primero en llegar, primero en ser atendido. Según el esquema de primero en llegar, primero en ser atendido, el trabajo que llegue primero será reenviado para su ejecución. Pero en el esquema AFCFS, una vez que un trabajo llega al sistema, el trabajo no se programará a menos que y hasta que haya suficientes procesadores disponibles para la ejecución del trabajo respectivo. [3] Cuando un trabajo grande llega al sistema y está presente al comienzo de la cola de listos pero no hay suficientes procesadores disponibles, entonces una política AFCFS programará el trabajo más pequeño para el cual haya suficientes procesadores disponibles, incluso si ese trabajo está al final 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]
En el esquema de ejecución anterior, las tareas que corresponden a un tamaño de trabajo creciente se colocan en una cola, y las tareas que pertenecen al grupo más grande se programan primero, pero este método de ejecución tiende a provocar la escasez de recursos de trabajos más pequeños y, por lo tanto, no es adecuado para ejecutarse en sistemas donde el número de procesadores es comparativamente bajo. [5]
El AFCFS y el 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 parte superior de la cola en estos procesadores mientras se repara el procesador actual.
De la cuestión anterior se desprenden dos escenarios: [5]
La programación grupal mientras se ejecutan los procesos vinculados a E/S mantiene a 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 mezcla de procesos de CPU y E/S, dado que estos procesos interfieren poco en el funcionamiento de los demás, se pueden definir algoritmos para mantener tanto la CPU como la E/S ocupadas al mismo tiempo y explotar el paralelismo. Este método presentaría la idea de emparejar pares de grupos, uno basado en E/S y otro vinculado a la CPU. Cada grupo asumiría que está trabajando de forma aislada ya que utilizan diferentes dispositivos. [6]
La programación simultánea de grupos es un algoritmo altamente escalable y versátil que supone la existencia de un sincronizador que utiliza el reloj interno de cada nodo. La programación simultánea de grupos consta principalmente de los tres componentes siguientes: [7]
El algoritmo de sincronización se realiza en dos etapas. [7]
Suponemos la existencia de un sincronizador que envía la señal a todos los nodos de un cluster en un intervalo constante. El CGS utiliza el hecho de que los eventos más comunes que ocurren en un PC son interrupciones del temporizador y utilizan el mismo parámetro que es el reloj interno. [7]
El sistema de programación SHARE utiliza el sistema de reloj interno de cada nodo y se sincroniza mediante el protocolo NTP . La programación se implementa mediante la recopilación de trabajos con los mismos requisitos de recursos en un grupo y su ejecución durante un intervalo de tiempo predefinido. Los trabajos incompletos se eliminan una vez que se agota el intervalo de tiempo. [8]
La memoria local del nodo se utiliza como espacio de intercambio para los trabajos preseleccionados. Las principales ventajas del sistema programado SHARE son que garantiza el tiempo de servicio para los trabajos aceptados y admite tanto trabajos por lotes como interactivos.
Sincronización:
Cada grupo de procesos que utiliza los mismos recursos se asigna a un procesador diferente. El sistema SHARE consta principalmente de tres módulos que colaboran. [8]
Se crea un nuevo espacio cuando no podemos empaquetar el trabajo en el espacio disponible. En caso de que se abra un nuevo espacio incluso si el trabajo se puede empaquetar en el espacio disponible, entonces la fracción de ejecución que es igual a uno sobre el número de espacios utilizados aumentará. Por lo tanto, se han diseñado ciertos algoritmos sobre los criterios de empaquetado que se mencionan a continuación:
Este algoritmo controla la capacidad de las ranuras y decide si es necesario abrir una nueva ranura. Existen dos variantes de este algoritmo:
1. Primer ajuste. Aquí se comprueba la capacidad de las ranuras utilizadas en orden secuencial y luego se elige la primera que tenga suficiente capacidad. Si ninguna de las ranuras disponibles tiene suficiente capacidad, se abre una nueva ranura y se asignan los elementos de procesamiento (PE) en la ranura en orden secuencial. [9]
2. Mejor ajuste. A diferencia del primer ajuste, las ranuras utilizadas se ordenan en función de 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, entonces 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]
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. Izquierda-derecha por slots. A diferencia del algoritmo anterior, donde la elección se basaba en el tamaño del trabajo, aquí la elección depende del slot. Ahora, los slots se indican como ocupados, es decir, se llenan desde la izquierda o desde la derecha. Los PE se asignan al trabajo en el mismo orden. El número de slots en ambos lados es aproximadamente igual, por lo que cuando se abre un nuevo slot, la dirección se indica en función del número de slots en ambas direcciones. [9]
Tanto los algoritmos basados en capacidad como los basados en izquierda-derecha no tienen en cuenta la carga de los PE individuales. Los algoritmos basados en carga tienen en cuenta la carga de los PE individuales mientras 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á sobre ellos. La disponibilidad de los PE libres en la ranura determina la capacidad de la ranura. Supongamos que los PE se asignan a un trabajo que tiene subprocesos, el PE en el orden de carga (el último) determinará la carga máxima que cualquier PE puede tener que esté disponible en la ranura. Se elige la ranura que tiene la carga máxima mínima sobre cualquier PE y se utiliza una cantidad de PE libres menos cargados en la ranura. [9]
2. Carga media mínima. A diferencia del esquema anterior, en el que las ranuras se elegían en función de la carga máxima mínima sobre los PE, aquí las ranuras se eligen en función del promedio de la carga sobre los PE menos cargados. [9]
En este algoritmo, los PE se asignan en grupos, no individualmente. Primero, los PE se dividen en grupos que son potencias de dos. A cada miembro del grupo se le asignará un controlador y, cuando llegue un trabajo de tamaño n, se le asignará un controlador de tamaño 2 [lg 2] (la potencia más pequeña de 2 que sea mayor o igual a n). El controlador se asigna primero ordenando 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, entonces solo se le asignará un trabajo recién llegado. De lo contrario, se abre una nueva ranura. [9]
En todos los algoritmos mencionados anteriormente, la política de ubicación inicial es fija y los trabajos se asignan a los PE en función de ella. 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]
