# Lei de Amdahl e limites do paralelismo

A fração serial, o cálculo do speedup máximo e a leitura crítica do teto.

Página: https://resumos.rgo.pt/cadeiras/cpd/lei-de-amdahl/

A [introdução](https://resumos.rgo.pt/cadeiras/cpd/lei-de-amdahl/computacao-paralela-introducao/) mostrou que o speedup real fica abaixo do ideal. A lei de Amdahl quantifica esse teto a partir de uma só pergunta, que fração do programa não se divide.

## A lei

Seja $f$ a fração serial do tempo de execução, a parte que nem com infinitos núcleos acelera. A fração paralelizável é $1 - f$ e, com $p$ núcleos, demora $(1 - f)/p$. O speedup máximo é:

$$
S_p = \frac{1}{f + \frac{1 - f}{p}}
$$

O denominador lê-se como orçamento de tempo. A parcela $f$ nunca mexe. A parcela paralela encolhe com $p$, mas nunca chega a zero enquanto $p$ for finito. Quando $p$ tende para infinito, o speedup tende para $1/f$. É esse o teto, e ele depende só da fração serial.

A curva para $f = 0{,}2$ sobe depressa no início e encosta no teto 5 sem nunca lá chegar. Cada duplicação de núcleos compra menos speedup que a anterior.

![Speedup em função de p para f igual a 0,2. A curva sobe de 1 até encostar no teto horizontal 5.](https://resumos.rgo.pt/cadeiras/cpd/lei-de-amdahl/figura-1.svg)

## Exemplo completo

Um simulador passa 20 por cento do tempo a ler dados e a escrever resultados, trabalho serial, e 80 por cento a calcular, trabalho paralelizável. Então $f = 0{,}2$.

Com 4 núcleos:

$$
S_4 = \frac{1}{0{,}2 + 0{,}8/4} = \frac{1}{0{,}2 + 0{,}2} = 2{,}5
$$

Com 16 núcleos, resolve tu antes de abrir o separador:

$S_{16} = \frac{1}{0{,}2 + 0{,}8/16} = \frac{1}{0{,}2 + 0{,}05} = 4{,}0$

Com $f = 0{,}3$ e $p = 8$: $S_8 = 1 / (0{,}3 + 0{,}7/8) = 1 / 0{,}3875 \approx 2{,}58$. Com 30 por cento serial, nem 8 núcleos chegam a 3.

Com infinitos núcleos:

$$
S_{\infty} = \frac{1}{0{,}2} = 5{,}0
$$

Repara no rendimento decrescente. Quadruplicar de 4 para 16 núcleos sobe o speedup de 2,5 para 4, um ganho de 60 por cento por 4 vezes mais hardware. E nenhum hardware do mundo passa de 5. A conclusão prática: quando o speedup estabiliza, o trabalho útil é atacar a fração serial, não comprar núcleos.

```python
f = 0.2
for p in [1, 2, 4, 16]:
    s = 1 / (f + (1 - f) / p)
    print(p, round(s, 2))
```

[Vídeo: Amdahl's Law in the Multicore Era](https://www.youtube.com/watch?v=KfgWmQpzD74)

A miniatura vem do YouTube. O vídeo só carrega quando clicas. [Abrir no YouTube](https://www.youtube.com/watch?v=KfgWmQpzD74)

Como pensar em teste

O enunciado dá-te a fração serial de outra forma, por exemplo “30 por cento do tempo é leitura de ficheiros”. Essa é o teu $f$, direto para a fórmula. Se te pedirem o número de núcleos para atingir certo speedup, resolve a equação em $p$ e arredonda para cima. Se não houver solução finita, o speedup pedido está acima do teto $1/f$, e é isso que deves responder.

O que a lei não conta

Amdahl assume trabalho fixo e ignora custos de coordenação[1](https://resumos.rgo.pt/cadeiras/cpd/lei-de-amdahl/#user-content-fn-amdahl-limites), por isso é um teto otimista. O speedup medido fica abaixo do calculado. Quando o problema cresce com o número de núcleos, a leitura muda e entra a lei de Gustafson, que a ficha não exige mas que explica por que programas reais escalam melhor do que Amdahl prevê para tamanho fixo.

## Notas de rodapé

1.  Trabalho fixo significa que o enunciado não cresce quando juntas núcleos. Na prática, criar threads, sincronizar e comunicar somam tempo que a fórmula não tem, por isso mede sempre depois de calcular. [Voltar](https://resumos.rgo.pt/cadeiras/cpd/lei-de-amdahl/#user-content-fnref-amdahl-limites)