Computação Embaraçosamente Paralela
Computação embaraçosamente paralela
• Um processamento que pode ser dividido em um
número de partes completamente independentes, cada
uma podendo se executada por um processador
diferente
Dados de
entrada
Processos
Resultados
Criação dinâmica de processos com técnica
mestre-escravo
spawn()
send()
Envio de
dados iniciais
recv()
Escravos
Mestre
send()
recv()
Coleta resultados
Exemplos
(a) Deslocamento: deslocar um objeto de x na dimensão
x e y na dimensão y
x   x  x
y  y  y
(b) Mudança de escala: mudar a escala de um objeto por
um fator Sx na dimensão x e por Sy na dimensão y
x  xSx
y  ySy
(c) Rotação: rotacionar um objeto de um ângulo  em
relação à origem do sistema de coordenadas
x  x cos  y sin 
y   x sin   y cos
Partição em regiões para os processos
individuais
x
Processo
80
y
640
80
480
Mapeia
Partição em regiões para os processos
individuais
Processo
10
640
Mapeia
480
Pseudocódigo para executar deslocamento
de imagem
• Mestre
for (i=0, row=0; i < 48; i++, row = row+10)
send (row, Pi); }
for (i=0; i < 480; i++)
for (j=0; j < 640; j++)
temp_map[i][j]=0;
for (i=0; i < (640*480); i++) {
recv(oldrow, oldcol, newrow, newcol, Pany);
if !((newrow < 0) || (newrow >=480) || (newcol < 0) || newcol >=640))
temp_map[newrow][newcol]=map[oldrow][oldcol]; }
for (i=0; i < 480; i++)
for (j=0; j < 640; j++)
map[i][j]= temp_map[i][j];
Pseudocódigo para executar deslocamento
de imagem
• Escravo
recv(row, Pmestre);
for (oldrow=row; oldrow < (row +10); oldrow++)
for (oldcol=0; oldcol < 640; oldcol++) {
newrow = oldrow + delta_x;
newcol = oldcol + delta_y;
send (oldrow, oldcol,newrow,newcol,Pmestre);
}
Análise de complexidade
• Seqüencial
ts  2n2  O(n2 )
• Paralela
– Comunicação
tcomm  tstartup  mtdata  p(tstartup  tdata )  n2 (tstartup  4tdata )  O( p  n2 )
– Computação
tcomp
 n2 
 2   O n 2 / p
 p

– Tempo total de execução
t p  tcomp  tcomm
Para uma constante p, O(n2)

Conjunto de Mandelbrot
• Conjunto de pontos no plano complexo que são quase
estáveis (diminuem e aumentam, mas não passam de
certo limite) quando calculados pela iteração da função
zk 1  zk2  c
onde z k 1 é a (k+1) iteração do número complexo z=a+bi
e c é um número complexo que dá a posição do ponto
no plano complexo
• Valor inicial de z é 0 e iterações são executadas até que
a magnitude de z (zlength) seja maior que 2 ou número de
iterações alcançou limite máximo
zlength  a 2  b 2
Conjunto de Mandelbrot
• Simplificando o cálculo de zk 1  zk2  c
z 2  a 2  2abi  b 2i 2  a 2  b 2  2abi
Cálculo do valorde z para cada iteração
z real  z real  zimag  creal
2
2
zimag  2 z real zimag  cimag
2
Rotina seqüencial para calcular valor de
um ponto retornando número de iterações
structure complex {
float real;
float imag;
}
int cal_pixel(complex c)
{
int count, max;
complex z;
float temp, lengthsq;
max=256;
z.real=0; z.imag=0;
count=0;
do {
temp=z.real*z.real -z.imag*z.imag +c.real;
z.imag=2*z.real*z.imag + c.imag;
z.real=temp;
lengthsq=z.real*z.real+z.imag*z.imag;
count ++
} while ((lengthsq < 4.0) && (count < max));
return count;
}
Mudança de escala do sistema de
coordenadas
• Para ser eficiente computacionalmente:
scale_real=(real_max - real_min)/disp_width;
scale_imag = (imag_max - imag_min)/disp_height;
• Incluindo a mudança de escala, temos o seguinte código
for (x = 0; x < disp_width; x++)
for (y = 0; y < disp_height; y++) {
c.real = real_min +((float) x * scale_real);
c.imag = imag_min + ((float) y * scale_imag);
color = cal_pixel(c);
display(x, y, color);
}
Paralelizando o cálculo do conjunto de
Mandelbrot com alocação dinâmica de
tarefas
Pool de trabalho
(xa,ya)
(xe,ye)
(xc,yc)
(xb,yb)
Tarefa
Retorna resultados/
pede nova tarefa
(xd,yd)
Código para a técnica de pool de trabalho
• Mestre
count = 0;
row = 0;
for (k=0; k < procno; k++) {
send(&row, Pk, data_tag);
count++;
row++;
}
do {
recv (&slave, &r, color, Pany, result_tag);
count--;
if (row < disp_height) {
send (&row, Pescravo, data_tag);
row ++;
count ++;
} else
send (&row, Pescravo, terminator_tag);
display ( r, color);
} while (count > 0);
Código para a técnica de pool de trabalho
• Escravo
recv(y, Pmestre, ANYTAG, source_tag);
while (source_tag == data_tag) {
c.imag = imag_min + ((float) y * scale_imag);
for (x = 0; x <disp_width; x++) {
c.real = real_min + ((float) x * scale_real);
color[x] = cal_pixel(c);
}
send (&i, &y, color, Pmestre, result_tag);
recv (y, Pmestre, source_tag);
};
Terminação do contador
Linhas tratadas nos escravos (count)
0
Término
Linha enviada
Incremento
disp_height
Linha retornada
Decremento
Análise de complexidade
• Seqüencial
ts  max n  O(n)
• Paralelo
– Fase 1: Comunicação - um número de linha é enviado para cada escravo
tcomm1  s(tstartup  tdata )
– Fase 2: Computação - Escravos executam o cálculo de Mandelbrot em
paralelo
tcomp 
max  n
s
– Fase 3: Comunicação - Resultados são enviados para o mestre por envios
individuais
tcomm 2  u(tstartup  vtdata )
– Complexidade geral
max  n
tp 
 s (t startup  t data )  u (t startup  vt data )
