Computação por Passagem de Mensagens
Multiprocessadores conectados por rede
• Processadores conectados por uma rede estática com
passagem de mensagens
P
M
P
Computadores
C
M
C
Rede com ligações
diretas entre computadores
C
P
M
Multiprocessadores conectados por rede
• Espaço de endereçamento compartilhado com acesso
não uniforme
– Ex: Cray Research T3E (2048), Sequent NUMA_Q (32 Pentium Pro), SGI
Origin 2000 (128 MIPS)
• Espaço de endereçamento compartilhado e uniforme
– Ex: Sun Enterprise 10000 (64 Ultra Sparc 1)
Clusters
• Nós de multiprocessadores similares a computadores
desktop
• Aumento da velocidade das redes locais
• Aparecimento de clusters de computadores de
prateleira interligados por redes de alta velocidade
• Exemplos:
– Sandia Cplant (592 Compaq XP100 workstations interconectadas pela
Myrinet)
– IBM RS/6000 SP2 (512 nós, switch própria)
Topologia das redes
• Topologias entre total conexão e barramento único
• Custo:
– número de switches
– número de ligações de um switch para conectar na rede
– número de bits por switch
• Desempenho:
– latência para receber e enviar mensagem entre nós
– número de mensagens por período de tempo
– retardos por contenção no switch
Topologia de redes
Anel
Grade bidimensional
ou malha de 16 nós
Árvore n-cubo de 8 nós
Topologia de redes - Crossbar Switch
111
110
101
100
011
010
001
Rede não bloqueante
000
Memórias
cruzamento aberto
000
CPUs
001
010
011
100
101
110
111
cruzamento fechado
Topologia de redes - rede Ômega
P0
P1
P2
P3
P4
P5
P6
P7
A
C
B
D
Caixa comutadora da rede Ômega
Programação por passagem de mensagens
• Programação de multiprocessadores conectados por
rede pode ser realizada:
– criando-se uma linguagem de programação paralela especial
– estendendo-se as palavras reservadas de uma linguagem seqüencial
existente de alto nível para manipulação de passagem de mensagens
– utilizando-se uma linguagem seqüencial existente, provendo uma
biblioteca de procedimentos externos para passagem de mensagens
Biblioteca de rotinas para troca de
mensagens
• Necessita-se explicitamente definir:
– quais processos serão executados
– quando passar mensagens entre processos concorrentes
– o que passar nas mensagens
• Dois métodos primários:
– um para criação de processos separados para execução em diferentes
processadores
– um para enviar e receber mensagens
Modelo Single Program Multiple Data
(SPMD)
• Diferentes processos são unidos em um único
programa e dentro deste programa existem instruções
que customizam o código, selecionando diferentes
partes para cada processo por exemplo
Código
fonte
Executáveis
Compila para
gerar executável
para cada processador
Processador 0
Processador n-1
Modelo Multiple Program, Multiple Data
(MPMD)
• Programas separados escritos para cada processador,
geralmente se utiliza o método mestre-escravo onde um
processador executa o processo mestre e os outros
processos escravos são inicializados por ele.
Processo 1
tempo
spawn();
Inicia execução
Processo 2
do processo 2
Rotinas básicas de envio e recebimento
Processo 1
Processo 2
x
y
send(&x, 2);
recv(&y, 1);
Rotinas síncronas
• Rotinas que somente retornam quando a transferência
da mensagem foi completada
• Não necessita de buffer para armazenar a mensagem
– uma rotina síncrona de envio pode esperar até que a mensagem completa
possa ser aceita pelo processo receptor antes de enviar a mensagem
• Uma rotina síncrona de recebimento espera até que a
mensagem que ela está esperando chegue
• Rotinas síncronas intrinsicamente realizam duas ações:
transferem dados e sincronizam processos
• Sugere a existência de alguma forma de protocolo de
sinalização
Rotinas síncronas para recebimento e envio
de mensagens usando protocolo de
sinalização
Processo 1
tempo
send();
Processo
suspenso
Ambos continuam
Processo 2
Pede para enviar
Confirmação
Mensagem
Processo 1
recv();
Processo 2
tempo
send();
Ambos continuam
Pede para enviar
Mensagem
Confirmação
recv();
Processo
suspenso
Rotinas com bloqueio e sem bloqueio
• Com bloqueio: utilizadas para descrever rotinas que
não retornam enquanto a transferência da mensagem
não se completou
– os termos com bloqueio e síncrona são sinônimos
• Sem bloqueio: utilizadas para descrever rotinas que
retornam tendo sido ou não recebida a mensagem
• Definições utilizadas pelo MPI:
– com bloqueio: retorna após ações locais terem sido executadas, mesmo
que a transferência da mensagem não esteja completa
– sem bloqueio: retorna imediatamente; assume que área onde está a
mensagem não será modificada por instruções até que ocorra a
transferência e deixa essa responsabilidade para o programador
Retorno das rotinas antes que transferência
tenha sido efetuada
• Necessita de um buffer para guardar a mensagem
Processo 1
Processo 2
Buffer de
mensagens
tempo
send();
Continua
o processo
recv();
Lê buffer
de mensagen
Índice da mensagem
• Utilizado para diferenciar os diversos tipos de
mensagem que podem ser enviadas
• Exemplo:
– Para enviar uma mensagem com dado x e índice 5 de um processo fonte 1
para um processo destino 2, poderíamos ter
send(&x, 2, 5);
no processo fonte e
recv(&y, 1, 5);
no processo destino
• Utiliza-se um índice especial (wild card) quando não se
requer casamento de índices das mensagens de modo
que a rotina recv() aceitará mensagem enviada por
qualquer rotina send()
Broadcast
• Envio da mesma mensagem para todos os processos
• Multicast: envio da mesma mensagem para um grupo
de processos
Ação
Processo 0
Processo 1
Processo n-1
dado
dado
dado
buf
bcast();
Código
bcast();
bcast();
Scatter
• Envio de cada elemento de uma matriz de dados do
processo raíz para um processo separado; o conteúdo
da i-ésima localização da matriz é enviado para o iésimo processo
Processo 0
Processo 1
Processo n-1
dado
dado
dado
Ação
buf
scatter();
Código
scatter();
scatter();
Gather
• Um processo coleta dados de um conjunto de processos
Processo 0
Processo 1
Processo n-1
dado
dado
dado
Ação
buf
gather();
Código
gather();
gather();
Reduce
• Operação de gather combinada com uma operação
lógica ou aritmética específica. Ex: valores coletados e
somados pelo processo raíz
Processo 0
Processo 1
Processo n-1
dado
dado
dado
Ação
buf
reduce();
Código
+
reduce();
reduce();
Ferramentas de software que utilizam
biblioteca de troca de mensagens
• PVM (Parallel Virtual Machine)
– desenvolvida pelo Oak Ridge National Laboratories para utilizar um
cluster de estações de trabalho como uma plataforma multiprocessada
– provê rotinas para passagem de mensagens entre máquinas homogêneas e
heterogêneas que podem ser utilizadas com programas escritos em C ou
Fortran
• MPI (Message Passing Interface)
– padrão desenvolvido por um grupo de parceiros acadêmicos e da indústria
para prover um maior uso e portabilidade das rotinas de passagem de
mensagens
PVM
• O programador decompõe o programa em programas
separados e cada um deles será escrito em C ou Fortran
e compilado para ser executado nas diferentes
máquinas da rede
• O conjunto de máquinas que será utilizado para
processamento deve ser definido antes do início da
execução dos programas
• Cria-se um arquivo (hostfile) com o nome de todas as
máquinas disponíveis que será lido pelo PVM
• O roteamento de mensagens é feito pelos processos
daemon do PVM
Passagem de mensagens utilizando o PVM
Estação de trabalho
Daemon
PVM
Mensagens
enviadas através da
rede
Estação de trabalho
Daemon
PVM
Estação de trabalho
Daemon
PVM
Passagem de mensagens utilizando o PVM
Estação de trabalho
Daemon
PVM
Programa
da aplicação
(executável)
Estação de trabalho
Daemon
PVM
Programa
da aplicação
(executável)
Mensagens
enviadas através da
rede
Estação de trabalho
Daemon
PVM
Programa
da aplicação
(executável)
Rotinas básicas do PVM
• Todas as rotinas são sem bloqueio (ou assíncronas na
terminologia PVM) enquanto que rotinas de
recebimento podem ser com bloqueio (síncronas) ou
sem bloqueio
• Utiliza um índice para mensagem (message tag) e tem
índice wild card
• pvm_psend() e pvm_precv()
– rotinas utilizadas quando dados sendo transmitidos são todos do mesmo
tipo
pvm_precv() e pvm_psend()
Processo 2
Processo 1
Array com
dados
Array para
receber
dados
Buffer de envio
Pack
pvm_psend();
Continua
o processo
pvm_precv();
Espera por
mensagem
Envio de mensagem com dados de vários
tipos
• Os dados são empacotados em um buffer antes de
enviá-los
• O receptor tem que desempacotá-los e acordo com o
formato em que foram empacotados
• Rotinas específicas para empacotamento e
desempacotamento para cada tipo de dados
Envio de mensagem com dados de vários
tipos
processo_1
processo_2
pvm_initsend();
pvm_pkint(.. &x ..);
pvm_pkstr( …&s …);
pvm_pkfloat( … &y …);
pvm_send(processo_2 ...);
Buffer de
envio
x
s
y
Buffer de
recepção pvm_recv(processo_1 …);
pvm_pkint(.. &x ..);
pvm_pkstr( …&s …);
pvm_pkfloat( … &y …);
Broadcast, multicast, scatter, gather e
reduce
• Operações utilizadas com grupo de processos
(pvm_bcast(), pvm_scatter(),pvm_gather() e pvm_reduce()) com
exceção de multicast (pvm_mcast)
• Um processo se junta a um grupo através da rotina
pvm_joingroup()
• pvm_bcast envia mensagem para cada membro do grupo
• pvm_gather() coleta valores de cada membro do grupo
Mestre
#include <stdio.h>
#include <stlib.h>
#include <pvm3.h>
#define SLAVE ``spsum´´
#define PROC 10
#define NELEM 1000
main() {
int mytid, tids[PROC]
int n=NELEM, nproc =PROC;
int no, i, who, msgtype;
int data[NELEM],result[PROC],tot=0;
char fn[255];
FILE *fp;
mytid=pvm_mytid();
no=pvm_spawn(SLAVE,(char **)0,0,`` ``,nproc,tids);
if (no < nproc) {
printf(``Erro em disparar escravo\n``);
for (i=0; i<no; i++) pvm_kill(tids[i]);
pvm_exit(); exit(1);
}
strcpy(fn,getenv(``HOME´´));
strcat(fn,´´/pvm3/src/rand_data.txt´´);
if ((fp=fopen(fn,``r´´))==NULL) {
printf(``Nao posso abrir arquivo %s \n´´,fn);
exit (1);
}
for (i=0; i<n; i++) fscanf(fp,”%d”,&data[i]);
Escravo
#include <stdio.h>
#include <pvm3.h>
#define PROC 10
#define NELEM 1000
main() {
int mytid, tids[PROC]
int n,me, i,msgtype;
int x, nproc,master;
int data[NELEM],sum;
int x, low, high;
mytid=pvm_mytid();
Mestre
pvm_initsend(PvmDataDefault);
msgtype=0;
pvm_pkint(&nproc,1 ,1);
pvm_pkint(tids, nproc, 1);
pvm_pkint(&n,1,1);
pvm_pkint(data, n, 1);
pvm_mcast(tids, nproc, type);
Escravo
msgtype=0;
pvm_recv(-1,msgtype);
pvm_upkint(&nproc,1,1);
pvm_upkint(tids, nproc, 1);
pvm_upkint(&n, 1,1 );
pvm_upkint(data, ,n,1);
Broadcast
for (i=0;i<nproc;i++)
if (mytid ==tids[i])
{me=i;break;}
msgtype = 5;
for (i=0; i<nproc; i++) {
pvm_recv(-1, msgtype);
Recebe
pvm_upkint(&who, 1, 1);
resultados
pvm_upkint(&result[who], 1, 1);
printf(“%d de %d \n”,result[who],who);
}
x=n/proc;
low=me*x;
high=low+x;
for (i=low;i<high;i++)
sum+=data[i];
pvm_initsend(PvmDataDefault);
pvm_pkint(&me, 1, 1);
pvm_pkint(&sum,1,1);
msgtype=5;
master=pvm_parent;
pvm_send(master,msgtype);
for (i=0;i<nproc;i++) tot +=result[i];
printf (“O total e %d. \n \n”,tot);
pvm_exit();
return(0);
pvm_exit();
return(0);
}
}
MPI
• Criação e execução de processos
– Propositalmente não são definidos e dependem da implementação
– MPI versão 1
• Criação estática de processos: processos devem ser definidos antes da
execução e inicializados juntos
• Utiliza o modelo de programação SPMD
• Communicators
– Define o escopo das operações de comunicação
– Processos têm posições definidas associadas ao communicator
– Inicialmente todos os processos participam de um communicator universal
chamado MPI_COMM_WORLD e cada processo possui uma única
posição (0 a n-1) , onde n é o número total de processos
– Outros communicators podem ser estabelecidos para grupo de processos
Utilizando o modelo SPMD
main (int argc, char *argv[])
{
MPI_Init(&argc, &argv);
.
.
MPI_Comm_Rank(MPI_COMM_WORLD, &myrank);
if (myrank ==0)
master();
else
slave();
.
.
MPI_Finalize();
}
Variáveis locais e globais
• Qualquer declaração global será duplicada em cada
processo
• Para não haver duplicação de variável, deve-se declarála dentro do código executado somente pelo processo
• Exemplo:
MPI_Comm_rank(MPI_COMMWORLD, &myrank);
if (myrank==0) {
int x, y;
.
.
else if (myrank==1) {
int x, y;
.
.
}
Modo não seguro de envio de mensagens
Processo 0
Destino
Processo 1
send(…,1,…);
lib()
Fonte
send(…,1,…);
recv(…,0,…);
lib()
recv(…,0,…);
Processo 0
Destino
Processo 1
send(…,1,…);
lib()
Fonte
send(…,1,…);
recv(…,0,…);
recv(…,0,…);
lib()
Solução MPI
• Communicators
– utilizados em todas comunicações ponto-a-ponto e coletivas
– domínio de comunicação que define um grupo de processos que podem se
comunicar entre si
– o domínio de comunicação da biblioteca pode ficar separado do domínio
do programa do usuário
– cada processo tem uma posição definida (rank) dentro de um
communicator, um inteiro que varia de 0 a n-1, onde n é o número de
processos
Tipos de communicator
• Intracommunicator
– comunicação dentro de um grupo
• Intercommunicator
– comunicação entre grupos
• Um processo tem um único rank em um grupo, que
varia de 0 a m-1, onde m é o número de processos
pertencentes a um grupo
• Um processo pode ser membro de mais de um grupo
• Intracommunicator default: MPI_COMM_WORLD
– é o primeiro communicator de todos os processos da aplicação
– conjunto de rotinas MPI para formar novos communicators
Comunicação ponto-a-ponto
• Índices para as mensagens
– MPI_ANY_TAG: para não especificar índice
• Para receber de qualquer fonte: MPI_ANY_SOURCE
• Tipo de dados é enviado como parâmetro na mensagem
• Rotinas com bloqueio
– retornam quando estão completas localmente (local utilizado para
guardar a mensagem pode ser utilizado novamente sem afetar envio
da mensagem
• Rotinas com bloqueio
– retornam imediatamente mesmo que o local utilizado para guardar a
mensagem não possa ser utilizado novamente sem afetar seu envio
Rotinas com bloqueio
MPI_Send (buf, count, datatype, dest, tag, comm)
Tipo de dados
de cada item
Endereço do
buffer de envio
Índice da
mensagem
Communicator
Número de ítens
a enviar
Rank do processo
destino
MPI_Recv (buf, count, datatype, src, tag, comm,status)
Endereço do
buffer de recepção
Tipo de dados
de cada item
Número máximo
de ítens a receber
Índice da
Status após
operação
mensagem
Communicator
Rank do processo
fonte
Exemplo de rotina com bloqueio
Envio de um inteiro x do processo 0 para o processo 1
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
if (myrank ==0) {
int x;
MPI_Send(&x, 1, MPI_INT, 1, msgtag, MPI_COMM_WORLD);
}
else if (myrank ==1) {
int x;
MPI_Recv(&x, 1, MPI_INT, 0, msgtag, MPI_COMM_WORLD, status);
}
Rotinas sem bloqueio
• MPI_Isend: retorna imediatamente antes do local da
mensagem estar seguro
• MPI_Irecv: retorna mesmo que não tenha mensagem a
receber
• Formatos:
– MPI_Isend(buf, count, datatype, dest,tag, comm, request)
– MPI_Irecv(buf, count, datatype, source, tag, comm, request)
• MPI_Wait(): retorna somente após término da operação
• MPI_Test(): retorna com um flag indicando se a
operação já foi completada
• Parâmetro request indica operação a ser verificada
Exemplo de rotina sem bloqueio
Envio de um inteiro x do processo 0 para o processo 1
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
if (myrank ==0) {
int x;
MPI_Isend(&x, 1, MPI_INT, 1, msgtag, MPI_COMM_WORLD,req1);
processa();
MPI_Wait(req1, status);
}
else if (myrank ==1) {
int x;
MPI_Recv(&x, 0, MPI_INT, 1, msgtag, MPI_COMM_WORLD, status);
}
Modos de envio
• Standard:
– Não assume a existência de uma rotina correspondente de recebimento
– Quantidade de memória para bufferização não definida
– Se existe bufferização, envio pode ser completado antes de ocorrer a
rotina de recebimento
• Bufferizado
– O envio pode ser inicializado e retornar antes de uma rotina
correspondente de recebimento
– A utilização do buffer deve ser especificada via as rotinas
MPI_Buffer_attach() e MPI_Buffer_detach()
Modos de envio
• Síncrono:
– As rotinas de envio e recebimento podem iniciar seus procedimentos uma
antes da outra mas têm que finalizá-los juntas
• Pronto (ready):
– O envio da mensagem só pode ser iniciado se existe uma rotina de
recebimento correspondente
• Os quatro modos podem ser aplicados para rotinas de
envio com e sem bloqueio
• O modo standard é o único disponível para rotinas de
recebimento com e sem bloqueio
• Qualquer tipo de rotina de envio pode ser utilizada com
qualquer tipo de rotina de recebimento
Comunicação coletiva
• Realizada em um conjunto de processadores definido
por um intracommunicator
• Não existem índices
• MPI_Bcast(): envio do processo raíz para todos os
outros
• MPI_Gather(): coleta valores para um grupo de
processos
• MPI_Scatter(): espalha buffer de dados em partes para
um grupo de processos
• MPI_Alltoall():envia dados de todos os processos para
todos os processos
Comunicação coletiva
• MPI_Reduce(): combina valores de todos os processos
em um único valor
• MPI_Reduce_scatter: combina valores e espalha
resultado
• MPI_Scan: calcula reduções de prefixo de dados dos
processos
Exemplo de rotina coletiva
Coletar dados de um grupo de processos no processo 0
int data [10];
.
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
if (myrank ==0) {
MPI_Comm_size(MPI_COMM_WORLD,&grp_size);
buf=(int *) malloc(grp_size*10*sizeof(int));
}
MPI_Gather(data, 10, MPI_INT, buf, grp_size*10, MPI_INT,0,MPI_COMM_WORLD);
}
Barreira (barrier)
• Em todos os sistemas de passagem de mensagens existe
uma maneira de sincronizar os processos
• MPI_Barrier():
– processos ficam bloqueados até todos os processos terem atingido essa
instrução no programa
#include <stdio.h>
#include <math.h>
#include `` mpi.h ´´
#define MAXSIZE 1000
void main(int argc, char *argv) {
int myid, numprocs;
int data[MAXSIZE],i,x,low,high,myresult,result;
char fn[255];
FILE *fp;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
MPI_Comm_rank(MPI_COMM_WORLD,&myid);
if (myid==0) {
strcpy(fn,getenv(``HOME´´));
strcat(fn,´´/MPI/src/rand_data.txt´´);
if ((fp=fopen(fn,``r´´))==NULL) {
printf(``Nao posso abrir arquivo %s \n´´,fn);
exit (1); }
for (i=0; i<MAXSIZE; i++) fscanf(fp,”%d”,&data[i]);
}
MPI_Bcast(data, MAXSIZE, MPI_INT, 0, MPI_COMM_WORLD);
x=MAXSIZE/numprocs; low=myid*x; high=low+x;
for (i=low;i<high;i++)
myresult+=data[i];
printf(``Obtive %d de %d \n´´, myresult, myid);
MPI_Reduce(&myresult, &result, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
if (myid==0) printf (``A soma é %d. \n´´, result);
MPI_Finalize();
}
Construções em pseudo-código
• Envio de uma mensagem com um inteiro x e um float y
por um processo chamado mestre para um processo
chamado escravo, que recebe os dados em a e b
– Mestre: send (&x, &y, Pescravo);
– Escravo: recv(&a, &b, Pmestre);
• Envio de uma mensagem para o i-ésimo processo Pi e
índice da mensagem data_tag
– send(&x, P2, data_tag);
• Rotinas de envio e recebimento com bloqueio, para
diferenciar outras formas utiliza-se prefixo
– envio síncrono: ssend(&data1, Pdestino);
Tempo de execução paralela
• Composto de duas partes:
– tcomp : parte de computação
– tcomm : parte de comunicação
– tp= tcomp + tcomm
• Tempo de computação estimado como em algoritmo
seqüencial
• Tempo de comunicação:
– tcomm= tstartup + ntdata
– tstartup : tempo para enviar uma mensagem sem dados
– tdata : tempo para transmitir uma palavra de dados
– n: número de palavras a transmitir
Tempo
Tempo teórico de comunicação
Tempo tstartup
Número de itens de dados (n)
Interpretação das eqüações
• Utilizadas para dar uma idéia do desempenho de um
algoritmo
• Tempo de execução paralela é normalizado para ser
medido em unidades de uma operação aritmética que
vai depender da máquina utilizada
• Assume-se que processadores homogêneos e que todas
as operações aritméticas requerem o mesmo tempo
• Conta-se número de passos de computação de um
processador ou daquele que precisa do maior número
de passos
Interpretação das eqüações
• Tempo de comunicação também medido em passos de
computação
• Assume-se o mesmo tempo para o envio de um inteiro e
de um float
• tcomm= q(tstartup+ ntdata), para q mensagens com n itens
• Exemplo:
– IBM SP-2 : tstartup= 35s, tdata=230ns, tempo de operação
aritmética=4.2ns
• normalizando: tstartup = 8333 e tdata=55
Como superar o gasto de tempo no envio de
mensagens?
• Suponha uma máquina que pode operar a 200
MFLOPS e cujo tempo tstartup seja 1s:
– podem ser executadas 200 operações de ponto flutuante no tempo gasto
para o início de envio de uma mensagem
• Manter o processador ocupado enquanto a
comunicação é efetuada
• Rotinas de envio sem bloqueio
• Mapeamento de múltiplos processos em um
processador utilizando uma técnica de tempo
compartilhado que gerencia os processos de modo que
quando um processo está parado esperando a
comunicação, outro processo passa a ser executado
utilização de threads
Complexidade no tempo
• Pode-se utilizar o cálculo de complexidade para
programas seqüenciais O( )
• Estimativa do número de passos computacionais,
considerando que as operações lógicas e aritméticas
gastam o mesmo tempo
• Expressão para o número de passos computacionais é
derivada em termos do número de itens de dados
manipulados pelo algoritmo
Exemplo de cálculo de complexidade no
tempo para um algoritmo paralelo
• Dois computadores somam n números da seguinte
maneira:
1. Computador 1 envia n/2 números para o computador 2
2. Ambos somam os n/2 números simultaneamente
3. Computador 2 envia resultado parcial para o computador 1
4. Computador 1 soma as somas parciais e produz resultado final
• Tempo de computação (para os passos 2 e 4)
– tcomp=n/2+1
– complexidade O(n)
• Tempo de comunicação (para os passos 1 e 3)
– tcomm= (tstartup+ n/2tdata)+ (tstartup+ n/2tdata)=2 tstartup+( n/2 + 1)tdata
– complexidade O(n)
Algoritmos com custo ótimo
• Custo é considerado ótimo quando o custo de resolver
um problema é proporcional ao tempo de execução em
um único processador utilizando o mais rápido
algoritmo seqüencial conhecido
– Custo = tp  n = k  ts
• Em termos de análise de complexidade, um algoritmo
paralelo é um algoritmo com custo ótimo quando
– Complexidade do algoritmo paralelo  número de processadores = complexidade
do algoritmo seqüencial
– Exemplo:
• Melhor algoritmo seqüencial: O(n log n)
• Algoritmo paralelo com custo ótimo: n processadores executando um
algoritmo paralelo com complexidade O(log n)
• Algoritmo paralelo não ótimo: n2 processadores executando um algoritmo
paralelo com complexidade O(1)
Complexidade para operações de broadcast
•
Considere uma operação de broadcast do nó 000 para todos os outros nós
em um hipercubo
10. passo 000
20. passo
110
001
000
010
001
011
100
111
101
010
30. passo
•
000
001
010
011
100
101
110
111
000
011
001
Complexidade O(log n), onde n é o número de nós do hipercubo: ótima
porque diâmetro do hipercubo é log n
Complexidade para operações de broadcast
•
Envio de uma mensagem do processador mais em cima à esquerda em
uma arquitetura mesh com n nós
1
2(n-1) passos
2
O(n)
3
2
3
4
4
3
4
5
5
4
5
6
6
Diâmetro da mesh = 2(n-1)
Complexidade para operações de broadcast
•
Broadcast em um cluster interconectado por Ethernet: O(n) para n itens
de dados
Mensagem
Fonte
•
Destinos
PVM: uma mensagem de broadcast que chega no daemon PVM é
convertido em várias mensagens para cada um dos N destinos: O(N)
Depurando e avaliando os programas
paralelos
• Diagrama de espaço-tempo
Processo 1
Processo 2
Processo 3
Processando
Tempo
Esperando
Rotina do sistema para passagem de mensagem
Mensagem
Estratégias de depuração
• Sugestão de Geist et al. Para depuração de programas
paralelos:
1. Execute o programa como um único processo e depure como um programa
seqüencial (se possível)
2. Execute o programa utilizando dois ou quatro processos em uma mesma
máquina e verifique se mensagens estão sendo enviadas de forma correta
(erros são comuns nos índices e destinos das mensagens)
3. Execute o programa utilizando os mesmos dois ou quatro processos em
várias máquinas para tentar descobrir problemas na sincronização e
temporização no programa que podem aparecer devido a atrasos na rede
Avaliando programas empiricamente
• Medindo tempo de execução
L1: time(&t1);
.
.
L2: time(&t2);
.
elapsed_time = difftime (t2,t1);
printf(“Elapsed_time = %5.2f segundos”, elapsed_time);
• Rotina MPI_ Wtime() provê hora em segundos
Avaliando programas empiricamente
• Medindo tempo de comunicação pelo método pingpong
P0
L1: time(&t1);
send(&x, P1);
recv(&x, P1);
L2: time(&t2);
elapsed_time = 0.5 * difftime (t2, t1);
printf(“Elapsed_time = %5.2f segundos”, elapsed_time);
P1
.
recv(&x, P0);
send(&x, P0);
.
Número de repetições ou tempo
Profiling
1
2
3
4
5
6
7
8
9
10
Número das instruções ou regiões do programa