Considerando os conhecimentos práticos e teóricos relacionad...

A alternativa correta para a questão apresentada é a Alternativa A. Vamos entender por que essa é a escolha certa, assim como analisar as demais opções.

Alternativa A: Um algoritmo paralelo é considerado ótimo se o seu custo estiver na mesma classe de complexidade do algoritmo sequencial ótimo. Isso significa que, mesmo após a paralelização, o desempenho do algoritmo não deve se deteriorar em termos de complexidade em relação ao melhor algoritmo sequencial disponível. Portanto, esta afirmação está correta, pois reflete a expectativa de que a paralelização não deve aumentar a complexidade algorítmica além do necessário.

Alternativa B: Aqui, o conceito de speedup está correto, sendo a razão entre o tempo de execução do algoritmo sequencial pelo tempo do algoritmo paralelo usando P processadores. No entanto, a fórmula apresentada para a eficiência está incorreta. A eficiência é calculada pela razão entre o speedup e o número de processadores, não o contrário. A formulação na questão inverte essa definição.

Alternativa C: Esta opção comete um equívoco ao classificar GPU (Graphics Processing Unit) como MISD (Multiple Instruction Single Data). Na verdade, GPUs são normalmente classificadas como SIMD (Single Instruction Multiple Data), pois executam a mesma instrução em múltiplas unidades de dado simultaneamente. Portanto, essa afirmativa está incorreta.

Alternativa D: A Lei de Amdahl afirma que a presença de partes do código que não podem ser paralelizadas (código sequencial) vai restringir significativamente o speedup do algoritmo paralelo. Na verdade, pequenas frações de código sequencial podem limitar bastante o speedup, o que é o oposto do que a alternativa sugere. Por isso, essa afirmação também está incorreta.

Entender essas nuances é essencial para resolver questões de computação paralela, especialmente no contexto de concursos públicos. As alternativas abordam conceitos fundamentais como complexidade de algoritmos, speedup, eficiência e a Taxonomia de Flynn, todos críticos para avaliar o desempenho de algoritmos em ambientes paralelos.

Gostou do comentário? Deixe sua avaliação aqui embaixo!

GABARITO A

a)  Um algoritmo paralelo é ótimo se o seu custo estiver na mesma classe de complexidade do algoritmo sequencial ótimo.

CORRETO. Busca-se em algoritmos paralelos à equivalência entre o grau de complexidade do paralelo e o sequencial correspondente, pois essa equivalência gera tempo de execuções igualmente equivalentes à medida que o tamanho dos dados aumenta.

b)  O speedup de um algoritmo paralelo é dado pela razão entre o tempo do algoritmo sequencial correspondente, utilizando apenas um processador, pelo tempo do algoritmo paralelo, utilizando P processadores. A eficiência é calculada pela razão entre o número de processadores e o speedup.

ERRADO. Speedup é a medida do quanto um algoritmo paralelo é mais rápido do que o algoritmo sequencial equivalente, sendo definido pela divisão do tempo de execução do algoritmo sequencial pelo tempo de execução do algoritmo paralelo. Ex. considerando 4 processadores: 

Algoritmo(seq) = 1s 

Algoritmo(par) = 0.5 s 

SpeedUp = 1 / 0,5 = 2 vezes

A eficiência será calculada pela razão do speedup e o número de processadores. Ex.: 

Eficiência = (speedup / número de processadores) * 100%

Eficiência = (2 / 4 * 100%) = 50%

c)  Considerando a Taxonomia de Flynn para arquiteturas (SISD- Single Instruction Single Data; SIMD - Single Instruction Multiple Data; MISD - Multiple Instruction Single Data; e MIMD Multiple Instruction Multiple Data), pode-se afirmar que as Graphics processing units (GPUs) podem ser consideradas MISD.

ERRADO. A Taxonomia de Flynn é um sistema de categorização de arquiteturas de computadores, a qual realiza a categorização conforme o modo de processamento dos dados e instruções. Na taxonomia de Flynn, a arquitetura MISD (Multiple Instruction Single Data) estabelece sistemas que processam várias instruções em um único conjunto de dados, enquanto as GPUs pertencem à categoria SIMD. Logo, as GPUs são arquiteturas SIMD (Single Instruction Multiple Data) que realizam o processamento de instruções em vários conjuntos de dados simultaneamente.

d)  A Lei de Amdhal estabelece que pequenas frações de código sequencial em um algoritmo paralelo limitam pouco seu speedup.

ERRADO. A Lei de Amdhal determina o limite de speedup que pode ser atingido em algoritmos paralelos quando existe uma parte do código que não pode ser dividida para execução simultânea em vários processadores. Dessa maneira, estabelece o quanto um algoritmo paralelo é mais rápido do que o algoritmo sequencial equivalente, considerando que a parte sequencial é o "gargalo" limitante do aumento de velocidade obtido através da paralelização, ou seja, o código sequencial limita muito o speedup.