Estratégias Pipelined
Estratégias pipelined
• O problema é dividido em uma série de tarefas que
devem ser completadas uma após a outra
• Cada tarefa é executada por um processo separado ou
processador
P0
P1
P2
P3
P4
P5
Exemplo
• Somar todos os elementos de um array a em uma soma
acumulativa
for (i=0; i < n; i++)
sum = sum + a[i];
• O loop pode ser desdobrado em:
sum = sum + a[0];
sum = sum + a[1];
sum = sum + a[2];
sum = sum + a[3];
sum = sum + a[4];
Pipeline para um loop desdobrado
a[0]
sum
sin
a
sout
a[1]
sin
a
sout
a[2]
sin
a
sout
a[3]
sin
a
sout
a[4]
sin
a
sout
Filtrando um sinal
Sinal sem Sinal sem Sinal sem Sinal sem
a freqüência a freqüência a freqüência a freqüência
f3
f2
f0
f1
f(t)
fin
f0
fout
fin
f1
fout
fin
f2
fout
fin
f3
fout
fin
f4
Sinal
filtrado
fout
Utilização de pipeline
• Dado que um determinado problema pode ser dividido
em uma série de tarefas seqüenciais, a estratégia de
pipeline pode ser utilizada para aumentar a velocidade
de processamento em três casos:
1.Se mais de uma instância do problema completo deve ser executada
2.Se uma série de dados deve ser processada e cada um dos dados requer
múltiplas operações
3.Se a informação para iniciar a próxima tarefa pode ser passada a frente
antes que o processo que a gera tenha completado todas as suas operações
internas
Diagrama espaço-tempo para tipo 1
m
p-1
P5
Instância Instância Instância Instância Instância
3
4
1
2
5
P4
Instância Instância Instância Instância Instância Instância
1
3
4
2
5
6
Instância Instância Instância Instância Instância Instância Instância
3
4
7
1
2
5
6
P3
P2
Instância Instância Instância Instância Instância
3
4
1
2
5
P1
Instância Instância Instância Instância Instância
3
4
1
2
5
P0
Instância Instância Instância Instância Instância Instância Instância
3
4
1
2
5
7
6
Tempo
Instância Instância
7
6
Instância Instância
7
6
Diagrama espaço-tempo alternativo
Instância 0
Instância 1
Instância 2
Instância 3
Instância 4
P0
P1
P2
P3
P4
P5
P0
P1
P2
P3
P4
P5
P0
P1
P2
P3
P4
P5
P0
P1
P2
P3
P4
P5
P0
P1
P2
P3
P4
Tempo
P5
Diagrama espaço-tempo para tipo 2
Seqüência de dados: d9d8d7d6d5d4d3d2d1d0
p-1
P9
P8
P7
P6
P5
P4
P3
P2
P1
P0
n
d0 d1
d0 d1 d2
d0 d 1 d2 d3
d0 d1 d2 d3 d4
d0 d1 d2 d 3 d4 d5
d0 d1 d2 d3 d4 d5 d6
d0 d1 d2 d3 d4 d5 d6 d7
d0 d1 d2 d3 d4 d 5 d6 d7 d8
d0 d1 d2 d3 d4 d5 d6 d7 d8 d9
d0 d1 d2 d3 d4 d5 d6 d7 d8 d9
Tempo
d2 d3 d4
d3 d4 d 5
d4 d5 d6
d5 d6 d7
d 6 d7 d8
d7 d8 d9
d8 d9
d9
d5 d6 d7 d8 d9
d6 d7 d8 d9
d7 d8 d9
d8 d9
d9
Diagrama espaço-tempo para tipo 3
P5
P5
P4
Transferência
de informação
suficiente para
iniciar nova
tarefa
P4
P3
P3
P2
P2
P1
P1
P0
P0
Tempo
Tempo
Particionando processos entre
processadores
• Se o número de estágios é maio que o número de
processadores, um grupo de estágios pode ser
designado para cada um dos processadores
Processador 2
Processador 1
P0
P1
P2
P3
P4
P5
Processador 3
P6
P7
P8
Plataforma computacional para aplicações
pipelined
Multiprocessador
Computador
host
Soma com pipeline
i
P2
5
i
1
1
P1
4
i
i
1
P0
3
2
i
1
P3
1
P4
Pseudo-código
• O código básico para o processador Pi:
recv(&accumulation, Pi-1);
accumulation = accumulation + number;
send(&accumulation, Pi+1);
• Para o processador P0:
send(&number, P1);
• Para o processador Pn-1:
recv(&number, Pn-2);
accumulation = accumulation + number;
Programa SPMD
• Pseudo-código
If (proces > 0) {
recv(&accumulation, Pi-1);
accumulation = accumulation + number;
}
if (process < n-1) send(&accumulation, Pi+1);
• O resultado final está no último processo
• Outras operações aritméticas podem ser executadas
Adição de números com processo mestre e
configuração em anel
Processo mestre
dn-1...d2d1d0
sum
Escravos
P0
P1
Pn-1
Adição de números com acesso direto aos
processos escravos
Processo mestre
Números
Escravos
d1
d0
sum
P0
P1
dn-1
Pn-1
Análise de complexidade
• O primeiro exemplo é do tipo 1 e cada processo executa
ações similares em cada ciclo de pipeline
• Tempo total de execução:
ttotal  (t empopara um ciclo de pipeline)(númerode ciclos)
ttotal  (tcomp  tcomm )(m  p  1)
onde existemm inst ânciasdo problemae p estágiosde pipeline
O tempomédio de comput açãoé dado por :
t
t a  total
m
Análise de complexidade
• Para uma instância
tcomp  1
tcomm  2(t startup  t data )
ttotal  (2(t startup  t data )  1)n
Complexidade  O(n)
• Para múltiplas instâncias: um ciclo de pipeline
ttotal  (2(t startup  tdata )  1)(m  n  1)
ta 
ttotal
 2(t startup  t data )  1
