AEDs III 11/04/2011

CONCEITO:
Overhead é o aumento de trabalho gasto na manutenção do funcionamento do paralelismo.

CONCEITOS:
Particionamento de dados é dividir os dados para processamentos separados até que possam ser únidos no resultado final.
Particionamento da execução é a criação de processos separados onde cada um realiza uma fração das tarefas sobre um conjunto de dados.
Particionamento hibrido é a adaptação dos dois metodos acima em conjunto.

CONCEITO:
The Owner Computes Rule -> O dono é quem computa, ou quem processa.

É garantir que os dados que foram tratados em um processador continuem naquele processador para os processamentos futuros.
Dessa forma voce evita tranferencias longas e desnecessárias tranferências de dados entre caches de processadores diferentes.
// Parece que o gerenciamento disso é manter uma thread mãe por processador que funciona do inicio ao fim do processamento, e garante que todos os dados que ela receber só serão delegados a outro processador uma vez que não houve mais atividades à serem feitas.

CONCEITO:
O que é decomposição exploratória?

É o mapeamento e balanceamento da divisão de tarefas de maneira dinâmica e adequada entre os processadores.
Este problema é NP completo, e se voce for faze isto de maneira dinâmica voce deve procurar uma heurística.
// Um exemplo dessa atividade é dividir as tarefas de calcular os vários possíveis próximos passos
// em um jogo de chadrês de maneira balanceada e sem abusar da capacidade de processamento.

CONCEITO:
Decomposição especulativa:
É o ato de gerar processos que processam dados que tem boa probabilidade de serem usados.
E fazer isto antes da real requisição destes, podendo acontecer de voce se preciptar e precisar descartar um processamento inteiro.
A vantagem disso é aproveitar os processadores que iriam estar ociosos, ocupando o tempo deles com uma especulação,
A desvantagem é que corre-se o risco desse trabalho ser perdido.
Um detalhe importante desse sistema é a necessidade de um mecanismo de "roll back" que é um meio para voltar a trás com
todo o programa, e manter a coerência.

// Exemplo disso: Simulação discreta de eventos
// Em uma simulação de trânsito é praticamente necessário a especulação de onde e quando cada carro deve surgir e etc,
// Usa-se uma lista de eventos para organizar o que está a acontecer e o que está em pendencia de ser processado
// Ex. de Roll Back no caso acima:
// Nesse caso se eu suponho que o carro do rubens chegava ao Hospital Belo Horizonte mas outro evento
// é lançado dizendo que rubens bateu antes de chegar lá é preciso fazer um roll back =/.
// É meio o que o Grand Chase faz ele permite que cada usuário faça sua jogada, e se houver uma incoêrencia
// ele arrasta o jogador que havia "sofrido o acidente" para a posição correta.

CONCEITO:
Marsheling é o ato de pausar o funcionamento de um processo que está funcionando muito rápido para evitar sobrecarga
de overhead e sincroniza-lo com os demais processos evitando especulações por demais precipitadas.
// Imagino que esse processo de marsheling deve ter razões bem genericas para ser utilizado, ele se parece com uma ferramenta
// de sincronização de processamentos, e portanto deve ter varias e varias aplicações, não necessáriamente apenas as que eu citei.

Nota do Professor:
Na distribuição de tarefas e de dados, deve-se tomar o cuidado para manter um tamanho adequado de processamento para cada processador.
-Se processos acabam muito rapido processando muito pouco o overhead explode, // rede
-Se voce copia um volume de dados muito grande para cada execução durar um tempo razoavel, voce pode estourar é a memória. // disco
-E se o número de processos superar em muito o de processadores mesmo com os dados balanceados,
 você estará ganhando overhead sem ganhar mais processamento. // processamento
// Repare que o professor acabou citando os 3 casos para os quais ele nos chamou a atenção na ultima aula.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

CONCEITO:
Como destribuir as tarefas que voce cria?
há dois meios:

