Estratégias de Particionamento e Divisão e
Conquista
Estratégias de particionamento
• Divide o problema em partes
• Exemplo:
– Soma de uma seqüência de números: divide a seqüência em m partes e as
soma de forma independente criando somas parciais
x0…x(n/m)-1
xn/m…x(2n/m)-1
x(m-1)n/m…xn-1
+
+
+
Somas parciais
+
Soma
Utilizando send()s e receive()s
separados
• Mestre
s = n/m;
for (i=0, x=0; i < m; i++, x=x+s)
send (&numbers[x], s, Pi);
sum = 0;
for (i=0; i < m; i++) {
recv(&part_sum, Pany);
sum=sum+part_sum; }
• Escravo
recv(numbers, s, Pmaster);
part_sum=0;
for (i=0; i < s; i++)
part_sum=part_sum+numbers[i];
send (&part_sum,Pmaster);
}
Utilizando rotina broadcast()
• Mestre
s = n/m;
bcast(numbers, s, Pslave_group);
sum = 0;
for (i=0; i < m; i++) {
recv(&part_sum, Pany);
sum=sum+part_sum; }
• Escravo
bcast(numbers, s, Pmaster);
start=slave_number * s;
end=start + s;
part_sum=0;
for (i=start; i < end; i++)
part_sum=part_sum+numbers[i];
send (&part_sum,Pmaster);
Utilizando rotinas scatter() e
reduce()
• Mestre
s = n/m;
scatter(numbers, &s, Pgroup,root=master);
reduce_add(&sum, &s,Pgroup,root=master);
• Escravo
scatter(numbers, &s, Pgroup,root=master);
.
.
reduce_add (&part_sum,&s, Pgroup,root=master);
Análise de complexidade
•
Seqüencial: n-1 somas
•
Paralela: Utilizando rotinas send e receive
– Fase 1: Comunicação
ts  O(n)
tcomm1  m(t startup  n tdata )
m
– Fase 2: Computação
tcomp1  n
m
1
– Fase 3: Comunicação: retorno dos resultados parciais
tcomm 2  m(tstartup  tdata )
– Fase 4: Computação: acumulação final
tcomp 2  m 1
– Tempo total de execução: Pior que seqüencial
t p  2m tstartup  (n  m)tdata  m  n
m
 2  O(n  m)
Divisão e conquista
• Divide o problema em subproblemas que são da mesma
forma que o problema maior e divisões posteriores
podem ser realizadas por recursão
• Exemplo
– Uma definição recursiva seqüencial para adicionar uma lista de números
int add (int *s)
{
if (number(s) <= 2) return (n1 + n2);
else {
divide (s, s1, s2);
part_sum1 = add(s1);
part_sum2 = add(s2);
return(part_sum1 + part_sum2);
}
}
Construção da árvore
Problema inicial
Divide o
problema
Tarefas finais
Implementação paralela
Lista original
P0
P0
P4
P0
P0
x0
P2
P1
P2
P6
P4
P3
P4
P5
P6
P7
xn-1
Implementação paralela
xn-1
x0
P0
P1
P0
P2
P3
P4
P2
P5
P6
P6
P4
P0
P4
P0
Soma final
P7
Código paralelo
• Suponha que foram criados 8 processos estáticamente
Processo P0
divide(s1, s1, s2);
send(s2, P4);
divide(s1, s1, s2);
send(s2, P2);
divide(s1, s1, s2);
send(s2, P1);
part_sum = *s1;
recv(&part_sum1, P1);
part_sum=part_sum + part_sum1;
recv(&part_sum1, P2);
part_sum=part_sum + part_sum1;
recv(&part_sum1, P4);
part_sum=part_sum + part_sum1;
Código paralelo
Processo P4
recv(s1, P0);
divide(s1, s1, s2);
send(s2, P6);
divide(s1, s1, s2);
send(s2, P5);
part_sum = *s1;
recv(&part_sum1, P5);
part_sum=part_sum + part_sum1;
recv(&part_sum1, P6);
part_sum=part_sum + part_sum1;
send(&part_sum, P0);
Análise de complexidade
• Assuma que n é uma potência de 2 e tstartup não é
incluído
– Fase 1: Comunicação - Divisão
n
n
n
n
n( p  1)
tcomm1  t data  tdata  tdata  ...  tdata 
tdata
2
4
8
p
p
– Fase 2: Combinação
tcomm 2  tdata log p
– Fase 3: Tempo total de comunicação
tcomm  tcomm1  tcomm 2 
– Computação
tcomp 
n
 log p
