Resolvido: Algoritmos - Teoria e Prática - 3ª Ed. 2012 | Cap 27 Ex 1PA
51
Algoritmos - Teoria e Prática - 3ª Ed. 2012

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 5keyboard_arrow_downkeyboard_arrow_up

Nesse exercício será implementando laços paralelos de SUM-ARRAY usando paralelismo aninhado, utilizando spawn e sync, lembrando que:

spawn é uma sub-routina que executa ao mesmo tempo que seu pai, essa execução ao mesmo tempo é responsável pelo paralelismo, que aumenta a performance do computador.

Passo 2 de 5keyboard_arrow_downkeyboard_arrow_up

Para o algoritmo, considere 3 vetores de tamanho n, suponha que:

, e

Considerando que o vetor C que armazena a soma dos vetores A e B.

Passo 3 de 5keyboard_arrow_downkeyboard_arrow_up

Agora, utilizando as variaveis de auxilio i e j. Podemos escrever a função NESTED-SUM-ARRAY, que irá utilizar o conceito de paralelismo aninhado:

NESTED-SUM-ARRAY(A,B,C,I,j)

If(i == j)

Else

spawn NESTED-SUM-ARRAY (A,B,C,i,p)

NESTED-SUM-ARRAY(A,B,C,p+1,j)

Sync

Passo 4 de 5keyboard_arrow_downkeyboard_arrow_up

Analisando, temos que o código passa por todo o vetor (todos os n nós de uma árvore de altura ). O seja, temos trabalho , duração , já que cada nó executa os dois filhos paralelamente. Isso nos leva a um paralelismo , tal que:

Passo 5 de 5keyboard_arrow_downkeyboard_arrow_up

Concluímos, então, que, utilizando o método de divisão e conquista para a paralelização, temos um algoritmo de trabalho , duração e paralelismo .

Navegar por capítulo

Aprenda agora com os exercícios mais difíceis

R$29,90/mês

Assine o PremiumCancele quando quiser, sem multa

Aproveite também

  • check Todos os materiais compartilhados
  • check Biblioteca com 5.000 livros, escolha 5 por mês
  • check Videoaulas exclusivas
  • check Resumos por tópicos