Geração estática: Seguro você sabe bem o que voce ta fazendo e o negocio não explode.
// Exemplo: voce tem 4 processadores e um vetor a ser processado
//          voce divide o vetor em 4 e a distribuição está feita. Isso é estático.

Geração dinamica: É perigoso, deve saber onde limitar isso senão voce explode a memória e não aproveita o processamento.
// Exemplo: voce tem 4 processadores e tem que prever jogadas em um jogo de chadrês.
//          o numero de possíveis jogadas é infinito, então voce tem que saber bem onde parar de especular
//          para não sobrecarregar sua máquina fisica. Tanto em questão de memória quanto em processamento.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

CONCEITO:
O que é interação de tarefas?
É um nome que reúni "mapeamento" e a "comunicação" em uma só palavra.
Podemos dividir os meios de se realizar essa tarefa em dois grupos:

Interação estática: fácil.
// Onde voce gera tarefas de maneira estatica e apenas as comunicações realmente necessárias, sendo fácil e seguro de se fazer.

Interação dinamica: difícil.
// Onde voce gera um diálogo entre os processos para decidir quem deve fazer o quê, isso aumenta a carga de comunicação
// mas pode vir a melhorar em muito a eficiência.

  Nesse caso diz-se que o ótimo é inimigo do bom.
  Uma ótima interação pode gastar mais processamento que o próprio programa,
  assim frequentemente uma heurística de balanceamento de interação é mais produtiva.

// Sendo este um problema NP finito, assuma então que se os processadores estiverem sempre ocupados, e sem muito overhead
// essa solução já está boa de mais, não perca muito tempo atrás do ótimo.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Relembrando
CONCEITO:
O que é mapeamento?
Mapeamento é balancear as tarefas para que os processadores sejam bem aproveitados.
Ou seja, cuidar das dependencias de dados para que ninguém fique esperando ninguém etc.

CONCEITO:
Distribuição cíclica é distribuir as tarefas de maneira ciclica entre os processadores, uma maneira de denotar isso é dizer que
a tarefa x será responsabilidade do processador x%n sendo n o número de processadores.
Assim consegue-se um certo balanceamento de número de tarefas entre os processos,
com o risco de algumas ficarem travadas devido a dependencias, por isso seu uso deve ser feito com cuidado.

Nota do Professor: Não vamos ser cobrados de fazer nada ótimo mas temos de entender o que se passa nessa área.
                   Principalmente nas provas.

CONCEITO:
Mapeamento Hierarquico é quando voce tem uma zona de processadores tipo um cluster ou processamento em rede
e é preciso bolar um mapeamento para os dados entre quadcores e coisas do tipo.
// É como se fosse um mapeamento em cima do outro, pois em pequena escala dentro de um quadcore pode haver mais comunicação,
// agora entre os diferentes clusters ainda que pouca comunição pode ser bem mais cara e deve ser balanceada de acordo.

CONCEITOS:
-Mapeamento dinâmico centralizado é quando você tem um "Mestre do jogo" que dita quem faz o que.

-Mapeamento dinamico distribuido é quando os processos decidem sozinhos ("entropia") o que fazer, sem haver realmente um lider.
// É o CAOS nas palavras do professor.

// Comentario do Professor: na prova agente vai ter que ver paralelismo e dizer pro professor onde tem oportunidades pra
//                          isso o que seria bom de se fazer e etc, então não esquente tanto a cabeça com detalhes.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Listagem de Estratégias:
Maximizar a localidade de dados. // disco
Minimizar o volume de troca de dados. // banda
Minimizar a frequência de troca de dados // latencia (banda e latencia fazem parte da rede)
Minimizar os gargalos, distribuir as tarefas e e evitar os "hot-spots"
que são os pacotes de dados que exigem mais processamento que o normal.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

O negócio de AEDs 3 é o Compromisso e pensar sempre como balancear esse tanto de coisas que se tem por ai.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Modelos de algoritimos paralelos:

Master-slave model

Pipleline/produtor-consumidor

e modelos hybridos.

UAHH ELE FALA MTA COISA E MTO RAPIDO. uahhhhh uahhh xP