Algoritmo Paralelo - Modelos

O modelo de um algoritmo paralelo é desenvolvido considerando uma estratégia de divisão dos dados e método de processamento e aplicando uma estratégia adequada para reduzir as interações. Neste capítulo, discutiremos os seguintes Modelos de Algoritmo Paralelo -

• Modelo paralelo de dados
• Modelo de gráfico de tarefas
• Modelo de piscina de trabalho
• Modelo mestre escravo
• Consumidor produtor ou modelo de pipeline
• Modelo híbrido

Paralelo de Dados

No modelo paralelo de dados, as tarefas são atribuídas a processos e cada tarefa executa tipos semelhantes de operações em dados diferentes. Data parallelism é uma consequência de operações únicas aplicadas a vários itens de dados.

O modelo de dados paralelos pode ser aplicado em espaços de endereços compartilhados e paradigmas de transmissão de mensagens. No modelo de dados paralelos, os overheads de interação podem ser reduzidos selecionando uma decomposição de preservação de localidade, usando rotinas de interação coletiva otimizadas ou por sobreposição de computação e interação.

A principal característica dos problemas de modelo de paralelismo de dados é que a intensidade do paralelismo de dados aumenta com o tamanho do problema, o que, por sua vez, torna possível usar mais processos para resolver problemas maiores.

Example - Multiplicação de matrizes densas.

Modelo de Gráfico de Tarefa

No modelo de gráfico de tarefas, o paralelismo é expresso por um task graph. Um gráfico de tarefa pode ser trivial ou não trivial. Neste modelo, a correlação entre as tarefas é utilizada para promover a localidade ou para minimizar os custos de interação. Este modelo é aplicado para resolver problemas em que a quantidade de dados associados às tarefas é grande em comparação com o número de cálculos associados a eles. As tarefas são atribuídas para ajudar a melhorar o custo da movimentação de dados entre as tarefas.

Examples - Classificação rápida paralela, fatoração de matriz esparsa e algoritmos paralelos derivados através da abordagem de dividir e conquistar.

Aqui, os problemas são divididos em tarefas atômicas e implementados como um gráfico. Cada tarefa é uma unidade independente de trabalho que tem dependências em uma ou mais tarefas antecedentes. Após a conclusão de uma tarefa, a saída de uma tarefa antecedente é passada para a tarefa dependente. Uma tarefa com tarefa antecedente inicia a execução somente quando toda a tarefa antecedente é concluída. A saída final do gráfico é recebida quando a última tarefa dependente é concluída (Tarefa 6 na figura acima).

Modelo de piscina de trabalho

No modelo de pool de trabalho, as tarefas são atribuídas dinamicamente aos processos para balancear a carga. Portanto, qualquer processo pode potencialmente executar qualquer tarefa. Este modelo é usado quando a quantidade de dados associados às tarefas é comparativamente menor do que o cálculo associado às tarefas.

Não existe uma pré-atribuição desejada de tarefas aos processos. A atribuição de tarefas é centralizada ou descentralizada. Os ponteiros para as tarefas são salvos em uma lista fisicamente compartilhada, em uma fila de prioridade ou em uma tabela ou árvore hash, ou podem ser salvos em uma estrutura de dados fisicamente distribuída.

A tarefa pode estar disponível no início, ou pode ser gerada dinamicamente. Se a tarefa for gerada dinamicamente e uma atribuição descentralizada de tarefas for feita, um algoritmo de detecção de término será necessário para que todos os processos possam realmente detectar a conclusão de todo o programa e parar de procurar mais tarefas.

Example - Pesquisa de árvore paralela

Modelo Master-Slave

No modelo mestre-escravo, um ou mais processos mestre geram tarefas e as alocam aos processos escravos. As tarefas podem ser alocadas de antemão se -

• o mestre pode estimar o volume das tarefas, ou
• uma atribuição aleatória pode fazer um trabalho satisfatório de balanceamento de carga, ou
• escravos recebem tarefas menores em momentos diferentes.

Este modelo é geralmente igualmente adequado para shared-address-space ou message-passing paradigms, uma vez que a interação é naturalmente de duas maneiras.

Em alguns casos, uma tarefa pode precisar ser concluída em fases, e a tarefa em cada fase deve ser concluída antes que a tarefa nas fases seguintes possa ser gerada. O modelo mestre-escravo pode ser generalizado parahierarchical ou multi-level master-slave model em que o mestre de nível superior alimenta a grande parte das tarefas para o mestre de segundo nível, que subdivide as tarefas entre seus próprios escravos e pode realizar uma parte da tarefa por si mesmo.

Precauções no uso do modelo mestre-escravo

Deve-se ter cuidado para garantir que o mestre não se torne um ponto de congestionamento. Isso pode acontecer se as tarefas forem muito pequenas ou os trabalhadores forem comparativamente rápidos.

As tarefas devem ser selecionadas de forma que o custo de execução de uma tarefa domine o custo de comunicação e o custo de sincronização.

A interação assíncrona pode ajudar a sobrepor a interação e o cálculo associado à geração de trabalho pelo mestre.

Modelo de Pipeline

Também é conhecido como producer-consumer model. Aqui, um conjunto de dados é transmitido por meio de uma série de processos, cada um dos quais executa alguma tarefa nele. Aqui, a chegada de novos dados gera a execução de uma nova tarefa por um processo na fila. Os processos podem formar uma fila na forma de matrizes lineares ou multidimensionais, árvores ou gráficos gerais com ou sem ciclos.

Este modelo é uma cadeia de produtores e consumidores. Cada processo na fila pode ser considerado como um consumidor de uma sequência de itens de dados para o processo que o precede na fila e como um produtor de dados para o processo que o segue na fila. A fila não precisa ser uma cadeia linear; pode ser um gráfico direcionado. A técnica de minimização de interação mais comum aplicável a este modelo é a interação sobreposta com computação.

Example - Algoritmo de fatoração de LU paralela.

Modelos Híbridos

Um modelo de algoritmo híbrido é necessário quando mais de um modelo pode ser necessário para resolver um problema.

Um modelo híbrido pode ser composto de vários modelos aplicados hierarquicamente ou vários modelos aplicados sequencialmente a diferentes fases de um algoritmo paralelo.

Example - Classificação rápida paralela