Introdução à
Programação Paralela
com Troca de
Mensagens
Onofre Trindade Jr
LCAD-USP
1
Conteúdo
Processamento Paralelo
Arquiteturas de Computadores Paralelos
Paradigmas de Programação
Programando com Troca de Mensagens
Conclusões
2
O que é Processamento Paralelo?
Execução simultânea (concorrente) de vários
programas, em diferentes processadores,
visando a solução de um único problema
3
Por que Usar Programação
Paralela?
Algumas classes de problemas:


Grandes demais para máquinas seqüenciais –
tempo de execução muito longo
Os resultados somente são úteis se obtidos
dentro de um limite máximo de tempo
4
Vantagens da Computação
Paralela
Computação mais rápida
Problemas maiores
Melhor relação custo/benefício
Escalabilidade: o desempenho de um
programa melhora se ele for executado em
mais processadores
Tolerante a falhas
5
Validação dos Resultados fornecidos pela
Computação Paralela
Resultados obtidos devem ser os mesmos:


a cada execução do código paralelo
quando comparados com aqueles obtidos na
versão seqüencial do programa
6
Por que preciso Programar em
Paralelo?
Não existem ferramentas de auxílio ao
desenvolvimento de programas paralelos
que


identifiquem automaticamente o paralelismo
de aplicações genéricas
gerem código eficiente para as mesmas
7
Por que preciso Programar em Paralelo?
(II)
A programação paralela pode ser dividida em
duas etapas

Encontrar o paralelismo

Explorar o paralelismo
8
Determinando Paralelismo
É a parte mais difícil
Uma dica: como você faria para distribuir sua
aplicação entre vários trabalhadores?
A sutileza do que você procura é a razão pela
qual o compilador não pode fazer a
paralelização por você!
Código seqüencial de base x código
originalmente paralelo
Novos algoritmos?
9
Explorando Paralelismo
Para explorar o paralelismo, deve-se distribuir
a carga computacional entre os diferentes
processadores
A melhor forma de se fazer isso depende da
natureza da aplicação e da arquitetura do
computador paralelo usado: mapeamento =>
eficiência
10
Comunicação entre Processos
Geralmente os processos necessitam trocar
informações entre si
Forma da comunicação dependente da arquitetura
do computador:


Variáveis Compartilhadas em máquinas com memória
compartilhada (shared memory)
Troca de Mensagens (message passing) em máquinas
com memória distribuída
11
Arquitetura de Computadores
Paralelos
Existem muitas arquiteturas diferentes
Autores agrupam-nas em classes (taxonomia)
Taxonomia de Flynn é uma das mais usadas
12
Taxonomia de Flynn
SISD: Single Instruction / Single Data.
Computadores seqüenciais.
MISD: Multiple Instructions / Single Data.
Computadores que operam como um pipeline.
SIMD: Single Instruction/Multiple Data.
Supercomputadores vetoriais.
MIMD: Multiple Instructions/Multiple Data.
Computadores paralelos intrínsecos.
13
Máquinas MIMD
Multiprocessadores com memória
compartilhada
Multicomputadores com memória
distribuída
Diferenças:


compartilhamento da memória
mecanismos utilizados para a comunicação
entre processadores
14
Multiprocessadores
Fluxo de Instruções
UCn
EPn
...
EP1
...
UC1
FD
Memória
Compartilhada
Globalmente
I/O
Nó de Processamento
15
Multicomputadores
I/O
Computador 1
Computador 2
Computador 3
Computador 4
I/O
Nó de Processamento
16
Forma de um Programa Paralelo
Inicialização
Divisão das Tarefas
Tarefa 2
Tarefa 1
Tarefa 3
Coleta
Fim
17
Controle Explícito do Paralelismo
O programador decompõe o problema em
tarefas independentes:

Decomposição de dados