p
– Tempo total
tp 
n( p  1)
tdata  tdata log p
p
n( p  1)
n
tdata  tdata log p   log p
p
p
Árvore para operador OR
OR
Achou/
Não achou
OR
OR
Dividir e conquistar M-ário
• As tarefas são divididas em mais de uma parte em cada
estágio
• Exemplo: Uma tarefa é quebrada em 4 partes. A
definição recursiva poderia ser
int add (int *s)
{
}
if (number(s) <= 4) return (n1 + n2+n3+n4);
else {
divide (s, s1, s2,s3,s4);
part_sum1 = add(s1);
part_sum2 = add(s2);
part_sum3 = add(s3);
part_sum4 = add(s4);
return(part_sum1 + part_sum2+part_sum3 + part_sum4);
}
Exemplos utilizando divisão e conquista
• Ordenação utilizando bucket sort
– O intervalo de números é dividido em m regiões iguais, 0 até a/m-1, a/m
até 2a/m-1, 2a/m até 3a/m-1, …
– Um balde ( bucket) é designado para armazenar os números que estão em
uma determinada região
– Os números são colocados nos baldes associados
– Os números de cada balde serão ordenados através de um algoritmo de
ordenação seqüencial
– Funciona bem, se números estiverem distribuídos de forma uniforme em
um intervalo conhecido 0 até a-1
Bucket sort
Números desordenados
Baldes
Ordenação
do conteúdo
dos baldes
Listas
concatenadas
Números ordenados
Análise de complexidade para o bucket sort
• Tempo seqüencial
ts  n  m((n m) log(n m))  n  n log(n m)  O(n log(n m))
• Tempo paralelo
– Designando um processador para cada balde, teremos que o segundo
termo da equação acima será reduzido para (n p) log(n p)
quando forem utilizados p processadores, onde p=m.
Uma versão paralela para o bucket sort
Números desordenados
p processadores
Baldes
Ordenação
do conteúdo
dos baldes
Listas
concatenadas
Números ordenados
Maior paralelização
• Particiona a seqüência em m regiões, uma para cada
processador
• Cada processador mantém p baldes pequenos e separa
os números nas suas regiões nos seus próprios baldes
menores
• Esses baldes menores são esvaziados nos p baldes finais,
que requer que cada processador envie um balde
pequeno para cada um dos outros processadores (balde
i para processador i)
Versão paralela do bucket sort
n/m números
Números desordenados
p processadores
Baldes
pequenos
Esvazia baldes
pequenos
Baldes
grandes
Ordenação
do conteúdo
dos baldes
Listas
concatenadas
Números ordenados
Análise de complexidade
– Fase 1: Computação e Comunicação - Particionando os números
tcomp1  n
tcomm1  t startup  ntdata
– Fase 2: Computação (ordenação nos baldes menores)
tcomp 2  n p
– Fase 3: Comunicação (envio para os baldes maiores)
tcomm3  ( p 1)(tstartup  (n p2 ) tdata )
– Computação (ordenação nos baldes maiores)
tcomp 4  (n p) log(n p)
– Tempo total
t p  tstartup  ntdata  n p  ( p 1)(tstartup  (n p2 )tdata )  (n p) log(n p)
Uso da rotina all-to-all na fase 3
Processo n-1
Processo 0
Buffer de
envio
Buffer de
envio
0
Buffer de
recebimento
n-1
Processo 1
0
n-1
Processo n-1
0
n-1
Processo 0
0
n-1
Processo n-2
Efeito da rotina all-to-all
A0,0 A0,1
A0,2 A0,3
A0,0 A1,0
A2,0 A3,0
A1,0 A1,1
A1,2 A1,3
A0,1 A1,1
A2,1 A3,1
A2,0 A2,1
A2,2 A2,3
A0,2
A12
A2,2 A3,2
A3,0 A3,1
A3,2 A3,3
A0,3 A1,3
A2,3 A3,3
Integração numérica
• Uma técnica geral de divisão e conquista consiste em
dividir a região continuamente em partes e existe uma
função de otimização que decide quando certas regiões
estão suficientemente divididas
• Exemplo:
– Integração numérica: divide a área em partes separadas e cada uma delas
pode ser calculada por um processo separado
b
I   f ( x)dx
a
Integração numérica utilizando retângulos
• Cada região pode ser calculada por uma aproximação
utilizando retângulos
f(x)
f(p)
a
f(q)
p 
q
b
x
Integração numérica utilizando retângulos
(uma aproximação melhor)
• Alinhamento dos retângulos
f(x)
f(p)
a
f(q)
p 
q
b
x
Integração numérica utilizando o método
trapezoidal
f(x)
f(p)
a
f(q)
p
 q
