Esse gráfico mostra algo muito importante quando se trata de algortimos paralelos: existe um limite no ganho de desempenho que é obtido com algoritmos paralelos, ou seja, o aumento do número de processadores utilizados de maneira indiscriminada pode significar uma piora do speedup (termo utilizado para medir o desempenho de algoritmos paralelos, se comparado com a melhor versão sequencial ou com o próprio algoritmo paralelo rodando em apenas um processador).
Note que não estou citando o termo thread, já que algoritmos paralelos podem rodar em ambientes heterogêneos, ou seja, em computadores diferentes, inclusive em locais diferentes (ver computação em grid).
Fica claro nesse gráfico que com 8 processadores obtem-se o maior speedup. A partir daí, o speedup cai com o aumento do número de processadores. Esse tipo de comportamento é natural em algoritmos paralelos.
Note que quando um problema é paralelizado, existe a necessidade de comunicação entre os processos (ou pelo menos com o nó central) para a resolução do problema. Essa comunicação pode ocorrer apenas no final, para consolidar o resultado produzido por cada processo ou pode ocorrer a todo tempo durante a computação. Assim, quanto mais processadores, mais tempo se gastará para comunicar e essa é uma das razões para que o speedup caia com o aumento dos processadores.
Uma outra razão importante é a granularidade. Pode-se dividir o problema em muitas partes pequenas o que, dependendo do problema pode torná-lo ineficiente. Além disso, podem existir muitas partes de código sequencial e isso pode também prejudicar o speedup (Lei de Amdahl).
Pequena analogia
Nesse sentido, uma analogia interessante é feita quando se trata de gerenciamento de projetos. Dobrar o número de pessoas em um projeto não significa que ele será entregue na metade do tempo. Pelo contrário, pode significar um atraso, pois é preciso coordenar todas essas pessoas juntas para a entrega do projeto. Da mesma forma, se existe uma pessoa no projeto que acumula muitas funções, então haverá atraso, mesmo que existam outras pessoas para fazer (analogia de algoritmos paralelos que possuam muito código sequencial).
Voltando ao assunto...
Isso, obviamente, varia de problema para problema. Problemas do tipo IO-bound (onde gasta-se mais IO do que CPU) se comportam de uma maneira. Já problemas do tipo CPU-bound (onde gasta-se muita CPU e pouco IO), se comportam de outra. É preciso entender o seu problema para saber o limite no número de processadores.
No cenário da pergunta, temos:
A - incorreta. Já que o aumento do número de threads representou (a partir de 8, exclusive) uma queda do desempenho (speedup). Ou seja, haviam threads suficientes para resolver o problema.
C - Creio estar incorreta, mas ainda estou analisando. Argumento inicial: A máquina foi aproveitada em todo seu potencial quando 16 ou mais threads foram utilizadas. Não confunda com o aproveitamente do algoritmo.
D - incorreta. Obviamente utilizando 4 threads gasta-se menos recurso (nesse caso cores) do que 16.
Assim, fica-se com a resposta B.
A resposta B diz que implementações com 4 threads ou menos tiveram um ganho acima de 90% do máximo teoricamente possível.
Estou entendendo ganho como eficiência. A eficiência é calculada pela seguinte formula: eficiencia = speedup/p
. Onde p
é o número processadores.
Assim, no caso ideal onde (speedup = p), tem-se uma eficiência de 100% (a eficiência teórica).
É possível verificar pelo gráfico que até 4 threads a eficiência ficou acima de 90%. Exemplo do cáclulo para 4 threads: 3,8/4=95%
. 3,8
é o speedup, encontrado no eixo Y do gráfico. 4 é o número de threads, encontrado no eixo X.
Nota: 3,8
é uma aproximação, já que a escala do gráfico está de 1 em 1.