m
Particionamento de dados com múltiplas
instâncias do problema
tcomp  d
tcomm  2(t startup  t data )
ttotal  (2(t startup  t data )  d )(m  n d  1)
• Aumentando a partição de dados d, o impacto na
comunicação diminui, mas diminui o paralelismo e
aumenta o tempo de execução
Ordenação por inserção
P0
1
2
3
4
5
6
7
8
9
10
P1
P2
P4
P3
4,3,1,2,5
4,3,1,2 5
2
5
4,3,1
1
2
4,3 5
3
21
4 5
2
4
3
5
1
1
3
4
5
2
4
5
32 1
5
5
4
4
3
3
2
2
1
1
Pseudo-código
• O algoritmo básico para o processo Pi é:
recv(&number, Pi-1);
if (number > x) {
send (&x, Pi+1);
x = number;
}
else send (&number, Pi+1);
• Com n números, o processo i aceita n-1 números e
passa a frente n-i-1 números.
Pipeline para inserção
P0
Série de números
xn-1...x1x0
Menores
números
P1
compara
xmax
Maior número
Próximo maior
número
P2
Ordenação utilizando configuração
bidirecional
Processo mestre
dn-1...d2d1d0
sum
Escravos
P0
P1
Pn-1
Pseudo-código
right_procno=n-i-1;
recv(&x, Pi-1);
for (j = 0; j < right_procno; j++) {
recv(&number, Pi-1);
if (number > x) {
send (&x, Pi+1);
x = number;
}
else send (&number, Pi+1);
send (&x, Pi-1);
for (j = 0; j < right_procno; j++) {
recv(&number, Pi+1);
send (&number, Pi-1);
}
Análise de complexidade
Seqüencial
t s  (n  1)  (n  2)  ...  2  1 
n(n  1)
2
P aralelo
tcomp  1
tcomm  2(t startup  t data )
ttotal  (tcomp  tcomm )(2n  1)  (1  2(t startup  t data ))(2n  1)
Geração de números primos - Método de
Eratóstenes
• Para encontrar os números primos entre 2 e n, gera-se
a série de todos os números até n
• O número 2 é o primeiro número primo e todos os
múltiplos de 2 são removidos da lista, pois não podem
ser primos
• Considera-se o próximo número da lista e removem-se
seus múltiplos até chegar a n
• Somente se analisam os números até n , porque os
números maiores que n já foram examinados
Código seqüencial
for (i =2; i < n; i++)
prime[i] = 1;
for (i =2; i < =sqrt_n; i++)
if (prime[i] == 1)
for (j = i + 1; j < n; j = j + i)
prime[j] = 0;
• Análise de complexidade
– Existem n 2 1 múltiplos de 2, n 3 1múltiplos de 3
 n

n  n  n 
t s    1    1    1  ...  
 1
2  3  5 
 n 
Complexidade seqüencial: O (n 2 )
Análise de complexidade
• Existem n 2 1 múltiplos de 2,
n 3 1 múltiplos
 n

n  n  n 
t s    1    1    1  ...  
 1
2  3  5 
 n 
Complexidade seqüencial: O (n 2 )
de 3
Pipeline para geração de números primos
Números não múltiplos
do primeiro número primo
P0
P1
P2
Série de números
xn-1...x1x0
Compara
múltiplos
Primeiro
número
primo
Segundo
número
primo
Terceiro
número
primo
Pseudo-código
• Para cada processador Pi:
recv(&x, Pi-1);
recv(&number, Pi-1);
if ((number %x) != 0 ) send (&number, Pi+1);
• Como a quantidade de números não é a mesma e é
desconhecida para cada processador, utiliza-se uma
mensagem de finalização
recv(&x, Pi-1);
for (i = 0; i < n; i++) {
recv(&number, Pi-1);
if (number == terminator) break;
if (number % x ) != 0) send (&number, Pi+1);
}
Resolvendo um sistema de equações
lineares
• Exemplo do tipo 3, os processos podem continuar
depois de passar informação
• Exemplo:
– resolver sistema de equações lineares da forma triangular superior:
an 1,0 x0  an 1,1 x1  an 1, 2 x2 ...  an 1,n 1 xn 1  bn 1
.
.
a2,0 x0  a2,1 x1  a2, 2 x2
 b2
