Algoritmo paralelo - Modelos

El modelo de un algoritmo paralelo se desarrolla considerando una estrategia para dividir los datos y el método de procesamiento y aplicando una estrategia adecuada para reducir las interacciones. En este capítulo, discutiremos los siguientes modelos de algoritmos paralelos:

• Modelo paralelo de datos
• Modelo de gráfico de tareas
• Modelo de piscina de trabajo
• Modelo maestro esclavo
• Productor consumidor o modelo de canalización
• Modelo híbrido

Paralelo de datos

En el modelo paralelo de datos, las tareas se asignan a los procesos y cada tarea realiza tipos similares de operaciones en diferentes datos. Data parallelism es una consecuencia de operaciones únicas que se aplican a varios elementos de datos.

El modelo paralelo de datos se puede aplicar en espacios de direcciones compartidas y paradigmas de paso de mensajes. En el modelo paralelo de datos, los gastos generales de interacción se pueden reducir seleccionando una localidad que preserva la descomposición, utilizando rutinas de interacción colectiva optimizadas o superponiendo el cálculo y la interacción.

La característica principal de los problemas del modelo paralelo de datos es que la intensidad del paralelismo de datos aumenta con el tamaño del problema, lo que a su vez hace posible utilizar más procesos para resolver problemas más grandes.

Example - Multiplicación de matrices densas.

Modelo de gráfico de tareas

En el modelo de gráfico de tareas, el paralelismo se expresa mediante un task graph. Un gráfico de tareas puede ser trivial o no trivial. En este modelo, la correlación entre las tareas se utiliza para promover la localidad o minimizar los costos de interacción. Este modelo se aplica para resolver problemas en los que la cantidad de datos asociados con las tareas es enorme en comparación con la cantidad de cálculos asociados con ellas. Las tareas se asignan para ayudar a mejorar el costo del movimiento de datos entre las tareas.

Examples - Clasificación rápida en paralelo, factorización de matriz dispersa y algoritmos paralelos derivados mediante el enfoque de dividir y conquistar.

Aquí, los problemas se dividen en tareas atómicas y se implementan como un gráfico. Cada tarea es una unidad de trabajo independiente que tiene dependencias en una o más tareas precedentes. Después de completar una tarea, la salida de una tarea anterior se pasa a la tarea dependiente. Una tarea con tarea antecedente comienza a ejecutarse solo cuando se completa toda su tarea antecedente. El resultado final del gráfico se recibe cuando se completa la última tarea dependiente (Tarea 6 en la figura anterior).

Modelo de piscina de trabajo

En el modelo de grupo de trabajo, las tareas se asignan dinámicamente a los procesos para equilibrar la carga. Por lo tanto, cualquier proceso puede ejecutar potencialmente cualquier tarea. Este modelo se utiliza cuando la cantidad de datos asociados con las tareas es comparativamente menor que el cálculo asociado con las tareas.

No hay una asignación previa deseada de tareas a los procesos. La asignación de tareas está centralizada o descentralizada. Los punteros a las tareas se guardan en una lista compartida físicamente, en una cola de prioridad o en una tabla o árbol hash, o podrían guardarse en una estructura de datos distribuida físicamente.

La tarea puede estar disponible al principio o puede generarse dinámicamente. Si la tarea se genera dinámicamente y se realiza una asignación descentralizada de la tarea, entonces se requiere un algoritmo de detección de terminación para que todos los procesos puedan detectar realmente la finalización de todo el programa y dejar de buscar más tareas.

Example - Búsqueda de árbol paralelo

Modelo maestro-esclavo

En el modelo maestro-esclavo, uno o más procesos maestros generan tareas y las asignan a procesos esclavos. Las tareas pueden asignarse de antemano si:

• el maestro puede estimar el volumen de las tareas, o
• una asignación aleatoria puede hacer un trabajo satisfactorio de equilibrio de carga, o
• a los esclavos se les asignan tareas más pequeñas en diferentes momentos.

Este modelo es generalmente igualmente adecuado para shared-address-space o message-passing paradigms, ya que la interacción es naturalmente de dos formas.

En algunos casos, es posible que sea necesario completar una tarea en fases, y la tarea de cada fase debe completarse antes de que se pueda generar la tarea de las siguientes fases. El modelo maestro-esclavo se puede generalizar parahierarchical o multi-level master-slave model en el que el maestro de nivel superior alimenta la gran parte de las tareas al maestro de segundo nivel, quien subdivide aún más las tareas entre sus propios esclavos y puede realizar una parte de la tarea en sí.

Precauciones al usar el modelo maestro-esclavo

Se debe tener cuidado para asegurar que el maestro no se convierta en un punto de congestión. Puede suceder si las tareas son demasiado pequeñas o los trabajadores son relativamente rápidos.

Las tareas deben seleccionarse de manera que el costo de realizar una tarea domine el costo de la comunicación y el costo de la sincronización.

La interacción asincrónica puede ayudar a superponer la interacción y el cálculo asociado con la generación de trabajo por parte del maestro.

Modelo de canalización

También se conoce como producer-consumer model. Aquí, un conjunto de datos se transmite a través de una serie de procesos, cada uno de los cuales realiza alguna tarea en él. Aquí, la llegada de nuevos datos genera la ejecución de una nueva tarea por un proceso en la cola. Los procesos podrían formar una cola en forma de matrices lineales o multidimensionales, árboles o gráficos generales con o sin ciclos.

Este modelo es una cadena de productores y consumidores. Cada proceso de la cola se puede considerar como consumidor de una secuencia de elementos de datos para el proceso que lo precede en la cola y como productor de datos para el proceso que lo sigue en la cola. No es necesario que la cola sea una cadena lineal; puede ser un gráfico dirigido. La técnica de minimización de interacciones más común aplicable a este modelo es la interacción superpuesta con la computación.

Example - Algoritmo de factorización LU en paralelo.

Modelos híbridos

Se requiere un modelo de algoritmo híbrido cuando se puede necesitar más de un modelo para resolver un problema.

Un modelo híbrido puede estar compuesto por múltiples modelos aplicados jerárquicamente o múltiples modelos aplicados secuencialmente a diferentes fases de un algoritmo paralelo.

Example - Clasificación rápida paralela