Please enable JavaScript.
Coggle requires JavaScript to display documents.
Desempenho de Programas Paralelos - Coggle Diagram
Desempenho de Programas Paralelos
Speedup S(N) = T(1) / T(N)
S(N) > 1 : solução paralela pior :red_cross:
1 < S(N) <= N : Normal
N < S(N) : speedup superlinear pouco frequente
Eficiência E(N) = S(N) / N
0 < E(N) <= 1 : Normal
1 < E(N) : speedup superlinear
Speedup
:check: Absoluto: Razão entre o tempo do melhor serial sobre o tempo de um algoritmo paralelo com N processadores
:check: Relativo: Razão entre o algoritmo paralelo em 1 processador sobre o algoritmo paralelo em N processadores
Speedup Superlinear
Efeito cache
Backtracking em paralelo
Lei de Amdahl
O speedup de um programa usando vários processadores em paralelo é limitado pelo tempo necessário pela fração sequencial do programa.
:warning: Speedup = 1 / (s + p / N)
Por exemplo, se o programa precisa de 20 horas usando um único núcleo de processamento, e a parte específica de um programa que demora uma hora para executar não pode ser paralelizado, enquanto as 19 horas restantes (95%) do tempo da execução pode ser paralelizado, independente de quantos processadores são dedicados a execução paralela deste programa, o tempo de execução mínima não pode ser menor que aquela crítica uma hora. Por isso o aumento de velocidade é limitado em no máximo 20x
Lei de Gustafson
A lei de Gustafson diz que, com uma quantidade de dados crescente, o speedup ob8do através de paralelização aumenta, porque o trabalho paralelo aumenta (escala) com a quan8dade de dados.
O tamanho do problema pode aumentar à medida que o
número de processadores aumenta
:warning: Speedup = s + Np
OBS
A lei de Amdahl assume um modelo de tamanho fixo ao passo que a lei de Gustafson assume um modelo com tamanho escalável.
s
representa a fração paralela, enquanto
p
representa a fração paralela e
N
representa a quantidade de processadores
Escalabilidade
Capacidade de crescimento (aumento do
número de processadores)
Mede o quanto um problema ou sistema pode crescer sem prejuízo significativo de desempenho
Tipos
Fraca
(Escalabilidade de Gustafson): quando speedup pode ser alcançado apenas aumentando o tamanho do problema proporcionalmente ao aumento da quan8dade de processadores
Forte
(Escalabilidade de Amdahl): quando speedup pode ser alcançado sem aumentar o tamanho do problema, apenas aumentando a quan8dade de processadores