a1,0 x0  a1,1 x1
 b1
a0 x0
 b0
Resolução por substituição
• Encontra-se primeiro x0 da última equação:
x0 
b0
a0 , 0
• Esse valor é substituído na próxima equação para
encontrar x1
x1 
b1  a1,0 x0
a1,1
• E assim por diante:
x2 
b2  a2,0 x0  a2,1 x1
a2, 2
Solução utilizando pipeline
P1
P0
Calcula x0
x0
Calcula x1
P3
P2
x0
x1
Calcula x2
x0
x1
x2
Calcula x3
x0
x1
x2
x3
Solução utilizando pipeline
• O processo i recebe os valores x0,x1,x2,...,xi-1 e calcula xi
através da equação:
i 1
xi 
bi   ai , j x j
j 0
ai ,i
Código seqüencial
x[0] = b[0]/a[0][0];
for (i = 1; i < n; i++) {
sum = 0;
for (j = 0; j < i; j++)
sum = sum + a[i][j]*x[j];
x[i] = (b[i] - sum)/a[i][i];
}
Código paralelo
for (j = 0; i< j; j++) {
recv(&x[j], Pi-1);
send (&x[j], Pi+1);
}
sum = 0;
for (j = 0; j < i; j++)
sum = sum + a[i][j]*x[j];
x[i] = (b[i] - sum)/a[i][i];
send (&x[i], Pi+1);
}
Diagrama espaço-tempo para processo
pipeline para resolução de sistemas lineares
P5
P4
P3
P2
P1
P0
Passou primeiro
valor adiante
Tempo
Valor final
calculado
Análise de complexidade
• Não pode assumir que o esforço computacional será o
mesmo em todos os estágios do pipeline
• O primeiro processo executa uma divisão e um envio de
mensagem
• O processo i executa i envios e i recebimentos de
mensagens, i multiplicações/adições, uma
divisão/subtração e um envio final, em um total de 2i+1
tempos de comunicação e 2i+2 passos de computação
• O último processo executa n-1 recebimentos, n-1
multiplicações/somas e uma divisão/subtração,
totalizando n-1 tempos de comunicação e 2n-1 passos
de computação