b
x
Designação estática
• Pseudo código SPMD
Processo Pi
if (i == master) {
printf (“Entre com o número de intervalos “);
scanf (“%d”, &n);
}
bcast(&n, Pgroup);
region = (b-a)/p;
start=a + region * i;
end = start + region;
d=(b-a)/n;
area=0.0;
for (x = start; x <end; x = x+d)
area = area +f(x) + f(x+d);
area=0.5 * area * d;
reduce_add(&integral, &area, Pgroup);
Método da quadratura adaptativa
• Solução se adapta ao formato da curva
• Exemplo:
– Utilize 3 áreas A, B e C. A computação termina quando a área calculada
para a maior das regiões entre A e B tiver um valor suficientemente
próximo à soma das áreas para as outras regiões
Construção pelo método da quadratura
adaptativa
f(x)
C
A
B
Método da quadratura adaptativa
A=B e C=0
f(x)
A
B
Problema dos N-corpos
• Encontrar as posições e movimentos de corpos no
espaço que estão sujeitos a forças gravitacionais dos
outros corpos segundo as leis de Newton
• A força gravitacional entre dois corpos de massas ma e
mb é dada por
Gm a mb
r2
onde G é uma constante e r a distância entre os corpos
F
• Submetido a uma força um corpo acelera segundo a
segunda Lei de Newton:
F  ma
onde m é a massa do corpo, F a força a que
ele está submetido e a a aceleração resultante
Problema dos N-corpos
• Seja o intervalo de tempo t. Então para um corpo com
massa m, a força é dada por
m(v t 1  v t
F
)
t
• a nova velocidade por
v t 1  v t 
Ft
m
• e a mudança de posição
x t 1  x t  vt
• Depois que os corpos se movem para as novas posições,
as forças mudam e o cálculo tem que ser repetido
Espaço tridimensional
• Temos as coordenadas (x,y,z) e a distância entre os
corpos em (xa,ya,za) e (xb,yb,zb) é dada por
r  ( xb  xa ) 2  ( yb  ya ) 2  ( zb  z a ) 2
• e as forças são resolvidas nas 3 direções por
Gma mb  xb  xa 


2
r
 r 
Gma mb  yb  y a 
Fy 


r2  r 
Gma mb  zb  z a 
Fz 


2
r
 r 
Fx 
Código seqüencial para N-corpos
for (t = 0; t , tmax; t++) {
for (i = 0; i < N; i++) {
F=Force_routine(i);
v[i]new = v[i[ + F * dt/m;
x[i]new = x[i] + v[i]new * dt;
}
for (i = 0; i < N; i++) {
x[i] = x[i]new;
v[i] = v[i]new;
}
}
Código paralelo para N-corpos
• O algoritmo seqüencial tem complexidade O(n2) para
cada iteração pois cada um dos N corpos é influenciado
pelos outros N-1 corpos
• Não é possível utilizar o algoritmo seqüencial
diretamente para os problemas mais interessantes onde
N é grande
• A complexidade pode ser reduzida observando-se que
um grupo de corpos distantes pode ser aproximado
com um único corpo distante com a massa total dos
corpos do grupo e situado no centro de massa do grupo
Algoritmo Barnes-Hut
• Inicie com um espaço único no qual um cubo contém
todos os corpos
• Divida esse cubo em 8 subcubos
• Se um subcubo não contém corpos, o subcubo é
retirado da lista de subcubos a serem analisados
• Se um subcubo contém mais de um corpo, ele é
recursivamente dividido em subcubos, até que cada
subcubo contenha apenas um corpo
• Esse processo cria uma octtree, 8 arestas de cada nó
• As folhas representam os subcubos com um corpo só
• Em cada nó, armazenam-se a massa total e o centro de
massa de cada subcubo
Algoritmo Barnes-Hut
• A força de cada corpo pode ser obtida atravessando a
árvore construída a partir da raíz, parando quando a
aproximação de agrupamento pode ser usada, isto é,
quando:
r
d

• onde  é uma constante tipicamente com valor 1.0 ou
menor
• A complexidade para construção da árvore é O(nlogn),
complexidade do método O(nlogn)
Algoritmo Barnes -Hut