Computações Síncronas
Computações síncronas
• Em aplicações síncronas, todos os processadores são
sincronizados em pontos regulares
• Barreira
– Um mecanismo básico para sincronização de processos que deve ser
inserido no ponto do programa onde os processos devem esperar para se
sincronizarem
– Todos os processos param sua execução, quando atingem o ponto onde
existe uma barreira, e retornam a executar assim que todos ou um certo
número de processos atinjam esse mesmo ponto
Rotinas que implementam barreiras
• MPI
– MPI_Barrier()
• tem como único parâmetro um identificador de communicator
• cada processo pertencente a esse communicator chama essa rotina, e
fica bloqueado até que todos os membros do grupo tenham atingido
essa chamada de rotina
• PVM
– pvm_barrier()
• tem como parâmetro um identificador de um grupo
• pode-se especificar o número de processos que devem chegar na
barreira para liberar os processos que acionam a rotina de barreira
Implementação de barreira
• Barreiras baseadas em contadores geralmente possuem
duas fases:
– um processo entra na fase denominada fase de chegada e não sai dessa
fase enquanto todos os processos cheguem nessa mesma fase
– depois os processos vão para a fase denominada fase de saída e são
liberados
• As implementações da barreira devem tomar cuidado
com o fato de que uma barreira pode ser utilizada mais
de uma vez em um processo
– pode ser que um processo entre em uma rotina de barreira pela segunda
vez antes que outros processos tenham retornado da rotina acionada em
uma primeira vez.
Exemplo de código
• Mestre:
for (i = 0; i < n; i++) /* conta os escravos assim que eles chegarem na
barreira */
recv (Pany);
for (i = 0; i < n; i++) /* libera os escravos */
send (Pi);
• Escravos:
send (Pmaster);
recv (Pmaster;
Implementação por árvore
• Suponha que existem oito processos P0, P1, P2, P3, P4,
P5, P6 e P7:
– 1o. estágio: P1 envia mensagem para P0; (quando P1 chega na barreira)
P3 envia mensagem para P2; (quando P3 chega na barreira)
P5 envia mensagem para P4; (quando P5 chega na barreira)
P7 envia mensagem para P6; (quando P7 chega na barreira)
– 2o. estágio: P2 envia mensagem para P0; (P2 e P3 chegaram na barreira)
P6 envia mensagem para P4; (P6 e P7 chegaram na barreira)
– 3o. estágio: P4 envia mensagem para P0; (P4, P5, P6 e P7 chegaram na
barreira)
P0 finaliza fase de chegada; (quando P0 chega na barreira e
recebeu mensagem de P4)
Sincronização local
• Suponha que um processo Pi tenha que se sincronizar e
trocar dados com o processo Pi-1 e Pi+1 antes de
continuar a execução do programa:
Processo Pi-1
Processo Pi
Processo Pi+1
recv (Pi);
send (Pi);
send (Pi-1);
send (Pi+1);
recv (Pi-1);
recv (Pi+1);
recv (Pi);
send (Pi);
• Essa não é uma barreira perfeita de três processos
porque Pi-1 e Pi+1 só são sincronizados com Pi
Deadlock
• Quando um par de processos precisa enviar e receber
mensagens entre eles, pode ocorrer um bloqueio
denominado deadlock
• Ocorre deadlock quando ambos os processos
executarem primeiro o envio de mensagem através de
rotinas síncronas ou rotinas bloqueantes sem espaço
suficiente de buffer: elas ficarão indefinidamente
esperando por uma rotina de recebimento que nunca
será executada
Deadlock
• Solução:
– Faça com que um processo receba primeiro uma mensagem e depois
envie, e o outro processo deve primeiro enviar a mensagem e depois
tentar receber
– Exemplo:
• Em um pipeline linear, os processos de números pares devem
executar seus envios primeiro e os processos de números ímpares
devem executar os recebimentos primeiro
Rotinas combinadas livres de deadlock
• Como comunicações bidirecionais são bastante comuns,
o MPI definiu rotinas combinadas bloqueantes para
envio e recebimento de mensagens que devem ser
implementadas de forma a evitar deadlock:
MPI_Sendrecv () e MPI_Sendrecv_replace()
Processo Pi-1
Processo Pi
Processo Pi+1
sendrecv (Pi);
sendrecv (Pi-1);
send recv(Pi+1);
sendrecv (Pi);
Computações síncronas
• Paralelismo de dados:
– Mesma operação executada sobre elementos de dados diferentes
simultaneamente
– Modelo conveniente porque:
• Fácil de programar (essencialmente necessita de um programa único)
• Escala facilmente para problemas de tamanho maior
• Vários problemas numéricos e não-numéricos podem ser modelados
utilizando esse modelo
– Exemplo:
• for (=i = 0; i < n; i++)
a[i] = a[i] + k;
Construção forall
• Construção especial paralela existente em algumas
linguagens de programação para especificar operações
paralelas sobre dados
• No exemplo abaixo, n instâncias das instruções contidas
em blocoinst serão executadas simultaneamente:
forall (i = 0; i < n; i++) {
blocoinst ()
}
• Um valor da variável do loop i é válido em cada
instrução do bloco de instruções blocoinst, para a
primeiro instância temos i = 0, para a próxima i =1 e
assim por diante.
Construção forall
• Para somar k a cada elemento de um array a, podemos
escrever :
forall (i = 0; i < n; i++) {
a[i] = a[i] +k;
• Utilizando-se a rotina barreira:
i = myrank; /* myrank é o rank do processo que varia de 0 a n-1 */
a[i] = a[i] +k;
barrier (mygroup);
Soma de prefixos
• Dada uma lista de números, x0, …, xn-1, calcule as somas
parciais (x0 + x1; x0 + x1 + x2;x0 + x1 + x2 + x3; …)
• Utilizada para compactação de dados, ordenação e
avaliação de polinômios
• Código seqüencial:
for (i = 0; i < n; i++) {
sum[i] = 0;
for (j = 0; j <= i; j++)
sum[i] = sum[i] + x[j];
}
•
Complexidade O(n2)
Paralelismo de dados para adicionar todas
as somas parciais de 16 números
• Código seqüencial:
for (j = 0; j < log(n); j++)
for (i = 2j; i < n; i++)
x[i] = x[i] + x[i - 2j];
•
Código paralelo:
for (j = 0; j < log(n); j++)
forall (i = 0; i < n; i++)
if (i >= 2j ) x[i] = x[i] + x[i- 2j];
Iterações síncronas ou paralelismo síncrono
• Resolver um problema por iterações onde cada iteração
é composta de vários processos que começam a
executar juntos no início da iteração e a próxima
iteração só pode ser iniciada quando todos os processos
tiverem finalizado a iteração prévia.
• Código utilizando forall:
for (j = 0; j < n; j++)
forall (i = 0; i < N; i++) {
blocoinst(i); }
• Código utilizando barreira:
for (j = 0; j < n; j++) {
i = myrank;
blocoinst(i);
barrier(mygroup) }
Resolvendo um sistema de equações
lineares por iterações
• Resolver um sistema de equações lineares de forma
geral com n equações e n entradas:
a n 1 , 0 x 0  a n 1 ,1 x1  a n 1 , 2 x 2 ...  a n 1 , n 1 x n 1  b n 1
.
.
a 2 , 0 x 0  a 2 ,1 x1  a 2 , 2 x 2  ...  a 2 , n 1 x n 1
 b2
a 1 , 0 x 0  a 1 ,1 x1  a 1 , 2 x 2  ...  a 1 , n 1 x n 1
 b1
a 0 , 0 x 0  a 0 ,1 x1  a 0 , 2 x 2  ...  a 0 , n 1 x n 1
 b0
Resolvendo um sistema de equações
lineares por iterações
• Rearruma a i-ésima equação:
a i , 0 x 0  a i ,1 x1  a i , 2 x 2 ...  a i , n 1 x n 1
 bi
para
x i  (1 a i , i ) [ bi  ( a i , 0 x 0  a i ,1 x1  a i , 2 x 2 ...  a i , n 1 x n 1 )]
ou
xi 
1 
 bi 
a i ,i 
a
ji
i, j

xj

Resolvendo um sistema de equações
lineares por iterações
• Iteração de Jacobi:
– Inicie as variáveis x com algum valor inicial, por exemplo, xi = bi
– Calcule os novos valores para as variáveis x utilizando a equação de


iteração: x  a1  b   a x 


– Com esses novos valores, recalcule as variáveis x
– Todos os valores de x são atualizados simultaneamente
– Repita esse processo até que valores suficientemente corretos para todas
as variáveis sejam obtidos
– Esse método converge no caso em que a é diagonalmente dominante, ou
seja, para cada linha da matriz a, o valor do elemento da diagonal de a tem
um valor absoluto maior que a soma dos valores absolutos dos outros
elementos dessa linha:
i
i
i, j
ji
i ,i

ji
a i , j  a i ,i
j
Terminação de processamento das iterações
• Umas maneira simples e comum de se terminar o
processamento das iterações é comparar os valores
calculados em uma iteração com os valores obtidos em
uma iteração prévia, e terminar o processamento na tésima iteração quando os valores estiverem dentro de
uma certa tolerância, isto é, quando:
t 1
xi  xi
t
 tolerância
t
i
ao erro
para todo i, onde x é o valor de x depois da t-ésima
iteração e x é o valor de x depois da (t-1)-ésima
iteração
t 1
i
i
i
Código seqüencial
• Dados os arrays a[][] e b[][] que armazenam as
constantes das equações, x[] que possui os valores das
variáveis e um número fixo de iterações limit:
for (i = 0; i < n; i++)
x[i] = b[i];
for (iteration = 0; iteration < limit; iteration ++) {
for (i = 0; i < n; i++) {
sum = 0;
for (j = 0; j < n; j++)
if (i != j) sum = sum + a[i][j] * x[j];
new_x[i] = (b[i] - sum)/ a[i][i] ;
}
for (i = 0; i < n; i++)
x[i] = new_x[i];
}
Código seqüencial
• Um pouco mais eficiente:
for (i = 0; i < n; i++)
x[i] = b[i];
for (iteration = 0; iteration < limit; iteration ++) {
for (i = 0; i < n; i++) {
sum = -a[i][i]*x[i];
for (j = 0; j < n; j++)
sum = sum + a[i][j] * x[j];
new_x[i] = (b[i] - sum)/ a[i][i] ;
}
for (i = 0; i < n; i++)
x[i] = new_x[i];
}
Código paralelo
• Código para o processo Pi:
x[i] = b[i];
for (iteration = 0; iteration < limit; iteration ++) {
sum = -a[i][i]*x[i];
for (j = 0; j < n; j++)
sum = sum + a[i][j] * x[j];
new_x[i] = (b[i] - sum)/ a[i][i] ;
broadcast_receive(&new_x[i]);
global_barrier();
}
• A rotina broadcast_receive() envia o novo valor
calculado x[i] do processo i para todos os outros
processos e recebe os valores enviados pelos outros
processos
Código paralelo
• Executando iterações até atingir uma certa tolerância
ao erro:
x[i] = b[i];
iteration = 0;
do {
iteration++;
sum = -a[i][i]*x[i];
for (j = 0; j < n; j++)
sum = sum + a[i][j] * x[j];
new_x[i] = (b[i] - sum)/ a[i][i] ;
broadcast_receive(&new_x[i]);
} while (tolerence ( ) && (iteration < limit ));
onde a rotina tolerence( ) retorna FALSE se estiver pronto para acabar
iterações, ou TRUE, caso contrário.
Particionamento
• Geralmente o número de processadores é muito menor
que o número de elementos de dados a serem
processados
• Deve-se particionar o problema, de modo que cada
processador trabalhe com mais de um elemento de
dados
• No problema anterior, por exemplo, cada processador
pode ser responsável pelo cálculo de um grupo de
variáveis
Particionamento
• Alocação por bloco:
– as variáveis são alocadas para cada processador em grupos de variáveis
consecutivas em ordem crescente
• Alocação cíclica:
– as variáveis são alocadas em ordem uma para cada processador, isto é, o
processador P0 recebe as variáveis x0,xp,x2p,...,x((n/p-1)p, o processador P1
recebe as variáveis x1,xp+1,x2p+1,...,x((n/p-1)p+1,
• Para esse caso não há vantagem de se utilizar a
alocação cíclica, pois fica complicado calcular os índices
das variáveis
Análise de complexidade
•
•
•
•
Suponha que existem n equações e p processadores
Um processador opera sobre n/p variáveis
Suponha que se executam  iterações
Cada iteração possui uma fase de computação e uma
para a comunicação broadcast
– Computação
t comp  n p ( 2 n  4 )
– Comunicação
t comm  p ( t startup  ( n p ) t data )  ( pt startup  nt data )
– Total
t p  ( n p ( 2 n  4 )  pt startup  nt data )
Problema da distribuição de calor
• Encontrar a distribuição das temperaturas em uma
folha quadrada de metal, para a qual se conhecem as
temperaturas das bordas
• Divide-se a área em uma malha de pontos, hi,j
• A temperatura em um ponto pode ser considerada
como a média de 4 pontos vizinhos
• As bordas são definidas pelos pontos adjacentes aos
pontos interiores (pontos para os quais 0 <i <n, 0 <j <n)
Problema da distribuição de calor
• A temperatura de cada ponto pode ser calculada
através de iterações da equação:
hi , j 
h i 1 , j  hi  1 , j  h i , j 1  hi , j  1
4
onde (0<i<n,0<j<n)
• O número de iterações é fixo ou executam-se iterações
até que a diferença entre os valores obtidos por duas
iterações consecutivas seja menor que um valor prédefinido
Problema da distribuição de calor
• Os pontos começam a ser numerados de 1 e incluem
aqueles que representam as bordas
• Para calcular a temperatura de cada ponto, utiliza-se:
xi 
x i 1  x i  1  x i  k  x i  k
4
• Pode ser escrita como uma equação linear contendo as
variáveis xi-k,xi-1,xi+1 e xi+k:
x i  k  x i 1  4 x i  x i  1  x i  k  0
• Método das diferenças finitas
Código seqüencial
• Utilizando um número fixo de iterações
for (iteration = 0; iteration < limit; iteration ++) {
for (i = 1; i < n; i++)
for (j = 1; j < n; j++)
g[i][j] = 0.25*(h[i-1][j]+h[i+1][j]+h[i][j-1]+h[i][j+1]);
for (i = 1; i < n; i++)
for (j = 1; j < n; j++)
h[i][j] = g[i][j];
}
Código seqüencial
• Para parar quando atingir uma certa precisão
do {
for (i = 1; i < n; i++)
for (j = 1; j < n; j++)
g[i][j] = 0.25*(h[i-1][j]+h[i+1][j]+h[i][j-1]+h[i][j+1]);
for (i = 1; i < n; i++)
for (j = 1; j < n; j++)
h[i][j] = g[i][j];
continue = FALSE;
for (i = 1; i < n; i++)
for (j = 1; j < n; j++)
if (!converged(i,j) {
continue = TRUE;
break;
}
} while (continue == TRUE);
Código paralelo
• Código para cada processo Pi,j com número fixo de
iterações:
for (iteration = 0; iteration < limit; iteration ++) {
g = 0.25*(w+x+y+z);
send(&g, Pi-1,j);
send(&g, Pi+1,j);
send(&g, Pi,j-1);
send(&g, Pi,j+1);
recv(&w, Pi-1,j);
recv(&x, Pi+1,j);
recv(&y, Pi,j-1);
recv(&z, Pi,j+1);
}
• As rotinas send() não devem ser bloqueadas pela espera
de um recv () correspondente, pode ocorrer deadlock
• As rotinas recv() tem que ser síncronas e esperar pela
execução das rotinas send() correspondentes
Código paralelo
• Código para cada processo Pi,j que para de executar
quando precisão requerida é atingida:
iteration = 0;
do {
iteration++;
g = 0.25*(w+x+y+z);
send(&g, Pi-1,j);
send(&g, Pi+1,j);
send(&g, Pi,j-1);
send(&g, Pi,j+1);
recv(&w, Pi-1,j);
recv(&x, Pi+1,j);
recv(&y, Pi,j-1);
recv(&z, Pi,j+1);
} while ((!converged(i,j)) && (iteration < limit));
send (&g, &i, &j, &iteration, Pmaster);
Código paralelo
• Código para processar as bordas:
if (last_row) w = bottom_value;
if (first_row) x = top_value;
if (first_column) y = left_value;
if (last_column) z = right_value;
iteration = 0;
do {
iteration++;
g = 0.25*(w+x+y+z);
if !(first_row) send(&g, Pi-1,j);
if !(last_row) send(&g, Pi+1,j);
if !(first_column)_ send(&g, Pi,j-1);
if !(last_column) send(&g, Pi,j+1);
if (!last_row) recv(&w, Pi-1,j);
if !(first_row) recv(&x, Pi+1,j);
if !(first_column) recv(&y, Pi,j-1);
if !(last_column) recv(&z, Pi,j+1);
} while ((!converged(i,j)) && (iteration < limit));
send (&g, &i, &j, &iteration, Pmaster);
Particionamento
• Normalmente aloca-se mais de um ponto para cada
processador
• Os pontos podem ser particionados em blocos ou em
faixas:
P0 P1
P0 P1
Pp-1
Pp-1
Particionamento por bloco
• Quatro bordas onde pontos são trocados
• Tempo de comunicação:

n
t comm  8  t startup 
t data

p





n
p
Particionamento por faixa
• Duas bordas onde pontos são trocados
• Tempo de comunicação:
t comm  4 t startup  nt data

n
Particionamento ótimo
• Em geral, o particionamento por faixa é melhor quando
o tempo de startup é muito grande, e o por bloco
quando esse tempo é pequeno
• O particionamento por bloco implicará em um tempo
total maior de comunicação caso:

n
8  t startup 
t data

p


  4 (t
 nt data )
startup


ou
t startup  n (1 
( p  9)
2
p
) t data
Pontos fantasma
• Uma linha adicional de pontos colocada em cada borda
com os valores dos pontos da borda adjacente
• Cada array de pontos é aumentado para acomodar as
linhas fantasma
Segurança e deadlock
• Na literatura relativa ao MPI, denomina-se um
processo “inseguro”, quando todos os processos enviam
primeiro suas mensagens e depois recebem as
mensagens, porque dessa maneira está se confiando na
capacidade de bufferização das rotinas send( )
• Se uma rotina send ( ) não possui espaço suficiente para
armazenar a mensagem quando acionada, a
implementação deve atrasar o retorno dessa rotina até
que haja espaço de armazenamento disponível ou que a
mensagem possa ser enviada sem bufferização
• Desse modo, a rotina localmente bloqueante send ( )
pode se comportar como uma rotina síncrona send (),
somente retornando quando uma rotina recv()
correspondente seja executada e podendo levar a um
deadlock
Tornando o código seguro
• Alternando a ordem das rotinas send() e recv() dos
processos adjacentes, de modo que somente um
processo execute as rotinas send() primeiro:
if ((i % 2 == 0) {
send(&g[1][1], &n, Pi-1);
recv(&h[0][1], &n, Pi-1);
send(&g[n/p][1], &n, Pi+1);
recv(&h[n/p+1][1], &n, Pi+1);
} else {
recv(&h[1][1], &n, Pi-1);
send(&g[n/p][1], &n, Pi-1);
recv(&h[0][1], &n, Pi+1);
send(&g[1][1], &n, Pi+1);
}
Rotinas seguras do MPI
• Rotinas combinadas de envio e recebimento:
MPI_Sendrecv() que tem a garantia de não provocar
deadlock
• Rotinas send() bufferizadas: MPI_Bsend (), onde o
usuário provê o espaço de endereçamento de forma
explícita
• Rotinas não bloqueantes: MPI_Isend() e MPI_Irecv,
que retornam imediatamente e existem rotinas
separadas para verificar quando a mensagem foi
recebida (MPI_Wait(), MPI_Waitall(), MPI_Waitany(),
MPI_Test(), MPI_Testall () ou MPI_Testany())
Utilizando rotinas seguras do MPI
• Utilizando-se rotinas não bloqueantes:
isend(&g[1][1], &n, Pi-1);
isend(&g[n/p][1], &n, Pi+1);
irecv(&h[0][1], &n, Pi-1);
irecv(&g[n/p+1][1], &n, Pi+1);
waitall(4);
• A rotina wait funciona como uma barreira, esperando
que todas as rotinas de passagem de mensagens
completem sua execução
Autômato celular
• O espaço do problema é dividido em células
• Cada célula pode estar em um estado dentro de um
número finito possível de estados
• As células são afetadas por suas vizinhas de acordo com
certas regras e simultaneamente em uma geração
• As regras são reaplicadas em gerações subsequentes de
modo que as células evoluam ou troquem de estado de
geração em geração
Jogo da vida
• O tabuleiro do jogo consiste de um array bidimensional de células teoricamente de dimensões
infinitas
• Cada célula pode conter um organismo e possui 8
células vizinhas, incluindo as adjacentes diagonais
• Inicialmente algumas células estão ocupadas de acordo
com um certo padrão
• As seguintes regras devem ser seguidas:
– Todo organismo que possui 2 ou 3 organismos vizinhos sobrevive para a
próxima geração
– Todo organismo com 4 ou mais vizinhos morre devido à superpopulação
– Todo organismo com 1 ou 0 vizinhos morre por isolamento
– Cada célula vazia com exatamente 3 vizinhos ocupados gera um
organismo
Tubarões e peixes
• O oceano é modelado como um array de células
tridimensional, onde cada célula pode possuir ou um
peixe ou um tubarão
• Regras para o peixe:
– Se existe uma célula adjacente vazia, ele se move para essa célula
– Se existe mais de uma célula adjacente vazia, ele se move para alguma
delas escolhida de forma aleatória
– Se não existem células adjacentes vazia, ele fica parado
– Se ele se move e atinge a idade de procriar, ele gera um peixe filho, que é
deixado na célula vaga
– Ele morre depois de x gerações
Tubarões e peixes
• Regras para o tubarão:
– Se existe uma célula adjacente ocupada por um peixe, ele se move para
essa célula e come o peixe
– Se existe mais de uma célula adjacente estiver ocupada por um peixe, ele
se move para alguma delas escolhida de forma aleatória e come o peixe
dessa célula
– Se não existem células adjacentes ocupadas por peixe, ele se move para
uma célula adjacente vazia da mesma forma que o peixe faz
– Se ele se move e atinge a idade de procriar, ele gera um tubarão filho, que
é deixado na célula vaga
– Se ele fica sem comer por y gerações, ele morre
Aplicações de autômatos celulares
•
•
•
•
•
Dinâmica para gases e fluidos
Difusão de gases
Crescimento biológico
Fluxo de ar em uma asa de avião
movimento e erosão da areia em uma praia ou margem
de rio