Decomposição de controle
O programador codifica explicitamente o
controle entre os processos
As decomposições podem se misturar em
uma aplicação
18
Decomposição de Dados
Os dados do problema são particionados
entre os diferentes processadores
Cada processador executa basicamente o
mesmo código, só que sobre dados diferentes
19
Exemplos de Decomposição de
Dados
Solução numérica de equações diferenciais
parciais pelo método das diferenças finitas
Troca de informações nas fronteiras
20
Exemplos de Decomposição de Dados (II)
Cálculo da área sob uma curva
Tarefas independentes!
21
Vantagens da Decomposição de
Dados
Pode-se dividir o domínio de forma a que todos os
processadores realizem a mesma quantidade de
computação: balanço de carga
Muitos problemas exigem comunicação entre as
tarefas somente nas fronteiras dos subdomínios de
dados
Muitos problemas de Física e Engenharia se
adaptam à Decomposição de Dados
22
Decomposição de Controle
Divisão das tarefas baseada nas funções a
serem executadas
Útil quando não se conhece, a priori, o volume
de computação total – pode facilitar o
balanceamento de carga
23
Exemplo de Decomposição de Controle
Estrutura tipo pipeline
1
2
3
5
4
Cada processador cuida de uma única etapa do
processo
24
Problemas com a Decomposição de
Controle
Não é de tão fácil aplicação quanto à
decomposição de dados
É mais difícil de implementar: exige maior
coordenação entre os processos
A adição de mais processadores não é
simples
25
Níveis de Particionamento de um
Programa
Granularidade: quantidade de computação
entre sincronizações
Dividida entre



Fina
Média
Grossa
Execução do programa envolve
combinação desses níveis
26
Níveis de Particionamento de um
Programa (II)
Níveis de granularidade
+Comunicação
+Sincronismo
Programas
+Paralelismo
Subprogramas
Subrotinas
Loops
Instruções
Grossa
Média
Fina
27
Níveis de Particionamento de um
Programa (III)
Instruções: compilador
Loops: compilador e programador
Subrotinas, subprogramas: programador
Programas: SO
28
Sincronismo e Comunicação
Processos devem cooperar entre si
Troca de dados deve ser feita na ordem
(seqüência) correta
Sincronismo é necessário!
29
Medindo o Desempenho do Programa
Paralelo
Quando se desenvolve uma aplicação
paralela, é útil sabermos o quanto seu
desempenho se aproxima do ótimo
Essa valor teórico é função:


da fração seqüencial f do código
do nº de processadores, n
30
Medindo o Desempenho do Programa
Paralelo (II)
Speedup (S): Quantas vezes o código paralelo fica
mais rápido (que sua versão seqüencial) com o nº
de processadores utilizados
Lei de Amdahl:
1
S 
(1  f )
f 
n
31
Medindo o Desempenho do
Programa Paralelo (III)
32
Medindo o Desempenho do Programa
Paralelo (IV)
A diferença entre o valor “ideal” e o valor obtido
na prática aumenta com o aumento do nº de
processadores
Para todo programa paralelo, há uma valor de n
acima do qual não compensa ir
1
n  , S 
f
33
Medindo o Desempenho do Programa
Paralelo (V)
No mundo real, o overhead causado pela
comunicação entre processadores chega até
a reduzir o speedup após certos valores de n
Menos de 5% de código seqüencial é difícil de
se conseguir!
34
Medindo o Desempenho do Programa
Paralelo (VI)
Desempenho (D): Mede a “taxa de uso” dos
processadores
É relacionada com o Speedup através da relação:
S
D 
 100 %
n
35
Medindo o Desempenho do Programa
Paralelo (VII)
36
Medindo o Desempenho do Programa
Paralelo (VIII)
Quanto maior o desempenho, maior é a
participação dos processadores na resolução
do problema
37
Programando com Troca de
Mensagens (TM)
Ferramentas para Programação Paralela





Compiladores paralelizadores (Cray, etc)
Linguagens paralelas (HPF, Occam, C*, etc)
Bibliotecas de troca de mensagens (PVM, MPI,
Parmacs, etc)
Depuradores / analisadores de código (XPVM,
Pablo, Paragraph, etc)
Ambientes de desenvolvimento (Forge, etc)
38
Características da TM
Criação de processos em processadores
diferentes
Encerramento desses processos
Transferência de dados (na forma de
mensagens) entre esses processos
39
Sistemas de TM
Se apresentam normalmente na forma de bibliotecas
Proprietárias e de Terceiros
Proprietárias: fornecidas pelo fabricante do
computador


