AEDs III 06/04/2011

A aula de hoje também será sobre programação paralela.

// Falaremos de projeto de algoritomos paralelos, um pouco nessa aula e um pouco talvez na seguinte.

Ao pensar no paralelismo de um programa deve-se pensar em "Tarefas" de modo que possam ser distribuidas entre as partições do programa.
// Há sempre no paralelismo a ideia de que voce acaba com uma carga maior de tarefas do existiria em processamento sequencial
// A questão então é se compensa mesmo usar o paralelismo,
// Normalmente se o tempo de execução for mais rapido, já é positivo,
// tem outros detalhes a se considerar mas não falaremos deles aqui.

Quanto às tarefas, existem dois tipos:
Os programas com tarefas regulares.
// Nesse caso as tarefas são visíveis voce consegue entender o que é preciso fazer e quantas vezes de cada coisa.
Os programas com tarefas irregulares.
// Nesse caso as tarefas ficam desbalanceadas novas tarefas podem surgir durante o processamento, e é necessária um gasto maior
// de processamento com a gestão e distribuição delas.

Nota do Professor:
Ao pensar no lucro de se fazer paralelismo não pense no numero máximo de processadores que voce podera usar,
mas sim quantos processadores voce usará a maior parte do tempo. Assim voce consegue uma idéia mais real do que se passa.

CONCEITO:
Caminho Crítico é o maior caminho que será realizado necessariamente de forma linear.
Esse caminho é o garga-lo de tempo. Por mais que voce distribua as demais tarefas, se voce não conseguir reduzir esse garga-lo.
o tempo final do seu programa será igual ao tempo do caminho crítico.
// Note que uma vez que voce elimine um caminho crítico outro aparece pra tomar o lugar dele, a idéia é tornar o programa
// mais balanceado, sem nenhum caminho muito mais longo que outro.

CONCEITO:
Mapeamento é a distribuição de processos por entre os processadores

Deve-se fazer o mapeamento de modo que nenhum processo fique sobrecarregado ou ele será o caminho critico,
E tambem devem haver poucas trocas de informações entre os processos pois elas são lentas e acabam prejudicando o programa.
Lembre-se no entando que mapeamento é um problema NP completo e portanto não tem solução ótima que dê pra se fazer.

Macetes: - os processos do caminho crítico devem ser associados a processadores tão rapido quanto possivel.
         - divida um processo pra cada processador se possivel.

CONCEITO:
O que é Decomposição Recursiva?
Decomposição Recursiva de tarefas é o programa que ao trabalhar na solução de um problema
gera a cada recursão uma nova arvore de tarefas, e para cada uma inicia um novo processo.
É uma atividade que se aplica muito bem a técnicas de divisão e conquista.

Nota do Professor:
Desperdiçar espaço para diminuir a comunicação entre processadores pode valer a pena,
quando o custo do espaço e da cópia dos dados for menor que o custo da comunicação.
É uma troca que deve ser bem pensada as vezes.