Lei de Amdahl e limites do paralelismo
Dobrar os processadores dobra a velocidade? Não — a Lei de Amdahl (1967) mostra que a parte serial do programa limita o speedup máximo, independentemente de quantos processadores você adicionar. Com 10% de código serial, nunca passa de 10× — mesmo com infinitas CPUs.
O gargalo serial determina tudo
Imagine construir uma casa. Algumas tarefas são paralelas (várias equipes constroem paredes ao mesmo tempo). Mas algumas são seriais: você não pode instalar o telhado antes das paredes. Essas tarefas seriais determinam o tempo mínimo, independentemente de quantas equipes você contratar.
A Lei de Amdahl formaliza isso: se p% do programa pode rodar em paralelo e (1−p)% é necessariamente serial, o speedup máximo com N processadores é 1 / (1 − p + p/N), e com infinitos processadores o limite é 1/(1−p).
Speedup vs processadores — arraste os sliders
Ajuste a fração paralelizável (p) e o número de processadores (N). Observe o limite assintótico e como adicionar CPUs tem retorno decrescente.
A fórmula de Amdahl em código
# Lei de Amdahl (1967) # Speedup(N, p) = 1 / ((1 - p) + p/N) # p = fração paralelizável (0 a 1) # N = número de processadores # Speedup máximo (N→∞) = 1 / (1 - p) def amdahl(p, n): return 1 / ((1 - p) + p / n) # Exemplos reveladores: amdahl(0.9, 10) # 5.26× (não 10×!) — 10% serial limita amdahl(0.9, 100) # 9.17× — 100 CPUs quase não ajudam além de 10 amdahl(0.9, 1000) # 9.91× — limite máximo é 10× (= 1/0.1) amdahl(0.99, 100) # 50.25× — 1% serial: 100 CPUs rendem bem amdahl(0.50, 4) # 1.60× — metade serial: 4 CPUs = 60% ganho # Conclusão: otimizar a parte SERIAL é crítico # Reduzir parte serial de 10%→5%: máximo de 10× para 20× # Vale muito mais que dobrar os processadores
Lei de Gustafson: escalando o problema, não o tempo
# Lei de Gustafson-Barsis (1988) — perspectiva complementar # Amdahl fixa o PROBLEMA (mesmo tamanho com mais CPUs) # Gustafson fixa o TEMPO (com mais CPUs, resolve problemas MAIORES) # Speedup = N - (1 - p) * (N - 1) # = p*N + (1-p) ← escala quase linearmente def gustafson(p, n): return n - (1 - p) * (n - 1) gustafson(0.9, 100) # 90.1× — muito mais otimista que Amdahl # Por que Gustafson é relevante? # Com mais CPUs você NÃO resolve o mesmo problema mais rápido — # você resolve problemas MAIORES no mesmo tempo. # Simulações climáticas, rendering 3D, ML: sempre há mais dado para processar. # A fração serial tende a ser constante enquanto o trabalho paralelo cresce. # Na prática: combine Amdahl (gargalos) + Gustafson (scaling) # Use profiler para achar os gargalos seriais — eles determinam tudo.
Medindo speedup na prática
Mini projeto: implemente a soma de 100 milhões de números em Python com multiprocessing.Pool usando 1, 2, 4 e 8 processos. Meça o tempo de cada configuração. Calcule o speedup real e compare com o previsto pela Lei de Amdahl (estime p medindo quanto tempo é paralelizável).
Projeto principal: use numpy com e sem paralelismo explícito para calcular uma multiplicação de matrizes 2000×2000. Compare: NumPy single-thread, NumPy com OpenBLAS multi-thread, e uma implementação Python pura com multiprocessing. Por que NumPy com BLAS quase sempre ganha? O que isso diz sobre Amdahl na prática?
Desafio extra: use CUDA (via cupy) ou OpenCL para executar uma operação vetorial em GPU. Meça o speedup vs CPU para arrays de tamanho 1K, 1M e 100M. Observe que para arrays pequenos a GPU é mais lenta (overhead de transferência de memória). Isso é Amdahl: a parte serial (transferência CPU↔GPU) limita o speedup para dados pequenos.
Teste sua intuição
Onde você encontra isso
Deep Learning — Amdahl nas GPUs
Treinar redes neurais em múltiplas GPUs esbarrou em Amdahl: a parte serial são os gradientes que precisam ser sincronizados entre GPUs (AllReduce). Com 8 GPUs, comunicação de gradientes pode consumir 30-50% do tempo. Por isso surgiram técnicas como gradient accumulation, model parallelism e pipeline parallelism. O sistema Megatron-LM do NVIDIA divide o modelo para minimizar comunicação serial.
Simulações científicas — HPC clusters
Simulações de dinâmica molecular (GROMACS, LAMMPS) e clima (WRF) rodam em clusters de milhares de CPUs. A parte serial inclui I/O de checkpoint, steps de inicialização e sincronização de bordas entre partições do espaço. Engenheiros de HPC passam dias analisando perfis de execução para reduzir esses gargalos e atingir eficiências acima de 85% em 1000+ núcleos.
MapReduce e Spark — paralelismo de dados
O paradigma MapReduce (Google, 2004) foi projetado com Amdahl em mente: a fase Map é perfeitamente paralela (p≈1); a fase Reduce agrega resultados (parte serial). Spark melhora reduzindo I/O entre fases. O "shuffling" de dados entre nós é o gargalo serial principal em jobs Spark — equipes de data engineering passam tempo otimizando particionamento justamente para minimizar essa parte serial.