Mais rápidas
Mais adaptadas à arquitetura
40
Sistema de TM (II)
Terceiros: geralmente executam em diferentes
arquiteturas


Portabilidade das aplicações
Execução em plataformas heterogêneas
PVM e MPI são exemplos mais comuns para
FORTRAN e C
Disponíveis para máquinas UNIX e Windows.
41
Tipos de Comunicação em TM
Em ambientes de TM, cada processo pode:



Enviar uma mensagem para outro processo
Enviar a mesma mensagem para vários outros
processos simultaneamente (broadcast)
Receber mensagens enviadas para ele
42
Tipos de Comunicação em TM (II)
Cada forma de comunicação é normalmente
executada através de uma chamada de
subrotina
O sistema de TM cuida dos detalhes de
transmissão e recepção dos dados no
computador
43
Tipos de Comunicação em TM (III)
O programador deve projetar a aplicação
paralela


Como uma coleção de tarefas
A lógica e o fluxo de execução são normalmente
controladas pela comunicação entre os processos
44
Tipos de Comunicação em TM (IV)
O envio/recepção podem ser


bloqueantes: a rotina não retorna até completar a
transmissão/recepção
não-bloqueantes: a rotina retorna antes de
completar a transmissão/recepção
45
Tipos de Comunicação em TM (V)
O envio/recepção podem ser

síncronos: existe um instante no tempo onde
transmissor e receptor estão simultaneamente
comprometidos com o processo de transferência
de dados
46
Tipos de Comunicação em TM (VI)
Modos bloqueantes devem ser evitados, pois
os processos poderiam estar fazendo
computação útil durante a comunicação
47
Tipos de Comunicação em TM (VII)
O ideal é que se misture computação com
troca de mensagens:


Envios não-bloqueantes
Recepções não-bloqueantes
Se todas as tarefas tentarem se comunicar ao
mesmo tempo, pode haver contenção na linha
de comunicação!
48
Divisões de Tarefa
Sistemas de TM são usados para implementar
as formas de divisão de tarefas mais comuns:



Pipeline
Paralelismo de Dados
Mestre-Escravo
49
Planejamento do Sistema
Escolhido o modelo, a lógica da aplicação fica
determinada
Essa lógica é implementada com a ajuda da biblioteca de
TM
O programador precisa



Determinar que dado é usado por qual processo e em que ordem
Implementar a comunicação entre os processos invocando as
rotinas da biblioteca de TM
Escrever as tarefas que lerão os dados e executarão o trabalho
50
Desenvolvimento de um Código
TM a Partir de um Código
Seqüencial
As regras abaixo são úteis no desenvolvimento
de aplicações com TM
1) Comece com uma versão seqüencial do
programa que


Não tenha código não executado
Construções obsoletas
51
Desenvolvimento de um Código
TM ... (II)
2) Verifique as opções de compilação disponíveis,
principalmente aquelas que monitoram o código em
tempo de execução



estouro de limites em vetores
problemas nos valores de ponto flutuante
minimize as otimizações
52
Desenvolvimento de um Código
TM ... (III)
3) Crie vários conjuntos de entradas/saídas do código
seqüencial para comparação com o resultado do
código paralelo
4) Faça uma análise do código serial (profiling),
ajustando-o para que tenha um bom desempenho
53
Desenvolvimento de um Código
TM ... (IV)
5) Tente extrair o paralelismo da aplicação.
Descubra os trechos de código que possam (e
justifiquem) ser paralelizados


Se em mais de um trecho, comece pelo de mais alto
nível (maior granularidade)
Use o profiling como guia!
54
Desenvolvimento de um Código
TM... (V)
7) Determine o uso das variáveis e dos vetores
utilizados:
a) Lidos ou modificados (L/M) somente na parte seqüencial
b) L/M somente na parte paralela
c) L/M localmente a cada tarefa independente
d) L/M por várias tarefas independentes
e) L/M pela partes seqüencial e paralela
f) M na parte seqüencial, L na parte paralela
g) M na parte paralela, L na parte seqüencial
A e C Ok!, os outros casos precisam de
tratamento especial
55
Desenvolvimento de um Código
TM... (VI)
8) Escolha o paradigma apropriado
9) Implemente uma versão inicial:

