30

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

Thomas CormenIBSN: 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

O passo a passo dos exercícios mais difíceis

12xR$ 29,90 /mêsCancele quando quiser, sem multa

E mais

  • check Videoaulas objetivas
  • check Resumos por tópicos
  • check Salve para ver depois
  • check Disciplinas ilimitadas
  • check Filtros exclusivos de busca