Definindo melhor alguns conceitosboeres/slides_AP/AlgParalelosII.pdfDefinindo melhor alguns conceitos Processamento Paralelo: processamento de informação concorrente que pertencem

Definindo melhor alguns conceitos

Processamento Paralelo: processamento de informação concorrente que pertencem a um ou mais processos que resolvem um único problema.

Processamento Distribuído: processamento de informações em um sistema cujos recursos estão sendo compartilhados por vários programas

Computador Paralelo: computador de múltiplos processadores capaz de realizar processamento paralelo

Supercomputador: computador de propósito geral capaz de resolver problemas em alta velocidade, comparando com outras máquinas da mesma época.

A vazão de um dispositivo é o número de resultados produzidos por unidade de tempo. (throughtput)

Speedup (aceleração): razão entre o tempo de execução necessário para o algoritmo seqüencial mais eficiente e o tempo necessário para se realizar a mesma computação numa máquina paralela

Existem diversas definições de speedup:

– speedup absoluto(n)= T(melhor alg. seq. )/ T( prog // c/ n proc.)

– speedup aproximado(n)= T(prog.// c/1 proc.)/T( prog // c/ n proc.)

– speedup relativo (n)= T(prog. // c/(n-1) proc.)/T(prog.// c/ n proc.)

Terminologia

Computação concorrente

Duas formas de se explorar a concorrência em computação em computação

– Paralelismo de controle e de dados

tempo t

7 + 3 string ==“casa”? 32 * 14 7 + 3

Computação concorrente

Duas formas de se explorar a concorrência em computação em computação

– Paralelismo de controle e de dados

tempo t

7 + 3 7 + 3 10 + 200 33 + 329

Paralelismo de Controle

aplicando-se operações diferentes a diferentes dados simultaneamente.

– fluxo de dados entre processos pode ser arbitrariamente complexo

Exemplo:

– Pipelining: cada estágio trabalha em velocidade plena sobre uma parte particular da computação. A saída de um estágio é a entrada do estágio seguinte


tempo

E4 E1 E2 E3


tempo

info 1

E4 E1 E2 E3


tempo

info 1

E4 E1 E2 E3

info 2 info 1


tempo

info 1

E4 E1 E2 E3

info 2 info 1

info 3 info 1 info 2


tempo

info 1

E4 E1 E2 E3

info 2 info 1

info 3 info 1 info 2

info 3 info 4 info 1 info 2

Paralelismo de Dados

uso de vários processadores para executar a mesma operação ao mesmo tempo sobre elementos distintos de dados

Um aumento de k vezes no número de unidades funcionais levaria a um aumento de k vezes a vazão do sistema

7 + 3 10 + 200 33 + 329

Aplicações

Aplicações ou programas podem ser executados mais rapidamente, considerando duas formas de paralelismo

– tratar o programa seqüencial como uma série de tarefas

– cada tarefa = uma instrução ou blocos de instruções

OU

– especificar um programa paralelo, que resolve o problema através da especificação de tarefas ou processos concorrentes

Exploração de paralelismo

Particionamento

– identificar em um programa, as tarefas que possam ser executadas em paralelo (simultaneamente em mais de um processador)

• caso extremo: cada linha do programa correspondendo a uma tarefa

um bom desempenho só é alcançado se um número máximo de comandos são executados simultaneamente

É preciso considerar dependências de dados

problema: se quase todos os comandos são dependentes

Exemplo: programa seqüencial paralelismo de instruções

program nothing(){

input (A1,B1,C1);

if A1>B1 then {

C1=A1-B1;

output (C1);

} else {

C1 = B1-A1;

output (A1,B1,C1)

}

A=0; B=1;

for i=1 to 3 {

input(C);

A=A+C;

B=B*C;

}

output (A,B,C);

}

Exemplo

Tarefa T1

input (A1,B1,C1);

if A1>B1 then{

C1=A1-B1;

output (C1);

}else{

C1 = B1-A1;

output (A1,B1,C1)

}

Tarefa T3

B=1;

Tarefa T4

for i=1 to 3 {

input(C);

A=A+C;

B=B*C;

}

output (A,B,C)

Tarefa T2

A = 0;

Exemplo

T1

T3 T2

T4

16

1 1

4

Algoritmos PRAM

para um problema: se um algoritmo PRAM tem complexidade de tempo menor que a do algoritmo seqüencial ótimo, então o paralelismo pode ser usado

Como iniciar um algoritmo PRAM: ativar os P processadores que farão parte da computação

– os processadores serem ativados um a um

– através do algoritmo de difusão: log P passos

depois da ativação, o algoritmo paralelo pode ser executado

Identificando Paralelismo

paradigmas de computação paralela

algoritmos aqui falados consideram o modelo PRAM. Exemplos:

Árvore Binária: o fluxo de dados (e controle) se dá da raiz até as folhas

– Difusão: a partir de um processador, o fluxo (controle ou dados) passa para dois processadores e assim, dobrando a cada iteração.

– Divisão e Conquista: um problema é subdividido em subproblemas cada vez menores

ou contrário, das folhas até a raíz:

– Redução: dado n valores, a operação X é uma binária associativa

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5 6 3 10 2 4 7 11 3

Memória compartilhada

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5 6 3 10 2 4 7 11 3

1º PASSO

3 4 8 2 9 1 0 5 6 3 10 2 4 7 11 3

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5 6 3 10 2 4 7 11 3

1º PASSO

3 4 8 2 9 1 0 5 6 3 10 2 4 7 11 3

+ + + + + + + +

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5 6 3 10 2 4 7 11 3

1º PASSO

3 4 8 2 9 1 0 5 6 3 10 2 4 7 11 3

+ + + + + + + + 7 10 10 5 9 12 11 14

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5 6 3 10 2 4 7 11 3

1º PASSO

3 4 8 2 9 1 0 5 6 3 10 2 4 7 11 3

+ + + + + + + + 7 10 10 5 9 12 11 14

7 10 10 5 9 12 11 14

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5 6 3 10 2 4 7 11 3

2º PASSO

7 10 10 5 9 12 11 14

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5 6 3 10 2 4 7 11 3

2º PASSO

10 7 10 5 9 12 11 14

7 10 10 5 9 12 11 14

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5

2º PASSO

10 7 10 5 9 12 11 14

+ + + +

7 10 10 5 9 12 11 14 6 3 10 2 4 7 11 3

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5

2º PASSO

10 7 10 5 9 12 11 14

+ + + + 17 15 21 25

7 10 10 5 9 12 11 14 6 3 10 2 4 7 11 3

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5

2º PASSO

10 7 10 5 9 12 11 14

+ + + + 17 15 21 25

7 10 10 5 9 12 11 14

17 15

21 25 17 15 6 3 10 2 4 7 11 3

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5

3º PASSO

7 10 10 5 9 12 11 14 21 25 17 15 6 3 10 2 4 7 11 3

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5

3º PASSO

15 17 21 25

7 10 10 5 9 12 11 14 21 25 17 15 6 3 10 2 4 7 11 3

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5

3º PASSO

15 17 21 25

+ +

7 10 10 5 9 12 11 14 21 25 17 15 6 3 10 2 4 7 11 3

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5 6 3 10 2 4 7 11 3

3º PASSO

15 17 21 25

+ + 17 15

7 10 10 5 9 12 11 14

32 46

21 25 17 15

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5 6 3 10 2 4 7 11 3

3º PASSO

15 17 21 25

+ + 17 15

7 10 10 5 9 12 11 14

32 46

21 25 17 15 32 46

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5 6 3 10 2 4 7 11 3

4º PASSO

7 10 10 5 9 12 11 14 21 25 17 15 32 46

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5 6 3 10 2 4 7 11 3

4º PASSO

46 32

7 10 10 5 9 12 11 14 21 25 17 15 32 46

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5 6 3 10 2 4 7 11 3

4º PASSO

46 32

+

7 10 10 5 9 12 11 14 21 25 17 15 32 46

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5 6 3 10 2 4 7 11 3

4º PASSO

46 32

+ 78

7 10 10 5 9 12 11 14 21 25 17 15 32 46

3 4

P1 P2 P3 P4 P5 P6 P7 P8

8 2 9 1 0 5 6 3 10 2 4 7 11 3

4º PASSO

46 32

+ 78

7 10 10 5 9 12 11 14 21 25 17 15 32 46 78

Redução: Soma

soma de n elementos: A = < 4, 3, 8, 2, 9, 1, 0, 5, 6, 3, 10, 2, 4, 7, 11, 3>

Soma_PRAM_Pi (){

Para ( 1 h log n ) faça

se ( i n/2h ) faça

A[i] := A[2i] + A[2i -1];

}

A[i] := A[2i] + A[2i -1]; leitura: A[2i] e A[2i -1];

computa: A[2i] + A[2i -1];

escreve: A[i]

Redução: Soma

primeiro loop: não há necessidade de mais do que n/2 processadores

processadores acessam dois locais de memória simultaneamente, mas distintos

processadores escrevem em um local de memória (cada) simultaneamente, mas distintos

para somar, log n iterações são necessárias, cada uma tem tempo constante

Complexidade do Algoritmo: O ( log n) com O ( n/2 ) processadores

Um parênteses

.......

Exponenciação e Logaritmo - Motivação

• Muitos fenômenos crescem não linearmente • População • Relação entre diferentes partes de um organismo • O número de espécimes em uma dada área • etc

• Funções exponenciais e logarítmicas expressam o desenvolvimento destes fenômenos


• Crescimento populacional • Crescimento de células • Comportamento típico:

1

32 64

1 2 3 4 5 6

1 2 4

8 16

32 64

1 2 3 4 5 6


1

32 64

1

Population Size vs. time

0

10

20

30

40

50

60

70

0 1 2 3 4 5 6 7

Time (t)

Po

pu

lati

on

Siz

e (

N)

Função exponencial: f(x) = ax, a> 0

Crescimento exponencial

• Quanto menor x, f(x) mais próximo de zero

• x crescendo, f(x) aumenta muito

Decréscimo exponencial

• Quanto maior x, f(x) mais próximo de zero

• x decrescendo , f(x) aumenta muito

Exponenciação e Logaritmo

• Potenciação an envolve dois números: • a base a e o expoente n

• Para n> 1; indica a multiplicação da base a por ela n vezes

• Se n = 0 a0 = 1

• Se n < 0 a-1 = 1/a

• a-n = (a-1)n = (1/a)n = 1n/an = 1/an

Logaritmo

Logaritmo

• O gráfico do logaritmo na base 2 atravessa o eixo das abcissas em x = 1 e passa pelos pontos com coordenadas (2, 1), (4, 2) e (8, 3)

pois

1 0 20= 1

2 1 21= 2

4 2 22= 4

8 3 23= 8

• O gráfico se aproxima do eixo das ordenadas, mas não chega a tocá-lo

Logaritmo – algumas regras:

• loga(xy) = logax + logay

• loga(x/y) = logax - logay

• logaxk = k·logax

• logaa = 1

• loga1 = 0

Logaritmo e exponencial

-4

-2

0

2

4

6

8

-6 -4 -2 0 2 4 6 8

f(x) = ax

f(x) = logax

Noções de Complexidade

Existem algoritmos PRAM cuja complexidade de tempo é menor do que o algoritmo correspondente seqüencial ótimo, mas podem desempenhar mais operações do que o seqüencial

Complexidade de tempo do pior caso em função do tamanho da entrada. Cada passo corresponde:

– uma fase de computação

– uma fase de comunicação

é importante especificar

– o número máximo de processadores usados, como função da entrada

– o modelo arquitetural sendo usado

Noções de Complexidade

Paralelismo Limitado

algoritmo p-paralelo se implementado em um modelo com p processadores, fixo

T(n) e P(n): o tempo de execução e a quantidade de processadores do algoritmo paralelo

se o número de passos é T(n) considerando p processadores, então esse algoritmo é p computável neste tempo

se T(n) é polinomial e p é limitado superiormente por polinômio, então o número de processadores é limitado polinomialmente, senão, ilimitado

Algumas Definições

Custo do Algoritmo Paralelo

produto tempo-processador T(n) P(n)

– ignora ociosidade de processador

Algoritmo paralelo de custo ótimo: Ts = T(n) P(n)

– Ts o tempo de execução do melhor algoritmo seqüencial

p < P(n) processadores: cada processador executa sequencialmente o que P(n)/ p processadores executam

– T(n) P(n)/p unidades de tempo

A - algoritmo paralelo n - o tamanho da entrada


Speedup , dado o número de processadores p

Se o S(A(n),p) é linear então todos os processadores são efetivamente utilizados

– difícil de ser alcançado devido a natureza dos algoritmos e do ambiente computacional paralelo

– difícil decompor o algoritmo em tarefas completamente independentes, onde cada tarefa leva Ts /p unidades de tempo para ser executada


Trabalho de um Algoritmo Paralelo

um algoritmo é descrito como uma seqüência de unidades de tempo, onde em cada unidade um conjunto de instruções concorrentes

trabalho de um algoritmo paralelo é o número total de operações executadas, não incluindo os tempos ociosos de certos processadores

são somadas, a cada unidade de tempo, o número de operações concorrentes podem estar sendo executadas

Voltando: soma de n elementos

• 1a unidade de tempo - n/2 operações (somas em paralelo)



• j-ésima unidade de tempo - n/2j operações

Quando termina o algoritmo?

..............


n/2k = 1 k = log n iterações

Na k-ésima iteração tal que o número de elementos é igual a 1, ou seja:


Contabilizando agora o número total de operações (ou trabalho do algoritmo paralelo)




• k-ésima unidade de tempo - n/2k operações

Total de operações: O(log n) n/2j = O(n)

..............

Pergunta:

Como seria a sua versão (mais realista) da soma paralela de N números em um número limitado p de processadores?

Implementação I – soma de n números

através de threads, implementar a soma de n números

- em um número qualquer de processadores

- em um número fixo de processadores

vantagens e desvantagens?

Pointer Jumping

T = (V,E) : árvore direcionada

odg(v) e idg(v): graus de saída e entrada do vértice v V

um vértice r tal que

v V-{r}, odg(v) = 1, odg(r)=0

v V-{r}, um caminho de v a r

O vértice r é dita raíz de T

Pointer Jumping é uma técnica usada para processamento de dados

armazenados em forma de um conjunto de árvores direcionadas enraizadas

Pointer Jumping - árvore direcionada

Problema F : floresta de árvores direcionadas enraizadas

especificação: através de um vetor F de n elementos onde

– F(i) = j se (i,j) E (é um arco) j é o pai ou predecessor imediato de i

– F(i) = i se i é a raiz

Problema: determinar a raiz S(j) da árvore contendo o vértice j

Solução Seqüencial - resolve o problema em tempo linear:

identificação das raízes: achar todos os vértices v tal que F(v) = v em O(n)

reversão dos arcos: pois estamos considerando que se (i,j) E então j é pai de i em O(n)

execução de uma busca em profundidade ou largura: nesta busca, podemos saber a partir da raiz r quem são seus descendentes

Solução Paralela

Um algoritmo eficiente foi proposto, sendo um esquema totalmente diferente do esquema seqüencial

inicialmente: i V, S(i) é o pai de i

a técnica pointer jumping consiste em atualizar o sucessor de cada

vértice pelo sucessor do sucessor

– percorrendo desta maneira, corresponde a cada iteração chegar mais e mais próximo doa raiz da árvore

– a cada iteração, a distância entre o vértice i e seu sucessor S(i) dobra

– o ponto de parada: quando S(i) é a raiz procurada;

Pointer Jumping

início : S[1] = 2 S[2] = 3 S[3] = 4 S[4] = 5 S[5] = 5

1o passo: S[1] = 3 S[2] = 4 S[3] = 5 S[4] = 5 S[5] = 5

2o passo: S[1] = 4 S[2] = 5 S[3] = 5 S[4] = 5 S[5] = 5

3o passo: S[1] = 5 S[2] = 5 S[3] = 5 S[4] = 5 S[5] = 5

……..

k-ésimo passo: S[1] = raiz d(1, S[1]) = 2k (término do Algoritmo)

Pointer Jumping

1 2 3 4 5 R

Pointer Jumping

1 2 3 4 5 R

Pointer Jumping

1 2 3 4 5 R

Pointer Jumping

1 2 3 4 5 R

Pointer Jumping

PointerJumping_Pp (){

S[p] = F[p];

While (S[p] != S[S[p]]{

S[p] := S[S[p]];

}

}

ler S[p], S[S[p]] em variáveis locais pai e avô

Comparar as duas informações;

Escrever avô em S[p];

Complexidade e Corretude do Algoritmo

como podemos provar que o algoritmo está correto?

simplesmente definimos um algoritmo e o executamos?

– seja h a altura máxima de uma árvore qualquer na floresta de árvores enraizadas direcionadas

– por indução em h

Temos que analisar tal algoritmo, considerando a altura da maior árvore dentre as da floresta: domina o tempo de execução do algoritmo

– cada passo j, definição de distância entre i e S[i]

dj(i,S[j]) = 2dj-1(i,S[i])

– por indução em k: supondo verdade que dk-1(i,S[i]) = 2k-1

Complexidade e Corretude do Algoritmo

– assim, no passo k

dk(i,S[j]) = 2 dk -1(i,S[i]) = 2* 2k-1

– logo, por definição da distância máxima, tem-se h = 2k e assim, o número máximo de iterações é k = O(log h)

em cada iteração, o tempo paralelo é O(1). Temos um total de O(log h) iterações. Ainda, o número de processadores é n

o algoritmo paralelo não tem custo ótimo. Por que?

é um algoritmo CREW PRAM

Soma de Prefixos

si = x1 x2 …. xi

saída: n elementos : s1, s2, …., sn

Aplicações: concatenação de strings, soma, multiplicação, etc

Algoritmo Seqüencial

Soma_Prefixos_Sequencial( x){

s1 := x1 ;

Para i = 2, …., n

si = si-1 xi ;

}

Complexidade: O(n)

Soma de Prefixos

Definição

Seja X = { x1, x2, …., xn } e uma operação binária e

a operação é fechada sobre X ou seja, se xi e xj são elementos de X então xi xj também é

a operação é associativa

Soma de Prefixos - pointer jumping

representação dos elementos é feita através de uma árvore direcionada enraizada

– cada vértice i da árvore tem um peso associado xi

– pointer jumping é usado, armazenando as somas intermediárias a cada iteração

– como várias árvores podem ser percorridas ao mesmo tempo, várias seqüências podem ser resolvidas ao mesmo tempo

algoritmo para soma de prefixos: temos a informação de quem é pai do vértice i, ou seja, F[i]

– em seqüência de n elementos F[i] = i+ 1, i = 1,…., n-1

– a árvore seria uma lista linear


5 4 3 2 1 0


5 4 3 2 1 0

5+4 4+3 3+2 2+1


5 4 3 2 1 0

5+4 4+3 3+2 2+1


5 4 3 2 1 0

5+4 4+3 3+2 2+1

5+4+3+2 4+3+2+1 3+2+1


5 4 3 2 1 0

5+4 4+3 3+2 2+1

5+4+3+2 4+3+2+1 3+2+1


5 4 3 2 1 0

5+4 4+3 3+2 2+1

5+4+3+2 4+3+2+1 3+2+1

5+4+3+2+1


5 4 3 2 1 0

5+4 4+3 3+2 2+1

5+4+3+2 4+3+2+1 3+2+1

5+4+3+2+1


Soma_Prefixo_PJ_Pp (){

S[p] = F[p];

sp[i] = x[i];

While (S[p] != S[S[p]]{

sp[p] = sp[p] + sp[S[p]];

S[p] := S[S[p]];

}

}

Implementação II – pointer jumping

através de threads, implementar a soma de prefixos de n números através da técnica do pointer jumping

- em um número qualquer de processadores

algum cuidado especial a ser tomado?

Soma de Prefixo – outro paradigma

si = x1 x2 …. xi

saída: n elementos : s1, s2, …., sn

Paradigma: árvores binárias

A[i] = xi

B[h,j] e C[h,j] onde 1 j n/2h (1 h log n especifica o nível)

ao final: sj = C[0,j]

P1 P2 P3 P4 P5 P6 P7 P8

B[0,1]=X1 B[0,2]=X2 B[0,3]=X3 B[0,4]=X4 B[0,5]=X5 B[0,6]=X6 B[0,7]=X7 B[0,8]=X8

B[1,1]=B[0,1]+B[0,2]

X1+X2

B[1,2]=B[0,3]+B[0,4]

X3+X4

B[1,3]=B[0,5]+B[0,6]

X5+X6

B[1,4]=B[0,7]+B[0,8]

X7+X8

B[2,1]=B[1,1]+B[1,2]

X1+X2+x3+x4

B[2,2]=B[1,3]+B[1,4]

X5+X6+x7+x8

B[3,1]=B[2,1]+B[2,2]

X1+X2+...+x7+x8

C[3,1]=B[3,1]

X1+X2+...+x7+x8

C[2,1]=B[2,1]

X1+X2+x3+x4

C[2,2]=C[3,1]

X1+X2+...+x7+x8

C[1,1]=B[1,1]

X1+X2

C[1,2]=C[2,1]

X1+X2+X3+X4

C[1,3]=C[2,1]+B[1,3]

X1+X2+...+X5+X6

C[1,4]=C[2,2]

X1+X2+...+X7+X8

C[0,1]=B[0,1]

X1

C[0,2]=C[1,1]

X1+X2

C[0,3]=C[1,1]+B[0,3]

X1+X2+X3

C[0,4]=C[1,2]

X1+X2+X3+X4

C[0,5]=C[1,2]+B[0,5]

X1+X2+X3+X4+X5

C[0,6]=C[1,3]

X1+X2...X5+X6

C[0,8]=C[1,4]

X1+X2...X7+X8

C[0,7]=C[1,3]+B[0,7]

X1+X2+...+X6+X7

Soma de Prefixos Não Recursivo

Algoritmo Paralelo não Recursivo

Soma_Prefixos_Paralela_nRecursivo( A ){

1. Para 1 i n faça em // : B[0,j] := A[j];

2. Para 1 h log n faça

2.1 Para 1 j n/2h faça em //

2.1.1 B[h,j] := B[h - 1, 2j-1] * B[h - 1, 2j];

3. Para h = log n … 0 faça

3.1 Para 1 j n/2h faça em //

3.1.1 se j é par, então C[h,j] := C[h + 1,j/2];

3.1.2 se j == 1, então C[h,1] := B[h,1];

3.1.3 se j é ímpar, então C[h,j] := C[h + 1,(j-1)/2] * B[h,j];

}

Princípio de Brent tempo de execução do algoritmo // A para P(n) processadores: T(n)

w operações do algoritmo A

tempo paralelo do algoritmo considerando p processadores de acordo com o princípio de Brent:

Tp(n) = w/p + T

Aplicação do Princípio

necessário saber quantas operações são executadas a cada passo

algoritmo de soma de prefixos com n = 2k - número de passos:

2log n + 2 2k+2

– qual o número de operações?

– qual o custo?

Princípio de Brent

w1,1 : número de operações no passo 1 considerando o único loop

w2,m : número de operações executadas no passo 2 na m-ésima iteração

w3,m : número de operações executadas no passo 3 na m-ésima iteração

Então:

w1,1 = n

w2,m = n/2m = 2k /2m para 1 m k

w3,m = 2m para 0 m k

Assim:

w = w1,1 + w2,m + w3,m

w = n + n/2m + 2m

w = n + n(1-1/n) + 2n-1 = 4n-2

w = O(n)

Divisão e Conquista

usada quando identificamos problemas que podem ser particionados em subproblemas menores, que são mais simples de serem resolvidos

– divisão da entrada em partições menores de mesmo tamanho (ou quase)

– resolução recursiva de cada subproblema definido por cada partição

– combinação das soluções de cada subproblema, produzindo a solução do

problema como um todo

tende a ser eficiente se a decisão e resolução podem ser feitas recursivamente

eficiente no mundo seqüencial

natural na exploração de paralelismo


Problema da Envoltória Convexa

Seja S = { p1 , p2

, …. , pn } um conjunto de n pontos em um plano, cada um

representado por suas coordenadas (xi, yi). A envoltória convexa planar de S é o menor polígono convexo que contém todos os pontos de S

observação: um polígono é convexo quando, para qualquer dois pontos, (xi, yi) (xj, yj), a reta [(xi, yi),(xj, yj)] está dentro do polígono.

o problema: determinar a lista ordenada de pontos S que formam o polígono convexo. Essa lista será denotada por CH(S) (convex hull).


Problema da Envoltória Convexa

é um problema muito importante em geometria planar:

– estatística

– processamento de imagem

– reconhecimento de padrões

– computação gráfica

– problemas geométricos

resolvido sequencialmente através de divisão e conquista O(n log n)

– o algoritmo de ordenação de pontos resolve esse problema mais eficientemente

Divisão e Conquista Paralelo

Dado um conjunto S de n pontos, sejam:

p S o ponto com o menor xi

q S o ponto com o maior xj

ordenação paralela: em O(log n) em uma PRAM EREW com O(n log n ) operações

particionam CH(S) em:

envoltório superior UH(S) = < todos os pontos de p a q pertencentes a CH(S) seguindo o sentido horário >

envoltório inferior LH(S) = < todos os pontos de q a p pertencentes a CH(S) seguindo o sentido horário >

O Problema da Envoltória Convexa

p q

CH(S)

S

envoltória inferior

LH(S)

envoltória superior

UH(S)

Divisão e Conquista Paralelo

p q

p q

Merging de duas envoltórias superiores

Merging de duas envoltórias superiores

p q

Tangente Comum Superior

• sequencial – O(log n) • busca binária

Algoritmo

Entrada: n pontos ordenados tais que x(p1) < x(p2) < .... <

x(pn)

Saída: UH(S)

1) Se n <= 4 então ache UH(S) por força bruta e retorne

2) S1 = (p1, ..., pn/2) e S2 = (pn/2+1, pn). Compute UH(S1)

e UH(S2) em paralelo, recursivamente

3) Ache a tangente comum superior entre UH(S1) e UH(S2) e

defina UH(S)

1) O(1)

2) T(n/2)

3) TCS(UH(S1), UH(S2)) em O (log n)

Combinar as duas curvas dada a tangente produzindo S

– em O(1) com n processadores leituras concorrentes

serão realizadas.

Documents

Definindo melhor alguns conceitosboeres/slides_AP/AlgParalelosII.pdfDefinindo melhor alguns conceitos Processamento Paralelo: processamento de informação concorrente que pertencem