Funcionalmente correta (esqueça o desempenho!)

Seja conservador no uso de sincronismo

Particione usando poucos processadores

Insira mensagens em locais apropriados para depurar
o código
56
Desenvolvimento de um Código
TM... (VII)
10) Expanda os testes



Faça pequenas alterações acompanhadas de testes
(chato, mas funciona!)
Cuidado com print, printf: podem alterar o
funcionamento do código por alterar o sincronismo
Teste cada caso gerado anteriormente em vários nós
57
Desenvolvimento de um Código
TM... (VIII)
Agora pode-se pensar em melhorar o
desempenho...
11) Remova todos as operações de I/O desnecessárias


Elas podem mascarar problemas de sincronismo
Reduzem desempenho (I/O de vídeo)
12) Melhore a comunicação



Elimine mensagens desnecessárias
Agrupe mensagens correlatas
Tente sobrepor comunicação com computação quando possível
58
Exemplo de Paralelização
Aplicação ao cálculo da área sob uma curva
no intervalo [a,b]
O método mais direto de paralelização é o
y  f ( x)
paradigma de decomposição de dados: dividir o
intervalo [a,b] em n subintervalos iguais
Regra do trapézio
59
Visão de alto nível
Inicialização
Divisão do Intervalo
[a+h,a+2h]
[a,a+h]
[a+2h,a+3h]
Soma dos resultados
Impressão
60
Divisão do Intervalo
Cada processador recebe um subintervalo de
comprimento
(b  a )
h
n
onde n é o nº de processadores usados
h
61
Divisão de Trabalho
Define-se um processo mestre para coordenar o
processo
Esse processo mestre irá disparar os n-1 (2)
processos auxiliares
do j=2,3
create(“quadr”, tid(j))
enddo
tid(1) é o identificador do mestre!
62
Dados enviados pelo Mestre
Cada tarefa precisa saber:


os extremos do seu subintervalo
o valor de h
Processo mestre manda esses dados para todas as tarefas:
if (me.eq.1) then
do j=2,3
send (a+(j-1)h,(a+j)h) to tid(j)
send (h) to tid(j)
enddo
endif
63
Recepção pelos Filhos
Cada processo filho recebe esses dados:
if (me.ne.1) then
rec (a_loc, b_loc) from tid(1)
rec (h) from tid(1)
endif
64
Transmissão/Recepção
Combinadas
Pode-se agrupar tudo em um mesmo trecho de código!
(SPMD)
if (me.eq.1) then
do j=2,3
send (a+(j-1)h,(a+j)h) to tid(j)
send (h) to tid(j)
enddo
else
rec (a_loc, b_loc) from tid(1)
rec (h) from tid(1)
endif
65
Cada Tarefa calcula a área do seu
subintervalo
Cada processo filho calcula a área pela regra do
Trapézio:
f (a _ loc)  f (b _ loc) 
I parcial  h

2


onde:
h  b _ loc  a _ loc
Uma
vez calculado, cada filho o manda seu Iparcial para o
mestre
66
Mestre recebe áreas parciais
if (me.ne.1) then
send (i_parcial) to tid(1)
else
i_total=i_parcial
do j=2,3
rec (i_parcial) from tid(j)
i_total=i_total+i_parcial
enddo
endif
67
Mestre recebe áreas parciais
Mestre mata os processos filhos:
if (me.eq.1) then
do j=2,3
call kill(tid(j))
enddo
endif
68
Conclusões
Computação paralela é a forma mais acessível de
se resolver problemas que exigem muita
computação
Está se difundindo cada vez mais mais pela queda
no custo dos componentes eletrônicos
69
Conclusões
As bibliotecas de comunicação PVM e MPI utilizadas
em multicomputadores constiuem o ambiente mais
básico e acessível para a prática de processamento
paralelo.
70