s
Métodos de Monte Carlo
•
A base dos métodos de Monte Carlo é utilizar seleções aleátorias para os
cálculos
•
Exemplo: Cálculo de 
2
Área = 
Área total=4
Área do círculo  (1) 2 


Área do quadrado 2  2 4
2
•
•
Pontos dentro do quadrado são escolhidos aleatoriamente e verifica-se a
fração desses pontos que está dentro do círculo
Dado um número suficiente de amostras aleatórias, essa fração será /4
Calculando uma integral
f(x)
1
1
y  1 x
1
2

0
1  x 2 dx 

4
x
1
Um par de números aleatórios (xr, yr) pode ser gerado entre 0 e 1 e contado
como dentro do círculo se y r  1  xr2 , ou seja, yr2  xr2  1
Calculando uma integral (método
alternativo)
• Gere valores aleatórios para x entre x1 e x2, calcule f(x) e
a soma dos valores de f(x)
Área 
x2

x1
1
f ( x)dx  lim
N  N
• Exemplo: Calcular
x2
N
 f ( x )( x
i 1
r
I   ( x 2  3x)dx
sum = 0;
for (i = 0; i < N; i++) {
xr = rand_v(x1, x2);
sum = sum + xr*xr -3 *xr;
}
area = (sum /N) * ( x2-x1);
x1
2
 x1 )
Implementação paralela
Mestre
Soma
parcial
Pedido
Escravos
Número
aleatório
Processo gerador
de números aleatórios
Pseudocódigo
• Mestre
for (i = 0; i < N/n; i++) {
for (j = 0; j < n; j+=)
xr[j] = rand ();
recv(Pany, req_tag, Pfonte);
send(xr, &n, Pfonte, compute_tag);
}
for (i = 0; i < slave_no; i++) {
recv(Pi, req_tag);
send(Pi, stop_tag);
}
sum=0;
reduce_add(&sum, Pgroup);
Pseudocódigo
• Escravo
sum = 0;
send(Pmaster, req_tag);
recv(xr, &n, Pmestre, source_tag);
while (source_tag == compute_tag) {
for (i = 0; i < n; i++)
sum = sum +xr[i] * xr[i] -3 * xr[i];
send(Pmestre, req_tag);
recv(xr, &n, Pmaster, source_tag);
}
reduce_add(&sum, Pgroup);
Geração de números aleatórios
• Geração de uma seqüência de números pseudo
aleatórios
x1 , x2, x3 ,..., xi 1 , xi , xi 1 ,..., xn 1 , xn
xi 1  (axi  c) modm
Geração paralela de números aleatórios
xi 1  (axi  c) modm
xi  k  ( Axi  C ) modm
onde A  a k modm, C  c(a k 1  a k  2  ...  a1  a 0 ) modm
x1
x2
xk-1
xk
xk+1
xk+2
x2k-1
x2k