AEDs III 13/04/2011

Hoje falaremos sobre Modelagem analítica de sistemas paralelos.

Nota do Professor:
Ao considerar o desenvolvimento de um algoritimo paralelo pense sempre no algoritimo quanto na arquitetura sobre a qual ele vai rodar,
diferente da programação sequencial no paralelismo um bom conhecimento da arquitetura é bastante importante.

// Existem maquinas quadprocessadas que na verdade não são porque o barramento é de um dual core.

// o E7 finge que são 8 cores pro sistema operacional, ai o SO prepara 8 threads pra ele.

// Pergunta ingenua, se eu usar 2 processadores meu programa não deveria rodar duas vezes mais rapido? não, tem sempre trabalho a mais

CONCEITO:
Modelagem analítica é tentar otimizar um algoritimo pensando na arquitetura.
Na variação do número de processadores,
Na variação do tamanho de memória e etc.

CONCEITOS:
Fontes geradoras de Overhead:

Comunicação,

Distribuição mal feita de processamento, gerando ociosidade em alguns processadores.

Computação excessiva que não é feita pela computação serial.
// (normalmente relacionado ao gerenciamento dos processos que não existem em computação serial)

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

Sendo
Ts o tempo de execução serial
Tp o tempo em paralelo
e Tall a soma do tempo de uso de cada processador
Temos:

Tall - Ts = Overhead total.
// Em um caso ideal isso seria 0, significando que a tarefa foi perfeitamente dividida entre os processadores,
// sem nenhum ganho de trabalho. Na prática no entanto isso nunca acontece.

CONCEITO:
Speedup é a razão do tempo gasto na resolução de um problema em serial sobre sua resolução em paralelo com n computadores.
Ou seja é mais ou menos isso: Ts/Tp(n), sendo Tp uma função de n.
Um speed up alto, é um bom incentivo ao uso de paralelismo.

// Repare que se voce divide por 2 processadores Tp fica igual à 1/2 de Ts + Overhead
// gerando um speed up um pouco menor que 2, e assim por diante a medida que se incrementa n.

CONCEITO:
Superlinear speedup é quando o incremento de velocidade ao se usar 4 processadores é maior que 4 mesmo considerando o overhead.
Isso ocorre quando fatores adversos como o tamanho da memória mudam juntamente com o número de processadores.
Pode vir a ser ocaso de com 1 processador a memoria x explode, com 4 a memoria 4x não explode.
// Tome cuidado portanto ao usar o valor de speed up como argumento para paralelismo,
// ele é uma medida que é refém da arquitetura, e portanto pode passar uma falsa impressão por culpa dela.

Nota: Como usar o superlinear speedup? Pode-se por exemplo rodar dois programas sobre a mesma base de dados e isso faz com que
o carregamento de dados de mais acertos que erros, evitando consultas na memoria, e dando um speedup só por usar dois programas
seriais sobre a mesma base de dados em um sistema multicore.

// Nota pessoal: se eu ler isso aqui de novo, eu preciso detalhar melhor esse conceito, e essa nota aí encima.
//               mas por hoje ta quase no horario da prova, então não vou refazer isso não xP.

CONCEITO:
Eficiencia E é o quão aproveitado foi o gasto do uso de seus processadores.
Digamos que voce gastou muitos processadores mas incrementou pouco a velocidade de processamento.
Em termos gerais a velocidade foi incrementada, mas voce gastou muitos mais processadores.

A eficiência então é o calculo do ganho de tempo dividido pelo número de processadores usados.
É uma boa medida então quando é preciso racionar o uso dos processados, em um computador que pode ter vários outros programas,
precisando de usa-los.

A eficiencia então é E = (speed up)/n
Quanto mais próximo esse tempo for de Ts melhor.

// se n--> infinito E --> 0, porque voce está desperdiçando o tempo de muitos processadores.
// e normalmente o speed up não vai crescer proporcionalmente a esse número.
// portanto existe um valor ótimo de número de processadores onde E atinge seu maior valor e pode ser útil descobrir
// esse valor.

CONCEITO:
Isoeficiencia é o aumento de speed up necessário para compensar a perda de eficiência pelo aumento de processadores.
// Isso gera em um gráfico de speedup/n linhas igualzinhas àquelas linhas isotermicas que apareciam em fisica a muito tempo atrás.
// Se voce não se lembra tente desenhar isso, já te adianto que o formato dessa linha é uma hiperbole que em 0 quase toca
// o eixo do speedup e em infinito quase toca o eixo n.