capitulo3

Prévia do material em texto

3
PROJETO DE ALGORITMOS PARALELOS
O desenvolvimento de um algoritmo é um componente crítico na solução de proble-
mas usando computadores. Um algoritmo seqüencial pode ser definido como uma seqüên-
cia de passos básicos para resolver um dado problema usando um computador seqüencial.
Já um algoritmo paralelo pode ser visto como uma receita que diz como resolver um dado
problema usando múltiplos processadores. Entretanto, especificar um algoritmo paralelo
envolve mais do que especificar os passos. Um algoritmo paralelo tem a dimensão de
concorrência e o desenvolvedor do algoritmo deve especificar um conjunto de passos que
podem ser executados simultaneamente. É essencial obter algum benefício de desempe-
nho ao utilizar um computador paralelo. Na prática, especificar um algoritmo paralelo pode
envolver todos ou alguns dos seguintes passos:
• Identificar porções de trabalho que podem ser realizadas concorrentemente;
• Mapear as porções concorrentes de trabalho em múltiplos processos para execu-
ção em paralelo;
• Distribuir entrada, saída e dados intermediários associados ao programa;
• Gerenciar o acesso aos dados compartilhados por múltiplos processadores;
• Sincronizar os processadores em vários estágios de execução do programa para-
lelo.
Geralmente, há diversas escolhas para cada um dos passos citados anteriormente.
Porém, poucas combinações de escolhas levam a um algoritmo paralelo que produza de-
sempenho compatível com os recursos computacionais e de armazenamento usados para
resolver o problema. Diversas escolhas produzem o melhor desempenho em diferentes
arquiteturas paralelas ou sob diferentes paradigmas de programação paralela.
O objetivo deste capítulo é discutir o processo de projeto e implementação de algorit-
mos paralelos.
58 DCC/UFLA - Programação Paralela e Distribuída
3.1 CONCEITOS INICIAIS
Dividir a computação em computações menores e atribuí-las a diferentes processado-
res para execução paralela são os dois passos chave no projeto de algoritmos paralelos.
O processo de dividir uma computação em partes menores, sendo que algumas ou
todas as partes podem ser potencialmente executadas em paralelo, é denominado decom-
posição. As tarefas são as unidades de computação definidas pelo programador onde
a computação principal é subdividida por meio da decomposição. A execução simultânea
de múltiplas tarefas é a chave para reduzir o tempo necessário para resolver o problema
inteiro. As tarefas podem ser de tamanho arbitrário, mas uma vez definidas, elas são consi-
deradas como unidades de computação granularidade. As tarefas nas quais um problema
é decomposto pode não ser todas do mesmo tamanho.
Exemplo 1: Considere uma multiplicação de uma matriz A densa, N x N, por um
vetor b para produzir outro vetor y. O i-ésimo elemento y[i] do vetor produto é o pro-
duto vetorial da i-ésima linha de A pela entrada do vetor b; isto é, y[i] = ∑N−1j=0 A[i, j].b[ j].
Como apresenta a Figura 3.1, a computação de cada y[i] pode ser considerada uma tarefa.
Alternativamente, como mostra a Figura 3.2, a computação pode ser decomposta em um
número menor de tarefas, onde cada tarefa computa n/3 das entradas do vetor y. Assim,
a tarefa 1 é composta pelas computações y[0] = ∑N−1j=0 A[0, j].b[ j], y[1] = ∑
N−1
j=0 A[0, j].b[ j] e
y[2] = ∑N−1j=0 A[0, j].b[ j].
Figura 3.1: Decomposição da multiplicação da matriz por vetor em N tarefas
Note que na Figura 3.1 todas as tarefas são independentes e podem ser executadas
todas juntas ou em qualquer sequencia. Entretanto, em geral, algumas tarefas podem usar
dados produzidos por outras tarefas e precisar esperar tais resultados para para iniciar sua
execução. O grafo de dependência de tarefas é a abstração usada para expressar as
dependências entre as tarefas e sua ordem relativa de execução. Em um grafo orientado
Projeto de Algoritmos Paralelos 59
Figura 3.2: Decomposição da multiplicação da matriz por vetor em N/3 tarefas.
e acíclico, os nós representam as tarefas e as arestas orientadas indicam a dependência
entre os nós. Uma tarefa correspondente a um nó e só pode ser executada quando todas
as tarefas conectadas a este nó por arestas incidentes tenham completado sua execução.
Note que o grafo de dependência de tarefas pode ser desconectado e o conjunto de arestas
do grafo de dependência de tarefas pode ser vazio. É o caso da multiplicação de matriz por
vetor, onde cada tarefa computa um subconjunto de entradas do vetor produto.
Exemplo 2: Considere o banco de dados relacional de veículos da Figura 3.3. Cada
linha da tabela é um registro que contém dados correspondentes a um determinado veí-
culo, tal como seu ID, modelo, ano, cor, etc. Considere as computações realizadas no
processamento da consulta:
MODEL="Civic"AND Year="2001"AND (COLOR="Green"OR COLOR="White")
Esta consulta procura todos os Civics 2001 cuja cor seja Green ou White. No banco de
dados relacional, esta consulta é processada criando tabelas intermediárias. Uma possível
forma é primeiro criar as quatro tabelas da Figura 3.4: uma tabela contendo todos os Civics,
uma tabela contendo todos os carros modelo 2001, uma tabela contendo todos os carros
de cor Green e uma tabela contendo todos os carros de cor White. A seguir, a computação
continua combinando estas tabelas pela computação de suas interseções ou uniões em
pares. Em particular, ele computa a interseção da tabela Civic com a tabela ano modelo
2001, para construir uma tabela de todos os modelos Civic 2001. Similarmente, ele computa
a união de tabelas cores Green e White para computar uma tabela armazenando todos os
carros cuja cor é Green ou White. Finalmente, ele computa a interseção da tabela contendo
todos os Civics 2001 com a tabela contendo todos os veículos Green ou White e retorna a
lista desejada.
Para este exemplo, cada nó na Figura 3.4 é uma tarefa que corresponde a uma tabela
intermediária que precisa ser computada e as setas entre os nós indicam dependências
60 DCC/UFLA - Programação Paralela e Distribuída
Figura 3.3: Banco de dados de armazenamento de informação sobre veículos usados
Figura 3.4: As diferentes tabelas e suas dependências em uma operação de processamento de
consulta
entre as tarefas. Por exemplo, antes de computar a tabela que corresponde aos Civics
2001, deve-se computar a tabela de todos os Civics e a tabela de todos os carros modelo
2001.
Note que há múltiplas formas de expressar certas computações, especialmente aque-
las envolvendo operações associativas tais como adição, multiplicação e AND ou OR ló-
Projeto de Algoritmos Paralelos 61
gicos. Diferentes formas de arranjar computações podem levar a diferentes grafos de de-
pendência de tarefas com diferentes características. Por exemplo, o banco de dados do
Exemplo 2 pode ser resolvido computando primeiro a tabela de todos os carros GREEN ou
WHITE, e então realizar uma interseção com a tabela de todos os carros modelo 2001, e
finalmente combinar os resultados com a tabela de todos os Civics. Esta seqüência pode
ser visualizada na Figura 3.5.
Figura 3.5: Um grafo alternativo de dependência de dados para a operação de processamento de
consulta
A taxa entre a quantidade de computação e de comunicação dentro de um programa
paralelo ou distribuído é conhecida como granularidade. O número e o tamanho das tarefas
em que um problema pode ser decomposto determina a granulosidade ou granularidade da
decomposição.
Uma decomposição em um número grande de pequenas tarefas é chamada granulo-
sidade fina (fine-grained), pois há relativamente menos execuções de instruções de CPU
produtivas comparadas com o número de vezes que os processadores comunicam via me-
mória compartilhada ou passagem de mensagens e esperam para sincronizar com outros
processadores.Já uma decomposição em um número menor de tarefas grandes é chamada granu-
losidade grossa (coarse-grained), pois ocorrerá um maior número de execuções de CPU
do que de comunicação entre os processadores.
Por exemplo, a decomposição da multiplicação matriz por vetor mostrada na Figura 3.1
é considerada de granulosidade fina porque há um grande número de tarefas que realizam
62 DCC/UFLA - Programação Paralela e Distribuída
um único produto. A Figura 3.2 mostra uma decomposição do mesmo problema em N/3
tarefas, onde cada tarefa computa 3 das entradas do vetor resultante de tamanho N.
Um conceito relacionado a granulosidade é o grau de concorrência.
O grau máximo de concorrência é o número máximo de tarefas que podem ser execu-
tadas simultaneamente em um programa paralelo em um instante de tempo. Normalmente,
o grau máximo de concorrência é menor do que o número total de tarefas devido às de-
pendências entre as tarefas. Por exemplo, o grau máximo de concorrência nos grafos de
tarefas das Figuras 3.4 e 3.5 é 4.
O grau de concorrência também depende da forma do grafo de dependência de tarefas
e a mesma granulosidade, em geral, não garante o mesmo grau de concorrência. Por
exemplo, considere o os grafos de tarefas da Figura 3.6, são abstrações dos grafos das
Figuras 3.4 e 3.5. O número em cada nó representa a quantidade de trabalho requerido
para completar a tarefa correspondente àquele nó.
Figura 3.6: Abstrações dos grafos de tarefas das Figuras 3.4 e 3.5
Em um grafo de dependência de tarefas, vamos nos referir aos nós que não possuem
arestas incidentes a eles como sendo os nós iniciais e os nós que possuem arestas que
saem deles como os nós finais. O mais longo caminho orientado entre um par de nós
iniciais e finais é conhecido como caminho crítico. A soma dos pesos dos nós ao longo
deste caminho é conhecido como tamanho de caminho crítico, onde o peso de um nó é
o tamanho ou a quantidade de trabalho associado com a tarefa correspondente. No grafo
de dependência de tarefas da Figura 3.6(a) o tamanho do caminho crítico é 27. Na Figura
3.6(b) é 34.
3.1.1 Processo e Mapeamento
Um processo refere-se ao agente de processamento ou computação que desempenha
tarefas. Os processadores são unidades de hardware que fisicamente realizam computa-
Projeto de Algoritmos Paralelos 63
ções. Há uma correspondência um-para-um entre processos e processadores e é apro-
priado assumir que há tantos processos quanto o número de CPUs físicas do computador
paralelo. O termo processo não é exatamente igual à definição usada em sistemas opera-
cionais. Um processo é uma entidade abstrata que usa o código e dados correspondentes
a uma tarefa para produzir a saída daquela tarefa dentro de uma quantidade de tempo fi-
nita, depois que a tarefa é ativada pelo programa paralelo. Durante este tempo, além de
realizar computações, um processo pode sincronizar ou comunicar com outros processos,
se for necessário. Para obter speedup sobre a implementação seqüencial, um programa
paralelo deve ter diversos processos ativos simultaneamente, trabalhando sobre diferentes
tarefas. O mecanismo pelo qual as tarefas são atribuídas aos processos para execução é
denominado mapeamento.
Um bom mapeamento deve buscar maximizar o uso da concorrência pelo mapea-
mento independente das tarefas em diferentes processos e minimizar o tempo de execução
total, garantindo que processos estejam disponíveis para executar as tarefas no caminho
crítico o mais breve que estas tarefas tornem-se executáveis. Além disso, deve minimi-
zar a comunicação entre os processos pelo mapeamento de tarefas com um alto grau de
comunicação mútua sobre o mesmo processo.
Figura 3.7: Mapeamento dos grafos de tarefas da Figura 3.6 em 4 processos
A Figura 3.7 apresenta um mapeamento das tarefas da Figura 3.6 em 4 processos.
Note que, neste caso, um máximo de 4 processos pode ser usado de forma útil, embora o
número total de tarefas seja 7. Isto ocorre porque o grau máximo de concorrência é 4. As
3 últimas tarefas podem ser mapeadas arbitrariamente entre os processos para satisfazer
as restrições do grafo de dependência de tarefas. Entretanto, faz mais sentido mapear as
tarefas conectadas por um aresta sobre o mesmo processo porque isso previne uma inte-
ração entre tarefas que se tornaria uma interação entre processos. Por exemplo, na Figura
3.7(b), se Task 5 for mapeada no processo P2, então os processos P0 e P1 precisarão se
64 DCC/UFLA - Programação Paralela e Distribuída
comunicar com P2. No mapeamento atual, somente uma única comunicação entre P0 e P1
é suficiente.
3.2 TÉCNICAS DE DECOMPOSIÇÃO
As técnicas de decomposição podem ser classificadas em: decomposição recursiva,
decomposição de dados, decomposição exploratória e decomposição especulativa. As téc-
nicas de decomposição recursiva e de dados são consideradas de propósito geral quando
elas podem ser usadas para decompor uma grande variedade de problemas. Por outro lado,
as técnicas de decomposição especulativa e exploratória são de natureza mais específica
porque elas aplicam a classes específicas de problemas.
3.2.1 Decomposição recursiva
É um método para induzir concorrência em problemas que podem ser resolvidos
usando a estratégia de divisão e conquista. O problema é resolvido pela sua divisão em um
conjunto de subproblemas independentes. Cada subproblema é resolvido recursivamente
aplicando uma divisão similar em subproblemas menores seguido por uma combinação
de seus resultados. A estratégia de divisão e conquista resulta em concorrência natural,
quando diferentes subproblemas podem ser resolvidos concorrentemente.
Exemplo 3: Considere o problema de ordenação de uma seqüência A de n elementos
usando o algoritmo quicksort. Quicksort é um algoritmo de divisão e conquista que inicia
selecionando um elemento pivô x e então particiona a seqüência A em 2 subseqüências A0
e A1 tal que todos os elementos em A0 sejam menores que x e todos elementos em A1 sejam
maiores ou iguais a x. Este passo de particionamento forma o passo de divisão do algoritmo.
Cada uma das subseqüências A0 e A1 é ordenada recursivamente chamando quicksort.
Cada uma das chamadas recursivas particiona as seqüências. A recursão termina quando
cada subseqüência contém somente um único elemento. Isto é ilustrado na Figura 3.8 que
apresenta uma seqüência de 12 números e o grafo de dependência de tarefas do quicksort
baseado na decomposição recursiva.
3.2.2 Decomposição de dados
A decomposição de dados é um método poderoso e muito utilizado para derivar con-
corrência em algoritmos que operam sobre estruturas de dados grandes. Neste método, a
decomposição de computações é feita em dois passos. No primeiro passo, os dados sobre
os quais as computações são realizadas são particionados. No segundo passo, este parti-
cionamento de dados é usado para induzir um particionamento de computações em tarefas.
As operações que estas tarefas realizam em diferentes partições de dados são geralmente
similares ou são escolhidas de um pequeno conjunto de operações.
Projeto de Algoritmos Paralelos 65
Figura 3.8: Grafo de dependência de tarefas do quicksort baseado na decomposição recursiva para
ordenação da seqüência de 12 números
O particionamento de dados pode ser feito de várias maneiras: particionamento de
dados de saída, de dados de entrada, dados de entrada e saída, dados intermediários.
Estas maneiras diferentes devem ser exploradas e avaliadas para que seja determinada
qual produz uma decomposição computacional natural e eficiente.
Particionamento dos dados de saída: em muitas computações, cada elemento da
saída pode ser computado independentemente de outros elementos como uma função da
entrada. Em tais computações, um particionamento de dados de saídaautomaticamente
induz uma decomposição de problema em tarefas, onde a cada tarefa é atribuído o trabalho
de computar uma porção da saída. Exemplo: multiplicação de matrizes 2x2
Tare f a1 : C[1,1] = A[1,1]B[1,1]+A[1,2]B[2,1]
Tare f a2 : C[1,2] = A[1,1]B[1,2]+A[1,2]B[2,2]
Tare f a3 : C[2,1] = A[2,1]B[1,1]+A[2,2]B[2,1]
Tare f a4 : C[2,2] = A[2,1]B[1,2]+A[2,2]B[2,2]
Particionamento de dados de entrada: o particionamento de dados de saída pode
ser realizado somente se cada saída pode ser naturalmente computada como uma função
da entrada. Em muitos algoritmos, não é desejável ou possível particionar os dados de
saída. Por exemplo: ao encontrar a soma de uma seqüência de N números usando p pro-
cessos (N > p), podemos particionar a entrada em p subconjuntos de tamanhos aproxima-
damente iguais. Cada tarefa, então, computa a soma de números em um dos subconjuntos.
Finalmente, os p resultados parciais podem ser adicionados para produzir o resultado final.
66 DCC/UFLA - Programação Paralela e Distribuída
Particionar dados de entrada e de saída: em alguns casos, em que é possível
particionar os dados de saída, particionar os dados de entrada pode oferecer concorrência
adicional.
Particionamentode dados intermediários: algoritmos são freqüentemente estrutu-
rados em computações em múltiplos estágios tal que a saída de um estágio é a entrada
do estágio subseqüente. O particionamento de dados intermediários pode algumas vezes
produzir uma concorrência maior do que particionar dados de entrada ou saída. Os da-
dos intermediários não são gerados explicitamente em algoritmo seqüencial para resolver
o problema e alguma reestruturação do algoritmo original pode ser necessária para usar o
particionamento de dados intermediário para induzir uma decomposição.
3.2.3 Decomposição exploratória
É usada para decompor problemas cuja computação corresponde a uma busca em
um espaço por soluções. Em decomposição exploratória, particionamos o espaço de busca
em partes menores e buscamos cada uma dessas partes concorrentemente, até que as
soluções desejadas sejam encontradas.
Exemplo 4: O 15-puzzle consiste em 15 quadradinhos numerados de 1 a 15 e um
quadradinho em branco, todos colocados numa grade 4x4. Um quadradinho pode ser mo-
vido da posição branco para uma posição adjacente a ela, criando um branco na posição
original do quadradinho. Dependendo da configuração da grade, até 4 movimentos são
possíveis: para cima, para baixo, para a direita e para a esquerda. As configurações iniciais
e finais dos quadradinhos são especificadas. O objetivo é determinar qualquer seqüência
ou a seqüência mais curta de movimentos que transforme a configuração inicial na con-
figuração final. A Figura 3.9 ilustra os estados gerados por uma instância do problema
15− puzzle.
3.2.4 Decomposição especulativa
É usada quando um programa pode tomar um de muitos ramos computacionalmente
possíveis dependendo da saída de outras computações que o precedem. Enquanto uma
tarefa está realizando computação cuja saída é usada na decisão da próxima computação,
outras tarefas podem concorrentemente iniciar as computações do próximo estágio. Este
cenário é similar à avaliação de um ou mais dos ramos de um comando switch em C em
paralelo antes da entrada para o switch estar disponível. Enquanto uma tarefa está rea-
lizada a computação que resolverá o switch, outras tarefas podem explorar os múltiplos
ramos do switch em paralelo. Quando a entrada do switch tiver sido computada, a com-
putação correspondente ao ramo correto seria usado enquanto que a correspondente aos
outros ramos seria descartada. O tempo de execução paralelo é menor do que o tempo de
execução seqüencial porque a quantidade de tempo necessária para avaliar a condição da
Projeto de Algoritmos Paralelos 67
Figura 3.9: Estados gerados por uma instância do problema 15-puzzle.
qual a próxima tarefa depende é utilizada para realizar uma computação útil para o próximo
estágio em paralelo.
3.2.5 Decomposições híbridas
Uma computação é estruturada em múltiplos estágios e é, algumas vezes, necessário
aplicar diferentes tipos de decomposição em diferentes estágios.
3.3 TÉCNICAS DE MAPEAMENTO PARA BALANCEAMENTO DE CARGA
Uma vez que uma computação tenha sido decomposta em tarefas, estas tarefas são
mapeadas em processos com o objetivo de que todas as tarefas executem no mais curto
intervalo de tempo. Para alcançar um tempo de execução pequeno, os overheads da exe-
cução de tarefas em paralelo devem ser minimizados.
Mapeamento é o mecanismo pelo qual tarefas são atribuídas aos processos para
execução.
As técnicas de mapeamento usadas para algoritmos paralelo podem ser classificadas
em estática e dinâmica. O paradigma de programação paralela e as características das
tarefas e comunicações entre elas determinam se é melhor utilizar ummapeamento estático
ou dinâmico.
Mapeamento estático: distribui as tarefas entre os processos antes da execução do
algoritmo.
68 DCC/UFLA - Programação Paralela e Distribuída
Mapeamento dinâmico: distribui o trabalho entre os processos durante a execução
do algoritmo. Se as tarefas são geradas dinamicamente elas devem também ser mapeadas
dinamicamente.
Geralmente, os algoritmos que fazem uso de mapeamento estático são mais fáceis
de projetar e programar. Já os algoritmos de mapeamento dinâmico são mais complicados,
principalmente no paradigma de passagem de mensagens. Esquemas para mapeamento
estático são baseados em particionamento de dados ou em particionamento de tarefas.
3.3.1 Mapeamento estático
As técnicas de mapeamento estático são usadas em conjunto com a decomposição
baseada em particionamento de dados. Além disso, são usadas para mapear certos pro-
blemas que são expressos naturalmente por um grafo de dependência de tarefas estático.
No mapeamento baseado em particionamento de dados as tarefas são associadas
com porções de dados. Mapear os dados relevantes em processos é equivalente a mapear
tarefas em processos.
A técnica de distribuição em blocos é a forma mais simples de distribuir um vetor
e atribuir porções contíguas do vetor a diferentes processos. Nesta distribuição, um vetor
de d-dimensões é distribuído entre os processos tal que cada processo receba um bloco
contíguo de entradas do vetor em um subconjunto específico de dimensões do vetor. A
distribuição em blocos de vetores são particularmente apropriadas quando há uma loca-
lidade de comunicação, isto é, a computação de um elemento de um vetor requer outros
elementos próximos a ele no vetor.
A distribuição em blocos cíclicos particiona o vetor em mais blocos do que o nú-
mero de processos e atribui as partições aos processos de forma round-robin tal que cada
processo receba diversos blocos não adjacentes.
O particionamento de grafo é usado para algoritmos que operam sobre estruturas
de dados esparsas e quando a dependência dos dados é altamente irregular.
As simulações numéricas de fenômenos físicos envolvem a computação de valores
de certas quantidades físicas em cada ponto da malha. A computação de um ponto da
malha geralmente requer dados correspondentes àquele ponto da malha e os pontos que
são adjacentes a ele na malha. A distribuição dos pontos visa balancear a carga e mi-
nimizar a quantidade de dados que cada processo precisa acessar para completar suas
computações. É necessário particionar a malha de forma que cada uma das p partições
seja atribuída a cada um dos p processos. Cada processo recebe regiões contínuas da
malha tal que o número total de pontos da malha que precisam ser acessados nos limites
da partição seja minimizado.
O mapeamento baseado em particionamento de tarefas visa particionar o grafo
de dependência de tarefas e mapear seus nós aos processos, onde as tarefaspossuem
Projeto de Algoritmos Paralelos 69
tamanhos conhecidos. Além disso, visa minimizar o tempo ocioso e o tempo de interação
de um algoritmo paralelo.
3.3.2 Esquemas para mapeamento dinâmico
O mapeamento dinâmico é necessário em situações onde o mapeamento estático
pode resultar em um alto desbalanceamento de trabalho entre os processos ou onde o grafo
de dependência de tarefas é dinâmico. A razão principal para usar mapeamento dinâmico é
balancear a carga de trabalho entre os processos, por isso, o mapeamento dinâmico pode
ser também denominado de balanceamento de carga dinâmico.
As técnicas de mapeamento dinâmico são geralmente classificadas como centraliza-
das e distribuídas.
Esquema de mapeamento dinâmico centralizado
Todas as tarefas são mantidas em uma estrutura de dados central ou em um processo
especial ou em um subconjunto de processos. Se um processo é designado como o ge-
rente do pool de tarefas disponíveis, então é denominado mestre e outros processos, que
dependem do mestre para receber trabalho são os escravos. Quando um processo não tem
trabalho, ele pega trabalho com o mestre ou na estrutura de dados central. Quando uma
nova tarefa é gerada ela é adicionada à estrutura de dados central ou reportada ao mestre.
Quanto maior o número de processos maior é o acesso ao mestre ou à estrutura de dados
centralizada, tornando-se um gargalo.
Esquema de mapeamento dinâmico distribuído
O conjunto de tarefas executáveis é distribuído entre os processos que trocam tarefas
em tempo de execução para balancear trabalho. Cada processo pode enviar ou receber tra-
balho dos demais processos. Os parâmetros críticos para um esquema de balanceamento
de carga distribuído são os seguintes:
• Como estão os processos enviando e recebendo juntos?
• A transferência de trabalho é iniciada pelo emissor ou pelo receptor?
• Quanto trabalho é transferido em cada troca? Se pouco trabalho é transferido,
então o receptor pode não receber trabalho suficiente e transferências freqüentes
podem resultar em interação excessiva. Se muito trabalho é transferido, então o
emissor pode ficar sem trabalho brevemente, novamente resultando em transferên-
cias freqüentes.
• Quando a transferência do trabalho será realizada? Por exemplo, no balancea-
mento de carga iniciado pelo receptor, o trabalho deve ser requisitado quando o
processo tem realmente que executar o trabalho ou quando o receptor tem pouco
trabalho e antecipa que faltará trabalho.
70 DCC/UFLA - Programação Paralela e Distribuída
3.3.3 Portabilidade para arquiteturas paralelas
Mapeamento centralizado e distribuído podem ser implementados em paradigmas de
passagem de mensagens e espaço de endereçamento compartilhado. Como o balance-
amento de carga dinâmico implica em movimento de tarefas de um processo para outro,
eles funcionam melhor em computadores de passagem de mensagens, onde o tamanho
das tarefas em termos de computação deve ser muito maior do que o tamanho dos dados
associados com as tarefas. No paradigma de espaço de endereçamento compartilhado, as
tarefas não precisam se mover explicitamente, embora haja algum movimento implícito de
dados para caches locais ou bancos de memória dos processos. Em geral, a granulosi-
dade das tarefas a serem movidas é muito menor do que em arquitetura de passagem de
mensagens.
3.4 MÉTODOS PARA CONTENÇÃO DE OVERHEADS DE INTERAÇÕES
O overhead que um programa paralelo possui devido a interações entre seus proces-
sos depende de muitos fatores, tais como o volume dados trocados durante interações, a
freqüência de interação, o padrão de interações espaciais e temporais, etc. As principais
técnicas usadas para conter overhead são:
• Maximizar localidade de dados;
• Minimizar contenção;
• Sobrepor computações com interações;
• Replicar dados ou computações;
• Usar operações de interação coletiva otimizadas;
• Sobrepor interações com outras interações.
Maximizar localidade de dados: as tarefas executadas por diferentes processos re-
querem acesso a alguns dados comuns. O overhead de interações pode ser reduzido
usando técnicas que promovem o uso de dados locais ou dados que foram buscados re-
centemente. A localidade de dados tenta minimizar o volume de dados não locais que
são acessados e maximizar a reutilização de dados recentemente acessados e minimizar
a freqüência de acessos.
Minimizar o volume de dados trocados: minimizar o volume global de dados que
são compartilhados por processos concorrentes. Isto equivale a manter os dados em me-
mória local ou cache para que os processos possam executar suas tarefas. Para isso, é
necessário usar decomposição e mapeamento apropriados. Outra forma de reduzir os da-
dos compartilhados que são acessados por múltiplos processos é usar dados locais para
armazenar resultados intermediários e realizar o acesso a dados compartilhados para so-
mente colocar os resultados finais da computação.
Projeto de Algoritmos Paralelos 71
Minimizar freqüência de interações: reestruturar o algoritmo tal que dados compar-
tilhados sejam acessados e usados em grandes pedaços. Isto implica em manter também
localidade espacial.
Minimizar contenção: contenção ocorre quando múltiplas tarefas tentam acessar o
mesmo recurso concorrentemente, múltiplas transmissões de dados sobre um link de inter-
conexão, múltiplos acessos simultâneos ao mesmo bloco de memória ou múltiplos proces-
sos enviando mensagens ao mesmo processo ao mesmo tempo. A redução da contenção
envolve reprojetar o algoritmo para acessar dados de uma forma livre de contenções.
Sobrepor computações com interações: a quantidade de tempo que processos
gastam esperando por um dado compartilhado chegar ou receber trabalho adicional depois
de uma interação ter sido iniciada pode ser reduzida realizando computação útil durante
este tempo de espera.Uma forma de sobreposição é iniciar uma interação cedo o suficiente
tal que ela se complete antes que seja necessária para computação. Identificar computa-
ções que possam ser realizadas antes da interação ou não dependam dela. Isto é possível
se o padrão de interação é espacialmente ou temporalmente estático e se múltiplas tarefas
que estão prontas para execução estão disponíveis em um mesmo processo tal que se uma
tarefa bloqueia para esperar por uma interação completar, o processo pode trabalhar em
outra tarefa. Em arquitetura de espaço de endereçamento compartilhado, o hardware com
prefetch realiza busca antecipada, adiantando o acesso a endereços de memória que serão
acessados em um futuro imediato e pode iniciar o acesso antecipadamente. Um compilador
pode também detectar o padrão de acesso e colocar pseudo referências a certas locações
de memória antes que estas locações sejam utilizadas pela computação
Replicação de dados ou computações: múltiplos processos podem requerer acesso
freqüente a estruturas de dados compartilhadas somente leitura. A replicação de uma có-
pia da estrutura de dados compartilhada em cada processo faz com que os acessos sub-
seqüentes a esta estrutura de dados estão livres de qualquer overhead de interação. No
paradigma de programação por passagem de mensagens a replicação reduz o overhead
de interação e simplifica a escrita do programa paralelo. No paradigma de espaço de ende-
reçamento compartilhado, a replicação de dados acessados para somente leitura é útil em
casos onde o acesso a dados compartilhados é mais caro ou mais difícil de expressar do
que o acesso a dados locais.
Usando operações interativas coletivas otimizadas: as operações de dados com-
partilhados coletivas podem ser: operações usadas por tarefas para acessar dados; ope-
rações para computações de comunicação intensiva; sincronização. As implementações
otimizadas destas operaçõesestão disponíveis em forma de bibliotecas, tais como MPI.
Sobrepondo interações com outras interações: se a capacidade de transferir da-
dos do hardware permitir, então a sobreposição de interações entre múltiplos pares de
processos pode reduzir o volume efetivo de comunicação. Por exemplo, em uma operação
72 DCC/UFLA - Programação Paralela e Distribuída
de broadcast um-para-todos com 4 processos, o P0 envia dados para P2. P0 envia dados
para P1 concorrentemente P2 envia os mesmo dados para P3 A operação inteira gasta 2
passos.
3.5 MODELOS DE ALGORITMOS PARALELOS
Um modelo de algoritmo é uma forma de estruturação de um algoritmo paralelo sele-
cionando uma técnica de decomposição e mapeamento e aplicando a estratégia apropriada
para minimizar interações.
Modelo de dados paralelos (data-parallel model): as tarefas são estaticamente ou
semi-estaticamente mapeadas aos processos e cada tarefa realiza operações similares em
dados diferentes. Tipo de paralelismo é o resultado de operações idênticas sendo apli-
cadas concorrentemente em diferentes itens de dados, sendo denominado paralelismo de
dados. O trabalho é realizado em fases e os dados operados em diferentes fases pode ser
diferente. Fases de computação de dados paralelos são intercaladas com interações para
sincronizar as tarefas ou obter dados mais atuais para as tarefas. Geralmente baseada no
particionamento de dados porque um particionamento uniforme de dados seguido por um
mapeamento estático é suficiente para garantir balanceamento de carga. Podem ser imple-
mentados para os paradigmas de espaço de endereçamento compartilhado e passagem de
mensagens.
Modelo grafo de tarefas: o interrelacionamento entre as tarefas é utilizado para pro-
mover localidade ou reduzir o custo de interação. Modelo utilizado para resolver problemas
em que a quantidade de dados associada com as tarefas é grande relativo à quantidade de
computação associada a elas. Geralmente, as tarefas são mapeadas estaticamente para
ajudar a otimizar o custo de movimentação de dados entre as tarefas. As técnicas de re-
dução de interação aplicáveis a este modelo incluem redução do volume e freqüência da
interação pela promoção de localidade durante o mapeamento das tarefas, baseado no pa-
drão de interação das tarefas e usando métodos de interação assíncronos para sobrepor a
interação com computação.
Modelo pool de trabalho: caracterizado pelo mapeamento dinâmico de tarefas aos
processos para balanceamento de carga em que qualquer tarefa pode potencialmente ser
executada por qualquer processo O mapeamento pode ser centralizado ou descentralizado
Ponteiros para as tarefas podem ser armazenados em listas compartilhadas fisicamente, fila
de prioridade, hash table ou árvore ou em estruturas de dados distribuídas fisicamente. O
trabalho pode estar estaticamente disponível no início ou pode ser gerado dinamicamente,
ou seja, os processos podem gerar trabalho e adicioná-lo ao pool de trabalho global Se o
trabalho for gerado dinamicamente e o mapeamento for descentralizado então é necessário
Projeto de Algoritmos Paralelos 73
um algoritmo de detecção de terminação. O paradigma de passagem de mensagens usa o
modelo pool de trabalho.
Modelo mestre-escravo (master-slave ou manager-worker): um ou mais processos
mestre gerenciam o trabalho e aloca aos processos trabalhadores. As tarefas podem ser
alocadas a priori, se o mestre puder estimar o tamanho das tarefas ou se um mapeamento
aleatório pode ser feito por um job adequado de balanceamento de carga. Em outro cená-
rio, os trabalhadores podem receber pedaços menores de trabalho em instantes diferentes.
Este modelo pode ser generalizado para o modelo hierárquico ou modelo mestre-escravo
multinível onde o gerenciador de nível mais alto atribui largos pedaços de tarefa para os ge-
renciadores do segundo nível, que por sua vez subdividem a tarefa entre seus trabalhadores
e pode também desempenhar parte do trabalho. Usado tanto em espaço de endereçamento
compartilhada quanto em passagem de mensagens.
Modelo pipeline ou produtor-consumidor: o fluxo de dados é passado para uma
sucessão de processos que realizam alguma tarefa sobre eles. A execução simultânea de
programas diferentes sobre um fluxo de dados é denominada paralelismo de fluxo. Com ex-
ceção do processo inicial do pipeline, a chegada de novos dados é disparada pela execução
de uma nova tarefa por um processo no pipeline Um pipeline é uma cadeia de produtores
e consumidores. Cada processo no pipeline pode ser visto como um consumidor de uma
seqüência de itens para processos precedentes a ele no pipeline e como um produtor de
dados para processos seguintes no pipeline. O pipeline não precisa ser uma cadeia linear,
pode ser um grafo orientado Usa mapeamento estático de tarefas aos processos.
Modelos híbridos: pode ser composto de múltiplos modelos aplicados hierarquica-
mente ou múltiplos modelos aplicados seqüencialmente para diferentes fases de um algo-
ritmo paralelo.
3.6 EXERCÍCIOS
1. Dada uma tarefa que pode ser dividida em m subtarefas, cada subtarefa requer
1 unidade de tempo, quanto tempo é necessário para um pipeline de m estágios
processar n tarefas?
2. Suponha que um vetor de 10.000 posições será alocado a 20 processadores de
forma cíclica, ou seja, o primeiro elemento será alocado ao primeiro processador,
o segundo elemento será alocado ao segundo processador e assim por diante. a)
Quantos elementos serão processados por cada processador? b) Que processo
é responsável pelo pedaço de trabalho j, onde 0 £ j <10.000? Considere que os
processadores são numerados a partir de 0.
3. Para o problema da questão anterior, se a alocação de trabalho aos processadores
for em blocos (subvetores), ou seja, o primeiro bloco alocado ao primeiro proces-
74 DCC/UFLA - Programação Paralela e Distribuída
sador, o segundo bloco ao segundo processador e assim por diante, como ficariam
as respostas das letras a) e b)?
4. Considerando os grafos de tarefas da Figura 3.11, determine o seguinte: a)grau
máximo de concorrência b)speedup máximo alcançado sobre um processo, assu-
mindo que um número arbitrariamente grande de processos está disponível c)o
número mínimo de processos necessários para obter o speedup máximo possível
d)o speedup máximo alcançável se o número de processos é limitado a (a) 2, (b)
4 e (c) 8.
5. O grafo de tarefas mostrado na Figura 3.10 representa uma aplicação de processa-
mento de imagens. Cada círculo representa um tarefa seqüencial. Há 12 tarefas:
uma tarefa de entrada, 10 tarefas de computação e uma tarefa de saída. Cada uma
das 12 tarefas podem ser realizada em uma unidade de tempo do processador. A
tarefa de entrada deve ser completada antes de qualquer tarefa computacional co-
meçar. Todas as 10 tarefas computacionais devem completar antes da tarefa de
saída começar. A tarefa de entrada consome a largura de banda inteira do disposi-
tivo de entrada. A tarefa de saída consome a largura de banda inteira do dispositivo
de saída.
(a) Qual o speedup máximo que pode ser alcançado se este problema for
resolvido em 2 processadores?
(b) Qual é o limite superior do speedup que pode ser alcançado se este pro-
blema for resolvido com processadores paralelos?
(c) Qual é o menor número de processadores necessário para alcançar o spe-
edup na parte (b)?
(d) Qual é o speedup máximo que pode ser alcançado para resolver cinco
instâncias deste problema em 2 processadores? Continue a assumir que
há somente um dispositivo de entrada e somente um dispositivo de saída.
6. Considere os grafos de tarefas da Figura 3.11 e assuma que cada tarefa gasta uma
unidade de tempo para ser executada e o tempo de comunicação entre os proces-
sadores é zero. Determine: i)o número mínimo de processosnecessários para
obter o speedup máximo possível; ii)o speedup máximo alcançável se o número
de processos é limitado a (a) 2, (b) 4 e (c) 8.
Projeto de Algoritmos Paralelos 75
Figura 3.10: Grafos de Tarefas do Exercício 2
Figura 3.11: Grafos de Tarefas do Exercício 3
76 DCC/UFLA - Programação Paralela e Distribuída